《算法设计与分析》课程教学大纲。
一、课程基本信息。
二、课程简介。
算法设计与分析》是信息与计算科学专业的专业选修课。算法是计算机科学的灵魂，《算法设计与分析》是一门面向设计，且处于计算机科学核心地位的课程。本课程的主要内容包括：
算法概述、递归与分治策略、动态规划、贪心算法、回朔法、分枝限界法，随机化算法等。
三、课程目标。
通过本课程中许多常见且有代表性算法的学习，使学生理解和掌握算法设计的主要方法，培养对算法时间复杂性进行正确分析能力，为独立的设计算法和给定算法进行复杂性分析打下良好的基础。培养学生具有针对给定问题设计和实现高效算法的能力。
四、教学内容及要求。
一）算法概述。
1，教学目的与要求。
1）了解算法与程序的概念。
2）掌握算法复杂性分析及其有关的概念。
3）了解np完全问题。
2，教学内容。
1）算法与程序。
2）算法复杂性分析。
3）np完全性理论。
二）递归与分治策略。
1，教学目的与要求。
1）理解递归的概念。
2）了解分治法的基本思想。
3）掌握二分搜索技术
4）掌握strassen矩阵算法现。
5）了解棋盘覆盖问题的算法。
6）理解合并排序和快速排序算法。
7）了解线性时间选择算法。
2，教学内容。
1）递归的概念。
2）分治法的基本思想。
3）二分搜索技术
4）大整数的乘法。
5）strassen矩阵乘法。
6）棋盘覆盖。
7）合并排序。
8）快速排序。
9）线性时间选择。
10）最接近点对问题。
11）循环日程表。
三）动态规划。
1，教学目的与要求。
1）掌握动态规划算法的概念、步骤和基本要素
2）掌握最长公共子序列算法设计和分析
3）掌握矩阵的连乘算法设计和分析
4）了解凸多边形最优三角剖分算法
5）了解多边形游戏问题的算法分析
6）了解图像压缩算法分析。
7）掌握电路布线问题的算法分析
8）掌握流水作业调度
9）了解背包问题的算法分析
10）了解最优二叉搜索树的算法分析
2，教学内容。
1）矩阵的连乘问题。
2）动态规划算法的基本要素。
3）最长公共子序列。
4）最大子段和。
5）凸多边形最优三角剖分
6）多边形游戏
7）图像压缩。
8）电路布线
9）流水作业调度
10）0－1背包问题
11）最优二叉搜索树
四）贪心算法。
1，教学目的与要求。
1）掌握贪心算法的概念和基本要素。
2）了解贪心算法的理论基础。
3）了解最优装载问题的算法分析。
4）了解哈夫曼编码的算法分析。
5）了解单源最短路径的dijkstra算法的设计与分析
6）了解最小生成树的prim和kruskal算法的设计与分析。
2，教学内容。
1）活动安排问题。
2）贪心算法的基本要素。
3）最优装载。
4）哈夫曼编码。
5）单源最短路径。
6）最小生成树。
7）多机调度问题。
五）回溯法。
1，教学目的与要求。
1）掌握回溯法的算法框架。
2）掌握批处理作业调度问题的算法设计与分析。
3）掌握n 后问题的算法设计与分析。
4）了解符号三角形问题的算法设计与分析。
5）了解背包问题的回溯法的算法分析。
6）了解最大团问题的算法设计与分析。
7）了解电路板排列问题的算法设计与分析构。
8）了解回溯法的效率分析。
2，教学内容。
1）回溯法的算法框架。
2）装载问题。
3）批处理作业调度。
4）符号三角形问题。
5）n后问题。
6）0－1背包问题。
7）最大团问题。
8）图的m着色问题。
9）旅行售货问题。
10）圆排列问题。
11）电路板排列问题。
12）连续邮资问题。
13）回溯法的效率分析。
六）分支限界法。
1，教学目的与要求。
1）掌握分支限界法的基本思想。
2）掌握单源最短路问题的分支限界法分析。
3）掌握背包问题的分支限界法分析。
4）了解旅行售货员问题的算法设计与分析。
2，教学内容。
1）分支限界法的基本思想。
2）单源最短路问题。
3）装载问题。
4）布线问题。
5）0－1背包问题。
6）最大团问题。
7）旅行售货员问题。
8）电路板排列问题。
9）批处理作业调度。
七） 随机化算法。
1，教学目的与要求。
1）理解数值随机化算法。
2）了解sherwood算法。
3）了解las vegas算法。
4）了解monte carlo算法
2，教学内容。
1）随机数。
2）数值随机化算法。
3）sherwood算法。
4）las vegas算法。
5）monte carlo算法
五、课时分配表。
六、教材及参考书。
教材：《计算机算法设计与分析》（第四版） 电子工业出版社2024年7月出版王晓东著。
参考书：《算法导论》（影印版）高等教育出版社 thomas charles ronald clifford stein
修订人 (签字) 梁新健。
审核人 (签字) 黄可坤。
批准人（签字） 陈德华。
算法设计与分析》实验教学大纲。
一、 基本信息。
二、实验课程简介。
算法设计与分析》实验课程是与《算法设计与分析》配套的课程。实验内容主要是使用c＋＋语言实验与理论课程相关的算法，主要包括：基本算法、递归、分治策略、动态规划、贪心算法、回溯法、分支界限法的实现。
三、实验目的。
算法设计与分析》旨在教会学生处理各种问题的方法，而通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。只有通过实验，学生才能判定自己所拟算法是否正确，是否算得上一个较优算法。
通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识。同时培养学生的实际动手能力，加强学生创新思维能力的培养。
四、实验内容与要求。
一）基本算法。
1．实验目的与要求。
通过实验使学生掌握使用c＋＋语言实现排序算法的方法，了解一些常见问题的算法设计与实验方法。
2．实验内容。
1）插入排序。
2）合并排序。
3）统计数字问题。
4）字典序问题。
二）递归与分治策略。
1．实验目的与要求。
通过实验使学生掌握使用递归和分治法实现算法的方法。
2．实验内容。
1）递归的使用。
2）分治法的实现。
3）众数问题。
4）有重复元素的排列问题。
三）动态规划。
1．实验目的与要求。
通过实验使学生掌握使用动态规划算法的基本设计思路，并用其解决实际问题。
2．实验内容。
1）矩阵连乘问题。
2）最大子段和问题。
3）最长公共子序列。
4）0－1背包问题。
5）独立任务最优调度问题。
6）数字三角形问题。
四）贪心算法。
1．实验目的与要求。
掌握贪心算法的基本设计思路，并用其解决实际问题。
2．实验内容。
1）0－1背包问题。
2）单源最短路径问题。
3）会场安排问题。
4）最优合并问题。
五）回溯算法。
1．实验目的与要求。
掌握回溯法的算法框架和算法的基本思想。
2．实验内容。
1）8皇后问题。
2）批处理作业调度。
3）0－1背包问题。
4）子集和问题。
六）分支界限法。
1．实验目的与要求。
通过实现掌握分支界限法的基本思想，并能用其解决问题。
2．实验内容。
1）0－1背包问题。
2）最小权顶点覆盖问题。
七） 随机化算法。
1．实验目的与要求。
了解随机化算法的基本思想。
2．实验内容。
模平方根问题。
五、主要仪器设备。
计算机。六、实验学时分配表。
七、考核方法。
上机考试采用开卷考试方式。
八、教材及参考书。
建议教材：
计算机算法设计与分析》（第四版） 电子工业出版社2024年7月出版王晓东著。
计算机算法设计与分析习题解答》（第二版） 电子工业出版社2024年6月出版王晓东著。
参考书：算法导论》（影印版）高等教育出版社 thomas charles ronald clifford stein
制订人（签字） 梁新健。
审核人 (签字) 黄可坤。
批准人（签字） 陈德华。
C 程序设计教学大纲
课程教学大纲。贵州大学科技学院。2007年8月。c 程序设计 课程教学大纲。课程中文名称 c 程序设计。课程英文名称 c language programming 课程类别 必修课。课程编号 课程归属单位 贵州大学科技学院。制订时间 2007年8月。一 课程的性质 任务。课程性质 c 程序设计 是电...
《C程序设计》教学大纲
一 说明。一 c程序设计 的课程性质 c程序设计 是高等院校计算机专业专业基础课，也是一门实践性很强的课程，既要掌握概念，又要动手编程，还要上机调试运行。对计算机类专业学生来说是一门必修的课程，同时，这门课程也是 安徽省非计算机专业学生计算机应用能力水平考试 二级考试的主要语种之一。二 教材及授课对...
《C程序设计》教学大纲
c程序设计。c程序设计 课程教学大纲。一 课程基本信息。课程名称 c语言程序设计。课程类别 专业核心课 必修课 适用专业 计算机科学与工程及相关专业课程简介 c程序设计 是计算机专业最最基本的课程之一。本课程旨在让学生掌握一门最常用的程序设计语言 c语言，掌握结构化程序设计的思想，掌握最基本通用算法...