课程号：00110060
课程名称：算法设计与分析
开课学期：秋
学分： 3
先修课程：，高等数学，数据结构，离散数学，概率论
基本目的：本课程通过系列典型问题阐释计算机算法的重要设计策略：贪心法，分治法，动态规划法，图检索和周游方法，回溯法等，同时概述分析算法时间复杂度和效率的方法，并简要介绍np难度问题及相应的近似算法和随机算法。期望学生掌握算法评估的基本原理与方法；提高设计新算法的能力。
内容提要：
第一章：引言（约2学时）
1)计算机算法的概念，算法评判的准则，时间复杂度与空间复杂度的计算，复杂度的渐近分析，多项式复杂度算法和指数复杂度算法，可行算法；2)算法语言：sparks
第二章：分治法 （约10学时）
1)分治法的原理，整数位乘，strassen 矩阵乘法，快速fourier变换；2)时间复杂度的递归表达式，master 定理；3)二分检索算法；4)选择问题：找最大和最小元素；找最大和次大元素，对手策略；5)排序问题：插入排序；堆排序，归并排序；快速排序，排序算法时间复杂度的下界估计，排序算法的优劣性比较；6）计算几何问题：最近点对问题和凸包问题
第三章：贪心法（约6学时）
1)最优化问题的框架，贪心法的思路，最小生成树的kruskal算法；2)磁带上的最优存储，最小延迟；3)背包问题；4)带有限期的作业调度；5)拟阵与贪心算法；6）最优根树
第四章：动态规划法（约8学时）
1)多阶段问题与最优性原理，矩阵连乘问题；2）最优二分检索树；3)最长递增子序列；4）0/1背包问题；5）流水线调度问题；6）最长非递减子序列
第五章：基本周游与检索方法（约8学时）
1)宽度优先检索与最少操作问题；2）深度优先检索，有向图的拓扑序，关键路径；3）有向图的强连通分图与无向图的双连通分图
第六章：回溯法（约4时）
1) 回溯法原理，骑士巡游问题；2)稳定婚姻问题
专题选讲（约6学时）
1）平摊分析；2）np-难度和np-完全问题简介；3）近似算法和随机算法简介
教学方式：每周授课3学时
教材与参考书：
1. 余祥宣，崔国华，邹海明，“计算机算法基础”，华中科技大学出版社，1998。
2. e. horowitz, s. sahni, “fundamentals of computer algorithms”, new york: computer science press, pitman, inc., 1978.
3. sara baase, allen van gelder, “computer algorithms: introduction to design and analysis (third edition)”, higher education press & pearson education asia limited., 2001.
4. thomas h. corman, charles e. leiserson, ronald l. rivest, clifford stein, “introduction to algorithms (second edition)”, higher education press & the mit press, 2002. （有中译本）
5. d. e. knuth, “the art of computer programming (third edition): fundamental algorithms (vol. 1)”, addison-wesley, 1998; 清华大学出版社（影印），2002.
6. d. e. knuth, “the art of computer programming (third edition): sorting and searching (vol. 3)”, addison-wesley, 1998; 清华大学出版社（影印），2002.
7. jon kleinberg and eva tardos, “algorithm design”, pearson education asia limited and tsinghua unversity press, 2006.（有中译本）
8. m h alsuwaiyel, algorithms: design techniques and analysis (revised edition), world scientific publishing co. pte. ltd., 2016.
学生成绩评定方法：作业20％，期末考试80％.
课程修订负责人：杨建生
