从程序设计到算法设计.pptx

相关课程教学中的几点经验,3,ACM/IEEE-CS计算机科学课程体系2013,1,从程序设计到算法设计的课程体系,2,数据结构课程教学方法及在线教学平台,4,内 容 提 要,ACM/IEEE-CS计算机科学课程体系2013,1,Curriculum 68CC 2001 CS 2008 CS 2013,中国计算机学会和全国高校计算机教育研究会也组成研究组：CCC2006,AL Algorithms and Complexity AR Architecture and Organization CN Computational Science DS Discrete Structures GV Graphics and Visual Computing HC Human-Computer Interaction IAS Information Assurance and SecurityIM Information Management IS Intelligent Systems NC Networking and CommunicationsOS Operating Systems PBD Platform-based DevelopmentPD Parallel and Distributed ComputingPL Programming Languages SDF Software Development Fundamentals SE Software Engineering SF System Fundamentals SP Social and Professional Issues,18个知识领域,1.1,计算机科学分支学科的知识领域,It is naturally tempting to associate each Knowledge Area with a course.We explicitly discourage this practice in general,even though many curricula will have some courses containing material from only one Knowledge Area or,conversely,all the material from one Knowledge Area in one course.We view the hierarchical structure of the Body of Knowledge as a useful way to group related information,not as a stricture for organizing material into courses.,很自然每一个知识领域都与一门课程相关联。一门课程可以包含一个知识领域的部分内容或全部内容。但我们认为，将相关的信息组织成知识体层次结构是十分有用的，而不是狭窄地将内容组织进课程中。,提示：,计算机科学分支学科的知识单元,程序设计导论面向对象的程序设计高级语言程序设计,1.2,算法设计与分析数据结构,知识领域的重要性,1.3,涵盖的学校类型,社区大学,学院,教学型大学,研究型大学,1.4,程序设计语言,算法设计与分析,数据结构,从程序设计到算法设计的课程体系,2,进阶,进阶,程序设计,数据结构,算法设计与分析,注重变量定义,注重数据组织,注重控制流程,注重数据处理方法,强调程序设计,强调“好程序”的设计,程序设计,数据结构,2.1,数据结构和程序设计课程的侧重点,掌握各种常用的数据结构,掌握各种常用的求解策略,数据结构,算法设计与分析,2.2,数据结构和算法设计与分析课程的侧重点,相关课程教学中的几点经验,高级语言程序设计,3,数 据 结 构,算法设计与分析,3.1,3.2,3.3,高级语言程序设计,定义变量：使用内存（纸张）运算符：使用CPU（笔）,程序（大脑）,3.1.1 计算机语言工具化的理念,3.1,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,示例：机器人环境,3.1.2 计算机语言提供的核心元素,提供的指令,Init(x,y)：初始位置Up：上移一个位置down：下移一个位置Left：左移一个位置Down：右移一个位置Over:是否超界End：结束,控制语句,顺序语句：串行执行（冯诺依曼体系结构）条件语句：if/switch循环语句：while、do-while、for,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,为什么需要条件语句？,Init(2,7);,Right;,Right;,超界,条件语句,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,编程：从(2，2)移动到(7，6),Init(2,2);,程序1,Left;,Left;,Left;,Left;,Down;,Down;,Down;,Down;,Down;,End;,任务完成,循环语句,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,Init(2,2);,程序2,for(i=1 To 4)Left;,for(i=1 To 5 Down;,End;,任务完成,为什么要使用循环语句？,数学思路是人求解问题的过程，而程序设计思路是人指挥计算机求解问题的过程。前者是人求解问题的方式，后者是计算机求解问题的方式。由于计算机的运行速度快，特别适合于求解简单重复的问题。所以将数学思路转换成设计程序思路时要充分利用这一特点，从问题求解中提炼出重复的步骤，用计算机语言中的循环语句加以实现。,3.1.3 数学思路和程序设计思路的关系,数学思维,计算思维,示例：从5位同学中选派4位同学在星期五、星期六、星期天参加公益活动，每人一天，要求星期五有2人参数，星期六、星期天各有1人参加，则不同的选派方法共有多少种？,从5人中选派4位同学有 种，再从选出的4人中选2人星期五劳动有 种，其余2人在星期六、星期天劳动有 种，所以总共有=60种。,数学思路求解：,程序设计思路求解：,为了统计所有不同的选派的情况，用week数组统计每天安排参加公益活动的人数，week0表示星期五的人数、week1表示星期六的人数、week2表示星期天的人数，week3表示不参加公益活动的人数。week0week3的初始值均为0。设5人分别安排公益活动的星期号为ae，显然，0ae3。当某人参加某星期号（编号i，0i3，i=3时表示不参加任何公益活动）的公益活动时，weeki增1。,void main()int week4=0;int a,b,c,d,e,count=0;for(a=0;a=3;a+)weeka+;for(b=0;b=3;b+)weekb+;for(c=0;c=3;c+)weekc+;for(d=0;d=3;d+)满足条件 weekd+;for(e=0;e=3;e+)weeke+;if(week0=2,线性化编程,指令1指令2指令n,3.1.4 程序设计基本方法,变量定义变量运算变量的输入和输出,知识点：,一个工业流程,一个模块,输出,输入,参数类型（输入型参数和输出型参数）从模块输入到输出的运算。,知识点：,模块,模块化编程,模块,模块的划分模块之间的关系,知识点：,模块1,模块2,模块3,结构化编程,3.1.5 程序设计涵盖计算机科学的各个分支,用户界面,数据处理,数据文件,可视化设计（窗体、网页）,算法设计（基本算法、网络、编译等）,DBMS,应用程序,应用程序的基本结构,3.2.1 为什么学习数据结构课程：数据是有结构的,引子：万事万物都是有结构的。,微观世界DNA结构,数 据 结 构,3.2,宏观世界建筑物的结构,知识结构平面几何的5条公理,公理1：从任意的一个点到另外一个点作一条直线是可能的。公理2：把有限的直线不断循直线延长是可能的。公理3：以任一点为圆心和任一距离为半径作一圆是可能的。公理4：所有的直角都相等。公理5：如果一直线与两线相交，且同侧所交两内角之和小于两直角，则两直线无限延长后必相交于该侧的一点。,欧几里德的几何原本,公理1,平面几何知识体系,公理2,公理3,公理4,公理5,平面几何知识体系结构,公理5又称之为平行公理，这个公理衍生出“三角形内角和等于180度”的定理。在高斯（F.Gauss,1777年1855年）的时代，公理5就备受质疑，俄罗斯数学家罗巴切夫斯基、匈牙利人波约阐明公理5只是公理系统的一种可能选择，并非必然的几何真理，也就是“三角形内角和不一定等于180”，从而发现非欧几里得的几何学，即“非欧几何”。,如微分几何在现代测量学等领域应用广泛,公理1,微分几何知识体系,公理2,公理3,公理4,公理5,微分几何知识体系结构,数据结构的观点：,逻辑结构,存储结构,操作功能实现,用户视角,线性结构树形结构图形结构,数据的逻辑结构类型,数据,基本的数据处理算法,3.2.2 数据处理是有方法的：提炼通用方法,方法是旧的，问题是新的。,教学中，突出通用方法的讲解！培养学生归纳的思想。,模块化,求递归模型的步骤：（1）对原问题f(s)进行分析，称为“大问题”，假设出合理的“小问题”f(s)（与数学归纳法中假设n=k-1时等式成立相似）；（2）假设f(s)是可解的,在此基础上确定f(s)的解，即给出f(s)与f(s)之间的关系（与数学归纳法中求证n=k时等式成立的过程相似）；（3）确定一个特定情况（如f(1)或f(0)）的解,由此作为递归出口（与数学归纳法中求证n=1时等式成立相似）。,递归模型 递归算法,递归算法设计,递归算法的核心是数据和数据处理的递归性。,数据：D=瓜的集合运算：Op=种瓜递归性：Op(D)D,第一年种瓜,递归：无处不在。,实例1：家谱,实例2：行政区划分,示例：设计不带头结点的单链表的相关递归算法。,a1,a2,an,.,L,f(L)：大问题,f(L-next)：小问题,把“大问题”转化为若干个相似的“小问题”来求解。为什么在这里设计单链表的递归算法时不带头结点？,求单链表中数据结点个数。,f(L),f(L-next),设f(L)为单链表中数据结点个数。,空单链表的数据结点个数为0,f(L)=0 当L=NULL,对于非空单链表：,=,+1,求单链表中数据结点个数递归算法如下：,int count(Node*L)if(L=NULL)return 0;else return count(L-next)+1;,当f(b-lchild)和f(b-rchild)可解时，f(b)就很容易求解了。,二叉树算法设计,示例：假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有叶子结点个数。,设f(b)为二叉树b中叶子结点个数。,空二叉树中叶子结点个数为0,f(b)=0 若b=NULL,f(b)=1 若*b为叶子结点,f(b),=,f(b-lchild),+f(b-rchild),int LeafNodes(BTNode*b)int num1,num2;if(b=NULL)return 0;else if(b-lchild=NULL,递归算法如下：,示例：假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有单分支结点个数。,f(b)=0 若b=NULLf(b)=f(b-lchild)+f(b-rchild)+1 若*b为单分支结点f(b)=f(b-lchild)+f(b-rchild)其他情况,设f(b)为二叉树b中单分支结点个数。递归模型f(b)如下：,int SSonNodes(BTNode*b)if(b=NULL)return 0;else if(b-lchild!=NULL,递归算法如下：,图算法设计,图算法,深度优先遍历,广度优先遍历,示例：假设图G采用邻接表存储，设计一个算法，判断顶点u到v是否有简单路径。,基于深度优先遍历算法的应用,从顶点u开始进行深度优先搜索，当搜索到顶点v时表明从顶点u到顶点v有路径，即：,用形参has（调用时其初值置为false）表示顶点uv是否有路径。,u,u1,u2,v,void ExistPath(AGraph*G,int u,int v,bool/p指向顶点u的下一个相邻点,示例：假设图G采用邻接表存储，设计一个算法输出图G中从顶点u到v的一条简单路径（假设图G中从顶点u到v至少有一条简单路径）。,采用深度优先遍历的方法。为此在深度优先遍历算法的基础上增加path和d形参，其中path存放顶点u到v的路径，d表示path中的路径长度，其初值为-1。当从顶点u遍历到顶点v后，输出path并返回。,DFS(G,u,v,path,d),输出path并返回,void FindaPath(AGraph*G,int u,int v,int path,int d)/d表示path中的路径长度，初始为-1 int w,i;ArcNode*p;visitedu=1;d+;pathd=u;/路径长度d增1，顶点u加入到路径中 if(u=v)/找到一条路径后输出并返回 printf(一条简单路径为:);for(i=0;iadjlistu.firstarc;/p指向顶点u的第一个相邻点 while(p!=NULL)w=p-adjvex;/相邻点的编号为w if(visitedw=0)FindaPath(G,w,v,path,d);p=p-nextarc;/p指向顶点u的下一个相邻点,示例：假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。,利用回溯的深度优先搜索方法。从顶点u开始进行深度优先搜索，在搜索过程中，需要把当前的搜索线路记录下来。为此设立一个数组path保存走过的路径，用d记录走过的路径长度。若当前扫描到的顶点u等于v时，表示找到了一条路径，则输出路径path。,DFS(G,u,v,path,d),回溯所有路径后结束,void FindPath(AGraph*G,int u,int v,int path,int d)/d表示path中的路径长度，初始为-1int w,i;ArcNode*p;d+;pathd=u;/路径长度d增1，顶点u加入到路径中visitedu=1;/置已访问标记if(u=v,恢复环境,使该顶点可重新使用,从1到4的所有路径:1 2 4 1 2 3 4 1 0 3 4 1 0 3 2 4,1,3,2,4,0,程序执行结果如下：,基于广度优先遍历算法的应用,u,一圈一圈向外走。,BFS思路：,v,以u到v的最短路径构成分层,示例：假设图G采用邻接表存储，设计一个算法，求不带权无向连通图G中从顶点u到顶点v的一条最短路径（路径上经过的顶点数最少）。,最好采用广度优先遍历来实现。,typedef struct int data;/顶点编号 int parent;/前一个顶点的位置 QUERE;/非循环队列类型,void ShortPath(ALGraph*G,int u,int v)/输出从顶点u到顶点v的最短逆路径 ArcNode*p;int w,i;QUERE quMAXV;/非循环队列 int front=-1,rear=-1;/队列的头、尾指针 int visitedMAXV;for(i=0;in;i+)/访问标记置初值0 visitedi=0;rear+;/顶点u进队 qurear.data=u;qurear.parent=-1;visitedu=1;,while(front!=rear)/队不空循环 front+;/出队顶点w w=qufront.data;if(w=v)/找到v时输出路径之逆并退出 i=front;/通过队列输出逆路径 while(qui.parent!=-1)printf(%2d,qui.data);i=qui.parent;printf(%2dn,qui.data);break;p=G-adjlistw.firstarc;/找w的第一个邻接点while(p!=NULL)if(visitedp-adjvex=0)visitedp-adjvex=1;rear+;/将w的未访问过的邻接点进队 qurear.data=p-adjvex;qurear.parent=front;p=p-nextarc;/找w的下一个邻接点,两种遍历算法的差别,1,3,2,4,0,0,1,3,2,4,以u到v的最短路径构成分层,深度优先遍历可能找到的一条路径：,1,3,2,4,0,0,1,3,2,4,路径：0 1 2 4,路径上的顶点可能在同一层,1,2,0,1,3,2,4,广度优先遍历找到的路径同一层只能有一个顶点。,逆路径：4 3 0,深度优先遍历能找所有路径，而广度优先遍历难以实现。,3.2.3 数据结构算法的多维性,同一问题的多种解法。,迷宫问题,示例:,各种求解方法的特点和差别,顺序查找算法,二分查找算法,利用了数据的有序性,示例1,3.2.4 数据结构经典算法的启示,串简单匹配算法,串KMP匹配算法,利用子串中部分匹配特性,示例2,简单选择排序算法,堆选择排序算法,利用了连续多次查找最大记录的特性,示例3,用Dijkstra求所有顶点之间的最短路径,Floyd算法,共享前面路径比较所得到的信息,示例4,找路径：AB,膨胀所有物体。,机器人路径规划问题,3.2.5“小算法”解决“大问题”,将路径搜索转换为图的顶点搜索。再可采用图遍历算法。,GIS求最短路径问题,ADT 逻辑结构抽象运算（功能描述）,3.2.6 数据结构解决问题的思路,基本算法策略,穷举法（枚举法、暴力法或蛮力法）,分治法,贪心法,动态规划,回溯法,分支限界法,许多算法都可以采用递归实现,算法设计与分析,3.3,3.3.1 求解问题的算法策略,示例：TSP问题（Travelling Salesman Problem）又称为旅行推销员问题、货郎担问题。,一个示意图,路径长度:23,顶点0顶点0并通过所有顶点的路径：,0,1,2,3,5,8,6,8,5,8,5,7,36,7,9,8,比较求出最短路径为：02310,路径1：01230：28,路径2：01320：29,路径3：02130：26,路径4：02310：23,路径5：03210：59,路径6：03120：59,时间复杂度为O(nn!),穷举法求解TSP问题,fk(i，V),假设从顶点s出发，最后回到出发点s的最短路径长度：,出发顶点i,经过的顶点集V,顶点集V中顶点数,动态规划求解TSP问题,顶点0顶点0,求出最短路径为：02310,时间复杂度为O(nn!),设f(i,V)表示从顶点i出发经过V（它是一个顶点的集合）中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。,回溯法求解TSP问题,f(3,)23：28,f(2,)32：29,f(2,3)12：16,f(3,2)13：13,顶点0顶点0,f(3,)13：26,f(1,)31：23,f(1,3)21：14,f(3,1)23：10,f(1,2,3)01：8,f(2,1,3)02：5,求出最短路径为：02310,时间复杂度为O(nn!),设f(i,V)表示从顶点i出发经过V（它是一个顶点的集合）中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。,分枝限界法求解TSP问题,f(3,)23：28,f(2,)32：29,f(2,3)12：16,f(3,2)13：13,顶点0顶点0,f(3,)13：26,f(1,)31：23,f(1,3)21：14,f(3,1)23：10,f(1,2,3)01：8,f(2,1,3)02：5,f(3,1,2)03：36,剪枝,求出最短路径为：02310,时间复杂度为O(nn!),采用最近邻点策略，即从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。,局部最优策略,贪心法求解TSP问题,顶点0顶点0,0,求出最短路径为：02310,时间复杂度为O(n2),实际上TSP问题不满足贪心法的最优子结构性质，所以采用贪心法不一定得到最优解，但可以采用合理的贪心策略。,局部最优 全局最优,=,?,贪心法需要证明具有贪心选择性质和最优子结构性质。,3.3.2 求解问题算法设计的基本步骤,分析求解问题,选择数据结构和算法设计策略,描述算法,算法正确性证明,算法分析,清华大学出版社全力打造的教学平台,数据结构课程教学方法及在线教学平台,4,“十二五”普通高等教育本科国家级规划教材,总 览,特 色：,完整的电子教材：包含PPT、讲课视频、知识点动画演示、教学大纲、教学指南和教学参考。丰富的学习训练：包含各类练习题的题库，并予以细致深入的解析和完整的解答。灵活的互动平台：包含师生和学生之间的问题与讨论，问题的疑难解析。全方位的教学管理：包含班级管理、作业管理、测试管理和成绩管理。,告,小,广,算法设计与分析（6月份出版）,