文档介绍：*计算机算法基础华中科技大学计算机学院韩建军******@***刃枉毖蔬舒祸逃氢伍庭计算机算法基础1计算机算法基础1*序专业基础课程:数据结构、计算机语言操作系统、编译如何编写计算机程序:数据结构+算法=程序算法:计算机软件的“灵魂”算法是计算机科学和计算机应用的核心直涤谍柑九殴渴派骨诀袜跳靶吮汤疡郧率境夕淮缓涪暮庄铝宽蓟鲁能沪亭计算机算法基础1计算机算法基础1*教材:计算机算法基础余祥宣等编著华中科技大学出版社参考书:算法设计与分析王晓东编著清华大学出版社计算机算法导引——设计与分析卢开澄编著清华大学出版社IntroductionToAlgorithm高教出版社,MITPress学时:36+4学时培近砖播删捎可獭灼吩酉芦幢装水味赂驮视霍雌抬疯樱卵神掖单付翼大肯计算机算法基础1计算机算法基础1*章节安排第一章导引与基本数据结构√第二章分治法 √第三章贪心方法 √第四章动态规划√第五章检索与周游√第六章回溯法⊙第七章分枝-限界⊙第八章NP-问题?牌钞瘫剿导料吓樟畸贪啮靖脆绞饰戏暗抨绥冀凡拓无喉家寞兜踪鳖保阳陷计算机算法基础1计算机算法基础1*?★算法如数字、计算一样,是一个基本概念。★算法是解一确定类问题的任意一种特殊的方法。★在计算机科学中,算法是使用计算机解一类问题的精确、有效方法的代名词;算法是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。某抡耶视汕志烽盟酪诞舟察辊宛碳录卡仓蜂织引蔫灌梁阶染屋唆颠禁理辛计算机算法基础1计算机算法基础1*、能行性、输入、输出、有穷性1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。例:不符合确定性的运算5/0将6或7与x相加未赋值变量参与运算锗元琐衡讫稽唇普镣沫石喷坎烈魁违动姓温粕槛烷句物抽镍坚穗当诵面钾计算机算法基础1计算机算法基础1*2)能行性算法中有待实现的运算都是基本的运算,原理上每种运算都能由人用纸和笔在“有限”的时间内完成。例:整数的算术运算是“能行”的实数的算术运算是“不能行”的狗喧谩些缨戌篱酷蕾邻骂臀茫磷师种券努皂京秩狈银柯息丑尖辞目率嵌溜计算机算法基础1计算机算法基础1*3)输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域)4)输出一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。锤蹈购呜沽丧舷日骚宪支忽杯蓉谨逆撞篡檄笛剐甥钵娶眺醒领姚椎俯时箍计算机算法基础1计算机算法基础1*5)有穷性一个算法总是在执行了有穷步的运算之后终止。计算过程:只满足确定性、能行性、输入、输出四个特性的一组规则。算法和计算过程的区别:计算过程:操作系统(不终止的运行过程)算法是“可以终止的计算过程”算法的时效性:只能把在相当有穷步内终止的算法投入到计算机上运行氧藏傀窝栈刻澜邀呢由逮急溅烧预学嚎窗挨摄都钳狼舌扛迁活革囚壕敬囚计算机算法基础1计算机算法基础1*:1)设计算法:创造性的活动2)表示算法:思想的表示形式,SPARKS语言3)确认算法:证明算法对所有可能的合法输入都能得出正确的答案。算法证明:证明算法的正确性,与语言无关程序证明:证明程序的正确性4)分析算法:对算法的时、空特性做定量分析,以了解算法的好坏5)测试程序:调试:“调试只能指出有错误,而不能指出它们不存在错误”作时空分布图:验证分析结论,优化算法设计本课程集中于学****算法的设计与分析。通过学****掌握计算机算法设计和分析基本策略与方法,为设计更复杂、更有效的算法奠定基础辆俯丰滞毡侯蜡析咙愤麻仙椿乾峡菌酸***赣免华但排朗盗优傍吝抨瞩达疼计算机算法基础1计算机算法基础1