C程序设计教学大纲

教学大纲――算法设计与分析《算法设计与分析》课程教学大纲一、课程基本信息课程名称（中文）算法设计与分析课程名称（英文）AlgorithmDesignandAnalysis课程类型专业选修课学分4总学时64适用对象信息与计算科学专业三年级考核方式闭卷笔试结合实践考核，平时成绩占总成绩的百分20%、实验成绩占总成绩的20%，期末考试成绩占总成绩的60%先修课程程序设计语言、离散数学、数据结构二、课程简介《算法设计与分析》是信息与计算科学专业的专业选修课。算法是计算机科学的灵魂，《算法设计与分析》是一门面向设计，且处于计算机科学核心地位的课程。本课程的主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回朔法、分枝限界法，随机化算法等。三、课程目标通过本课程中许多常见且有代表性算法的学习，使学生理解和掌握算法设计的主要方法，培养对算法时间复杂性进行正确分析能力，为独立的设计算法和给定算法进行复杂性分析打下良好的基础。培养学生具有针对给定问题设计和实现高效算法的能力。四、教学内容及要求（一）算法概述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，教学内容《算法设计与分析》实验教学大纲基本信息课程名称（中文）算法设计与分析课程名称（英文）AlgorithmDesignandAnalysis课程类型专业选修课学分4实验学时32适用专业信息与计算科学专业三年级先修课程程序设计语言、离散数学、数据结构二、实验课程简介《算法设计与分析》实验课程是与《算法设计与分析》配套的课程。实验内容主要是使用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．实验内容模平方根问题。五、主要仪器设备计算机六、实验学时分配表序号实验项目名称学时实验内容实验性质每组人数必/选做演示验证设计综合1基本算法4221必做2递归与分治策略8621必做3动态规划6421必做4贪心算法441必做5回溯法441必做6分支界限法221必做7随机化算法441选做七、考核方法上机考试采用开卷考试方式。八、教材及参考书建议教材：《计算机算法设计与分析》（第四版）电子工业出版社2012年7月出版王晓东著《计算机算法设计与分析习题解答》（第二版）电子工业出版社2012年6月出版王