算法与复杂性-第1讲-概述课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《算法与复杂性-第1讲-概述课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 复杂性 概述 课件
- 资源描述:
-
1、算法与复杂性算法与复杂性刘杰南华大学计算机学院软件工程系课程简介课程简介1 1课程学时课程学时 总学时:总学时:4848学时(理论)学时(理论)2 2课程主要内容课程主要内容p 介绍算法的概念及算法分析的基础知识;介绍算法的概念及算法分析的基础知识;p 介绍一些经典算法介绍一些经典算法*蛮力法蛮力法 分治法分治法 贪心法贪心法 动态规划动态规划 回溯法回溯法 分支限界法分支限界法 NP完全问题完全问题 *算法赏析算法赏析3 3考核方法考查考核方法考查 课堂表现、考勤、实验(占课堂表现、考勤、实验(占6060)期末考查(小组答辩,占期末考查(小组答辩,占4040)4 4本课程主要参考书本课程主要
2、参考书11王晓东编著,王晓东编著,计算机算法设计与分析计算机算法设计与分析(第第4版版),电子工业出,电子工业出版社,版社,2012201222屈婉玲等,算法设计与分析,清华大学出版社,屈婉玲等,算法设计与分析,清华大学出版社,20112011刘汝佳刘汝佳“白皮书白皮书”、“黑宝书黑宝书”5 5网上学习(百度网上学习(百度&CSDN&CSDN)作业提交作业提交l算法设计实现类的作业算法设计实现类的作业l网址:网址:http:/:9988/(南华(南华OJ)l登陆账号:学号登陆账号:学号(如:(如:20134330101)l密码:学号后面的密码:学号后面的6位数字位数字(以上面账号为例,则密码(
3、以上面账号为例,则密码为为330101)注意:注意:已注册过的同学提交本课程作业请用新账号和口令。已注册过的同学提交本课程作业请用新账号和口令。l课程课程PPT和参考资料、其他作业(报告)和参考资料、其他作业(报告)lhttp:/61.187.179.69:9988/sc8/(南华大学数字化教学(南华大学数字化教学中心)中心)l计算机:计算机:WSTD-6758 软件软件2班:班:UFSM-0601l软件软件3班:班:KQEQ-5247 物联网:物联网:PPKL-3080l船本软件:船本软件:PWAH-5676 船本计算机:船本计算机:VPKW-5550从经典的从经典的IBM面试题说起面试题说
4、起l村子中有村子中有50个人,每人有一条狗。在这个人,每人有一条狗。在这50条狗中有病狗条狗中有病狗(这种病不会传染)。于是人们就要找出病狗。(这种病不会传染)。于是人们就要找出病狗。l每个人可以观察其他的每个人可以观察其他的49条狗,以判断它们是否生病(如条狗,以判断它们是否生病(如果有病一定能看出来),只是自己的狗不能看。观察后得果有病一定能看出来),只是自己的狗不能看。观察后得到的结果不得交流,也不能通知病狗的主人。主人一旦推到的结果不得交流,也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗(发现后必须在一算出自己家的是病狗就要枪毙自己的狗(发现后必须在一天内枪毙),而
5、且每个人只有权利枪毙自己的狗,没有权天内枪毙),而且每个人只有权利枪毙自己的狗,没有权利打死其他人的狗。利打死其他人的狗。l第一天大家全看完了,但枪没有响,第二天仍没有枪响。第一天大家全看完了,但枪没有响,第二天仍没有枪响。到了第三天传来一阵枪声,问村里共有几条病狗,如何推到了第三天传来一阵枪声,问村里共有几条病狗,如何推算得出?算得出?Brainstorml腾讯面试题:腾讯面试题:给你给你10分钟时间,根据上排给出十个数,在分钟时间,根据上排给出十个数,在其下排填出对应的十个数,要求下排每个数都是先前上排其下排填出对应的十个数,要求下排每个数都是先前上排那十个数在下排出现的次数。那十个数在下
6、排出现的次数。上排的十个数如下:上排的十个数如下:【0,1,2,3,4,5,6,7,8,9】l阿里巴巴面试题:阿里巴巴面试题:澳大利亚的父母喜欢女孩,如果生出来澳大利亚的父母喜欢女孩,如果生出来的第一个女孩,就不再生了,如果是男孩就继续生,直到的第一个女孩,就不再生了,如果是男孩就继续生,直到生到第一个女孩为止,问若干年后,男女的比例是多少?生到第一个女孩为止,问若干年后,男女的比例是多少?l淘宝校园笔试题:淘宝校园笔试题:N个鸡蛋放到个鸡蛋放到M个篮子中,篮子不能为空,个篮子中,篮子不能为空,要满足:对任意不大于要满足:对任意不大于N的数量,能用若干个篮子中鸡蛋的数量,能用若干个篮子中鸡蛋的
7、和表示。对输入整数的和表示。对输入整数N和和M,输出所有可能的鸡蛋的放法。,输出所有可能的鸡蛋的放法。l百度移动开发笔试题:百度移动开发笔试题:三色球排序的问题,相同的球放到三色球排序的问题,相同的球放到一起,让你按顺序输出红白蓝三种颜色的球,可以用一起,让你按顺序输出红白蓝三种颜色的球,可以用012来表示,要求只能扫描一次数组。来表示,要求只能扫描一次数组。为什么学习算法为什么学习算法?关于用计算机解决问题关于用计算机解决问题计算机的能力计算机的能力每秒每秒5000次次每秒数千亿次每秒数千亿次继电器继电器真空管真空管晶体管晶体管集成电路集成电路大规模集成电路大规模集成电路超大规模集成电路超大
8、规模集成电路元器件元器件“单兵作战单兵作战”计算机网络计算机网络单机的串行单机的串行分布计算分布计算结构结构算法算法运算速度运算速度世界最快的超级计算机(世界最快的超级计算机(2014)10.神秘计算机神秘计算机这是美国政府运营的一台神秘的、基于无限带宽技这是美国政府运营的一台神秘的、基于无限带宽技术的术的Cray CS-Storm机器,具体位置不详。它是唯一新入选榜单者,也机器,具体位置不详。它是唯一新入选榜单者,也是最节能的超级计算机,每瓦特电可每秒进行是最节能的超级计算机,每瓦特电可每秒进行2386.42百万次浮点运算。百万次浮点运算。最高速度:每秒最高速度:每秒3.57千万亿次浮点运算
9、,总核心数:千万亿次浮点运算,总核心数:7.28万个万个 9.Vulcan(美国)(美国)Vulcan是跻身最新榜单的美国能源部四大超级计算是跻身最新榜单的美国能源部四大超级计算机性能最弱的一台,它目前应用于能源部的高性能运算创新中心。最高机性能最弱的一台,它目前应用于能源部的高性能运算创新中心。最高速度:每秒速度:每秒4.29千万亿次浮点运算,总核心数:千万亿次浮点运算,总核心数:39.3216万个万个8.JUQUEEN(德国)(德国)JUQUEEN是前十榜单的是前十榜单的“常客常客”,2012年年中年年中以来未曾落选过。它运营于德国北莱茵以来未曾落选过。它运营于德国北莱茵-威斯特伐利亚的威
10、斯特伐利亚的Jlich研究中心。研究中心。相比欧洲上榜的另一台超级计算机,它的性能较弱。最高速度:每秒相比欧洲上榜的另一台超级计算机,它的性能较弱。最高速度:每秒5千万亿次浮点运算,总核心数:千万亿次浮点运算,总核心数:45.8752万个万个7.Stampede(美国)(美国)该来自德州大学的超级计算机是此榜单上的唯一该来自德州大学的超级计算机是此榜单上的唯一一台戴尔产品,它也是全球最强大的学术用超级计算机。最高速度:每一台戴尔产品,它也是全球最强大的学术用超级计算机。最高速度:每秒秒5.17千万亿次浮点运算,总核心数:千万亿次浮点运算,总核心数:46.2462万个万个6.Piz Daint(
11、瑞士)(瑞士)Piz Daint是欧洲性能最强大的一台超级计算机,是欧洲性能最强大的一台超级计算机,它运营于位于卢加诺的瑞士国家计算中心,以该中心它运营于位于卢加诺的瑞士国家计算中心,以该中心80英里以外的阿尔英里以外的阿尔卑斯山命名。最高速度:每秒卑斯山命名。最高速度:每秒6.27千万亿次浮点运算,总核心数:千万亿次浮点运算,总核心数:11.5984万个万个5.Mira(美国)(美国)Mira是前十榜单的另一位常客,效力于美国阿贡国家是前十榜单的另一位常客,效力于美国阿贡国家实验室。这是它第六次上榜,同时也是连续第四次位居第五位。最高速实验室。这是它第六次上榜,同时也是连续第四次位居第五位。
12、最高速度:每秒度:每秒8.59千万亿次浮点运算,总核心数:千万亿次浮点运算,总核心数:78.6432万个万个4.K Computer(日本)(日本)富士通富士通K Computer登上前十榜单的次数比登上前十榜单的次数比Mira还要多,达到还要多,达到10次。次。2011年年6月首次上榜它便是全球最快速的超级月首次上榜它便是全球最快速的超级计算机。跟计算机。跟Mira一样,它也是连续一样,它也是连续4次入选。最高速度:每秒次入选。最高速度:每秒10.5千万千万亿次浮点运算,总核心数:亿次浮点运算,总核心数:70.5024万个万个3.Sequoia(美国)(美国)Sequoia在跻身前在跻身前5
13、00强榜单的时间比富士通强榜单的时间比富士通K Computer仅晚仅晚6个月,第二次上榜便荣登首位。它运行于美国能源部位个月,第二次上榜便荣登首位。它运行于美国能源部位于加州的劳伦斯利弗莫尔国家实验室。最高速度:每秒于加州的劳伦斯利弗莫尔国家实验室。最高速度:每秒17.2千万亿次浮千万亿次浮点运算,总核心数:点运算,总核心数:157.2864万个万个2.Titan(美国)(美国)该美国超级计算机也是能源部的机器,它运行于位于该美国超级计算机也是能源部的机器,它运行于位于田纳西州的橡树岭国家实验室。在最近的田纳西州的橡树岭国家实验室。在最近的4次评比中,它都位居第二位。次评比中,它都位居第二位
14、。最高速度:每秒最高速度:每秒17.6千万亿次浮点运算,总核心数:千万亿次浮点运算,总核心数:56.064万个万个1.天河二号(中国)天河二号(中国)运行于位于广州的超级计算中心。最高速度:每秒运行于位于广州的超级计算中心。最高速度:每秒33.9千万亿次浮点运算,总核心数千万亿次浮点运算,总核心数312万个。万个。计算机什么都能做计算机什么都能做?天河二号:天河二号:3200032000颗主颗主CPUCPU,4800048000个协处理器个协处理器,300300多万个计算核心多万个计算核心,峰值计算速度达到每秒,峰值计算速度达到每秒5.495.49亿亿次,而持续计算时的速度每秒可达亿亿次,而持
15、续计算时的速度每秒可达3.393.39亿亿次。亿亿次。假设每人每秒钟进行一次运算,假设每人每秒钟进行一次运算,“天河二号天河二号”运算一小时,相当于运算一小时,相当于1313亿人同时用计算器算亿人同时用计算器算上上10001000年。年。除了助力除了助力探月工程探月工程、载人航天载人航天等政府科研项目外,等政府科研项目外,天河二号目前已经逐渐应用于民用领域,比如天河二号目前已经逐渐应用于民用领域,比如石石油勘探油勘探、汽车飞机的设计制造汽车飞机的设计制造、基因测序基因测序等。等。天河二号能做什么?天河二号能做什么?比如拿最简单例子,比如拿最简单例子,2626个英文字母全排列,个英文字母全排列,
16、它的排列数为:它的排列数为:2626!4 410102626以每年以每年365365天计算,共有天计算,共有 3653652424360036003.15363.153610107 7秒秒以每秒能完成以每秒能完成10109 9个排列的超高速电子计算机来个排列的超高速电子计算机来做这项工作,需要做这项工作,需要 4 410102626/(3.1536/(3.153610101616)1.2)1.210101010年年即使计算机运行速度随着技术的提高,恐怕也还即使计算机运行速度随着技术的提高,恐怕也还是不可能实现的。因计算机的速度再提高也有它是不可能实现的。因计算机的速度再提高也有它的极限。的极限
17、。用计算机解决问题的关键用计算机解决问题的关键算法算法一个熟悉的公式(一个熟悉的公式(Nicklaus Wirth):):程序程序=算法十数据结构算法十数据结构l算法是计算机科学的基础,更是程序的基石,算法是计算机科学的基础,更是程序的基石,只有具有良好的算法基础才能成为训练有素只有具有良好的算法基础才能成为训练有素的软件人才。的软件人才。l对于计算机专业的学生来说,学习算法的理对于计算机专业的学生来说,学习算法的理由是非常充分的。因为你必须知道来自不同由是非常充分的。因为你必须知道来自不同计算领域的重要算法,你也必须学会设计新计算领域的重要算法,你也必须学会设计新的算法、确认其正确性并分析其
18、效率。的算法、确认其正确性并分析其效率。1 1、学习算法的必要性、学习算法的必要性2 2、研究算法的重要性、研究算法的重要性2.1 2.1 问题能解决吗问题能解决吗 假设某一负责人交给你一个很难的任务,几假设某一负责人交给你一个很难的任务,几天后询问你问题解决了没有。可能会发生如下天后询问你问题解决了没有。可能会发生如下图这样的情况:图这样的情况:问:问:“交给你的问题,解决方案设计出来了吗?交给你的问题,解决方案设计出来了吗?”答:答:“我找不到一个有效的算法来解决它,没能完我找不到一个有效的算法来解决它,没能完成任务。成任务。”问:问:“交给你的问题,解决方案设计出来了吗?交给你的问题,解
19、决方案设计出来了吗?”答:答:“我找不到一个有效的算法来解决它,因为我找不到一个有效的算法来解决它,因为 这样的算法是不存在的。这样的算法是不存在的。”(不过,要证明一个问题不存在有效算法,往往跟不过,要证明一个问题不存在有效算法,往往跟寻找有效算法一样难。寻找有效算法一样难。)问:问:“交给你的问题,解决方案设计出来了吗?交给你的问题,解决方案设计出来了吗?”答:答:“我找不到一个有效的算法来解决它,但不是我找不到一个有效的算法来解决它,但不是 我不行,因为所有这些名人也都找不到解决它我不行,因为所有这些名人也都找不到解决它 的有效算法。的有效算法。”如果是你的话,你愿意是哪种结果?如果是你
20、的话,你愿意是哪种结果?伟大的智者伟大的智者Donald E.Knuth(美)高德纳(美)高德纳 计算机程计算机程序设计艺术序设计艺术的作者;的作者;谦逊的长者谦逊的长者Edsger Wybe(荷兰)(荷兰)Dijkstra算法(最短算法(最短路径算法)发明者;路径算法)发明者;运筹学大师运筹学大师George Dantzing(俄国)在运筹学建树极(俄国)在运筹学建树极高,获得了包括高,获得了包括“冯诺伊曼理论奖冯诺伊曼理论奖”在内的诸多奖项。;在内的诸多奖项。;推动时代前进的人推动时代前进的人James Cooley(美)(美)FFT(快速傅利(快速傅利叶变换)算法发明者,该算法主要用语数
21、字信号处理技术;叶变换)算法发明者,该算法主要用语数字信号处理技术;FORTRAN之父之父John Backus(美)(美)FORTRAN之父,之父,又提出规范编程语言语法的又提出规范编程语言语法的Backus-Naur Form(BNF);影响计算机算法世界的十位大师影响计算机算法世界的十位大师实践探索先锋实践探索先锋 Jon Bentley(美)(美)Programming Pearls(中文名(中文名编程珠玑编程珠玑)作者,精于软件工程;)作者,精于软件工程;Pascal之父之父Nicklaus Wirth(瑞士)(瑞士)PASCAL之父,提出了之父,提出了“算法算法+数据结构数据结构=
22、程序程序”,他是创办,他是创办Borland公司的公司的Philie kahn的的老师;老师;算法的讲解者算法的讲解者Robort Sedgewick(美)算法讲解者;(美)算法讲解者;计算机领域的爵士计算机领域的爵士 Tony Hoare(英)快速排序算法(英)快速排序算法(Quick Sort)发明者,年加入微软创办了剑桥研究院;)发明者,年加入微软创办了剑桥研究院;首席算法官首席算法官 Udi Manber(美)(美)Google副总裁,首席算法官。副总裁,首席算法官。影响计算机算法世界的十位大师影响计算机算法世界的十位大师来自圣经的十大算法来自圣经的十大算法No10:Huffman c
展开阅读全文