算法設計與分析

算法設計與分析課程教學大綱、教學周曆

課程序号：                                        院（系）：計算機科學與工程系

一、           教學目标和要求：

本課程是計算機科學技術中的處于核心地位的課程，是本一級學科各專業方向必修的一門重要的專業基礎課。在任何一個與計算機科學技術相關的研究領域，無論是計算機理論、計算機系統、系統軟件還是計算機的各種應用方向中，算法設計與分析都是不可缺少的，是計算機科學通常要解決的主要問題之一。本課程的主導思想是面向設計，将系統地介紹計算機科學技術領域中的一些常用的、經典的非數值算法，系統地分析這些算法所需的時間和空間，同時嚴格證明這些算法的正确性。通過本課程的學習，使學生掌握算法設計的常用方法，提高學生算法設計與複雜性分析的素質和能力，為學生能夠獨立進行算法的設計和計算複雜性的分析奠定一個比較堅實的基礎。以便使學生在将來從事計算機領域或其它有關領域的研究中，能夠運用這些方法來設計解決一些常用的或較為複雜的實際問題的算法，并力争做到快捷、有效，從而提高程序的質量并較好地解決科學研究與實際應用中所遇到的問題。

要求學生掌握計算機科學技術領域中的一些常用的、經典的算法設計技術，學會分析算法、估計算法的時空複雜性，在非數值計算的層面上，具備把實際問題抽象描述為數學模型的能力，同時能針對不同的問題對象設計有效的算法，用典型的方法來解決科學研究及實際應用中所遇到的問題。并且具備分析算法效率的能力，能夠科學地評估有關算法和處理方法的效率。

二、教學大綱（含章節目錄）：

1)     計算模型

a)      RAM，RASP，Turing機的基本概念和時間複雜度的分析。

b)      各種計算模型時間複雜度相互之間的關系。

c)      原始、一般、部分遞歸函數與計算模型相互之間的關系。

2)      算法基本概念與算法數學基礎

a)      算法的五個特征，評價算法的标準，算法的正确性，程序的測試。

b)      遞推方程的生成函數求解法，遞歸方程求解的主定理。

c)      遞歸方程求解的疊代法，積分法，代換法。

3)      分治法

a)      分治與平衡的基本概念，大整數相乘的分治法，斯特拉森矩陣乘法。

b)      選擇問題，最近點對問題，快速離散傅立葉變換。

4)      動态規劃法

a)      動态規劃法的基本概念，矩陣鍊相乘問題，最優二叉搜索樹問題算法設計與分析。

b)      最長公共子序列問題，流水線調度問題的算法設計與分析。

5)      基于集合的數據結構和算法

a)      UNION-FIND算法的設計與分析。

b)      字典，優先隊列，可并堆，可連接隊列上的各種算法設計與分析。

6)      随機算法

a)      随機算法的基本概念，Las Vegas方法, Monte Carlo方法和Sherwood方法等基本方法。

b)      随機算法設計與分析實例：字符串匹配，素數測試，最近點對問題。

7)      NP完全性理論

a)      非确定性Turing機，多項式變換與驗證基本概念，Cook定理。

b)      NP完全問題的證明：3-CNT-SAT, CLIQUE,VERTEX-COVER, SUBSET-SUM等。

8)      近似算法

a)      Bin Packing問題的算法和分析，PTAS和FPTAS的概念與實例。

b)      Knapsack, 多Knapsack, TSP問題的近似算法和分析。

9)      下界理論

選擇和對手論證，求最大、最小元問題，排序問題，選擇問題。

三、教學周曆：