当前位置:
文档之家› 算法分析基本概念 PPT课件
算法分析基本概念 PPT课件
(1)国王奖励有功的大臣:棋盘放 麦子的问题。说明一个问题:计算复杂 性问题,没有知识是多么可怕啊。 (2)网络安全:其实也是一个计算复 杂性问题。没有绝对安全的网络,从理 论上可以证明构建绝对安全的网络是一 个完全NP问题,无法达到,只能寻求某 种情况下的最优。 (如果你不知道这些,会在上面浪费非 常多的人力、无力,而没有任何效果, 不能无限制满足甲方的不合理要求)
算法1.1 LinearSearch伪码描述: Input: 数组 A[1…n] 、欲搜索元素x。 Output: 若x=A[j]且1jn,输出j,否则输出0。 1. j1 2. while (jn) and (xA[j]) //处理循环 3. jj+1 4. end while 5. if x=A[j] then return j else return 0.
1.2 历史背景
● 20世纪30年代,人们的注意力是放在问题的可 解与不可解的分类上,即是否存在有效过程来求解 问题,为此产生了计算模型的概念. 例如:递归函数、 演算、POST机、 Turing机. ● 令人惊奇的是“几乎所有”的问题都是不可 解的。(请参考书上的说明,不做要求) ● 把问题的可判定性和可解性的研究领域称为 可计算性理论或计算理论。
(1)排序算法:要考虑需要进行排序的数 据的顺序程度、数据取值的可能限制、 数据所处于介质如内存、磁盘、磁带等 的情况。 (2)倒排索引:搜索引擎中的算法;页面 关联度分析算法等等; (3)海量数据中的查找算法; (4)图形、图像中的各种算法:高斯去噪; 图像分割、图像内容提取、图像修复等 等。
(5)智能优化算法(最多)。 遗传算法、蚁群算法、粒子群算法等等。 用于解决那些无法找到确定性算法解决 的问题,即NP问题。(这是我们毕业生 做的最多的) (6)大数据中的数据挖掘、关联度分析 等等算法。 (7)软件保护中的加解密、水印算法等等。
● 数字计算机出现后,对于可解问题研究的要 求越来越多, 由于有限的可用资源与开发复杂算 法的要求, 导致了在计算理论中出现了一个称为 计算复杂性的新领域。 ● 在此领域,人们研究可解类问题的效率。
1.3 二分搜索Biblioteka 注意:自本节起,在搜索与排序的问题以及类 似问题中,均假定元素取自线序集合(如整数集)。
算法设计技巧与分析
信工学院软件与理论教研室
纪律要求等情况说明:
1、请勿随意缺课; 2、交作业(会适当); 3、交试验报告(务必运行程序让我看结果,跟我说明 程序的设计思想) 4、实验纪律(点名出勤,缺课1/3则没有实验分数) 5、最终分数=试卷(70%)+实验(30%) 作业依据质量融入实验分数中; 6、考试形式:按照往常年的情况就是7或8道分析设 计题(10-15分/题)。 涉及编程、设计思想、求解步骤分析等。一般情 况下是没有选择、填空、判断、简答等的题目。
3、美国计算机协会组织的ACM大赛。是目 前为止,最受肯定的国际级别的比赛, 主要专注的就是算法设计和编程。 参赛者组成一个团队,以5个小时之 内完成的算法和编程完成情况排名。 (这个赛事备受各个大公司猎头的关 注,亲们可以组队参加试试) 4、跟大家毕业相关的算法介绍 计算科学的算法实在是太多了,介 绍几个如下:
算法的规则须满足特点:
(1) 有穷性—执行有限条指令后一定要终止。 (2) 确定性(无二义)—算法的每一步操作都必须 有确切定义,不得有任何歧义性。 (3) 可(能)行性—算法的每一步操作都必须是可 行的,即每步操作均能在有限时间内完成。 (4) 输入—一个算法有n(n>=0)个初始数据的输 入。 (5) 输出—一个算法有一个或多个与输入有某种 关系的有效信息的输出。深什么能够屹立业界: 先进的搜索引擎处理算法、非开源 的云计算架构; (注:hadoop是开源的)
2、IT公司的竞争其实是科技含量的竞争, 实质就是在算法、架构能否优先的竞争。 3、优秀软件公司的组织结构: a、CTO(首席架构师) b、需求分析师:负责跟甲方沟通; c、系统设计师+核心算法设计小组人 员。 d、项目经理 e、编码人员(这个阶层人数最多) f、测试小组; g、质量管理人员。
● 考虑这样的问题:判定给定元素 x 是否在数 组A[1…n]中。此问题可表述为:寻找索引j, 1jn,如果x在A中,则有x=A[j],否则j=0。
●解决该问题能够想到的最简单的方法:
顺序扫描法(线性搜索):
算法思想如下:
扫描A中所有项,将每一项与x比较,如果在 比较j次后(1jn)搜索成功,即x=A[j],则返回j的 值,否则返回0,表示没有找到。
微软高薪挖角:挖掉了borland delphi的首席架构师等人,去做VS系列 以及设计C#等。 (PS: 编译器中的优化算法等等各个 公司的编译器均不相同。) 搜索引擎中的各个算法处理方案也不 尽相同。 DNA中基因对序列排队也会涉及复杂 的算法。 网络数据传输中的路由选择算法。 (QQ、微信中的信息传输)
自动化软件测试中的路径测试用例自 动生成技术。 该问题也是一个复杂性相当强的问题, 会产生组合爆炸。 围棋软件、象棋软件等等 (我们身边的:查询你自己的通话记 录,有优秀算法的存在吗? 数据库:优化、索引)
科学研究中的算法
1、图灵奖的获得者绝大部分是做算法的研究的; 姚期智:受聘于清华大学计算机系,唯一的一 个图灵奖华裔获得者。 2、寻求计算方面的突破。可计算性理论与计算 复杂性理论等等。 最简单的实例:围棋中的人工智能其实就 是一个计算复杂性太大的问题,各种组合会产 生组合爆炸的问题,在目前图灵机模型下没有 办法进行突破。 排序算法的突破:寻求更快速、更稳定的 排序算法。(基于比较的排序算法和非比较排 序算法O(nlogn)、O(n))
1.1 引 言
算法的直觉含义:一个由有限的指令集组成的 过程.
Knuth教授的定义:一个算法就是一个有穷规 则的集合,其中的规则确定了一个解决某一特
定类型问题的运算序列.
算法导论中的定义:定义良好的计算过程,它 取一个或一组作为输入,并产生出一个或一组 作为输出。
在计算机科学领域,算法设计与分析是十分 重要的。D.E.Knuth说:“计算机科学就是算法 的研究”。