算法与复杂性-第1讲-概述课件.pptxVIP

;课程简介;3．考核方法－－考查 课堂表现、考勤、实验（占60％）期末考查（小组答辩，占40％）;从经典的IBM面试题说起;Brainstorm;;关于用计算机解决问题;世界最快的超级计算机（2014）;天河二号：32000颗主CPU，48000个协处理器， 300多万个计算核心，峰值计算速度达到每秒5.49亿亿次，而持续计算时的速度每秒可达3.39亿亿次。 假设每人每秒钟进行一次运算，“天河二号”运算一小时，相当于13亿人同时用计算器算上 1000年。 除了助力探月工程、载人航天等政府科研项目外，天河二号目前已经逐渐应用于民用领域，比如石 油勘探、汽车飞机的设计制造、基因测序等。 计算机什么都能做?;比如拿最简单例子， 26 个英文字母全排列，它的排列数为： 26！≈4×1026 以每年365天计算，共有 365×24×3600＝3.1536×107秒 以每秒能完成109个排列的超高速电子计算机来做这项工作，需要 4×1026/(3.1536×1016)≈1.2×1010年 即使计算机运行速度随着技术的提高，恐怕也还是不可能实现的。因计算机的速度再提高也有它的极限。;用计算机解决问题的关键——算法;算法是计算机科学的基础，更是程序的基石，只有具有良好的算法基础才能成为训练有素 的软件人才。 对于计算机专业的学生来说，学习算法的理由是非常充分的。因为你必须知道来自不同计算领域的重要算法，你也必须学会设计新的算法、确认其正确性并分析其效率。;2、研究算法的重要性;问：“交给你的问题，解决方案设计出来了吗？”答： “我找不到一个有效的算法来解决它，因为 这样的算法是不存在的。” (不过，要证明一个问题不存在有效算法，往往跟寻找有效算法一样难。);问：“交给你的问题，解决方案设计出来了吗？” 答： “我找不到一个有效的算法来解决它，但不是 我不行，因为所有这些名人也都找不到解决它的有效算法。” 如果是你的话，你愿意是哪种结果？;伟大的智者——Donald E. Knuth（美）高德纳 《计算机程序设计艺术》的作者； 谦逊的长者——Edsger Wybe（荷兰） Dijkstra算法（最短路径算法）发明者； 运筹学大师——George Dantzing（俄国）在运筹学建树极高， 获得了包括“冯诺伊曼理论奖”在内的诸多奖项。； 推动时代前进的人——James Cooley（美） FFT（快速傅利叶变换）算法发明者，该算法主要用语数字信号处理技术； FORTRAN之父——John Backus（美） FORTRAN之父，又提出规范编程语言语法的Backus-Naur Form(BNF)；;实践探索先锋—— Jon Bentley（美）《Programming Pearls》 （中文名《编程珠玑》）作者，精于软件工程； Pascal之父——Nicklaus Wirth（瑞士） PASCAL之父，提出了“ 算法+数据结构=程序”，他是创办Borland公司的Philie kahn的老师； 算法的讲解者——Robort Sedgewick（美）算法讲解者； 计算机领域的爵士 —— Tony Hoare（英）快速排序算法（Quick Sort）发明者，１９９９年加入微软创办了剑桥研究院； 首席算法官 —— Udi Manber（美）Google副总裁，首席算法官。;;为什么要学算法？;为什么要学算法？;作为即将从事计算机专业的人士;2.2 问题解决的好吗？;一些有趣的问题;设距离矩阵如下：;（ 2) 皇后问题 : 这是高斯 1850 年提出的一著名问题： 国际象棋中的 “ 皇后 ” 在横向、直 向、和斜向都能走步和吃子，问在 n×n 格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。 当n很大时，问题很难。 对于n=8, 现已知此问题共有92 种解，但只有12种是独立的，其余的都可以由这12种利 用对称性或旋转而得到。 设n=4，试一试。;数据挖掘领域十大经典算法;数据挖掘领域十大经典算法;第1部分 算法和算法分析;;1.1 算法概述;1.1.1 什么是算法;输入（input）：算法有零个或多个输入量；输出（output）：算法至少产生一个输出量；确定性（definiteness）：算法的每一条指令都 有确切的定义，没有二义性； 能行性（effectiveness）：算法的每一条指令必 须足够基本，它们可以通过已经实现的基本运算执行有限次来实现； 有穷性（finiteness）：算法必须总能在执行有 限步之后终止。;欧几里德算法(辗转相除法) 计算两个整数m和n（0≤m＜n)的最大公约数，记为gcd(m, n)。;【程序1-1】 欧几里德递归算法 void Swap（int a，int b） { int c=a；a=b；b=c； } int RG