博碩士論文 962201019 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:9 、訪客IP:54.81.69.220
姓名 顏志瑜(Chih-yu Yen)  查詢紙本館藏   畢業系所 數學系
論文名稱 穩定婚姻及穩定配偶的模擬
(The Simulation of Stable Marriage and Stable Pairs)
相關論文
★ 混合先驗分佈下誤差項為自我迴歸之線性混合效應模型的貝氏分析
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 本文主要在於探討穩定配對中的穩定婚姻問題,提及穩定男伴、拆散配對以及P循環的概念,重新推導 Knuth, Motwani 與 Pittel 的結論:
對任何女生的穩定男伴為至少 max(0,(1/2-epsilon)lnn ,最多為 (1+epsilon)lnn 個的機率趨近 1,當n → ∞ 時,其中 0< varepsilon <1 。並介紹兩種方法找到所有的穩定配對,透過 C++ 模擬結果比較各方法的優缺點,並與理論值作比對。
摘要(英) In this paper we study the stable marriage and stable husbands problems of stable matching, using the concept of breakmarriage and p-cycle, and revisit the result of Knuth ,Motwani and, Pittel :
any particular girl has at least max(0, (1/2−epsilon) ln n) and at most (1+epsilon) ln n different husbands, with probability approaching 1 as n → ∞, if 0 < epsilin < 1. We introduce two methods to find all stable matchings and simulate in C++ programming language to compare these two methods and theoretical results.
關鍵字(中) ★ 穩定婚姻
★ 穩定配偶
關鍵字(英) ★ stable marriage
★ stable pairs
論文目次 1. 簡介................................................1
2. 穩定配對 ...........................................2
2.1 穩定男伴........................................2
2.2 隨機模型........................................6
2.3 機率性定理......................................7
3. 拆散配對...........................................23
3.1 基本觀念.......................................23
3.2 所有穩定配對...................................25
4. P循環..............................................30
4.1 所有穩定配偶...................................30
4.2 演算法.........................................31
4.3 利用 P 循環架構 G..............................34
4.4 樹狀圖 T.......................................37
5. 結論...............................................39
參考文獻..............................................40
附錄一................................................41
附錄二................................................44
附錄三................................................46
附錄四................................................50
參考文獻 [1] D. Gale and L. S. Shapley (1962), College admissions and the stability of marriage, Am. Math. Monthly, 69, 9-15.
[2] R. L. Graham, D. E. Knuth, and O.Patashnik (1989), Concrete Mathematics, AddisonWesley, Reading, MA.
[3] D. Gusfield (1987), The fast algorithms for four problems in stable marriage, SIAM J. Comput. 16, 111-128.
[4] D.E.Knuth (1976), Marriages Stable et leurs relations avec d'autres problemes combinatoires, Les Presses de l'Universite de Montreal, Montreal.
[5] D.E. Knuth (1988), Personal Communication .
[6] D.E. Knuth and R. Motwani and B. Pittel (1990), Stable husbands, Random Structures and Algorithms, Vol.1, No.1.
[7] D. G. McVitie and L. B. Wilson(1971), The stable marriage problem, Commun. ACM, 14 , 486-492.
[8] B. Pittel (1989), The average number of stable matchings, SIAM J. Discr. Math., to appear.
指導教授 于振華(Jenn-hwa Yu) 審核日期 2010-7-21
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明