算法分析与设计-北京邮电大学计算机学院（国家示范性软件学院）

课程信息

当前位置：网站首页 > 师资建设 > 教师一览 > 计算机应用技术中心

算法分析与设计

课程编号	522.5*075
课程名称	算法分析与设计
任课老师	刘晓鸿
课程类型	必修/学位课
课程阶段	硕士
学时学分	36学时2学分
基本要求	计算机软件的核心是算法，而算法设计与分析是关于算法的方法论，其研究分为两个方面： 1）软件开发中经常遇到的实际问题的解法； 2）分析算法的基本规律和原理。计算机专业传统上对于非数值方法（主要是分类和查找）有较多的训练,但这在计算机和通信日益发展的今天已经日益显现出了其局限性。在本课程中，除去传统的分类查找算法和一般的设计方法外，加入了对数论中基本算法的介绍，因为溯本求源，许多设计方法都来自于组合学及规划；另外，讨论了实际中使用非常频繁的概率算法，由于随机特性而传统上被回避了。希望通过这一课程的学习，能对现代的算法设计及分析的基本工具能有较全面的掌握。
内容提要	一、引言实例：快速分类及斯特拉森矩阵乘法二、基本工具 2.1递推关系 2.2母函数法三、若干数论中方法 3.1基本知识 3.2素数判定孙子定理 Miller Rabin方法 3.3整数因子分解 Pollard的ρ方法 3.4离散对数四、基本的非数值算法 4.1分类冒泡排序选择排序选择排序插入排序快速排序合并排序 Shell排序堆排序基数排序 4.2查找折半查找 HASH法 B*树最佳查询树的构造五、串匹配查找及集合UNION-FIND 5.1SMP算法 5.2UNION-FIND 六、基本算法设计策略 6.1分治法快速排序算法的设计与分析快速变换:FFT及快速数论变换 6.2 贪心法背包问题的算法的设计与分析带有限期的作业排序算法的设计与分析最小生成树的算法的设计与分析 6.3 动态规则 0/1背包问题货郎担问题 Viterbi译码 6.4 基本搜索算法图的基本搜索BFS及DFS 对策树 6.5 回溯法 8-皇后问题哈密尔顿回路问题 6.6 分枝—限界规划中的应用 0/1背包问题七、概率方法 7.1随机数生成 7.2 Monte Carlo方法 7.3减小方差的方法 7.4 拟Monte Carlo方法 7.5 在优化中的应用八、 NP难和NP完全问题 8.1 基本概念 8.2 非确定算法 8.3 COOK定理
教学方式
指定教材
参考书目	1．自编教材 2． Knuth,程序设计技巧，卷二、三 3． Aho, A.V and J. E. Hopcroft Ullman,The Design and Analysis of Computer Algorithms.Addison Wesley Publishing Company,1974. 4． Horowitz and Sahni，Foundations of Computer Algorithms.New York: Computer Science Press, 1978. 5． Sara Basse，算法设计与分析，北京：高等教育出版社，2000 6． Neal Koblitz ，A Course in Number Theory and Cryptography 2 nd ed. 7． Harald Niederreiter，Random Number Generation and Quasi- Monte Carlo Methods，1992
先修课程
开课学期	春

版权所有 © 北京邮电大学计算机学院

地址:北京市海淀区西土城路10号北京邮电大学教三10层邮编:100876

【师德师风监督举报途径】电话：010-62282980，邮箱：buptcs@bupt.edu.cn

北邮计语公众号

计算机学院