第1章算法设计序言.ppt

你在思考这些问题吗？为什么是课程？在课程中我们应该学什么？结构怎么样？Isithardtopasstheexams？IamnotgoodinMath。Mybackgroundisnotstrong。IcanreadlittleEnglish。没有问题，欢迎！课程介绍，课时：32学时，16种实验考试方法：考试成绩：20%期中考试10%平时70%期末教材：王晓东，算法设计与分析(第二版)，清华大学出版社；参考文献：1张德福，算法设计与分析，国防工业出版社；2MichaelT。古德里奇，算法分析与设计，人民邮电出版社。3Kleinberg等，算法导论，清华大学出版社，主要内容简介，第1章算法导论，第2章递归与分治策略，第3章动态规划，第4章贪婪算法，第5章回溯法，第6章NP完全性理论，课程信息，2009年，选修算法门课程的学生人数为：人，3336112人，期末考试学生人数为：79人，合格学生人数为：57人likemathoranalysisorlogic，pleasenottethatthecoursemaybeahighloadeyour .(thiscourseneedsyourtime)2 .Readthelecturenotescarefully，while willbemorehelpfolforyouthatteketches . 3 . makesuretathyoucansolvetheproblestopthighlinesinthecourse .1.1基本介绍，思考，什么是计算机，你为什么选择这个专业？计算机和普通机器有什么区别？我们需要电脑做什么？什么是计算机问题？计算机问题，计算机问题：Atasktobeperformedbycomputers(需要由计算机解决的任务)problems mathemathemathematic functionfrom mintsumingtomtchoutputs(一个数学函数输入到相应的输出)一个special inputmustallawayresultl tintsameoutputeventhimethefunctioniscompled(同一台输入计算机每次给出相同的输出)problemdefinitionshouldincludiculdeconstraintsontheresourcesthatmaibentamummedbuyeccessable解决方案(在定义问题时，您需要指定计算机可以使用的资源)，三个不同的计算机问题，决策问题(判断问题并回答是或否)，如：输入数是否大于60最优问题(优化问题，寻找最优解)，如：从a到b的最短路径是什么？例如，用计算机解方程或积分，这些问题属于数值计算中的算法。1.methodemarprocessfollowedtosolveproblemusingcomputer 2。takesheinputofprobleandtransformationsittooutput 3。什么是算法？算法属性，Mustbecorrect算法必须正确。composeddoferiesofconcretionstateeps包含一系列具体步骤。执行算法时，noambiguityastwishstepwisebepered next没有歧义。composedofafinineunemberofsteps只包含有限数量的步骤。必须终止。输入：有零个或多个外部量作为算法的输入。输出：该算法生成至少一个数量作为输出。确定性：构成算法的每一条指令都清晰明确。有限性：算法中每个指令的执行次数是有限的，执行每个指令的时间也是有限的。是满足以下属性的指令序列。算法：程序和算法。计算机程序是一种算法，它使用特定程序语言的特定表达式。一个Java程序和一个C程序可以做同样的事情。这两种语言表达相同的算法。计算机程序是为计算机准备的，而算法是为人们阅读准备的。将算法直接输入到计算机中的是algorithm scanbeexpressedypsedudocodes(伪代码)或justsomemshortpetstatatarieetoreadaptedunderstanding，总结了计算问题的算法设计、算法设计思想，选择了问题的数学模型初始状态、结束状态和已知条件下的状态关系从已知状态到结束状态的操作步骤形成算法。为了将两个操作层分开，使两者在设计上互不影响，两者之间的接口必须是抽象的。让底层通过接口为顶层服务，顶层通过接口调用底层操作。这个接口是抽象数据类型(ADT)，顶层操作步骤，底层操作步骤，自顶向下，数据模型层，数据结构层，通用算法设计方法，我不确定我是否能做到这一点。一系列活动，每个活动都有开始时间和结束时间。目标。找到最大的一组活动，使这两次活动的输入重叠。一系列活动，每个活动都有开始时间、结束时间和权重。找出一组权重最大的活动，这样这些活动的时间就不会重叠。时间，0，0，2，3，4，5，6，7，8，9，10，11，20，11，16，13，23，12，20，26，二部匹配问题，C，1，5，2，A，E，3，B，D，4，输入。二部图。目标。找到最多的一组边，这样没有两条边有一个公共顶点。最大独立集问题，6，2，5，1，7，3，4，输入。图表。目标。找出图中数量最大的一组点，这样组中的任意两点之间就没有边了。1.3算法的复杂性分析，一个故事，一个关于古印度希罕的故事记录在志贺莫夫写的算法中：希恩打算奖励西萨本达希尔，西萨本达希尔是“国际象棋”(真正的国际象棋后来进化而来)的发明者和贡品赠送者，总理。这位明智的部长似乎没有多大胃口。他跪在国王面前说：“陛下，请在棋盘的第一格给我一粒小麦。第二个细胞有两个颗粒，第三个细胞有四个颗粒。以这种速度，每个细胞将加倍前一个细胞。陛下，把棋盘上的64格麦粒都给你的仆人！”希恩听后非常生气，说：“你也瞧不起我们的国家印度。我给你一袋小麦。”，西萨班达伊尔坚持认为最好按要求放满。最后，每个人都带了很多袋小麦，只完成了一小部分的填充工作。只有那时，每个人才感觉到问题的严重性。有什么问题吗？ofwheat，algorithm complexity analysis，algorithm complex是算法运算所需的计算机资源量，所需的时间资源量称为时间复杂性，所需的空间资源量称为空间复杂性。这个数量应该只取决于算法要解决的问题的规模、算法的输入和算法本身的功能。如果N、I和A分别用来表示算法要解决的问题的规模、算法的输入和算法本身，而C用来表示复杂性，那么应该有C=F(N、I、A)。一般来说，时间复杂度和空间复杂度分别用T和S来表示，然后有：T=T(N，I)和S=S(N，I)。(通常，让A隐含在复杂性函数的名称中)，1.4算法的复杂性分析，主要问题：如何具体化复杂性函数？根据T(N，I)的概念，它应该是算法在抽象计算机上运行所需的时间。假设这个抽象计算机提供了k种元操作，它们被表示为O1，O2，好，假设每次执行这些元操作的时间是t1，tk。对于算法a，假设元运算Oi被统计使用的次数是ei=ei(N，I)。因此，对于1.4算法复杂度分析，最差情况时间复杂度：最佳情况时间复杂度：平均情况时间复杂度：其中DN是标度n的合法输入的集合；I*是DN中使T(N，I*)达到Tmax(N)的合法输入；是使T(N)达到Tmin(N)的合法输入；而P(I)是在算法的应用中输入I的概率。对于一个n输入的问题，给出了两种算法a和b。算法a运行100n步，算法b运行nlogn步。哪个算法好？即使它们都是多项式，它们也需要显示差异。如果算法a运行n2个100n步，算法b运行n2步。哪个算法好？很多时候我们认为n和n2之间的差别很大，而n和5n之间的差别很小，甚至可以被愚弄。如何表达这种差异？这个问题可以通过使用递进表达式来解决。复杂性的渐近行为：当N单调增加时，T(N