算法设计与分析
计算机科学系本科生必修课, 厦门大学, 2021-03
该课程为厦门大学计算机科学与技术系大二下学期必修课，是理论性与实践性都很强的学科，是计算机学科的重要专业课之一。本课程主要介绍算法的基础知识，包括抽象计算模型、算法基本概念、算法复杂性分析基础、算法设计的基本方法、以及算法复杂性理论基础。课程教学的基本要求是通过教学活动，使每一个学生较好地掌握课程的主要内容，同时具备对实际问题应用所学知识设计出有效算法并编程实现这些算法的能力。此外，配合实验课程的教学，学生应理论联系实际，理论指导实践，通过实验工作，借助程序设计语言，掌握运用数据结构、算法和程序解决一些实际问题的方法。
通过本课程的学习，要求学生达到以下目标：
- 了解可支持算法运行的抽象机器计算模型，算法的定义和复杂性概念，算法设计的基本技术方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法以及高级图论算法等，理解并掌握算法复杂性的分析方法、NP完全性理论基础等计算复杂性的基本知识以及完全性证明概要。
- 通过教学和实践，培养学生运用数学工具和方法分析问题和从算法的角度运用数学工具解决问题的基本能力。
- 使学生能够正确地分析和评价一个算法，进一步设计出真正有效或更有效的算法。
教材
张德富，《算法设计与分析》，国防工业出版社，2009
课程大纲
| 章节 | 主要内容 |
|---|---|
| Lecture 1 Introduction | insertion sort, correctness of algorithms, loop invariants, time complexity |
| Lecture 2 Asymptotic Notation | big O, big Omega, big Theta, use limit to calculate |
| Lecture 3 Algorithm Analysis | probabilistic analysis, amortized analysis |
| Lecture 4 Recursion | towers of Hanoi, selection sort, generating permutations, substitution method, master method |
| Lecture 5 Divide-and-Conquer | recursion equation, mergesort, quicksort, large integer multiplication, matrix multiplication, defective chessboard |
| Lecture 6 Dynamic Programming | optimal substructure property, Fibonacci sequence, assembly-line scheduling, matrix-chain multiplication, the longest-common-subsequence, 0/1 knapsack problem, optimal binary search tree, |
| Lecture 7 Greedy Algorithms | greedy selection property, activity selection problem, fractional knapsack Problem, Huffman coding |
| Lecture 8 Graph Algorithm | DFS, BFS, minimum spanning tree, Kruskal’s algorithm, Prim’s algorithm, the shortest path problem, Dijkstra’s algorithm, Floyd-Warshall algorithm |
| Lecture 9 Network Flow and Matching | max-flow problem, the Ford-Fulkerson method, max-flow min-cut theorem, Edmonds-Karp algorithm, matching problem, bipartite graph matching problem, Hungry tree algorithm |
| Lecture 10 Linear Programming | standard form of linear programming, slack form of linear programming, simplex algorithm |
| Lecture 11 NP Complete Theory | polynomial-time algorithm, decision problem, definition of P and NP, NP complete, reducibility, NP-completeness proof, satisfiability problem, 3-CNF satisfiability problem, clique problem, vertex cover problem |
| Lecture 12 Backtracking | solution space tree, constraint function, bounding function, container loading problem, 0/1 knapsack problem, n queen problem, traveling salesperson problem |
| Lecture 13 Branch-and-Bound | FIFO branch-and-bound, max-profit branch-and-bound |
期末合影
