算法设计与分析课件

xxx算法设计与分析辽宁师范大学计算机与信息技术学院计算机科学与技术专业课程AlgorithmDesignandAnalysis关于任课教师课程介绍什么是算法算法的描述算法分析宋传鸣讲师2003年本科毕业于辽宁师范大学计算机科学与技术系计算机应用技术专业,工学学士2006年硕士毕业于辽宁师范大学计算机科学与技术系计算机应用技术专业,工学硕士2010年博士毕业于南京大学计算机科学与技术系计算机应用技术专业,工学博士2010年7月回校任教至今联系方式电子邮件:办公室:西山校区第二教学楼B614

个人主页:关于《算法设计与分析》课程课程介绍什么是算法算法的描述算法分析课程性质本课程属于专业选修课(计算机科学与技术)、专业必修课(计算机科学与技术(动画))开设目的使学生掌握非数值算法设计的主要方法独立设计算法和对算法进行复杂性计算奠定基础利用所学的算法设计策略解决实际问题的能力

学时安排48学时,每周3学时,修完课程可获3学分考核方式——考察期末为闭卷笔试,成绩占总成绩的50%平时出勤占5%,学期论文(3篇)占45%(第4/8/12周)试卷题型:概念型、设计型、证明型关于《算法设计与分析》课程课程介绍什么是算法算法的描述算法分析在专业教学计划中的地位和作用在IEEEACM公布的《ComputerScienceCurriculum2008》与中国计算机学会教育委员会、全国高等学校计算机教育研究会推出的CCC2004(ChinaComputingCurricula2004-CS)中,算法设计与分析都是其核心课程之一算法设计与分析具有学科核心的重要地位,能够充分体现计算机科学方法论的理论、抽象和设计3个过程,知识面较宽,有一定的深度

反复再现计算机科学中用到的典型问题的复杂性、效率、抽象的层次、重用、折衷等带有普遍性的概念

不仅是计算机科学与技术专业后续课程的理论基础,而且还广泛地用于新兴的技术和研究领域

关于《算法设计与分析》课程课程介绍什么是算法算法的描述算法分析计算思维(ComputationalThinking)摘自《中国计算机学会通讯》2012年第一期理论科学、实验科学、计算科学被称为推动人类文明进步和科技发展的三大科学科学思维包括理论思维、实验思维和计算思维理论思维以推理和演绎为特征,如数学学科实验思维以观察和总结自然规律为特征,如物理学科计算思维以设计和构造为特征,如计算机学科计算思维是运用计算的基础概念去求解问题、设计系统和理解人类行为的一种方法.它合用了数学思维(求解问题的方法)、工程思维(设计、评价大型复杂系统)和科学思维(理解可计算性、智能、心理和人类行为)计算思维课程现已在部分高校中开启教材(Textbook)课程介绍什么是算法算法的描述算法分析王晓东编著.计算机算法设计与分析(第3版).北京:电子工业出版社,2007.主要参考书(References)课程介绍什么是算法算法的描述算法分析M.H.Alsuwaiyel著,吴伟昶,方世昌译.算法设计技巧与分析.北京:电子工业出版社,2010.ThomasH.Cormer等著,潘金贵,顾铁成等译.算法导论(第二版).北京:机械工业出版社,2010

主要参考书(References)课程介绍什么是算法算法的描述算法分析TheArtofComputerProgramming数据结构的开拓者D.E.Knuth的计算机科学发展史上的不朽之作第1卷基本算法:介绍计算机程序设计的基本算法,包括基本的编程概念和技术以及信息结构--机内信息的表示、数据元及其处理的结构关系第2卷半数值算法:介绍随机数和算术,提供了计算机编程和数值分析之间的丰富接口第3卷排序与查找:介绍排序和查找的最权威的经典技术,扩充了第1卷的数据结构,以处理大小型数据库及内外部存储.本书偏重分析技术,采用汇编语言描述算法,是一本本学科最经典最权威的百科全书,适合于从事数据结构与算法研究的专家阅读《算法设计与分析》课程的主要内容课程介绍什么是算法算法的描述算法分析第一章绪论第二章数学预备知识与典型的数据结构第三章递归与分治策略

第四章动态规划第五章贪心算法第六章NP完全问题第七章回溯法第八章分支限界法第九章随机化算法

第十章网络流算法第十一章并行算法入门《算法设计与分析》课程的基本要求课程介绍什么是算法算法的描述算法分析培养学习方法与习惯上课记笔记阅读与自学理论联系实际查找资料课上认真听讲,课后多思考多翻阅资料关于理论计算机科学课程介绍什么是算法算法的描述算法分析关于计算机和计算机械的数学理论,也称计算理论自动机与形式语言理论程序理论形式语义学算法分析和计算复杂性理论学科产生20世纪30年代,人们关注是否存在一种有效过程求解问题,即问题的可解与不可解性如果存在某个模型能够建立一个算法求解问题,则将该问题归入可解的问题类30年代前期,哥德尔等创立递归函数30年代中期,丘奇的λ演算,波斯特的波斯特机,图灵的图灵机40年代后期:存储程序型计算机(RAM,RASPM)算法分析与计算复杂性理论课程介绍什么是算法算法的描述算法分析各类具体算法的复杂性的研究称作算法分析一般算法的复杂性的研究称作计算机复杂性理论计算复杂性理论原是可计算理论的一支,是以各种可计算函数(递归函数)的计算复杂性为研究对象基本问题实际可计算函数的结构和性质60年代中期以来,有关研究者一般以计算时间多项式有界的函数作为实际可计算的函数确定性机器与非确定性机器的解题能力比较关于计算和算法的研究对串行计算的性质研究多对并行计算性质的研究少算法(Algorithm)的定义课程介绍什么是算法算法的描述算法分析解决问题的一种方法或过程,由若干条指令组成Algorithm一词源于公元九世纪的一位波斯数学家MuhammadibnMusaal-Khwarizmi的书<Rulesofrestoringandequating>示例:给定正数m和n,找出两个数的最大公约数E1.用n除以m,并令r为余数(0≦r<n)E2.如果r=0,则算法结束,n为所求E3.令m=n,n=r,转入E1.算法的性质输入:有零个或多个由外部提供的量输出:至多一个量作为输出确定性:每条指令是清晰的,无歧义的有限性:每条指令执行次数有限,执行时间也有限有效性:每个操作须使用户利用纸笔在有限时间内精确地完成求解问题的一般过程课程介绍什么是算法算法的描述算法分析算法与程序课程介绍什么是算法算法的描述算法分析算法与程序的区别程序是算法用某种程序设计语言的具体实现程序可以不满足算法的第四条性质为什么要学习算法？算法是程序的灵魂问题求解过程:分析问题—设计算法—编写程序—整理结果程序设计研究的四个层次:算法—方法学—语言—工具提高分析问题的能力算法的形式化—思维的逻辑性和条理性算法可以解决哪些类型的问题?课程介绍什么是算法算法的描述算法分析问题的特点有很多候选的解决方案,而要找出其中真正需要的方案并不容易的情况有着实际应用背景,但是受到经济利益,运行成本等多方面的限制算法应用举例人类基因组项目:找出人类DNA中所有100000种基因,确定构成人类DNA的30亿种化学基对的各种序列,并将信息存储,检索和分析等互联网:寻找合理的数据传输路径电子商务:保持私人信息,采用公钥和数字签名等交通:GPS导航计算几何:求解平面上n个点的凸壳数值计算:求解n个矩阵相乘,解方程组等……算法可以解决哪些类型的问题?课程介绍什么是算法算法的描述算法分析重要的问题类型查找问题排序问题图问题组合问题几何问题算法的描述课程介绍什么是算法算法的描述算法分析自然语言优点:容易理解缺点:冗长,有二义性使用方法:粗线条描述算法思想注意事项:避免写成自然段流程图优点:直观缺点:缺少严密性和灵活性使用方法:描述简单算法注意事项:注意抽象层次算法的描述课程介绍什么是算法算法的描述算法分析程序设计语言优点:能由计算机执行缺点:抽象性差,对语言要求高使用方法:对算法进行验证注意事项:将算法写成子函数算法的描述课程介绍什么是算法算法的描述算法分析伪代码(PseudoCode)—算法语言介于自然语言和程序设计语言之间.采用某一程序设计语言的基本语法,操作指令可结合自然语言来设计优点:表达能力强,容易理解1.r←m%n;2.循环直到r←02.1m←n;2.2n←r;2.3r←m%n;3.输出n算法复杂性分析(ComplexityAnalysis)课程介绍什么是算法算法的描述算法分析算法复杂性=算法所需要的计算机资源时间复杂性(TimeComplexity):T=T(N,I)空间复杂性(SpatialComplexity):S=S(N,I)N表示问题的规模,I表示算法的输入计算机包含的运算有多种,记为O1,O2,…,Ok,执行时间分别为t1,t2,…,tk,每种运算的次数为e1,e2,…,ek,则有一般情况下,不考虑每种运算的时间差异有代表性的算法复杂性课程介绍什么是算法算法的描述算法分析评价规模为N的某些或某类有代表性的合法输入时的算法复杂度最坏情况下的时间复杂度最好情况下的时间复杂度平均情况下的时间复杂度DN表示规模为Ｎ的合法输入的集合,P(I)表示出现输入I的概率例:插入排序和合并排序的复杂性分析课程介绍什么是算法算法的描述算法分析插入排序(升序排列):每次选取未排序数中的第一个数,将其插入已排好序数列的合适位置代价执行次数C1nC2n－1C3n－1C4sum(tj)C5sum(tj－1)C6sum(tj－1)C7n－1例:插入排序和合并排序的复杂性分析课程介绍什么是算法算法的描述算法分析插入排序的时间复杂度最好情况下:输入数组已排好序,每次不进入while循环,则有最好情况下:输入数组逆序,A[i]必须与已排好序的元素逐一比较,因此tj=j,则有例:插入排序和合并排序的复杂性分析课程介绍什么是算法算法的描述算法分析插入排序的时间复杂度平均情况下:A[i]必须与已排好序的一半元素逐一比较,因此tj=j/2,则有例:插入排序和合并排序的复杂性分析课程介绍什么是算法算法的描述算法分析合并排序:将待排序元素分成大小大致相同的两个子集合,然后分别将排好序的子集合合并成所要求的排好序的集合例:插入排序和合并排序的复杂性分析课程介绍什么是算法算法的描述算法分析合并排序:将待排序元素分成大小大致相同的两个子集合,然后分别将排好序的子集合合并成所要求的排好序的集合假如n为2的幂次,递归算法要递归(log2n+1)层,每一层需要计算cn次,因此例:插入排序和合并排序的复杂性分析课程介绍什么是算法算法的描述算法分析插入排序与合并排序的比较最好情况下:插入排序的时间复杂性低于合并排序最坏和平均情况下:可以证明对于任意的a,b,c,d,总存在N使得当n>N时,有an2+bn+c>dnlog2n+dn,即:合并排序的时间复杂性低于插入排序实例计算机A每秒执行10亿条指令,计算机B每秒执行1千万条指令.由A执行插入排序,B执行合并排序插入排序的T(n)简化为c1n2,合并排序的T(n)简化为c2nlog2n,并设c1=2,c2=50要排序100万个数,A机器需要2000秒,B机器大约需要100秒要排序1000万个数,A机器需要2.3天,B机器需要20分钟随着问题规模的增长,合并排序的相对优势更明显例:插入排序和合并排序的复杂性分析课程介绍什么是算法算法的描述算法分析一般考察算法的最坏情况下的运行时间Tmax(n)是算法再任何输入下的运行时间上界对于某些算法,最坏情况出现得相当频繁如在数据库中检索根本不存在的信息大致看来,

Tavg(n)通常与Tmax(n)一样差知名学者课程介绍什么是算法算法的描述算法分析姚期智姚期智(AndrewChi-ChihYao),世界著名计算机学家,2000年图灵奖得主,美国科学院院士,美国科学与艺术学院院士,中国科学院外籍院士,清华大学高等研究中心教授.1967年获得台湾大学物理学士学位,1972年获得美国哈佛大学物理博士学位,1975年获得美国伊利诺依大学计算机科学博士学位.1975年至1986年曾先后在美国麻省理工学院数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机系任助教授、教授.1986年至2004年在普林斯顿大学计算机科学系担任WiliamandEdnaMacaleer工程与应用科学教授.2004年起在清华大学任全职教授.多年来,姚期智先生以其敏锐的科学思维,不断向新的学术领域发起冲击,在数据组织、基于复杂性、姚期智的伪随机数生成理论、密码学、通信复杂性乃至量子通信和计算等多个尖端科研领域，都做出了巨大而独到的贡献.他所发表的近百篇学术论文,几乎覆盖了计算复杂性的所有方面,并在获图灵奖之前,就已经在不同的科研领域屡获殊荣,曾获美国工业与应用数学学会乔治·波利亚奖和以算法设计大师克努特命名的首届克努特奖,是计算机理论方面国际上最拔尖的学者.知名学者课程介绍什么是算法算法的描述算法分析陈国良陈国良任中国科学技术大学教授,博士生导师,现任中国科学技术大学软件学院院长,国家高性能计算中心（合肥）主任,智能感知与图像理解教育部重点实验室（西安电子科技大学）学术委员会主任.中国计算机学会高性能计算专业委员会主任,享受国家政府特殊津贴.1973年起在中国科学技术大学任教.陈国良2003年当选中国科学院院士,国家教育部高等学校计算机科学技术教学指导委员会副主任,全国首届高等学校教学名师,安徽省计算机学会理事长,国际高性能计算（亚洲）常务理事.他是我国非数值并行算法研究的学科带头人,他围绕着并行算法的教学与研究,逐渐形成了“算法理论－算法设计－算法实现－算法应用”一套完整的并行算法学科体系,提出了“结构－算法－编程”一体化的并行计算研究方法.他率先创建的我国第一个国家高性能计算中心是我国并行算法研究、环境科学与工程计算软件等的科研与教学基地,在学术界和教育界有一定的影响和地位.知名学者课程介绍什么是算法算法的描述算法分析