南台課程大綱
學年度 98學年第二學期 系所 電子系
課程名稱 高等演算法 班級 碩研電子一甲
授課教師 黎靖 點 閱 次 數 89
選修
選修
課程概述
演算法是指利用電腦解決問題所需要的具體方法和步驟。也就是說給定初始狀態或輸入數據,經過電腦程序的有限次運算,能夠得出所要求或期望的終止狀態或輸出數據。本課程介紹電腦科學中重要的演算法及其分析與設計技術,熟知這些演算法,才能有效的使役電腦為我們服務。
課程目標
讓同學知道及學習撰寫好的程式,了解基本的演算法設計策略,知道這些策略有何優缺點及使用上的限制,並懂得經由複雜度分析判定演算法的好壞。
課程大綱
第1章 演算法: 效率分析及複雜度
1.1 概述
1.2 幾個簡單演算法之範例
1.3 演算法之效率
1.4 逼近分析法
1.5複雜度分析
第2章 分治法
2.1 遞迴
2.2 遞迴演算法之複雜度分析
2.3 分治法
2.4分治法之限制
第3章 動態規劃法
3.1 概述
3.2 費氏數列
3.3 二項式係數
3.4 最短路徑問題
3.5 最佳的二元搜尋樹
3.6 旅行推銷員問題
3.7動態規劃法之限制
第4章 貪婪法
4.1 概述
4.2 最小代價開展樹
4.3 單一起點最短路徑問題
4.4 排程問題
4.5 Huffman碼
第5章 回溯法
5.1 概述
5.2 n后問題
5.3 子集求和問題
5.4 漢米爾頓迴路問題
5.5 背包問題
第6章 分支設限法
6.1 概述
6.2 背包問題
6.3 分支設限之擇優搜尋法
6.4 旅行推銷員問題
第7章 時間複雜度: 排序問題
7.1 插入排序法
7.2 交換排序法
7.3 選擇排序法
7.4 簡單排序法之時間複雜度下限
7.5 合併排序法
7.6 快速排序法
7.7 堆積排序法
7.8 基數排序法
英文大綱
Chapter 1. Algorithms: Efficiency, Analysis, and Complexity
1.1 Introduction
1.2 Some simple algorithms
1.3 The efficiency of algorithms
1.4 Asymptotics
1.5 Complexity analysis
Chapter 2. Divide-and-Conquer
2.1 Recursion
2.2 Complexity analysis for recursive relation
2.3 Divide-and-conquer
Chapter 3. Dynamic Programming
3.1 Introduction
3.2 Fibonacci numbers
3.3 Binomial Coefficient
3.4 Shortest Paths Problem
3.5 Optimal binary search trees
3.6 The traveling salesperson problem
Chapter 4. Greedy algorithm
4.1 Introduction
4.2 Minimum spanning trees
4.3 Single-source shortest paths problem
4.4 Scheduling
4.5 Huffman code
Chapter 5. Backtracking method
5.1 Introduction
5.2 The n-queens problem
5.3 The Sum-of-Subsets Problem
5.4 The Hamiltonian circuits problem
5.5 Knapsack Problem
Chapter 6. Branch-and-Bound
6.1 Introduction
6.2 Knapsack Problem
6.3 Best-First Search with Branch-and Bound Pruning
6.4 The traveling salesperson problem
Chapter 7. Computational Complexity: The Sorting Problem
7.1 Insertion Sort
7.2 Exchange Sort
7.3 Selection Sort
7.4 Lower Bounds for Algorithms of Simple Sort Methods
7.5 Merge Sort
7.6 Quick Sort
7.7 Heap Sort
7.8 Radix Sort

下載
Doc Pdf Html
連結(一) 連結(二) 連結(三)

上一頁