User Tools

Site Tools


0147--b-i-to-n-th-k-la-gi

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

0147--b-i-to-n-th-k-la-gi [2018/11/07 17:09] (current)
Line 1: Line 1:
 +<​HTML>​ <​br><​div id="​mw-content-text"​ lang="​vi"​ dir="​ltr"><​div class="​mw-parser-output"><​p><​b>​Bài toán thư ký</​b>​ là một bài toán nổi tiếng trong lý thuyết dừng tối ưu. Bài toán này đã được nghiên cứu trong xác suất ứng dụng, thống kê, và lý thuyết quyết định.
 +</​p><​p>​Dạng cơ bản của bài toán là như sau. Một người quản lý cần tuyển thư ký tốt nhất trong <​i>​n</​i>​ ứng viên có thể xếp hạng. Các ứng viên được phỏng vấn lần lượt theo một thứ tự ngẫu nhiên. Quyết định cho mỗi ứng viên phải được đưa ra ngay sau khi phỏng vấn ứng viên đó. Sau khi đã bị từ chối, ứng viên đó sẽ không thể được tuyển. Trong quá trình phỏng vấn, người quản lý có thể xếp hạng các ứng viên đã phỏng vấn nhưng không biết gì về chất lượng của các ứng viên chưa phỏng vấn. Câu hỏi đặt ra là nên sử dụng chiến thuật nào để tối ưu hóa xác suất tuyển được ứng viên tốt nhất.
 +</​p><​p>​Bài toán cơ bản trên có một lời giải đẹp. Đầu tiên phỏng vấn và từ chối khoảng <​i>​n/​e</​i>​ ứng viên (trong đó <​i>​e</​i>​ là cơ số của lôgarit tự nhiên). Sau đó chấp nhận ứng viên đầu tiên tốt hơn tất cả các ứng viên đã được phỏng vấn trước đó (hoặc chấp nhận ứng viên cuối cùng nếu điều này không xảy ra). Nếu áp dụng thuật toán này thì xác suất tuyển được ứng viên tốt nhất là khoảng <​i>​1/​e</​i>​ và đây cũng là xác suất tối ưu.
 +</p>
  
 +<​p>​Bài toán được xuất bản lần đầu tiên bởi Martin Gardner trong Scientific American năm 1960.
 +</​p><​p>​Bài báo năm 1989 của T. S. Ferguson<​sup id="​cite_ref-1"​ class="​reference">​[1]</​sup>​ chỉ ra rằng có những bài toán khác tương tự đã được xem xét bởi Arthur Cayley năm 1875 và Johannes Kepler từ lâu trước đó.
 +</p>
 +
 +
 +
 +<​ul><​li><​span id="​CITEREFBearden2006"​ class="​citation journal">​Bearden,​ J.N. (2006). “A new secretary problem with rank-based selection and cardinal payoffs”. <​i>​Journal of Mathematical Psychology</​i>​ <​b>​50</​b>:​ 58–9. doi:​10.1016/​j.jmp.2005.11.003.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=A+new+secretary+problem+with+rank-based+selection+and+cardinal+payoffs&​amp;​rft.au=Bearden%2C+J.N.&​amp;​rft.aufirst=J.N.&​amp;​rft.aulast=Bearden&​amp;​rft.date=2006&​amp;​rft.genre=article&​amp;​rft.jtitle=Journal+of+Mathematical+Psychology&​amp;​rft.pages=58-9&​amp;​rft.volume=50&​amp;​rft_id=info%3Adoi%2F10.1016%2Fj.jmp.2005.11.003&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span class="​citation journal">​Bearden,​ J.N., Murphy, R.O. Rapoport, A. (2005). “A multi-attribute extension of the secretary problem: Theory and experiments”. <​i>​Journal of Mathematical Psychology</​i>​ <​b>​49</​b>​ (5): 410–425. doi:​10.1016/​j.jmp.2005.08.002.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=A+multi-attribute+extension+of+the+secretary+problem%3A+Theory+and+experiments&​amp;​rft.au=Bearden%2C+J.N.%2C+Murphy%2C+R.O.+Rapoport%2C+A.&​amp;​rft.aulast=Bearden%2C+J.N.%2C+Murphy%2C+R.O.+Rapoport%2C+A.&​amp;​rft.date=2005&​amp;​rft.genre=article&​amp;​rft.issue=5&​amp;​rft.jtitle=Journal+of+Mathematical+Psychology&​amp;​rft.pages=410-425&​amp;​rft.volume=49&​amp;​rft_id=info%3Adoi%2F10.1016%2Fj.jmp.2005.08.002&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span class="​citation journal">​Bearden,​ J.N., Rapoport, A., Murphy R.O. (2006). “Sequential observation and selection with rank-dependent payoffs: An experimental test”. <​i>​Management Science</​i>​ <​b>​52</​b>​ (9): 1437–49. doi:​10.1287/​mnsc.1060.0535.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=Sequential+observation+and+selection+with+rank-dependent+payoffs%3A+An+experimental+test&​amp;​rft.au=Bearden%2C+J.N.%2C+Rapoport%2C+A.%2C+Murphy+R.O.&​amp;​rft.aulast=Bearden%2C+J.N.%2C+Rapoport%2C+A.%2C+Murphy+R.O.&​amp;​rft.date=2006&​amp;​rft.genre=article&​amp;​rft.issue=9&​amp;​rft.jtitle=Management+Science&​amp;​rft.pages=1437-49&​amp;​rft.volume=52&​amp;​rft_id=info%3Adoi%2F10.1287%2Fmnsc.1060.0535&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span class="​citation journal">​F. Thomas Bruss (1984). “A unified Approach to a Class of Best Choice problems with an Unknown Number of Options”. <​i>​Annals of Probability</​i>​ <​b>​12</​b>​ (3): 882–891. doi:​10.1214/​aop/​1176993237.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=A+unified+Approach+to+a+Class+of+Best+Choice+problems+with+an+Unknown+Number+of+Options&​amp;​rft.au=F.+Thomas+Bruss&​amp;​rft.aulast=F.+Thomas+Bruss&​amp;​rft.date=1984&​amp;​rft.genre=article&​amp;​rft.issue=3&​amp;​rft.jtitle=Annals+of+Probability&​amp;​rft.pages=882-891&​amp;​rft.volume=12&​amp;​rft_id=info%3Adoi%2F10.1214%2Faop%2F1176993237&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span class="​citation journal">​F. Thomas Bruss (2000). “Sum the odds to one and stop”. <​i>​Annals of Probability</​i>​ <​b>​28</​b>​ (3): 1384–91. doi:​10.1214/​aop/​1019160340.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=Sum+the+odds+to+one+and+stop&​amp;​rft.au=F.+Thomas+Bruss&​amp;​rft.aulast=F.+Thomas+Bruss&​amp;​rft.date=2000&​amp;​rft.genre=article&​amp;​rft.issue=3&​amp;​rft.jtitle=Annals+of+Probability&​amp;​rft.pages=1384-91&​amp;​rft.volume=28&​amp;​rft_id=info%3Adoi%2F10.1214%2Faop%2F1019160340&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span class="​citation journal">​Ferguson,​ T.S. (1989). “Who solved the secretary problem?​”. <​i>​Statistical science</​i>​ <​b>​4</​b>​ (3): 282–296. doi:​10.1214/​ss/​1177012493.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=Who+solved+the+secretary+problem%3F&​amp;​rft.au=Ferguson%2C+T.S.&​amp;​rft.aufirst=T.S.&​amp;​rft.aulast=Ferguson&​amp;​rft.date=1989&​amp;​rft.genre=article&​amp;​rft.issue=3&​amp;​rft.jtitle=Statistical+science&​amp;​rft.pages=282-296&​amp;​rft.volume=4&​amp;​rft_id=info%3Adoi%2F10.1214%2Fss%2F1177012493&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span class="​citation journal">​Gnedin,​ A. (1994). “A solution to the game of Googol”. <​i>​Annals of Probability</​i>​ <​b>​22</​b>​ (3): 1588–1595. doi:​10.1214/​aop/​1176988613.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=A+solution+to+the+game+of+Googol&​amp;​rft.au=Gnedin%2C+A.&​amp;​rft.aufirst=A.&​amp;​rft.aulast=Gnedin&​amp;​rft.date=1994&​amp;​rft.genre=article&​amp;​rft.issue=3&​amp;​rft.jtitle=Annals+of+Probability&​amp;​rft.pages=1588-1595&​amp;​rft.volume=22&​amp;​rft_id=info%3Adoi%2F10.1214%2Faop%2F1176988613&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span class="​citation journal">​Freeman,​ P.R. (1983). “The secretary problem and its extensions: A review”. <​i>​International Statistical Review / Revue Internationale de Statistique</​i>​ <​b>​51</​b>​ (2): 189–206. JSTOR 1402748. doi:​10.2307/​1402748.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=The+secretary+problem+and+its+extensions%3A+A+review&​amp;​rft.au=Freeman%2C+P.R.&​amp;​rft.aulast=Freeman%2C+P.R.&​amp;​rft.date=1983&​amp;​rft.genre=article&​amp;​rft.issue=2&​amp;​rft.jstor=1402748&​amp;​rft.jtitle=International+Statistical+Review+%2F+Revue+Internationale+de+Statistique&​amp;​rft.pages=189-206&​amp;​rft.volume=51&​amp;​rft_id=info%3Adoi%2F10.2307%2F1402748&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li>​Hill,​ T.P. "​Knowing When to Stop". <​i>​American Scientist</​i>,​ Vol. 97, 126-133 (2009). (Có một bản dịch tiếng Pháp tại cover story trong số tháng 7 của <​i>​Pour la Science</​i>​ (2009))</​li>​
 +<​li><​span class="​citation journal">​Seale,​ D.A., Rapoport, A. (1997). “Sequential decision making with relative ranks: An experimental investigation of the '​secretary problem<​span style="​padding-right:​0.2em;">'</​span>​”. <​i>​Organizational Behavior and Human Decision Processes</​i>​ <​b>​69</​b>​ (3): 221–236. doi:​10.1006/​obhd.1997.2683.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=Sequential+decision+making+with+relative+ranks%3A+An+experimental+investigation+of+the+%27secretary+problem%27&​amp;​rft.au=Seale%2C+D.A.%2C+Rapoport%2C+A.&​amp;​rft.aulast=Seale%2C+D.A.%2C+Rapoport%2C+A.&​amp;​rft.date=1997&​amp;​rft.genre=article&​amp;​rft.issue=3&​amp;​rft.jtitle=Organizational+Behavior+and+Human+Decision+Processes&​amp;​rft.pages=221-236&​amp;​rft.volume=69&​amp;​rft_id=info%3Adoi%2F10.1006%2Fobhd.1997.2683&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​span id="​CITEREFSteinSealeRapoport2003"​ class="​citation journal">​Stein,​ W.E.; Seale, D.A.; Rapoport, A. (2003). “Analysis of heuristic solutions to the best choice problem”. <​i>​European Journal of Operational Research</​i>​ <​b>​151</​b>:​ 140–152. doi:​10.1016/​S0377-2217(02)00601-X.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=Analysis+of+heuristic+solutions+to+the+best+choice+problem&​amp;​rft.au=Rapoport%2C+A.&​amp;​rft.au=Seale%2C+D.A.&​amp;​rft.au=Stein%2C+W.E.&​amp;​rft.aufirst=W.E.&​amp;​rft.aulast=Stein&​amp;​rft.date=2003&​amp;​rft.genre=article&​amp;​rft.jtitle=European+Journal+of+Operational+Research&​amp;​rft.pages=140-152&​amp;​rft.volume=151&​amp;​rft_id=info%3Adoi%2F10.1016%2FS0377-2217%2802%2900601-X&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li>​Merrill R. Flood, thư viết năm 1958, một bản sao nằm trong bài báo của Martin Gardner tại Stanford University Archives, series 1, box 5, folder 19.</​li>​
 +<​li>​Martin Gardner, "New Mathematical Diversions"​ trong <​i>​Scientific American</​i>​. Simon and Schuster, 1966, Chương 3, bài 3 [in lại từ bài báo xuất bản tháng 2 năm 1960 với thông tin bổ sung].</​li>​
 +<​li><​span class="​citation book">​Miller,​ Geoffrey F. (2001). <​i>​The mating mind: how sexual choice shaped the evolution of human nature</​i>​. Anchor Books. ISBN 0-385-49517-X.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.au=Miller%2C+Geoffrey+F.&​amp;​rft.aulast=Miller%2C+Geoffrey+F.&​amp;​rft.btitle=The+mating+mind%3A+how+sexual+choice+shaped+the+evolution+of+human+nature&​amp;​rft.date=2001&​amp;​rft.genre=book&​amp;​rft.isbn=0-385-49517-X&​amp;​rft.pub=Anchor+Books&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span></​li>​
 +<​li><​i>​Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology'​s Answer to the Frame Problem</​i>,​ Timothy Ketelaar and Peter M. Todd, Chương 5 của <​i>​Conceptual Challenges in Evolutionary Psychology</​i>,​ tr. 187.</​li>​
 +<​li><​span class="​citation journal">​Sardelis,​ D., Valahas, T. (tháng 3 1992). “Decision Making: A Golden Rule”. <​i>​American Mathematical Monthly</​i>​ <​b>​99</​b>​ (3): 935–942.</​span><​span title="​ctx_ver=Z39.88-2004&​amp;​rfr_id=info%3Asid%2Fvi.wikipedia.org%3AB%C3%A0i+to%C3%A1n+th%C6%B0+k%C3%BD&​amp;​rft.atitle=Decision+Making%3A+A+Golden+Rule&​amp;​rft.au=Sardelis%2C+D.%2C+Valahas%2C+T.&​amp;​rft.aulast=Sardelis%2C+D.%2C+Valahas%2C+T.&​amp;​rft.date=th%C3%A1ng+3+1992&​amp;​rft.genre=article&​amp;​rft.issue=3&​amp;​rft.jtitle=American+Mathematical+Monthly&​amp;​rft.pages=935-942&​amp;​rft.volume=99&​amp;​rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal"​ class="​Z3988"><​span style="​display:​none;">​ </​span></​span>​ </​li></​ul><​!-- ​
 +NewPP limit report
 +Parsed by mw1323
 +Cached time: 20181012093249
 +Cache expiry: 1900800
 +Dynamic content: false
 +CPU time usage: 0.104 seconds
 +Real time usage: 0.115 seconds
 +Preprocessor visited node count: 440/1000000
 +Preprocessor generated node count: 0/1500000
 +Post&#​8208;​expand include size: 21334/​2097152 bytes
 +Template argument size: 33/2097152 bytes
 +Highest expansion depth: 7/40
 +Expensive parser function count: 0/500
 +Unstrip recursion depth: 0/20
 +Unstrip post&#​8208;​expand size: 261/5000000 bytes
 +Number of Wikibase entities loaded: 0/400
 +Lua time usage: 0.042/​10.000 seconds
 +Lua memory usage: 2.5 MB/50 MB
 +--><​!--
 +Transclusion expansion time report (%,​ms,​calls,​template)
 +100.00% ​  ​86.590 ​     1 -total
 + ​79.05% ​  ​68.453 ​    11 B&#​7843;​n_m&#​7851;​u:​Ch&​uacute;​_th&​iacute;​ch_t&#​7841;​p_ch&​iacute;​
 + ​15.60% ​  ​13.506 ​     1 B&#​7843;​n_m&#​7851;​u:​Tham_kh&#​7843;​o
 +  4.23%    3.663      1 B&#​7843;​n_m&#​7851;​u:​Harvtxt
 +  4.15%    3.592      1 B&#​7843;​n_m&#​7851;​u:​Ch&​uacute;​_th&​iacute;​ch_s&​aacute;​ch
 +  3.93%    3.404      1 B&#​7843;​n_m&#​7851;​u:​Column-count
 +--><​!-- Saved in parser cache with key viwiki:​pcache:​idhash:​823399-0!canonical and timestamp 20181012093248 and revision id 25951415
 + ​--></​div><​noscript><​img src="​http://​vi.wikipedia.org/​wiki/​Special:​CentralAutoLogin/​start?​type=1x1"​ alt=""​ title=""​ width="​1"​ height="​1"​ style="​border:​ none; position: absolute;"/></​noscript></​div>​
 +
 +</​HTML>​
0147--b-i-to-n-th-k-la-gi.txt · Last modified: 2018/11/07 17:09 (external edit)