|
|
 |
|
|
6.856J / 18.416J 2002秋季課程：隨機演算法(Randomized Algorithms, Fall 2002)
|
|
審定：俞征武(簡介並寄信)
審定簡介：
中華大學資工系副教授
個人專長：演算法(algorithms)、離散數學(discrete mathematics)、圖論(graph theory)及無線網路(wireless networks) 。
翻譯：顏嘉俊(簡介並寄信)
編輯：朱學恒(簡介並寄信)
|
|
|
 |
|
 |
|
切割演算法是用來解決複雜且需大量計算的問題,如四元素翼面的無結構格網所示。(影像乃取材自美國太空總署(NASA)網站：http://www.nasa.gov.)
Partitioning algorithms are used to solve complex large scale computational problems, as shown in this unstructured grid for a four element airfoil. (Image is taken from NASA's Web site: http://www.nasa.gov.)
|
|
|
課程重點
這個課程擁有完整的授課講義以及附上解答的問題
This course site features a full set of lecture notes and problem sets with solutions.
課程描述
這課程研究如何用亂數並透過隨意抽樣、隨機選擇証物、破壞對稱以及馬可夫鏈使得演算法更簡單和更有效率。主題包括︰隨機計算、資料結構（雜湊表、省略串列）、圖論演算法（最小擴張樹，最短路徑，最少切割）、幾何演算法（凸殼、在固定或任意維度的線性規劃)、近似計數、平行演算法、線上演算法、消去隨機技術，以及演算法的機率分析工具。
This course examines how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Topics covered include: randomized computation; data structures (hash tables, skip lists); graph algorithms (minimum spanning trees, shortest paths, minimum cuts); geometric algorithms (convex hulls, linear programming in fixed or arbitrary dimension); approximate counting; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms.
|
|
|
| 師資 |
|
講師：
David R. Karger 教授
|
| 上課時數 |
|
教師授課：
每週2節
每節1.5小時
|
| 程度 |
|
研究所
|
| 回應 |
| 告訴我們您對本課程或「開放式課程網頁」的建議。 |
| 聲明 |
麻省理工學院開放式課程認可 開放式課程計畫（OOPS）的翻譯計畫，開放式課程計畫（OOPS）乃是運用其獨立團隊、獨立資源、獨立流程進行翻譯計畫之團隊。
所有麻省理工學院開放式課程之材料皆以麻省理工學院開放式課程創作共享授權發佈，所有之翻譯資料皆由開放式課程計畫（OOPS）所提供，並由其負翻譯品質之責任。
此處麻省理工學院開放式課程之資料乃由 開放式課程計畫（OOPS） 譯為正體中文。麻省理工學院開放式課程在此聲明，不論是否遭遇或發現相關議題，麻省理工學院開放式課程、麻省理工學院教師、麻省理工學院校方並不對翻譯正確度及完整性作保證。上述單位並對翻譯後之資料不作明示或默許對任一特定目的之適合性之保證、非侵權之保證、或永不出錯之保證。麻省理工學院校方、麻省理工學院開放式課程對翻譯上之不正確不負任何責任。由翻譯所引發任何關於此等資料之不正確或其他瑕疵，皆由開放式課程計畫（OOPS）負全責，而非麻省理工學院開放式課程之責。
原文聲明 |
|
|
|
|
|
 |
|
