課程資料

3348 演算法分析			開課學期：1061		開課班級： 應數系 3A
授課教師：蔡國裕	選修	學期課	學分數：3.0	大義 0720 星期五 09:10-12:00

3348 ANALYSIS OF ALGORITHMS			2017 Fall		Department of Applied Mathematics 3A
Professor：TSAI, KUO-YU	Elective	Semester	Credits: 3.0	Da Yi 0720 Friday 09:10-12:00

發展願景

傳揚中華文化，促進跨領域創新，與時精進，邁向國際
It is our objective to promote Chinese culture, enhance cross-disciplinary innovation, seek constant advancement, and embrace global community.

辦學宗旨

秉承質樸堅毅校訓，承東西之道統，集中外之精華，研究高深學術, 培養專業人才，服務社會，致力中華文化之發揚, 促進國家發展.
Based on our motto—“Temperament, Simplicity, Strength, and Tenacity,” “inheriting the merits of the East and the West” and “absorbing the essence of Chinese and foreign cultures,” we make it our mission to pursue advanced research, develop professional talents, serve the society, promote Chinese culture and support national development.

校教育目標
校基本素養
校核心能力

院教育目標

奠定自然科學基礎培養後續學習能力
強化理論與實務並重的多元課程
推動跨領域學習
促進國際化教學提升學生競爭力

院核心能力

自然科學知識的能力
理論與實務結合的能力
國際化與團隊溝通合作的能力
多元整合的能力

系教育目標

訓練學生具備紮實的數學基本能力
依興趣選擇應用數學學群，統計科學學群，或計算機科學學群
兼顧理論與實務，讓學生得以繼續升學或直接就業

系核心能力

具備基礎科學知識能力
具計算、分析、演算法與證明等能力
使用數學或套裝軟體求解問題能力
解釋結果與表達溝通能力

課程目標

培養邏輯思考與推理之能力，增進學生設計優良程式的功力。 Students will develop the ability to think and reason logically and improve their ability to design good programs.

課程能力

具備基礎科學知識能力 (比重 20%)
具計算、分析、演算法與證明等能力 (比重 40%)
使用數學或套裝軟體求解問題能力 (比重 10%)
解釋結果與表達溝通能力 (比重 30%)

課程概述

演算法是指解決一個問題所需要的具體步驟和方法，演算法在科學與計算領域扮演中心的角色。本課程強調演算法的設計技巧與分析，其宗旨在於培養同學構思求解問題的演算法，增進程式設計的能力。另一方面，我們將簡單介紹演算法與資料結構，演算法效率性分析，及並且採用下列分類介紹數學的各分支中有名的演算法：暴力法，分裂與征服演算法，減少與征服演算法，變換與征服演算法，空間與時間的取捨。動態規畫法，貪婪技術演算法。 Algorithms are the specific steps and methods needed to solve a problem, and they play a central role in the field of science and computing. This course emphasizes the design techniques and analysis of algorithms, with the aim of developing students' ability to conceive algorithms for solving problems and improving their programming skills.

授課內容

本課程主要介紹演算法之設計概念，並讓學生學習如何分析演算法、評估效率，進而學習如何設計演算法解決問題。主要內容包括：演算法效率分析的基本原則、暴力法(包括選擇排序、泡沫排序、尋序搜尋等)、分解征服法(包括合併排序、快速排序、二元搜尋等)、縮減征服法(包括插入排序、深度優先搜尋與廣度優先搜尋、拓撲排序等)、轉換征服法(包括預先排序、高斯消去法及平衡搜尋二元樹等)、時空取捨法、動態規劃(包括Floyd-Warshall演算法、最佳二元搜尋樹及背包問題)及貪婪法(包括普林演算法、克魯斯克爾演算法及戴克斯特拉演算法)等。

This course will introduce the concepts of algorithms, and students can learn how to analyze algorithms and evaluate efficiency, and further, learn how to design an algorithm to solve a problem. The topics include fundamentals of the analysis of algorithm efficiency, brute force and exhaustive search (including selection sort, bubble sort, and sequential search etc.), decrease-and-conquer (including megesort, quicksort, and binary sort etc.), divide-and-conquer (including insertion sort, depth-first search and breadth-first search, and topological sorting etc.), transform-and-conquer (including presorting, Gaussian Elimination, and balanced search tree etc.), space and time tradeoffs, dynamic programming (including Floyd–Warshall algorithm, optimal binary search tree, and knapsack problem etc.), and greedy techniques (including Prim’s algorithm, Kruskal’s algorithm, and Dijkstra’s algorithm etc.) etc.

授課方式

以投影片教學，輔以隨堂問答

評量方式

課程能力 /評量方式	具備基礎科學知識能力 (比重 20%)	具計算、分析、演算法與證明等能力 (比重 40%)	使用數學或套裝軟體求解問題能力 (比重 10%)	解釋結果與表達溝通能力 (比重 30%)
期中測驗評量30%刪除	30%	30%	30%	10%
期末測驗評量30%刪除	30%	30%	30%	10%
課堂參與20%刪除	20%	20%	30%	30%
出席紀錄考核評量20%刪除	30%	30%	30%	10%

上課用書

（師生應遵守智慧財產權及不得非法影印）
演算法(Introduction to The Design and Analysis of Algorithms 2/E) 原作者：Anany　Levitin　莊承翃 譯 出版年份：2009　出版社：高立出版

參考書目

（師生應遵守智慧財產權及不得非法影印）
1. Introduction to Algorithms Third Edition 作者： Cormen, Thomas H./ Leiserson, Charles E./ Rivest, Ronald L./ Stein, Clifford 出版年份：2009 出版社：MIT Press
2. 啊哈！圖解演算法必學基礎 作者：啊哈磊　出版年份：2014　出版社：碁峰
3. 資料結構、演算法與應用－使用JAVA(附範例光碟片) 作者：戴顯權 出版社：全華
4. Shie Mannor, Ron Meir, and Tong Zhang, "Greedy Algorithms for Classification – Consistency, Convergence Rates, and Adaptivity," Journal of Machine Learning Research, Vol 4, pp. 713-742, 2003. (已上傳至教材區)

課程需求

要考試

其他需求

輔導時間

• 星期一 13:00-15:00
• 星期二 14:00-15:00
• 星期三 14:00-15:00
• 星期五 13:00-15:00

教師聯絡資訊

Email：cgy13@ulive.pccu.edu.tw
分機：25141

課程進度

1. 2017/09/22

   演算法簡介與緒論

2. 2017/09/29

   演算法效率分析的基本原則

3. 2017/10/06

   暴力法

4. 2017/10/13

   分解征服法

5. 2017/10/20

   縮減征服法 (I)

6. 2017/10/27

   縮減征服法 (II)

7. 2017/11/03

   轉換征服法

8. 2017/11/10

   時空取捨法

9. 2017/11/17

   期中考 指定研讀資料 第一章~第七章

10. 2017/11/24

    動態規劃 (I)

11. 2017/12/01

    動態規劃 (II)

12. 2017/12/08

    貪婪法 (I)

13. 2017/12/15

    貪婪法 (II)

14. 2017/12/22

    反覆改進 (I)

15. 2017/12/29

    反覆改進 (II)

16. 2018/01/05

    演算法能力的極限

17. 2018/01/12

    超越演算法能力的極限

18. 2018/01/19

    期末考 指定研讀資料 第8章~第12章