| 106學年第1學期課程綱要 |
|
@尊重智慧財產權,請同學勿隨意影印教科書 。 Please respect the intellectual property rights, and shall not copy the textbooks arbitrarily. |
|
| 一、課程基本資料 |
| 開課序號 | 2658 | 課程學制 | |
| 科目代碼 | CSC0017 | 課程名稱 | 高等演算法 |
| 英文名稱 | Advanced Algorithms | ||
| 全/半年 | 半 | 必/選修 | 選修 |
| 學分數 | 3.0 | 每週授課時數 | 正課時數: 3 小時 |
| 開課系級 | 資工系（碩）碩博合開 | ||
| 先修課程 | |||
| 課程簡介 | 本課程介紹電腦科學中演算法的基本原理、分析技術、與設計策略，訓練學生能設計各種演算法，以解決實際的問題。熟知這些演算法知識，乃為未來可能做的學術研究打下基礎。 | ||
| 課程目標 | 對應系所核心能力 | ||
| 1. 實作以程式為主的作業 | 碩士: 1-1 具有軟體開發能力 博士: 1-1 具有軟體開發能力 |
||
| 2. 介紹電腦科學中演算法的基本原理、分析技術、與設計策略 | 碩士: 1-2 能了解資訊系統軟硬體的關係及運作原理 博士: 1-2 能了解資訊系統軟硬體的關係及運作原理 |
||
| 3. 訓練學生能熟悉資訊基礎理論 | 碩士: 1-3 能熟悉資訊及數學基礎理論 博士: 1-3 能熟悉資訊及數學基礎理論 |
||
| 4. 探討解決問題所需的時間及空間複雜度 | 碩士: 2-3 具有從經驗中提升專業思考層次的能力 博士: 2-3 具有從經驗中提升專業思考層次的能力 |
||
| 5. 研究其它特殊專題及未來趨勢 | 碩士: 3-3 具有持續追求新知的精神 博士: 3-3 具有持續追求新知的精神 |
||
| 二、教學大綱 |
| 授課教師 | 林順喜 | ||
| 教學進度與主題 | |||
|
Ch. 1-4 數學基礎 Insertion sort、Selection sort、Merge sort、Tower of Hanoi、四柱河內塔 Ch. 5 亂數化演算法(Fire Pi、Buffon`s Needle、阿基米得法、BDD問題、亂數化簡演算法) Ch. 6-9 排序問題(Insertion sort、Selection sort、Bubble sort、Shell sort、Merge sort、Heap sort、Quicksort、Bucket sort、Radix sort、Blum selection演算法) Ch. 10-14 一般資料結構(Binary search tree、Skip list、Hash table、AVL-tree、紅黑樹、Josephus game) Ch. 15 動態規劃(矩陣連乘、0/1背包、多邊形三角化、最佳二元搜尋樹) Ch. 16 Greedy演算法(Huffman編碼、摩爾斯電碼、Scheduling with deadlines) Ch. 17 Amortized分析法 Ch. 18 高等資料結構(B-tree、B+ tree、Min heap、Max Heap、Trie) Ch. 22-26 圖的各種演算法(令人迷惑的圖、 Kruskal MST、Djikstra`s algorithm) Ch. 29 線性規劃 Ch. 31 密碼學及安全確認問題(Euclid`s Game、extended GCD、modulo運算、Cryptarithms、RSA密碼) Ch. 34 NP-complete問題(3n+1 problem、旅行推銷員) Ch. 35 近似演算法 |
|||
| 教學方法 | |||
| 方式 | 說明 | ||
| 講述法 | 上課口授及討論 | ||
| 討論法 | 上課口授及討論 | ||
| 問題解決教學 | 課堂將針對相關課題討論 | ||
| 評量方法 | |||
| 方式 | 百分比 | 說明 | |
| 作業 | 50 % | 平時作業約5次（每次約佔總成績10％） | |
| 期中考 | 20 % | 共二次考試（每次約佔總成績20％） | |
| 期末考 | 20 % | 共二次考試（每次約佔總成績20％） | |
| 課堂討論參與 | 5 % | 課堂將針對相關課題討論 | |
| 出席 | 5 % | 抽點未到者，將逐次扣分。公假、事假或病假需附正式証明始得另以公式計分。 | |
| 參考書目 |
指定教科書：T. H. Cormen，C.L. Leiserson，R. L. Rivest，Introduction to Algorithms，3rd Edition，MIT Press，2009，開發代理進口。http://mitpress.mit.edu/algorithms 參考書籍： 1. D. Harel，Algorithmics: The Spirit of Computing，Addison-Wesley，2nd Edition。 2. H. S. Wilf，Algorithms and Complexity，Prentice-Hall。 |
||