《算法设计基础》课程教学大纲（本科）.docx

算法设计基础(Introduction to Algorithm Design)课程代码：06410027学分：5学时：96 (其中：讲课学时：64实验学时：0上机学时：32课外学时:0 )先修课程：离散数学、程序设计基础适用专业：物联网工程教材：数据结构(C+)，王红梅，清华大学出版社，2011年6月第2版教材名称、主编、出 版社、版次一、课程性质与课程目标(-)课程性质算法设计基础是高等工科院校计算机通信类的一门专业基础课，算法是程序设计的灵魂和 思想，在任何应用领域，精心设计的算法都是解决各种问题最有效的方法。它不仅是计算机应用程 序和系统程序设计的基础，也是单片机及嵌入式系统程序开发的重要基础。通过算法设计基础 课程的学习，使学生能针对实际应用问题，分析设计出合理的算法，编写出优质程序。(二)课程目标1 .知识方面课程目标1.1:理解用算法描述计算问题的过程和方法，掌握算法分析的事前估计法及算法分析 相关的两个基本概念：时间复杂度和空间复杂度，学会用两种复杂度来表示算法的基本性能。课程目标1.2：理解算法设计中所处理的数据对象及数据对象间的关系，即数据结构的概念，深 刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的物理存储表示，以数据结构为基 础，理解各种不同数据结构上基本算法的设计与实现，同时对算法能作时间和空间性能的分析。课程目标1.3：着重理解算法中查找和排序两种基本的算法，掌握不同结构上的查找、排序方法 及对应的算法描述、性能分析。2 .能力和素养方面课程目标2.1：具备依据工程实际问题的需求抽象数据和数据关系，并将此在计算机中合理表(3)熟练掌握图的两种搜索路径的遍历方法。3 .实验要求本实验要求实现以下功能：(1)以邻接矩阵或邻接表作为存储结构建立一个无向图。(2)深度(或广度)优先搜索该无向图，输出遍历序列。(3)若图是一个非连通图，求图的连通分量个数。实验7：二叉排序树的查找性能1 .实验目的(1)理解二叉排序树的基本特征。(2)掌握二叉排序树上的查找、插入等基本算法的操作过程。2 .实验要求本实验要求实现以下功能：(1)对给定的同一个查找集合，按升序和随机顺序建立两课二叉排序树。(2)比较同一个待查值在不同二叉排序树上进行查找的比较次数。(3)对随机顺序建立的二叉排序树，输出查找最好、最坏和平均情况。实验8：内部排序方法的验证1 .实验目的熟悉各种内部排序算法的基本思想。2 .实验要求本实验要求实现以下功能：对从键盘输入的顺序任意的8个正整数，通过各种排序(至少2个排序方法)使之成为有 序的序列。输出每一趟排序的结果。四、学时分配及教学方法章(按序填写)教学形式及学时分配主要教学方 法支撑的课程目 标课堂 教学实验上机课程 实践小 计第一章绪论426讲授1.1第二章线性表6410讲授+演示1.2, 2.1, 2.2,2.3第三章栈和队列6410讲授+案例+1.2, 2.1, 2.2,演示2.3第四章字符串和多维数组8412讲授+演示1.2, 2.1, 2.2,2.3第五章树和二叉树12416讲授+演示+ 案例+互动1.2, 2.1, 2.2,2.3第六章图12618讲授+演示+ 案例+自学1.2, 2.1, 2.2,2.3第七章查找技术8412讲授+案例+演示+对比+自学1.2, 2.1, 2.2,2.3第八章排序技术8412讲授+演本+ 对比1.2, 2.1, 2.2,2.3合计643276五、课程考核考核形式考核要求考核权重备注平时作业主要考核学生对课堂讲授的知识点的 复习、理解和掌握程度，考核作业是否 提交或按时提交、考核所完成作业的质 量和正确程度。总分数平均计算（取5 次作业）10%课堂和上机考勤主要考核学生课堂听讲出勤情况、上机 实验出勤情况。缺勤一次扣1分10%上机完成8个上机实验，主要考核对算法的 理解，编程能力。10%评分细则见附录1期末考试闭卷70%六、参考书目及学习资料1.算法基础：打开算法之门，托马斯H.科尔曼著王宏志译，机械工业出版社，2015年第1版.2 .数据结构（C语言版），严蔚敏，清华大学出版社，1997年第1版.3 .数据结构（用面向对象方法与C+语言描述），殷人昆，清华大学出版社,2007年第2版。七、大纲说明（内容可包括课程基本要求、习题要求及其它一些必要的说明）1、本课程的课程设计见算法设计课程设计教学大纲。2、课程以讲授为主，辅以课堂讨论、课程成绩根据学生课堂参与情况、平时作业和期末考试 成绩综合评定。3、采用多媒体和黑板相结合的教学手段，注重学生的课堂氛围和对知识掌握程度的及时反馈。2017年 8月27日附录1:实验评价内容与评分比重以及评分细则考核内容成绩考核要求考核权重指标点预习准备情 况优秀（90-100）明确实验要求、已准备好所有程序代 码。20%2-2良(80-89)明确实验要求、已准备了大部分程序 代码。中(70-79)对实验要求较明确、已准备了部分程 序代码。及格(60-69)对实验要求理解得不够透彻、只有少 量程序代码或只有一些简单的思路。不及格（60分以下）对实验要求理解不明确，有极少或没 有程序代码和思路。编程实现能 力与运行结 果优秀（90-100）程序正确，运行结果正确且提示较为 清晰和友好。60%1-3良(80-89)程序正确，运行结果正确但提示不够 清晰友好。中(70-79)程序能运行，但运行结果有少量错 误。及格(60-69)程序能运行，但运行结果不正确或程 序错误较多无法运行或没有程序。不及格（60分以下）只有个别程序能运行或程序错误较 多无法运行或没有程序。报告清晰， 按时提交优秀(90-100)报告清楚，按时提交。20%2-2良(80-89)报告较清楚，按时提交中(70-79)报告清楚或较清楚，但未按时提交。及格(60-69)报告不清楚但按时提交。不及格（60分以下）报告不清楚也未按时提交。示的能力。课程目标2.2：具备依托工程实际问题中数据对象的关系设计有效算法，并对算法性能进行时 空分析的能力。课程目标2.3：具备将算法转化为解决工程实际问题的可运行程序的能力。（三）课程目标与专业毕业要求指标点的对应关系本课程支撑专业培养计划中毕业要求1中的指标点1-1,毕业要求2中的指标点2-1. 2-2. 2-3,毕业要求4中的指标点4-3.1 .毕业要求1-3:具备将工程基础知识用于描述、求解物联网领域复杂工程问题的能力。2 .毕业要求2-1：具备对物联网领域复杂工程问题进行识别和有效分解的能力。3 .毕业要求2-2：能够针对物联网复杂工程问题中的模块或过程进行恰当表述，并建立合 适的数学模型。4 .毕业要求2-3：能够利用恰当条件，对物联网领域复杂工程问题进行分析和探讨，能意识到问题的关键环节。5.毕业要求4-3：理解离散结构、计算模型在物联网基础问题求解中的意义与基本运用。课程目标 毕业要求孤课程目标1.1课程目标1.2课程目标1.3课程目标2.3课程目标2.2课程目标2.3毕业要求1-3VVV毕业要求2-1VVVV毕业要求2-2VVVV毕业要求2-3VVV毕业要求4-3VVV二、课程内容与教学要求第一章绪论（一）课程内容1 .算法起源和算法的基本概念。2 .数据结构的基本概念，以及算法和数据结构之间的关系。3 .算法的时间复杂度和空间复杂度分析。（二）教学要求. 了解课程的性质、任务和目的。1 .掌握与数据结构有关的几个重要概念。2 . 了解算法设计的重要性。3 .对算法分析有初步了解。（三）重点与难点.重点与数据结构有关的几个重要概念：数据、数据元素、数据项；数据的逻辑结构和存储结构在 概念上的联系与区别；评价算法优劣的标准及方法。1 .难点算法与程序的区别；逻辑结构、存储结构的联系与区别；算法的时间复杂度分析方法。第二章线性表（-）课程内容1 . 了解线性表的逻辑结构。2 .掌握线性表在两种不同存储结构上各种操作的算法实现。3 .线性表的应用算法举例。（二）教学要求.掌握线性表的基本概念和特点。1 .熟练掌握对顺序表和单链表的常用操作方法及其算法实现。2 .掌握线性表的简单应用一一一元多项式的表示及相加运算（三）重点与难点1 .重点顺序表和链式表的基本操作。2 .难点链式表的基本操作以及一元多项式的相加运算。第三章栈和队列（一）课程内容1 .栈的定义和逻辑结构特征；理解在栈的顺序存储和链式存储上实现各种栈操作的算法。2 .队列的定义和逻辑结构特征；队列的顺序存储（循环队列）和链接存储表示及各种操作的实现算法；3 .栈的应用算法一一表达式求值。（二）教学要求.掌握栈和队列的定义。1 .熟练掌握两种结构在顺序和链接存储结构上各种操作的算法实现。2 .掌握表达式求值方法并了解其算法实现过程。（三）重点与难点.重点栈和队列的顺序存储表示、链式存储表示及基本操作的实现。1 .难点顺序栈的溢出判断条件；循环队列的队空、队满判断条件。第四章字符串和多维数组（一）课程内容1 .字符串的定义和存储，理解字符串模式匹配算法。2 .多维数组的定义和存储。3 .特殊矩阵的压缩存储和寻址方法。4 .字符串应用算法一一凯撒密码；数组应用算法一一幻方。（二）教学要求.熟悉串的定义、存储结构和操作。1 .掌握数组的定义及顺序存储结构。2 .掌握特殊矩阵和稀疏矩阵的定义以及各种存储结构。3 .掌握稀疏矩阵的转置方法并了解其算法。4 . 了解凯撒加密和幻方算法。（三）重点与难点.重点掌握数组的定义和数组的存储结构、特殊矩阵和稀疏矩阵的压缩存储。1 .难点稀疏矩阵的压缩存储表示下的矩阵运算的算法实现。第五章树和二叉树（-）课程内容1 .树的基本概念。2 .二叉树的逻辑结构、基本性质和遍历操作的定义。3 .二叉树的顺序、链式存储，以及链式存储上的遍历算法实现。4 .二叉树的非递归遍历算法。5 .树的存储结构，树、二叉树及森林之间的相互转换。6 .二叉树应用算法一一哈夫曼编码。（二）教学要求.掌握树的定义、存储结构以及树和森林的遍历算法。1 .熟练掌握二叉树的定义、性质、存储结构、各种遍历方法及其实现。2 .掌握树、二叉树及森林间的转换方法。3 .熟练掌握二叉树的应用一一哈夫曼树的构造算法，掌握哈夫曼树的应用。（三）重点与难点.重点二叉树的概念、遍历及基本操作，树的存储结构表示以及树、森林与二叉树的转换方法、树的 遍历方法，哈夫曼树及其应用。1 .难点利用二叉树的基本遍历操作实现其他复杂的运算。第六章图（一）课程内容1 .图的逻辑结构。2 .图的存储结构及实现；图的深度优先和广度优先遍历算法。3 .最小生成树算法。4 .最短路径算法。5 .拓扑排序算法。（二）教学要求.掌握图的定义和术语。1 .熟练掌握图的存储结构及深度和广度优先搜索方法及其实现。2 .掌握图的生成树的概念，熟练掌握求图的最小生成树的普里姆和克鲁斯卡尔方法，了解 其实现算法，并具有利用普里姆法和克鲁斯卡尔法构造图的最小生成树的能力。3 .掌握图的最短路径迪杰斯拉特方法，了解其实现算法，并具有构造单源点最短路径及其 长度的能力。4 .掌握拓扑排序的方法并了解其实现算法。（三）重点与难点.重点图的存储结构、深度和广度优先搜索方法及其实现、图的最小生成树的构造方法、图的最短路 径及其长度的求解方法、有向无环图的拓扑有序序列的构造方法。1 .难点最小生成树、最短路径的算法思想及其算法实现、拓扑排序的算法实现。第七章查找技术（-）课程内容1 .查找的基本概念。2 .线性表的查找：顺序表的查找、有序表的折半查找。3 .树表的查找：二叉排序树的定义，二叉排序树表上的查找、插入、删除算法的设计和实 现。4,散列查找：散列表、散列函数的基本概念，散列表的构造方法及散列查找算法。（二）教学要求. 了解查找的基本思想及查找成功和不成功的概念。1 .掌握在顺序表、有序表上的查找方法和算法，并能利用平均查找长度分析算法的性能。2 .熟练掌握二叉排序树的插入、查找方法及其算法实现，并具有对二叉排序树进行查找分 析的能力，了解二叉排序树的删除操作及其算法实现。3 . 了解平衡二叉树的基本概念。4 .熟练掌握散列表的构造方法，并具有对散列表进行查找和分析的能力。（三）重点与难点.重点顺序表的查找、二叉排序树的查找和插入以及查找性能的分析、散列表的构造方法以及查找性 能的分析。1 .难点二叉排序树删除操作的算法实现。第八章排序技术（一）课程内容1 .排序的基本概念。2 .以插入、交换、选择、归并和分配思想为基础的各种排序算法实现及分析。3 .上述各种排序算法的比较。（二）教学要求.理解排序的基本思想和基本概念。1 .理解并掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数 排序的基本思想、步骤、算法及时空效率分析。2 . 了解各种典型的内部排序算法的特点和适用范围。3 .理解稳定性的概念。（三）重点与难点.重点各种排序方法及时空效率分析。1 .难点快速排序、堆排序及其算法实现。三、本课程开设的实验项目编号实验项目名称学时类型要求支撑的课程目标1冒泡排序算法的改良2验证+设计型必做1.1, 1.2, 2.1, 2.22单链表的合并4设计型必做1.1, 1.2, 2.1, 2.2,3栈和队列的应用4设计型必做1.2, 2.1, 2.2, 2.34统计文本中单词个数4设计型必做1.2, 2.1, 2.2, 2.35二叉树的遍历算法4验证型必做1.1, 1.2, 2.1, 2.26图的遍历算法及应用6验证+设计型必做1.1, 1.2, 2.1, 2.27二叉排序树的查找性能4验证+设计型必做1.1, 1.2, 1.3, 2.1,2.28排序算法4验证型必做1.1, 1.2, 1.3, 2.1,2.2实验1：冒泡排序算法的改良1 .实验目的(1)熟悉用Visual C+进行程序设计的方法。(2)掌握用时间复杂度分析算法性能的方法。2 .实验要求本实验要求实现以下功能：(1)实现经典的冒泡排序算法。(2)从提前结束排序过程的角度出发，考虑对冒泡排序算法进行简单的改进。(3)对改进后的算法分析最好、最坏和一般情况下的时间复杂度。实验2：单链表的创建、合并和输出1 .实验目的(1)熟悉线性表的基本操作。(2)掌握单链表的创建、查找、插入和合并等运算。2 .实验要求本实验要求实现以下功能：(1)从键盘输入顺序任意的5个整数，按有序插入的要求生成第一个有序单链表，将该链表 输出显示。(2)再从键盘输入顺序任意的5个整数，按有序插入的要求生成第二个有序单链表，将该链 表输出显示。(3)将这两个有序单链表合并成一个有序单链表，要求使用两个单链表的原有空间进行合 并，将生成的有序单链表输出显示。实验3：栈和队列的应用1 .实验目的(1)理解栈和队列的结构特征和运算特征。(2)学会在实际问题背景下灵活运用栈和队列的特征。2 .实验要求本实验要求实现以下功能：(1)从键盘输入任意括号序列，编程判断括号是否匹配。假设允许有三种括号：圆括号()、 方括号| 和花括号 ,其嵌套的顺序随意。如：()口)或( )等为正确嵌套格式，() 或()为不正确的格式。(2)给出一个参数n,打印n层的杨辉三角。根据n-l层的数，计算出n层的数并将其打印 杨辉三角第n-l层产生第n层举例提示：给出133 11出队读取3 1和3相加入队贝I为33 143出队读取33和3相力口入队则为3 1463出队读取13和1相加入队则为1464此时1出对，说明n-l层读取完毕，输出第n层杨辉三角。实验4：统计文本中单词的个数.实验目的熟悉字符串的特征和基本操作。1 .实验要求本实验要求实现以下功能：(1)被处理文本的内容可以由键盘读入。(2)可以读取任意文本内容，包括英文和汉字。(3)设计算法，统计文本中的单词个数。(4)分析算法的时间性能。实验5：二叉树的遍历算法.实验目的(1)进一步掌握指针变量的使用。(2)掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。(3)掌握用指针类型描述、访问和处理二叉树的运算；.实验要求本实验要求实现以下功能：(1)按前序次序建立一颗二叉树，以表示空。(2)中序、后序遍历该二叉树，输出遍历序列。(3)求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。(4)试以栈为辅助存储结构实现二叉树的中序非递归算法或以队列为辅助存储结构实现二叉 树的层次遍历算法。说明：(3)、(4)选做一题。实验6：图的生成和遍历算法.实验目的(1)掌握图的基本存储方法一一邻接表和邻接矩阵。(2)掌握有关图的操作算法并用高级语言编程实现。