算法分析与设计第一二三章1(算法与分析算法).ppt

2008-09-01版权所有:杨波,武汉科技大学理学院一个正六边形被分成了6个相同的小三角形如果用红、黄两种颜色分别涂满小三角形,那么有()种不同的涂法。(旋转后图案相同的认为是同一种涂法)2008-09-01版权所有:杨波,武汉科技大学理学院第一章数学预备知识第二章导引与基本数据结构第三章递归算法武汉科技大学理学院信息与计算科学系杨波cookie_******@2008年9月2008-09-01版权所有:杨波,武汉科技大学理学院序专业基础课程:数据结构、计算机语言操作系统、编译如何编写计算机程序:?数据结构+算法= 程序?算法:计算机软件的“灵魂”算法是计算机科学和计算机应用的核心2008-09-01版权所有:杨波,武汉科技大学理学院ACM国际大学生程序设计竞赛ACM国际大学生程序设计竞赛(英文全称:ACM International Collegiate Programming Contest(ACM-ICPC或ICPC)是由美国计算机协会(ACM)主办的,一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过30多年的发展,ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。赛事目前由IBM公司赞助。2008-09-01版权所有:杨波,武汉科技大学理学院内容?入门三本:?《数据结构与算法》(傅清祥,王晓东编著)?程序设计导引及在线实践作者: 李文新?ACM程序设计培训教程吴昊?基础提高:?算法艺术与信息学竞赛第二版刘汝佳?算法设计与分析王晓东?科曼:《算法导论》?组合数学第三版冯舜玺译?计算几何-算法设计与分析周培德?《Concrete Mathematics --- A Foundation puter Science》 Ronald L. Graham , Donald E. Knuth , Oren Patashnik《具体数学》《计算机程序设计艺术》三卷 Knuth ?组合数学的算法与程序设计?《程序设计中的组合数学》吴文虎?图论的算法与程序设计2008-09-01版权所有:杨波,武汉科技大学理学院教材与参考书?教材:?余祥宣等编著,计算机算法基础(第三版),华中理工大学出版社,2006年?参考书:?徐士良编,C常用算法程序集,华大学出版社,1998年?CLLIFORD A. SHAFFER著,A Practical Introduction to DATA STRUCTURES AND ALGORITHM ANALYSIS,电子工业出版社,1998年?卢开澄编,计算机算法导引,清华大学出版社,2003年2008-09-01版权所有:杨波, 算法什么是算法??算法如数字、计算一样,是一个基本概念。?算法是解一确定类问题的任意一种特殊的方法。?在计算机科学中,算法是使用计算机解一类问题的精确、有效方法的代名词。?算法是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。2008-09-01版权所有:杨波,武汉科技大学理学院算法的五个重要特性确定性、能行性、输入、输出、有穷性?1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。?例:不符合确定性的运算?5/0 ?将6或7与x相加?未赋值变量参与运算2008-09-01版权所有:杨波,武汉科技大学理学院2)能行性算法中有待实现的运算都是基本的运算,原理上每种运算都能由人用纸和笔在“有限”的时间内完成。例:整数的算术运算是“能行”的实数的算术运算是“不能行”的2008-09-01版权所有:杨波,武汉科技大学理学院3)输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域)?4)输出?一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。