算法设计与分析 教学大纲.docx

《算法设计与分析 教学大纲.docx》由会员分享，可在线阅读，更多相关《算法设计与分析 教学大纲.docx（18页珍藏版）》请在第一文库网上搜索。

1、算法设计与分析教学大纲课程名称：算法设计与分析英文名称：DesignandAna1ysisofA1gorithms教学安排：3学时/周，总48学时授课对象：本科生、跨专业研究生先修课程：数据结构、高等数学、概率论与数理统计、高级算法语言（如PASCA1,C）主要教学环境的组织课堂教学、练习、讨论1教学目的通过本课程中一些常用的、有代表性的算法的学习，让学生理解并掌握算法设计的基本技术，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。另外培养学生对算法复杂度进行正确分析的初步能力，同时鼓励学生运用算法知识解决各自学科的实际问题。培养他们的独立科研的能力和理论联系实践的能力。2课程简介算法研

2、究是计算机科学的核心问题之一，如何设计高效率的算法及评价一类算法的时空复杂性，是计算机科学工作者必须研究的核心课题，具有极大的应用和理论价值。算法的研究领域非常广泛，涉及到计算机软件设计、硬件设计中的许多地方，本课程主要介绍计算机科学及应用领域中常见的有代表性的非数值算法及算法设计的若干重要方法，同时介绍算法分析的基本知识。课程首先介绍了计算复杂性的定义和算法分析的基本方法，其次介绍了几种重要的算法设计的方法：分治法、动态规划、贪心法、回溯法、分枝限界法，使学生在掌握各种算法的同时，掌握算法分析的基本基本方法和技巧，为进一步研究算法理论打下基础。3教学内容第一章算法基础本章教学目的和内容：通过

3、章的学习，使学生理解算法的概念及其特性，掌握算法的数学基础知识。本章教学重点：算法数学基础、算法复杂性分析、排序算法、递归技术本章教学难点：平均时间复杂性分析、对数耗费标准、递归技术、递归方程、生成函数、排序算法本章学时分配：本章共6学时第二章信息结构本章教学目的和内容：通过本章的学习，使学生理解和掌握常用的信息结构，并能熟练的应用到算法设计与分析中。信息结构主要包括：线性表、树、二叉树、二叉搜索树、红黑树、B树、散列表、最小生成树等。本章教学重点：二叉树、最小生成树、散列表本章教学难点：二叉树的遍历、散列表性能分析本章学时分配：本章共6学时第三章分治法本章教学目的和内容：通过本章的学习，使学

4、生理解分治法的内涵，然后从解决计算机科学和应用中出现的几个实际问题入手，用分治法的基本思想描述了几个经典的精巧的算法，包括折半查找、顺序统计、大整数乘法、最大子数组问题、矩阵乘法、递归树求解、证明主定理、马的周游路线、循环赛日程安排等，同时对每个算法给出了数量级的分析，以使学生理解本章介绍的算法，并能用于解决实际问题。本章教学重点：分治法的一般方法、顺序统计、大整数乘法、矩阵乘法本章教学难点：顺序统计、大整数乘法本章学时分配：本章共8学时第四章动态规划本章教学目的和要求:通过本章的学习，使学生理解并掌握动态规划的一般方法,理解用动态规划解决钢条切割问题、矩阵连乘问题、最长公共子序列问题、最优二

5、叉树搜索问题、单源最短路径问题、资源分配问题、多重配置系统可靠性问题、货郎担问题、流水作业调度等问题的算法。本章教学重点：动态规划的一般方法、最长公共子序列问题、系统可靠性设计、流水作业调度问题、单源最短路径问题本章教学难点：单源最短路径问题、最长公共子序列问题本章学时分配：本章共6学时第五章贪心方法本章教学目的及内容：通过本章的学习，使学生理解并掌握贪心方法，然后用贪心设计策略解决背包问题、带时限的作业调度问题、最佳合并顺序问题、磁盘文件的最佳存储问题、哈夫曼编码、拟阵等问题，并给出了相应的算法，要求学生理解这些算法。本章教学重点：贪心设计策略的一般方法，背包问题、带时限的作业调度问题、合并

6、顺序问题本章教学难点：带时限的作业调度问题、拟阵本章学时分配：本章共4学时第六章回溯法本章教学目的和内容：通过本章的学习，使学生理解并掌握回溯的一般方法，掌握用回溯法解决n-皇后问题、子集和问题、图的M着色问题、背包问题、哈密顿回路问题、连续邮资等问题的方法，并理解相应的算法，了解相应算法的效率。本章教学重点：回溯的一般方法、皇后问题、子集和问题本章教学难点：n-皇后问题、子集和问题本章学时分配：本章共6学时第七章分枝限界法本章教学目的和要求：通过本章的教学，使学生理解分枝-限界的一般方法，理解1e-检索的概念，掌握用分枝-限界法解决15谜问题、货郎担问题、背包问题、同顺序任务加工问题、最大团

7、问题、装载问题、布线问题的方法，理解相应的算法。本章教学重点：分枝限界的一般方法、15谜问题、作业调度问题、最大团问题本章教学难点：作业调度问题、最大团问题本章学时分配：本章共6学时第八章概率分析和随机算法本章教学目的和要求：通过本章的教学，使学生理解概率分析和随机算法的一般方法,理解随机数产生的方法，掌握用概率分析和随机算法解决数值计算的方法,掌握蒙特卡罗、拉斯维加斯、舍伍德等常用算法，并解决主元素问题、素数测试问题、n皇后问题、随即排序、整数因子分解、元素选择问题、搜索有序表、跳跃表、生日悖论等问题。本章教学重点：概率分析和随机算法一般方法、常用随机算法本章教学难点：蒙特卡罗、拉斯维加斯、

8、舍伍德等常用算法本章学时分配：本章共6学时授课目录第1章算法基础/11.1 算法概念与特征11.1.1 算法概念11.1.2 算法特征11.2 数学基础11.2.1 数学归纳法11.2.2 取整函数31.2.3 二项式定理51.2.4 二项式系数61.2.5 斐波那契数81.2.6 生成函数81.3 算法复杂性分析111.3.1 算法复杂性概念111.3.2 算法复杂性刻度标准111.3.3 算法复杂性耗费标准121.3.4 渐进表示1213.5渐进记号的常用函数141.4.1 插入排序161.4.2 希尔排序161.4.3 择排序171.4.4 冒泡排序181.4.5 合并排序191.4.6

9、 快速排序191.4.7 排序算法的稳定性问题2015递归与递推201.5.1 递归201.5.2 递推20第2章信息结构/232.1 线性表232.1.1 线性表的操作232.1.2 栈和队列242.1.3 表的存储242.1.4 表的操作252.2 树262.2.1 树的定义262.2.2 二叉树272.2.3 二叉树的遍历282.3.1 二叉搜索树的建立与插入292.3.2 二叉搜索树的删除312.3.3 二叉搜索树的杳找322.3.4 二叉搜索树操作算法复杂度分析332.4红黑树332.4.1 定义342.4.2 红黑树性质342.4.3 树结构的调整352.4.4 插入352.4.5

10、 删除382.5B树401.1.1 定义401.1.28 树插入操作411.1.38 树删除操作432.6 散列表462.6.1 定义462.6.2 散列表性能分析47263散列函数472.7 最小生成树472.7.1 定义472.7.2 Kruska1算法482.73Prime算法48第3章分治法/503.1 概念503.1.1 分治法的基本思想503.1.2 分治法所处理问题的基本特征513.1.3 分治算法的实现思路513.2 折半直找533.2.1 问题描述533.2.2 问题分析533.2.3 问题求解533.2.4 算法实现543.2.5 折半查找判定树553.2.6 算法复杂度分

11、析553.3 顺序统计563.3.1 问题描述563.3.2 问题分析563.3.3 问题求解563.3.4 算法实现563.3.5 算法复杂度分析583.4 大整数乘法583.4.1 问题描述583.4.2 问题分析583.5 最大子数组问题593.5.1 问题描述593.5.2 算法分析603.5.3 分治法求解最大子数组问题603.5.4 算法实现603.5.5 算法复杂性分析613.6 矩阵乘法613.6.1 问题描述613.6.2 问题分析623.6.3 分治法求解矩阵相乘623.6.45 trassen算法实现矩阵乘法633.7 递归式求解633.7.1 问题描述633.7.2 代

12、入法求解递归式643.7.3 递归树法求解递归式653.7.4 主方法求解递归式663.8 证明主定理673.8.1 主定理673.8.2 主定理递归树表示671.1.1 定理证明681.1.2 问题分析731.1.3 问题求解731.1.4 求解过程743.10循环赛日程安排763.10.1 问题描述763.10.2 问题分析763.10.3 问题求解763.10.4 算法实现773.10.5 算法复杂度分析78第4章动态规划法/794.1概述794.1：1概念794.1.2算法实现794.13使用条件及特点804.2钢条切割问题814.2.1 问题描述814.2.2 问题分析811.1.1

13、 题求解824.2.4 算法实现824.2.5 小结834.3矩阵连乘问题834.3.2问题分析831.1.1 题求解831.1.4 算法实现841.1.5 复杂性分析844.4 最长公共子序列问题854.4.1 问题描述854.4.2 问题分析854.4.3 题求解864.4.4 算法实现864.4.5 复杂性分析874.5 最优二叉树搜索问题874.5.1 问题描述874.5.2 问题分析874.53 问题求解884.54 4算法实现884.6 单源最短路径问题894.6.1 问题描述894.6.2 问题分析904.6.3 题求解904.6.4 算法实现914.7 资源分配问题914.7.

14、2问题分析914.73 问题求解914.74 4算法实现934.8 多重配置系统可靠性问题934.8.1 问题描述934.8.2 问题分析944.8.3 题求解944.8.4 算法实现954.9 货郎担问题964.9.1 问题描述964.9.2 问题分析961.1.1 题求解964.9.4 算法实现974.9.5 复杂性分析984.10流水作业车间调度问题984.10.1 问题描述984.10.2 问题分析994.10.3 问题求解994.10.4 算法实现IoO第5章贪心算法/1015.1概念1015.1.2贪心算法的基本思想1015.13贪心算法的实现过程1015.1.4适用条件1025.

15、2 背包问题1025.2.1 问题描述1025.2.2 问题求解1025.2.3 算法实现1035.2.4 算法分析1045.3 带时限的作业调度问题1055.3.1 问题描述1055.3.2 问题分析1055.3.3 以利润最大作为贪心策略1065.3.4 以最大时限作为贪心策略1075.3.5 快速调度法1085.4 最佳合并顺序1095.4.1 问题描述1095.4.2 问题分析1091.1.1 题求解1091.1.4 算法实现1101.1.5 算法正确性证明I115.5 磁盘文件的最佳存储I115.5.1 问题分析I115.5.2 问题求解1125.5.3 算法实现1135.5.4 算法分析1135.