算法分析与设计前言精.ppt

《算法分析与设计前言精.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计前言精.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析与设计前言第1页，本讲稿共29页课课 程程 简简 介介|算法设计与分析是计算机科学与技术专业一门专业选修课。|通过本课程的学习，学生可以了解计算机应用中的各种常用算法，掌握设计和分析各种算法的基本原理、方法和技巧。能运用所学到的知识熟练地分析各种算法并能指出解决同一问题的各种算法的好坏。第2页，本讲稿共29页课课 程程 要要 求求|了解计算机应用中的各种常用算法|了解评价算法的准则和方法|掌握设计和分析算法的基本原理、方法和技巧|提高分析问题和解决问题的能力第3页，本讲稿共29页课课 程程 内内 容容第一章第一章 绪论绪论|计算机发展及其与算法的关系|算法分析的原则|本书用到的一些符号

2、和术语第4页，本讲稿共29页课课 程程 内内 容容第二章第二章 动态规划动态规划|最短路径问题、最佳原理|流动推销员问题|矩阵链乘问题|最长公共子序列|图的任意两点间的最短距离|整数规划|同顺序流水作业的任务安排问题|可靠性问题、设备更新问题第5页，本讲稿共29页课课 程程 内内 容容第三章第三章 优先策略优先策略|最短树的Kruskal算法|求最短树的Prim算法|求最短路径的Dijkstra算法|文件存储问题|有期限的任务安排问题第6页，本讲稿共29页课课 程程 内内 容容第四章第四章 HuffmanHuffman编码、编码、FFTFFT算算 法和数据压缩法和数据压缩|Huffman编码|

3、快速傅里叶变换（FFT）|卷积及其应用第7页，本讲稿共29页课课 程程 内内 容容第五章第五章 分治策略分治策略|二分查找|整数乘法|矩阵乘积的Strassen算法|矩阵乘积的Winograd算法|布尔矩阵的乘法问题第8页，本讲稿共29页课课 程程 内内 容容第六章第六章 线性规划的分解原理线性规划的分解原理|线性规划和单纯形法简介|DantzigWolfe分解算法第9页，本讲稿共29页课课 程程 内内 容容第七章第七章 最佳二分树最佳二分树|二分树|最佳二分树第10页，本讲稿共29页课课 程程 内内 容容第八章第八章 内存分类法之一内存分类法之一|分类|分类的下界估计|二分插入分类法|She

4、ll分类法第11页，本讲稿共29页课课 程程 内内 容容第九章第九章 内存分类法之二内存分类法之二|递选分类法|二分树递选分类法|堆集分类法第12页，本讲稿共29页课课 程程 内内 容容第十章第十章 内存分类法之三内存分类法之三|下溢分类法|快速分类法第13页，本讲稿共29页课课 程程 内内 容容第十一章第十一章 内存分类法之四内存分类法之四|归并分类法|FordJohnson归并插入分类法|基数分类法第14页，本讲稿共29页课课 程程 内内 容容第十二章第十二章 求第求第k k个元素个元素|求最小及第二小元素|求第k个元素第15页，本讲稿共29页课课 程程 内内 容容第十三章第十三章 外存分

5、类法外存分类法|外存归并分类法|置换选择段的构造|三条带的外存归并分类法第16页，本讲稿共29页课课 程程 内内 容容第十四章第十四章 分类网络分类网络|分类网络举例|01原理|归并网络|Batcher奇偶归并网络第17页，本讲稿共29页课课 程程 内内 容容第十五章第十五章 查找及均衡树查找及均衡树|AVL树关于高度均衡的二分树|关于高度均衡的二分树的插入和删除第18页，本讲稿共29页课课 程程 内内 容容第十六章第十六章 2-32-3树和树和2-3-42-3-4树树|23树|234树|红黑树第19页，本讲稿共29页课课 程程 内内 容容第十七章第十七章 B B树树|B树概念|插入和删除第2

6、0页，本讲稿共29页课课 程程 内内 容容第十八章第十八章 哈希表哈希表|什么是哈希表|哈希函数的构造方法|解决冲突的方法|哈希算法的分析（线性探测法分析）|二重哈希法第21页，本讲稿共29页课课 程程 内内 容容第十九章第十九章 DFSDFS算法和算法和BFSBFS算算 法法|概述|DFS算法|无向图的DFS算法|有向图的DFS算法|互连通块问题|强连通块问题|BFS算法第22页，本讲稿共29页课课 程程 内内 容容第二十章第二十章 剪技术和剪技术和 分支定界法分支定界法|剪技术|分支定界法和流动推销员问题|同顺序加工任务安排问题第23页，本讲稿共29页课课 程程 内内 容容第二十一章第二十

7、一章 整数规划整数规划|概述|01规划和它的DFS搜索（隐枚举）解法|分支定界法在解整数规划中的应用第24页，本讲稿共29页先先 修修 课课 程程|数据结构数据结构|程序设计程序设计第25页，本讲稿共29页学学 时时 安安 排排|序号序号内内 容容 学时安排学时安排 1 绪论 2 2 动态规划 6 3 优先策略 2 4 分治策略 2 5 Huffman编码、FFT算法 4 6 线性规划分解原理 4 7 最佳二分树 2 8 内存分类法之（1一4）8 9 求第k个元素 210 外存分类法 211 分类网络 212 查找及均衡树等 613 DFS算法和BFS算法 414-剪技术和分支定界法 215 整数规划 216 复习考试 2第26页，本讲稿共29页教教 材材计算机算法导引设计与分析，卢开澄，清华大学出版社第27页，本讲稿共29页主主要要参参考考书书|算法设计和分析，朱洪等，上海科技文献出版社，1989|算法设计分析的理论与方法，顾立尧等，上海交通大学出版社第28页，本讲稿共29页课课 外外 上上 机机 学生应有学生应有2020小时的课外上小时的课外上机安排，用所学到的方法解决机安排，用所学到的方法解决一些实际问题。一些实际问题。第29页，本讲稿共29页