算法设计与分析

算法设计与分析课程教学大纲、教学周历

课程序号：                                        院（系）：计算机科学与工程系

一、           教学目标和要求：

本课程是计算机科学技术中的处于核心地位的课程，是本一级学科各专业方向必修的一门重要的专业基础课。在任何一个与计算机科学技术相关的研究领域，无论是计算机理论、计算机系统、系统软件还是计算机的各种应用方向中，算法设计与分析都是不可缺少的，是计算机科学通常要解决的主要问题之一。本课程的主导思想是面向设计，将系统地介绍计算机科学技术领域中的一些常用的、经典的非数值算法，系统地分析这些算法所需的时间和空间，同时严格证明这些算法的正确性。通过本课程的学习，使学生掌握算法设计的常用方法，提高学生算法设计与复杂性分析的素质和能力，为学生能够独立进行算法的设计和计算复杂性的分析奠定一个比较坚实的基础。以便使学生在将来从事计算机领域或其它有关领域的研究中，能够运用这些方法来设计解决一些常用的或较为复杂的实际问题的算法，并力争做到快捷、有效，从而提高程序的质量并较好地解决科学研究与实际应用中所遇到的问题。

要求学生掌握计算机科学技术领域中的一些常用的、经典的算法设计技术，学会分析算法、估计算法的时空复杂性，在非数值计算的层面上，具备把实际问题抽象描述为数学模型的能力，同时能针对不同的问题对象设计有效的算法，用典型的方法来解决科学研究及实际应用中所遇到的问题。并且具备分析算法效率的能力，能够科学地评估有关算法和处理方法的效率。

二、教学大纲（含章节目录）：

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)      下界理论

选择和对手论证，求最大、最小元问题，排序问题，选择问题。

三、教学周历：