課程名稱: 高等演算法              授課老師: 林順喜 

開課系級: 資工碩              學分數: 3                 必選修:

預修課程:最好修過 程式設計、資料結構、離散數學

上課時間:2011913日至2011110(每週二)09:10~12:00

上課地點:B101(理學院大樓)

老師電話: (02)77346671

老師e-mail linss@csie.ntnu.edu.tw

老師諮詢時間:每周一10:00~12:00、每周三9:00~12:00

老師諮詢地點:資工系202

 

助教:邱勝文       e-mail699470383@ntnu.edu.tw

           

本課程網站:http://www.csie.ntnu.edu.tw/~linss請多加瀏覽

 

總成績公佈如有疑問,請於117日前連絡老師或助教

 

2008_11_14_期中考考古題    2009_01_16_期末考考古題

 

作業一請下載  作業二請下載  作業三請下載
作業四請下載   
Chinese_7017_phrases.txt請下載    Chinese_10_phrases.txt請下載

 

期中考參考解答

課程內容

授課內容與方式:上課口授及討論。

考試與作業:考試共二次,約佔40%。

                        作業(以程式實作為主),約佔50%。

抽點未到者,將逐次扣分平時成績約佔10%。

公假、事假或病假需附正式証明方可另以公式計分。

考試作弊或作業抄襲者,學期成績一律零分計算,並送校方處理。

上課認真聽講、出席踴躍、不懂立刻發問,務求徹底了解。

上課後立刻複習,收獲通常更大。

參考書目

 

指定教科書:T. H. CormenC.L. LeisersonR. L. RivestIntroduction to Algorithms3rd  EditionMIT Press2009,開發代理進口。

http://mitpress.mit.edu/algorithms

參考書籍:

1.        D. HarelAlgorithmics: The Spirit of ComputingAddison-Wesley2nd Edition

2.        H. S. WilfAlgorithms and ComplexityPrentice-Hall

3.         Journal and Conference papers

本課程介紹電腦科學中演算法的基本原理、分析技術、與設計策略,訓練學生能設計各種演算法,以解決實際的問題。熟知這些演算法知識,乃為未來可能做的學術研究打下基礎。此課程內容包括:

 

Ch. 1-4  數學基礎
Insertion sort
Selection sortMerge sortTower of Hanoi四柱河內塔

Ch. 5  亂數化演算法(Fire PiBuffon's Needle阿基米得法
          BDD問題亂數化簡演算法)
   
Pi的值:pi=3.14159 26535 89793 23846 26433 83279 50288 41971 69399
        37510 58209 74944 59230 78164
    Pi
的打油詩:山巔一寺一壺酒,二侶舞仙舞,罷酒去舊衫,握扇把市溜

Ch. 6-9  排序問題(Insertion sortSelection sortBubble sort
 Shell sortMerge sortHeap sortQuicksort
 Bucket sortRadix sortBlum selection演算法)

Ch. 10-14  一般資料結構(Binary search treeSkip listHash table
AVL-tree
紅黑樹紅黑樹之歌Josephus game)

Ch. 15  動態規劃(矩陣連乘0/1背包多邊形三角化最佳二元搜尋樹)

Ch. 16  Greedy演算法(Huffman編碼摩爾斯電碼Scheduling with deadlines)

Ch. 17  Amortized分析法

Ch. 18  高等資料結構(B-treeB+ treeMin heapMax HeapTrie)

Ch. 22-26  圖的各種演算法(令人迷惑的圖 Kruskal MSTDjikstra's algorithm)

Ch. 29  線性規劃

Ch. 31 密碼學及安全確認問題(Euclid's Game
                   extended GCDmodulo運算CryptarithmsRSA密碼)

Ch. 34  NP-complete問題(3n+1 problem旅行推銷員)

Ch. 35  近似演算法

其它特殊專題(logic gamesThe game of Nim)

 

課程預定表:

週數

星期二

上課內容

1

9/13

課程簡介,Ch.14

2

9/20

Ch.5

3

9/27

Ch.6

4

10/4

Ch. 78

5

10/11

Ch.9

6

10/18

Ch.10

7

10/25

Ch.11

8

11/1

Ch.15

9

11/8

Ch.15

10

11/15

期中考

11

11/22

Ch.16

12

11/29

Ch.17

13

12/6

Ch.1825

14

12/13

Ch.2628

15

12/20

Ch.2931

16

12/27

Ch.3233

17

1/3

Ch.3435

18

1/10

期末考