图论算法与模型67张课件

图论算法与模型56、极端的法规，就是极端的不公。——西塞罗57、法律一旦成为人们的需要，人们就不再配享受自由了。——毕达哥拉斯58、法律规定的惩罚不是为了私人的利益，而是为了公共的利益；一部分靠有害的强制，一部分靠榜样的效力。——格老秀斯59、假如没有法律他们会更快乐的话，那么法律作为一件无用之物自己就会消灭。——洛克60、人民的幸福是至高无个的法。——西塞罗图论算法与模型图论算法与模型56、极端的法规，就是极端的不公。——西塞罗57、法律一旦成为人们的需要，人们就不再配享受自由了。——毕达哥拉斯58、法律规定的惩罚不是为了私人的利益，而是为了公共的利益；一部分靠有害的强制，一部分靠榜样的效力。——格老秀斯59、假如没有法律他们会更快乐的话，那么法律作为一件无用之物自己就会消灭。——洛克60、人民的幸福是至高无个的法。——西塞罗图论算法与模型刘汝佳SSSP给加权图和一个起点s,求s到所有点的最短路(边权和最小的路径)·最短路有环吗正环:何必呢,删除环则得到更短路负环:无最短路,因为可以沿负环兜圈子分组协作学习模式，对于中职计算机教学而言，既是一种高效的学习方法，又是一种先进的班级管理手段。一个教师管理几十个学生难免顾此失彼，尤其是中职计算机专业实践内容较多，有时学生同时上机练习，教师不可能对每个人都观察到、指点到、评价到。采取分组协作模式，根据学生之间的差异，将其科学分组，然后给每个小组布置一个工作任务，要求他们通过协作共同完成，既可以让他们之间的差异形成互补，又可以通过这种竞争机制，激发他们的动力，教师还可以节省出时间对学生进行客观评价，从而为他们量身制订更为高效的学习计划，使每个学生的提高成为现实。本文结合教学实例，对分组协作的具体应用进行了详细阐述。一、分组协作的前提是科学的“分”分组是一门学问，很多教师并不注重分组的科学性，导致分组协作学习模式效率不高。分组之前，教师要对班内学生有一个初步了解，分析学生的基本水平、认知能力、性格特点等综合因素，对学生进行科学分组。小组学生人数可根据学习内容的难度不同合理设置，如简单的“word”板报制作人数不宜太多，一般两到三人即可；而针对制作多层网页，就应该安排七到九人左右。小组内成员水平应均衡，优、平、劣比例适当，可以形成以优带劣的学习局面；成员性格之间尽量做到互补，这样那些较内向不擅发言的学生会被积极的、活泼的学生带动起来。每个组都应有一个组织、管理、协调能力较强的人做组长，便于组内管理，确保学习更有效率。二、分组协作的保障是积极的“合”科学分组之后，就是如何指导和引导小组内成员之间进行协作。青少年在这个时期容易暴露出独立、自我的性格倾向，大多数人既不具备合作意识，又缺乏合作能力，并不知道怎样与他人合作。合作是一种自我意识，教师可以“任务驱动”的形式，即将学习内容根据组间差异分解成为若干个任务，分派到各组让他们自行解决。学生可以提前预习，也可以课下讨论，不限制他们学习的方法与形式，只要最终完成任务，并在课上进行任务过程与任务成果的展示即可。在任务完成过程中，学生可以寻求教师的帮助，也可以邀请教师参与他们的过程。这种通过外界适当的压力“催化”学生合作意识的产生，能够让他们为了某个目标而主动团结起来，寻求和接受他人的帮助，并伴随任务难度的升级开始尝试更多的协作办法。事实证明，只有让合作成为一种自发行为，才能真正发挥其作用。本文以“个性化网站制作”一课为例，对分组协作的具体应用进行了详细阐述。1.分组个性化网站制作是适合具有一定计算机基础知识的中职高年级学生开展的活动，学生对此非常感兴趣，希望能够制作出不一样的个性化网站进行展示。但是个性化的标准不好判定，所以教师为了分组科学，提供了一些网站链接，在课上供学生欣赏，然后大家简单交流一下意见，如认为哪家网站不错，理由是什么，然后对学生的兴趣、爱好，以及对网站制作的了解程度进行摸底，随后五人一组进行分组，组长的人选由小组成员投票指定。2.准备先在课上给学生预留出部分时间，让他们上网搜索、了解网站建设的所需元素，通过组内讨论，找三个他们认为最满意的网站，选出一名代表进行总结发言，说出满意的理由，并在课上确定各个小组个性化网站主题。为了激发学生的创造热情，培养他们筛选、搜集素材的能力，为接下来的素材做好准备，教师可以指导每个小组先建立一个电子学档，统一存在教师指定路径下。各建一个专用文件夹，文件夹里要有一份包括网站主题、设计背景、内容简介、成员分工、制作进度等内容的计划书；一个存放图片、动画、文字、声音等素材的资料分类文件和一个存放网页文件的网站文件夹。同时，教师可以为学生准备扫描仪、动画制作工具等，最大限度地为学生提供帮助，为他们完成任务增强信心。3.过程为学生限定一个完成时间，然后让每个小组各自完成。在这个过程中，教师为学生提供多种学习工具和学习指南，关注各小组的进展情况，及时给予帮助。活动过程以小组分散活动为主，集中讨论为辅，对于一些普遍存在的共性问题，随时召开集中会议进行讨论解决。教师要通过对各个小组内学生的学习态度、合作能力、组织实施能力等方面的观察，对每个学生进行初步评价。4.展示与评价集中对小组作品进行展示。小组内选出代表进行发言，对本组个性化网站进行现场展示，重点对网站建设过程中的“亮点”进行介绍。展示完毕后各个小组开始打分，选出分数最高的为最优秀作品，发布到校园公共网站上。最后教师通过“学生任务完成评价量规”表，对学生在整个任务完成过程中作品的思想与内容、网站建设与组织、主题表达及技术方面进行综合评价。每个教育者都期望自己的学生能有所提高，但即便是处在同一水平的不同学生，在学习过程中也会出现提升有高低、进步有快慢的现象。所以需要教育者找到存在于个体之间的差异，通过科学分组，合理引导，让每个个体之间通过协作形成互补，从而实现高效率的学习。“兴趣是最好的老师”。心理学实验证明，人在有兴趣时会使血液循环亢奋起来，会把观察、记忆、想象等多种心理活动调动起来，呈现出积极的活跃状态。一个人做他感兴趣的事，他的全部才能可发挥80％以上，而不感兴趣的只能发挥20％左右。可见，最好地调动学生学习积极性的方法，莫过于激发学生对所学材料有浓厚兴趣。“激趣教法”就是在教学的各个环节中，注意培养，激发学生的学习兴趣，调动学习的积极性，变过去的教师主宰教材灌输知识为现在的教师引导学生凭借教材学习。在教学过程中，设置有趣的问题或采用激励的方法，使学生带着一种高涨的激动的情绪从事学习和思考，在欢愉的环境中获得知识。兴趣如此重要，那么在初中语文课堂教学中如何激发培养学生的学习兴趣呢?一、习旧引新，激发“学”趣根据语文教材富有连续性的特点，在教学中，对前后知识性联系密切的课文，特别是同单元的课文，教师应注重挖掘课文间的内在联系，选用复习，巩固已学知识引入新课，激发学生学习新知识的兴趣，如《白杨》一文在揭题前，先提问复习已学过的《青松》这首借物喻人的诗歌，让学生进一步明确诗歌表面是描写青松具有抗争恶劣环境，顽强旺盛的生命力，而实际是借青松来歌颂不怕困难险阻的中国人民，再顺当地点明又要新学借物喻人的散文《白杨》。通过具体介绍白杨树的特点。引导学生认识白杨与青松的共性和都可借物喻人的特征。如此导题，既复习巩固已学知识，又激发学生学习新课兴趣，便利学生更快更好地学习掌握新课的内容。二、课堂主旋律要引人入胜(一)一线串珠，倒析因果。对《荔枝蜜》一文教读时，提出开头“我一向不大喜欢蜜蜂”和结尾“梦见自己变成一只小蜜蜂”，这前后岂不是矛盾的吗?我为什么会变成一只小蜜蜂呢?这篇课文的最后结果当作问题的开头提出，分析因果，让学生深入探微，更好的感知课文中作者思想感情的变化，学生理清线索，就会感受到一线串珠的妙处。(二)巧用插图，奇思妙想。教学《天上的街市》时，先让学生认真朗读，品味诗的意境和韵味，再让学生深入体会作者希望超脱现实、去憧憬美好的生活的愿望，让学生的联想和想象沿着诗句徐徐展开，这时教师抓住时机，充分利用文中的插图，指导学生自由的发挥联想和想象。由此及彼，扩大时空范围，拓宽思路，开掘深度，学生在创造性的想象中闪现出智慧的光芒。(三)辩论观点，抛砖引玉。许多课文都存在不同的观点和见解，并且答案是丰富多彩的。教师要善于利用这些课文的特点，组织全班进行讨论后，展开辩论。在讲授《杨修之死》时，关于杨修之死有两种意见，第一种是杨修恃才放旷，终于招致杀身之祸；第二种是曹操借违反军纪之名将杨修处死，以消除隐患。学生对这两种观点互相辩论，引经据典，旁征博引，各抒己见，引出了《三国演义》、《三国志》及历来对曹操的评论和曹操的其他言行来分析杨修之死的前因后果。借此调动学生对名著《三国演义》、《三国志》的兴趣，丰富了同学们的文学常识和历史知识，锻炼了学生的语言表达能力，培养了学生的思维能力。(四)课堂竞赛，丰富多彩。上好语文活动课，要注重培养学生的良好行为习惯，积极开拓学生的视野。教师为活跃课堂氛围，以力求创新的教学目标为基点，努力营造一种竞争的氛围，开展竞赛活动。如举办全班写字比赛，看谁写得好；查字典比赛，看谁查得快；举办词语(包括同义词、反义词、格言、谚语、歇后语等)比赛，看谁积累的多：开展古诗词鉴赏、讲故事或典故、介绍报刊时文或现代新闻、讨论社会热点问题、评析学生实际生活中遇到的场景等竞赛，看谁说得好。学生从这里得到的认识是感性的、具体的，但正是这些感性的事实，让学生更易于接受融会其中的道德和观念，从中学会读书做人的道理。(五)巧变结局，另辟蹊径。在讲析《我的叔叔于勒》一文的结局时，我打破常规，变换角度，设想此时卖牡蛎的不是于勒，真正的于勒也在这只船上，安排菲利普夫妇与发财后的于勒在船上相见时的情景会怎样?为此布置学生写一篇短文，对菲利普夫妇见到发财后的于勒进行神态、言行的描述。这种打破常规，比较容易引发超常逆向思维的效应，常会收到意想不到的效果。三、多媒体教学，直观激趣多媒体进课堂，已是当前教学活动的一项很重要的形式。它以有趣的音乐、图像、颜色、画面、动作等强有力地吸引着学生。教师结合课文内容，把幻灯片、录像片、教学光盘等教学手段穿插到教学活动中来，使学生兴趣浓厚。如《苏州园林》一课介绍了江南第宅园林建筑的风貌。我们的学生基本上没有去过苏州园林。在学习这一课时，我让学生先观看录像(课件)，再闭上眼睛，想象苏州园林的总体特征以及局部的特点，然后让学生默读课文中的介绍，最后说出各自的收获。让学生在这样的情景中去学习，使他们如闻其声，如见其形，如临其境。如果我们在教学中根据课文内容利用多媒体设备创设出浓郁的情境，就能使学生不由自主地调动多种情绪，积极主动地跟随老师进行课堂活动，求知欲会更强，效果会更好。综上所述，兴趣虽然属于非智力因素，却是学好语文的先决条件。因此，激发学生浓厚的学习兴趣，调动学生学习的主动性和积极性，是提高语文教学质量不可忽视的问题。一旦学生的兴趣激发出来，语文教学就会达到事半功倍之效。激趣教法的目的是为了提高教学效果，当然就必须避免走向极端，一味的讲究情趣，无目的的鼓励。我们在教学过程中，激趣教法必须与掌握知识、发展智能、提高写作紧密结合起来，以达到作文教学的最优化，使学生学得既轻松又有激情。图论算法与模型56、极端的法规，就是极端的不公。——西塞罗图1图论算法与模型刘汝佳图论算法与模型2SSSP给加权图和一个起点s,求s到所有点的最短路(边权和最小的路径)·最短路有环吗正环:何必呢,删除环则得到更短路负环:无最短路,因为可以沿负环兜圈子SSSP3最优性原理最优性原理:若最短路u→V经过中间结点W,则u→w和w→V的路径分别是u到w和w到v的最短路.·意义:贪心、动态规划Hfs→a→b→c→d→andsax→y→d-uarebothshortestpathsthens→a→b→c→d→uisalsoashortestpath最优性原理4最短路的表示最短路的表示s到所有点的最短路不需要分别表示最短路树:到每个点都沿着树上的唯一路径走实际代码:记录每个点的父养pred[u即可输出最短路:从终点沿着pred[u]递推回起点x最短路的表示5为什么单源最短路形成树?考虑下图·如果u→z的路只取一条即可为什么单源最短路形成树?6最短路树和最小生成树最短路树和最小生成树7般SSSP算法临时最短路存在此路,即真实的最短路长度不大于此路长度但是有可能有更短的,所以此路长度只是一个上界给定起点s,对于每个顶点v,定义dist)为临时最短路树中s->V的长度pred(ⅵ)为临时最短路树中s->v中v的前驱初始化:dist(S)=0,pred(s)=NULL,初始化:所有其他dist(v)为无穷,pred(v)=NULLdist(v)称为点v的标号(abel),它是最短路的上界·基本想法:让标号不断趋近,最终达到最短路般SSSP算法8般SSSP算法什么样的标号明显可以改进(趋近最短路)?条边(uv)被称为紧的(tense),如果dist(u)+w(u,v<dist(v)可以松弛:dist(v)=dist(u)+W(u,v),pred(v)=uRELAXI,w)RELAN(∥,V,w)结论(b)存在紧的边,一定没有正确的求出最短路树不存在紧的边,一定正确的求出最短路树般SSSP算法9般SSSP算法的正确性(u,v)被称为紧的:dist(u)+W(u,v)<dst(v)·不存在紧边,一定求出最短路树即由pred表示出的路径上所有边权和等于dist(v)(归纳于松弛的次数)结束时对s到v的任意路s→V,dist)<=W(s→)归纳于s→v所含边数,假设s→u-(u=pred)dstu)<=W(→u),两边加W(uy)得:dist(u)+W(u,v)<=W(s→V)。因为无紧边,所以dist(v)<=dist(u)+w(u,v<=W(s>v)般SSSP算法的正确性10般SSSP算法的结東条件·刚才已经证明结束时dist(v)和pred(v)相容若算法结束,则结果正确·算法何时能结束呢?含负圈(能到达的),则永不结束,因为在次松弛以后,负圈上一定有紧边(反证)不含负圈,则一定结束,因为要么减少一个无穷dist值,要么让所有有限dist值之和至少减少个“不太小的正值”。般SSSP算法的结東条件11图论算法与模型67张课件12图论算法与模型67张课件13图论算法与模型67张课件14图论算法与模型67张课件15图论算法与模型67张课件16图论算法与模型67张课件17图论算法与模型67张课件18图论算法与模型67张课件19图论算法与模型67张课件20图论算法与模型67张课件21图论算法与模型67张课件22图论算法与模型67张课件23图论算法与模型67张课件24图论算法与模型67张课件25图论算法与模型67张课件26图论算法与模型67张课件27图论算法与模型67张课件28图论算法与模型67张课件29图论算法与模型67张课件30图论算法与模型67张课件31图论算法与模型67张课件32图论算法与模型67张