系所

資訊與決策科學研究所

1 年級

課號 / 班別

ms1306 / A

3 學分

科目中文名稱

演算法設計與應用

科目英文名稱

每週授課時數

3 小時

專業選修

任課老師

張肇明

開課期間

一學期

人數上限

20 人

一、教學目標

藉由學習好的演算技巧，使得學生可以設計有效率的電腦程

式，進而了解問題的難易。

二、先修科目

資料結構

三、教材內容

Introduction to the Design and analysis of Al-

gorithms (2nd Ed) --- R.C.T. Lee     

四、教學方式

課堂講授（使用 PowerPoint） 課程內容包括學習如何分

析一個演算法的複雜度與界定一個問題難度的下界，並完整

介紹整套NP-completeness計算理論。 其中關於解決問題

所使用的有效技巧，課程中將介紹一般常用的「貪婪法」、

「各個擊破法」、「樹狀搜尋法」、「修剪與搜尋」、與「

動態規劃法」。 同時課程中也將簡介一些演算法新的發展方

向，包括「近似演算法」、「攤還分析」、「隨機演算法」、

「線上演算法」等概念。           

五、參考書籍

Introduction to Algorithms (2nd Ed) --- T.H.

Cormen, C.E. Leiserson, R.L. Rivest, C. Stein

（開發圖書代理）

六、教學進度

第一章 Introduction

第二章 The complexity of algorithms and the-

lower bound of problems

第三章 The greedy method

第四章 The divide-and-conquer strategy

第五章 Tree searching strategies

第六章 Prune and Search

第七章 Dynamic programming

第八章 The theory of NP-completeness

對應指標           

第一章 資管專才

第二章 務實學習     

第三章 創新研究  

第四章 創新研究 

第五章 創新研究 

第六章 創新研究

第七章 創新研究 

第八章 資管專才 

七、評量方式

平常考核 20%，期中考 40%，期末報告 40%

八、講義位址