《算法设计与分析》课程简介

更新:2019-04-23 17:02:30 阅读:人次

一、课程名称(中英文)

中文名称:算法设计与分析

英文名称:Algorithms Design and Analysis

二、课程性质

专业方向课选修

三、学时与学分

总学时:48(理论学时:40学时;实验学时:8学时)

学分:3

四、主要教学内容

《算法设计与分析》是计算机专业的一门重要专业基础课。计算机学科中,无论是软件设计,还是硬件设计都离不开算法,算法计算机科学的核心。本课程为学生打开算法之门,介绍常用的算法设计策略和技术、众多经典问题及其算法设计思想、算法证明和分析的方法和技术等。通过本课程的学习,使学生熟练掌握算法设计的基本理论、方法和技术,训练计算思维,提高分析问题和解决问题的实际能力。

(一)算法概述

1.1算法的基本概念和性质

1.2算法复杂度的渐进分析

(二)递归与分治策略

2.1递归的概念

2.2分治策略的基本思想

2.3二分搜索*

2.4最大子数组问题

2.5 Strassen矩阵乘法

2.6归并分类算法*

2.7快速分类算法*

2.8选择问题

2.9最近点对问题*

2.10递归式求解:代入法、递归树法、主方法

(三)概率分析和随机算法

3.1雇佣问题

3.2概率分析和随机算法的基本思想

3.3平均情况运行时间和期望运行时间分析

(四)中位数和顺序统计量*

4.1顺序统计量、中位数的概念

4.2带权中位数和一维邮局问题、二维邮局问题

4.3带权中位数的性质证明

(五)动态规划

5.1动态规划的基本概念、要素和步骤,备忘录方法

5.2钢条切割问题

5.3矩阵链乘法问题

5.4最长公共子序列

5.5最优二叉搜索树

5.6 0-1背包问题

(六)贪心算法

6.1贪心算法的基本思想和要素

6.2活动安排问题

6.3哈夫曼编码

6.4最优归并模式*

6.5分数背包问题

6.7最小生成树的Prim算法、Kruskal算法、Boruvka算法的分析和设计*

6.8贪心方法的理论基础*

(七)图算法

7.1图的概念、表示和基本的BFS/DFS算法*

7.2最短路算法:Bellman-Ford算法、Dijkstra算法、Floyd算法、SPFA算法*

7.3差分约束系统

7.4 Johnson算法*

7.5最大流网络:流网络的定义、最大流最小切割定理、Ford-Fulkerson方法

(八)回溯法

8.1回溯法的基本思想和算法框架

8.2装载问题

8.3 N皇后问题

8.4子集和数问题

8.5旅行商问题*

8.6着色问题*

8.7回溯法的效率分析*

(九)分支限界法

9.1分支限界法的基本思想

9.2 A*算法

9.4 α-β搜索法

9.5 0-1背包问题*

9.6十五子问题*

9.7作业调度问题

(十)NP完全性问题

10.1 P类问题和NP类问题

10.2 NP完全性的概念

10.3问题变换与计算复杂性归约

10.4一些典型的NP完全问题*

(十一)高级数据结构专题*

11.1红黑树

11.2不相交集合和并查集

(十二)字符串匹配*

12.1朴素的字符串匹配算法

12.2 KMP算法

12.3 BM算法

注:带*的章节可根据情况选讲或自学。

五、课程特色:

1)内容充实,覆盖常用算法设计策略和众多经典问题,知识面广、探讨深入

2)内容新颖:探究式学习,从实例出发展开问题讨论,生动讲解算法设计的原理和方法

3)理论和实践相结合:除理论教学外,精心设计课上、课下实验/实践教学,提高实践动手能力

4)直接对接算法和程序类考试,如CSP、PAT等。

六、考核方式

考核方式:考试

成绩评定:平时成绩(30%,包括平时作业、实验、考勤)+考试成绩(70%)

七、教材及参考书

教材:《算法导论》(Introduction to Algorithms,MIT,第三版)

参考书:《算法设计》(Algorithm Design,J. Kleinberg)、《Algorithms》(R. Sedgewick, K. Wayne,第四版)