Teacher: 郭育倫 Mail: d95037@csie.ntu.edu.tw 演算法 Teacher: 郭育倫 Mail: d95037@csie.ntu.edu.tw.

Presentation on theme: "Teacher: 郭育倫 Mail: d95037@csie.ntu.edu.tw 演算法 Teacher: 郭育倫 Mail: d95037@csie.ntu.edu.tw."— Presentation transcript:

1 Teacher: 郭育倫 Mail: d95037@csie.ntu.edu.tw
演算法 Teacher: 郭育倫 Mail:

2 課程大綱 「程式 = 演算法＋資料結構」，這是在學習計算機科學的基礎時常常聽到的一句話，要發揮計算機的效能必須要有良善的程式，要開發出良善的程式則必須有適當的演算法。

3 課程大綱 演算法是探討如何利用有效的方法，如Greedy Method，Dynamic Programming 等來解決進階問題的重要基礎。
課程中介紹各種電腦科學中常用演算法基本概念及分析其效能與時間空間複雜度.並配合程式實作的方式更深入了解演算法的技巧與概念

4 課程大綱 (1/9) 複習演算法所需使用到的數學 標記與表示法 函數 數學歸納法 對數 集合 二項式定理 遞迴方程式

5 課程大綱 (2/9) 演算法簡介 什麼是演算法 (定義) 演算法的用途 演算法的考量 特性 表示 效能評估 最佳化

6 課程大綱 (3/9) 效能分析 最差狀況 平均狀況 時間複雜度 Θ 符號表示 O 符號表示 Ω 符號表示 空間複雜度

7 課程大綱 (4/9) 遞迴公式 基本資料結構 取代方法 支配方法 (Master Theorem) 鏈結串列 (Link List)
堆疊 (Stack) 佇列 (Queue) 二元樹 (Binary tree)

8 課程大綱 (5/9) 排序 選擇排序 (Select Sort) 氣泡排序 (Bubble Sort) 插入排序 (Insert Sort)
合併排序 (Merge Sort) 快速排序 (Quick Sort) 堆積排序 (Heap Sort) 計數排序 (Counting Sort) 基數排序 (Radix Sort)

9 課程大綱 (6/9) 搜尋樹 線性搜尋 二元搜尋 二元搜尋樹 平衡樹 AVL 樹 紅黑樹 B樹

10 課程大綱 (7/9) 雜湊 (Hash) 雜湊函數 字串搜尋 基本圖論 深度優先搜尋 廣度優先搜尋

11 課程大綱 (8/9) 加權圖 最小生成樹 (minimum spanning tree) Prim Kruskal 最短路徑
Dijkstra Bellman-Ford Floyd-Warshall

12 課程大綱 (9/9) 貪婪演算法 (Greedy) 拓樸排序 霍夫曼編碼 動態規劃 (Dynamic programming) etc.

13 教材(1/2) 教科書: 演算法概論 作者:蔡郁彬 胡繼陽 侯玉展 出版社:學貫出版社 出版日：

14 教材(2/2) 參考書目 中文書 演算法使用C++虛擬碼 建構式演算法 原文書 Introduction to Algorithms

15 課程網頁 成績評量 http://www.csie.ntu.edu.tw/~d95037/ 平時成績：30% (含作業20%、出席率10%)
期中考成績：30% 期末考成績：40%