演算法

目錄

本課程需要使用 algotutor 這是一套以 perl-Tk 所撰寫的資料結構/演算法教學軟體。 Perl-Tk 在 *BSD 或 Linux 上, 只需要安裝一個套件; 在 Windwos 上, 則需要先安裝 cygwin 或 active perl (見 perl-Tk 網頁); 這一切都已收錄在 freeduc-science 版的 knoppix 光碟裡面, 只要下載 iso 檔, 燒出一片可開機光碟, 就什麼都不必安裝了。

  1. 簡介 -- 以排序為例
  2. Asymptotic Notations
  3. 常見的排序演算法
  4. 用 Heap 實作 Priority Queue
  5. 總結排序
  6. 平衡樹
  7. 愚公移山與遞迴
  8. 動態規劃
  9. 貪婪演算法
  10. 圖 (Graph) 的演算法
  11. 計算幾何簡介
  12. Reduction: 借力使力
  13. NP 問題簡介

參考資料

  1. Dave Mount. Algorithms. 很清楚明瞭的線上講義。 本學期也許我們會用到其中幾個章節。
  2. Robert Sedgewick. Algorithms in C. Addison-Wesley. 新智代理. 作者擅長以簡馭繁, 將數個演算法併於同一脈絡介紹; 程式也常以非常聰明的方式簡化原本需要分開處理的不同狀況. 我的 perl 範例程式多以他的版本為師. (講義中, 稱此書為 "Sedgewick")
  3. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms. MIT Press. 開發代理. 很多學校用. (C.L.R.S.)
  4. Herbert S. Wilf. Algorithms and Complexity
  5. Paul E. Black. Dictionary of Algorithms, Data Structures, and Problems.
  6. David Eppstein. Design and analysis of algorithms.
  7. Guy Blelloch. Algorithms in the Real World
  8. 這兩個「線上課程索引」指向許多課程公告的網頁, 但其中只有少數課程伴隨有講義可以下載: Collection of Lecture Notes 及 Algorithms Courses on the WWW
  9. The Stony Brook Algorithm Repository 收集了很多程式, 並按照演算法分類. 如果你的目的是找演算法解決問題, 而不是對頭腦體操有興趣, 或許下載程式讀手冊, 會比研究演算法的步驟更符合你的需要.
  10. Gonnet and Baeza-Yates. Handbook of Algorithms and Data Structures
  11. Algorithms Directory - Lecture Notes, Courses ...