演算法導論(SMA 5503)

Introduction to Algorithms (SMA 5503), Fall 2005

2005秋季
該課程主要講授高效演算法的設計和分析技巧,並著重實踐中有用的方法。所包含的主題有:排序演算法;查找樹、堆、散列法;分治法;動態規劃;平攤分析;圖形演算法;最短路徑;網路流;計算幾何學;數論演算法;多項式和矩陣計算;暫存以及平行計算。該課程也是新加坡-麻省理工學院聯盟(SMA)課程的一部分,課程號為SMA 5503(演算法分析和設計)。

指定教科書

Cormen, Thomas H.、Charles E. Leiserson、Ronald L. Rivest和 Clifford Stein所著的《演算法導論》第二版,Cambridge, MA: MIT Press,ISBN: 0262032937

課綱與詳述事項

課程重點 本課程的重點在課堂講稿部分提供一套完整的講稿和視頻,在作業部分也有課程作業及答案。另外,在閱讀資料部分有該課程指定和推薦閱讀的廣泛參考書目。該課程的教材由Leiserson教授參與編寫。

 

技術需求 開啟本課程一些文件(.c, .java, .mp3, .rm)時,需要使用特別的軟體。    

 

教學大綱

課程目標和成果

課程目標 本課程向學生介紹電腦演算法的分析和設計,完成本課程的學習之後,學生將能夠:

分析演算法的漸近表現。

熟練掌握主要演算法和資料結構。

應用重要的演算法設計範式及分析方法。

在一般的工程設計條件下合成高效演算法。

 

課程成果 完成本課程學習的學生都應具備以下能力:

利用歸約證明和迴圈變數判斷演算法的正確性。

利用漸進分析方法來分析演算法的最差運行時間。比較由多項式、指數和對數函數組成的複合函數的漸趨行為,並分析最差、平均和最好情況的優缺點。

當演算法的運行時間符合機率分佈時,分析它的平均運行時間。利用指標隨機變數和期望值線形關係來完成分析。用這種分析法來演示演算法分析。

解釋隨機演算法的基本屬性和分析它們的方法。演示使用隨機性的演算法。解釋隨機演算法和含機率輸入演算法之間的區別。

適時利用分攤分析來分析演算法,演示運用此分析方法之簡單演算法的分析。描述分攤分析的不同策略,包括會計法和潛能法。

描述分治法並解釋何時演算法設計情況下會需要進行分治。演示使用此範例的演算法。合成分治法。導出並解決描述分治法性能的遞歸。

描述動態規劃範式並解釋什麼情況下演算法設計會需要使用它。演示使用此範式的演算法。合成並分析動態規劃法。

描述貪心範式並解釋什麼情況下演算法設計會需要使用它。演示使用此演算法。合成及分析貪心法。

解釋主要的排序演算法。演示對這些演算法的分析及它們所包含的設計策略。合成將排序做為副程式的演算法。估算比較排序法執行時間的下限並解釋怎樣克服這些界限。

解釋實現動態集合所需的主要基本資料結構及對其操作進行分析。演示使用資料結構的演算法並瞭解它們的效率是如何依賴於所使用的資料結構。用增強已有資料結構的方法來合成新資料結構。合成將資料結構作為重要成分的演算法。

解釋主要圖形演算法及其分析。適時使用圖形來對工程問題進行建模。合成新的圖形演算法和使用圖形作為關鍵部分的演算法並進行分析。

演示不同領域的幾個重要演算法,熟練掌握若干應用演算法-如:計算幾何學、運作研究、安全與加密、並行與分佈計算、作業系統,及電腦體系結構。

 

必備先修條件

需要對程式寫作有深刻的瞭解且對離散數學有很好的掌握,包括機率,這些都是該課程的必備先修條件。對於麻省理工學院的學生來說,本課程是麻省理工學院電子與電腦學院計算理論工程集中選修課的先導課程,你需要已修過6.001電腦程式結構和詮釋,以及6.042J / 18.062J電腦科學數學這兩門課,而且成績至少達到C以上。如果你不符合上述條件,在註冊該課程前務必先與助教談妥。

 

授課

每週一和週三上課,每次1.5小時。你必需確實掌握講師課上所教的課程,包括講師口述的內容。

 

復習

學生每週必須參加一次復習,每次一個小時。課程教員會安排復習的時間。你必需確實掌握復習課的內容,復習課的出勤一直以來都與考試成績有著緊密的關係。復習也提供更多提問和與教員互動的機會。復習課導師將會負責給出期末成績。復習課於每週五由助教主持。

 

講義

大多數講義都可以從伺服器下載,而且是可以列印的格式。學生應從伺服器上下載並列印講義。我們會通過伺服器或電子郵件通知學生何時在何處可以下載未上傳的講義。

 

教科書

該課程主要的教材為Cormen, Thomas H.、Charles E. Leiserson、Ronald L. Rivest和 Clifford Stein所著的《演算法導論》第二版,Cambridge, MA: MIT Press,ISBN: 0262032937。上一個學期就使用了該書第一版作為教材,但第二版對第一版的基礎上進行了大幅擴充,所以第一版已不再適合作為本課教材。這本教材可以從多間本地和網上書店買到。

 

額外幫助 每個助教會將自己每週的辦公室時間張貼在伺服器上。這學期大家將提供實驗性的作業實驗室,開放時間和地點會明列在相應的作業中。作業實驗室提供了一個地點,讓大家可以和同學一起完成作業。助教會在作業實驗室給大家提供幫助。另外,麻省理工學院電機工程與電腦科學系對很多選修大學基礎課程VI的學生提供一對一的免費服務。在學期開始的前九周,你可以申請一名輔導老師,每週會面幾小時,以幫助你更好地理解課程資料。你和輔導老師自行商量每週見面的時間,更多的資訊請參見HKN網頁。少數族群教育辦公室在輔導服務至也提供了輔導服務,這裏的輔導老師都是大學生和研究生,所有的輔導服務都會在輔導服務室或附近的教室進行。

 

註冊 請在伺服器上註冊,你所提供的資訊會幫助教員更瞭解你並創建一份郵寄清單和課程目錄。註冊是該課程的必需條件,如果沒有註冊成功,那麼通過課程會非常困難。註冊後退課請務必通知助教。旁聽的學生也需完成註冊,以便加入郵寄清單。請務必在第一節之前完成註冊。我們會在第一節課後的隔天將復習作業寄發給你。

 

作業

本學期中將會分發9次作業。教學時程表列明作業的暫時分發時間和提交期限,但是最終的提交期限都會明列在作業上。

一般而言,不能遲交作業。如有特殊情況,請提前與復習輔導老師聯繫並做預先安排。如果未預做安排,則需院長辦公室證明。

每個問題需要寫在另外一張(或多張)紙上,因為每個問題的評分老師可能不同,在每張紙的頂端都需寫下: 你的名字 復習課導老師名字 問題編號該問題的合作人(參見合作規定),如果你獨立解決了該問題,請標注「沒有合作人」。你可以手寫或列印答案,但是必須用三孔紙並提交書面版本。教員會用環夾套住紙孔防止作業丟失。這樣批改後的作業也可以放到你的活頁筆記本中。

在給出問題答案時請盡可能清晰準確,答案的可理解性和正確性同樣重要,因為技術資料的溝通是一項重要的技能。一個簡單直接的分析結果得分會比迂迴的結果更高,因為它較簡單,較不易出錯,而且更易讀易懂。潦草的答案即使正確,分數也不會太高,所以請確認你的手寫字跡清楚。建議你將問題的答案複製一份再提交,這麼做不但可以讓你的作業更工整,也能再次對作業進行完整的檢查,改正錯誤。

作業包括一些需要解決但不需要提交的練習,這可以幫助你進一步掌握課程資料,且對解決需要提交的題目助益很大。練習中涵蓋的內容將會出現在考試中。

 

演算法描述

在解決某個問題時,你經常需要提出一個演算法來解決。你應該採用短文的形式提交問題解答。主題段需要對你解決的問題和解決方法給出綜述。文章的主體應該提供:

1.      英文演算法描述,必要時可用虛擬碼

2.      至少用一個實例或圖解來詳細說明你所給出的演算法成立

3.      演算法正確性的證明(或指示)

4.      演算法運行時間的分析切記,你的目標是溝通。

評分老師可能會因為迂迴及愚鈍的描述而扣你分數。

 

評分規則

期末分數主要根據平時作業、一次隨堂測驗(Q1)、一次課外測驗(Q2)和一次期末考試來決定。平時作業 約為80分、隨堂測試約80分、課外測驗約150分,期末考試約180分。雖然平時作業在最後成績中只佔80分,但你還是得完成。下表給出沒有完成作業對最後成績的影響:

漏做作業題數

影響

0

沒有影響

1

一個等級分的1/100

2

一個等級分的1/10

3

一個等級分的1/5

4

一個等級分的1/4

5

一個等級分的1/3

6

一個等級分的1/2

7

一個等級分

8

兩個等級分

9題或以上

不及格

請注意這張表是針對遺漏的作業題數,而非作業次數。如有需要,這項評分規定會進行相應調整。

 

合作規定

平時作業的目的是為了幫助學生掌握課程資料,所以我們鼓勵學生在作業上進行合作。事實上,組成學習小組的學生往往在考試上的表現會比單獨完成作業的學生更好。如果參加學習小組,你應該對自己和小組負責,為學習會議做充份的準備。確切的說,你應該提前花至少30到45分鐘來解決每一個題目,如果你的小組不能解決問題,要和其他小組進行討論或請教復習課導老師。 你必須獨立寫下每道題目的解決方案,無論你是否和其他人合作解決該道問題。在每次作業上都要注明你的合作人。如果你獨立完成作業,也應該註明「沒有合作人」。如果你是通過搜索(如:網路)得到答案,標明來源並用自己的話來作答。如果你不能對問題的答案向教員進行口頭解釋,就算是違背本規則。 考試時,任何形式的合作都不允許。本課程的第二個測驗可以在家裏完成,你必須獨立作答,考試時間長達數天。在第20課中將會有更多關於課外測驗的合作規定。請注意該堂課是測試的一個組成部分,所以強制出席。剽竊和其他違反智慧財產的行為在任何鼓勵個人表現的學術環境中都是無法被容忍的行為,如果你對合作規定有任何疑問或者你覺得你已經違背規定,請告知教員。雖然教員負責處理學術欺騙行為,但是如果我們從學生本人那裏得知違規情況而不是校方,我們的作法相對地會較為寬容些。 該課程有很多內容,所以盡情享受吧!

相關連結

講者介紹

Prof. Charles Leiserson

Prof. Erik Demaine

翻譯工作人員

翻譯人員张晓薇

繁體編輯劉契良

簡體編輯陈盈

檔案後製處理劉契良