算法导论课件第一讲算法概述
49页1、Introduction to Algorithms 算法导论,李彬 山东轻工业学院 理学院,2,教材及参考书,Sara Baase and Allen Van Gelder, Computer AlgorithmsIntroduction to Design and Analysis (3rd Ed), Addison-Wesley, 2000 计算机算法:设计与分析导论,朱清新等编著,人民邮电出版社 2007,3,教材及参考书,Gelder, 乌迪 曼博(Udi Manber) 算法引论一种创造性方法,电子工业出版社,2009 算法导论,潘金贵(译),机械工业出版社,2006,4,教材及参考书,计算机算法设计与分析,王晓东,电子工业出版社,2012,5,第一章 引论,算法的基本概念 算法的数学基础 集合论 逻辑学 概率论 求和与递归 快速估算法 算法的效率和复杂度,6,1.1 算法的基本概念,算法导论:进行算法的分析与设计(如何高效地进行转化). 软件工程:使转化的过程更加规范化和易于管理.,输入,输出,7,可计算性,可计算性理论描述那些在算法上可解的问题的特征. 定义:我们说一个
2、问题是算法上可解的,如果我们能够设计出一个计算机程序,对于该问题的任何一个输入都可以给出正确的答案. 在上述定义中我们假设所需要的计算资源(时间和存储空间)是充分大的. Enough storage space Enough time,8,理论与现实可解性,下棋程序 棋盘的数学(西萨与舍罕王),9,不可解问题,Alan Turing, On computable numbers, with an application to the Entscheidungs problem,(论可计算数及其在判定问题中的应用) Proceedings of the London Math. Society, Series 2, 42 (1936), pp 230-265. 在这篇划时代的论文中,图灵提出了图灵机的概念,给出了停机问题的定义并且证明了它是不可解问题.,10,Halting Problems,Question: Does the following program stop for any n? While (n 1) If (odd(n) N = 3*n + 1 ; Else N =
3、n / 2; End (while),11,Halting Problems,图灵停机问题的描述:不存在一个程序(或算法),它能够计算任何程序在给定输入上是否会结束(停机). 停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题.如果这个问题可以在有限的时间之内解决,那么就可以有一个程序判断其本身是否会停机.但是,在程序停止之前,没有办法判断它会不会停止.所以这是一个不可解的问题.,12,阿兰图灵,Turing, Alan Mathison 1912年6月 23日生于英国伦敦, 1954年6月7日 卒于英国威姆斯洛(Wilmslow). 牛津大学安德鲁哈吉斯在谜一 样的图灵(Alan Turing: The Enigma)中做了这样的描述:“图灵似乎是上天派来的一个使者,匆匆而来,匆匆而去,为人间留下了深邃的思想,后人必须为之思索几十年或几百年甚至永远.”,13,历史注记,1900年罗素认识到数学是逻辑学的一部分。1910年罗素和他的老师阿尔弗雷德诺斯怀特海一起发表了三卷本的数学原理, 对这一概念做了系统阐述,创建了数理逻辑. 怀特海和罗素创建数理逻辑的原因主要是为了对付“
4、悖论”.他们认为“悖论”是由于人类语言的先天不精密造成的,而逻辑本身是天衣无缝的.他们坚信所有的数学成果都可以用逻辑推导出来.,14,希尔伯特纲领,1928年德国数学家大卫希尔伯特(DHillbert)提出著名的“希尔伯特纲领”,认为数学原理中所定义的系统既是一致的,也是完备的,换言之,一个系统的完备和一致性,可以由该系统本身得到证明. 1931年,“希尔伯特纲领”被奥地利逻辑学家库尔特哥德尔(Godel)捅出一个大窟窿,哥德尔认为没有一种公理系统可以导出数论中所有的真实命题,除非这种系统本身就有悖论。这就是著名的“哥德尔定理”.,15,哥德尔不完备性定理,哥德尔定理: 对每个丰富而可靠的数学形式系统S.第一,在S中存在既不可证也不可否证,即不可判定的命题(第一不完全性定理);第二,在S中不可证S的一致性(第二不完全性定理). 哥德尔定理中最重要的是哥德尔第一不完备性定理.第二不完备性定理是第一定理的一个推论: “任何相容的形式体系不能用于证明它本身的相容性”. 哥德尔定理不仅推翻了“希尔伯特纲领”,还矛头直指数学原理,说它本身就是不一致的.,16,图灵机,为了验证数学系统的一致性,图
《算法导论课件第一讲算法概述》由会员E****分享,可在线阅读,更多相关《算法导论课件第一讲算法概述》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页