课程名称（中、英文）：算法设计与分析、Design and Analysis of Algorithm
课程编号：0811031 学分数：3 总学时数：45(理教：40 实验：6)
适用专业：计算机科学与技术专业、软件工程、网络工程
一、课程的性质、目的与任务
随着计算机的广泛应用，对计算机算法的研究变得日益重要。本课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；本课程首先介绍计算复杂性的定义和算法分析的基本方法，结合计算机科学及应用领域中常见的有代表性的非数值算法，介绍了几种重要的算法设计的方法：分治法、动态规划、贪心法、回朔法、分枝限界法，NP完全问题。使学生在掌握各种算法的同时，掌握算法分析的基本方法和技巧。
本课程的任务是：培养学生具有针对给定问题设计和实现高效算法的能力。包括以下三方面：
1．通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。
2．培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。
3．鼓励学生运用算法知识解决各自学科的实际问题，培养他们的科研的能力和理论联系实践的能力。
二、课程的基本要求
本课程在学习之前，最好具有离散数学、程序设计、数据结构等方面的知识。在此基础上通过本课程的学习，掌握算法的定义及基本概念、计算模型和复杂度的质量；为分析算法的复杂性做准备，在这个基础上，学习一些常用的算法设计策略，掌握其基本思想和相应算法，编制出相应程序上机调试。
三、基本教学内容与学时安排
1. 算法概述（4学时）
(1)了解算法与程序的概念。
(2)掌握算法复杂性分析及其有关的概念。
2. 递归与分治策略（8学时）
(1)理解递归的概念。
(2)了解分治法的基本思想。
(3) 掌握Strassen矩阵乘法、大整数乘法、线性时间选择、最接近点对问题的算法。
(4) 理解合并排序和快速排序算法。
3. 动态规划（8学时）
(1)掌握动态规划算法的概念和步骤。
(2)掌握矩阵的连乘算法设计和分析。
(3)掌握动态规划算法的基本要素。
(4)掌握最长公共子序列、0-1背包问题的算法设计和分析。
(5)了解凸多边形最优三角剖分、多边形游戏、流水作业调度问题的算法设计和分析。
4. 贪心算法（6学时）
(1)掌握贪心算法的概念。
(2)掌握贪心算法的基本要素。
(3)了解最优装载问题的算法分析。
(4)了解哈夫曼编码的算法分析。
(5)了解单源最短路径的Dijkstra算法的设计与分析。
(6)了解最小生成树的Prim和Kruskal算法的设计与分析。
5. 回溯法（4学时）
(1)掌握回溯法的算法框架。
(2)掌握装载问题、批处理作业调度、符号三角形问题、0-1背包问题、图的m着色问题的算法设计与分析。
(3)了解n后问题、最大团问题的回溯法的算法设计与分析。
6. 分支限界法（4学时）
(1)掌握分支限界法的基本思想。
(2)掌握单源最短路问题、0-1背包问题的分支限界法分析。
(3)了解旅行售货员问题的算法设计与分析。
7. 随机化算法（2学时）
(1)掌握随机化算法的特征。
(2)掌握随机化算法的4种分类。
(3) 理解产生伪随机数的算法。
8. NP完全性问题（4学时）
(1)了解NP完全性问题的概念。
(2)理解求解问题的计算模型。
(3)了解P类问题和NP类问题。
(4)了解NP完全问题。
(5)了解一些典型的NP完全问题。
四、 建议学时分配表
| 序号 | 教 学 内 容 | 课时分配 | |||
| 讲课 | 实验 | 习题 | 小计 | ||
| 1 | 第一章 算法概述 | 4 | 4 | ||
| 2 | 第二章 递归与分治策略 | 8 | 2 | 10 | |
| 3 | 第三章 动态规划 | 8 | 2 | 10 | |
| 4 | 第四章 贪心算法 | 6 | 2 | 10 | |
| 5 | 第五章 回溯法 | 4 | 4 | ||
| 6 | 第六章 分支限界法 | 4 | 4 | ||
| 7 | 第七章 随机化算法 | 2 | 2 | ||
| 7 | 第八章 NP完全性问题 | 4 | 4 | ||
| 合 计 | 40 | 6 | 46 | ||
课程教材：
1. 王晓东.《计算机算法设计与分析》.电子工业出版社.2007年5月
主要参考书：
1. 吕国英.算法设计与分析 .清华大学出版社. 2006.3(1)
2. 王晓东. 算法设计与实验题解. 电子工业出版社 2006.9(1)
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2001), Introduction to Algorithms (the second edition). The MIT Press，中文名《算法导论（第二版）》（影印版），高等教育出版社
六、 考核方式
考核方式：平时作业、课堂回答问题及考勤、实验占30%，期末考试占70%。
制定：高艳霞执笔，教研室集体讨论
审定：
批准：
2007年11月
《算法设计与分析》实验教学大纲
课程名称（中、英文）：算法设计与分析、Design and Analysis of Algorithm
课程编号：0811031 课程总学时/学分： 45/3 实验总学时： 6
适用专业：计算机科学与技术专业、网络工程、软件工程
一、实验教学目标
《算法设计与分析》旨在教会学生处理各种问题的方法，而通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。只有通过实验，学生才能判定自己所拟算法是否正确，是否算得上一个较优算法。
通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识。同时培养学生的实际动手能力，加强学生创新思维能力的培养。
二、主要仪器设备名称
计算机、C语言或C++语言。
三、实验基本要求
《算法设计与分析》是计算机相关专业的专业基础课程，其先修课程有数据
结构和至少一门高级语言。
算法设计与分析课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；通过此课的学习，学生应该具有针对所给的问题设计和实现高效算法的能力。通过上机实验，将使学生熟悉、掌握课堂教学中所学的大部分算法。
同时，上机实习是对学生在软件设计方面的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。通过理论联系实际，以最终提高学生动手操作的能力以及分析问题的能力。
四、实验项目设置与内容
| 序号 | 实验 名称 | 内容提要 | 实验 学时 | 每组 人数 | 实验 类型 | 开出 要求 |
| 1 | 递归与分治法 | 用分治法查找数组元素的最大值和最小值 用分治法实现归并排序算法 | 2 | 1 | 设计 | 二选一 |
| 2 | 动态规划 | 0/1背包问题 有一个背包容量为，输入个物品，每个物品有重量i，以及物品放入背包中所得的收益。问选择放入的物品，要么全部放入，要么不放，不超过背包的容量，且得到的收益最好。 最长公共子序列 给定两个序列X和Y，根据动态规划的思想求X和Y的最长公共子序列。 | 2 | 1 | 设计 | 二选一 |
| 3 | 贪心算法 | 背包问题 有一个背包容量为，输入个物品，每个物品有重量，以及物品放入背包中所得的收益。问选择放入的物品，不超过背包的容量，且得到的收益最好。 最短路径 已知图，边的权值矩阵，求某点到其他各点的路径最短。 | 2 | 1 | 设计 | 二选一 |
| 4 | 回溯法 | 8-皇后问题:在国际象棋盘上放八个皇后，要求任一皇后吃不到别人，也不受其他皇后的攻击，求出问题的所有解。 | 2 | 1 | 设计 | 选做 |
根据学生的实验预习、实验纪律、考勤、实验动手能力及实验报告结果，进行综合评定，给出A、B、C。
六、教材及主要教学参考书
课程教材：
1．王晓东.《计算机算法设计与分析》.电子工业出版社.2007年5月
主要参考书：
1．吕国英.算法设计与分析 .清华大学出版社. 2006.3(1)
2．王晓东. 算法设计与实验题解. 电子工业出版社 2006.9(1)
3．T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2001), Introduction to Algorithms (the second edition). The MIT Press，中文名《算法导论（第二版）》（影印版），高等教育出版社
制定：高艳霞执笔
审定：
批准：
2008年4月下载本文
