算法设计与分析40学时课件ch1new
27页1、第一章 引 言,骆吉洲 计算机科学与工程系,1.1 Role of Algorithms in Computer Science,算法是计算机科学的主题 计算机科学体系与算法设计与分析的地位 算法设计与分析的意义,70年代前 计算机科学基础的主题没有被清楚地认清。 70年代 Knuth出版了The Art of Computer Programming 以算法研究为主线 确立了算法为计算机科学基础的重要主题 1974年获得图灵奖。 70年代后 算法作为计算机科学核心推动了计算机科学技术 飞速发展,算法是计算机科学基础的重要主题,解决一个计算问题的过程,计算机科学的体系,可计算否,可计算理论 计算模型 可计算问题/不可计算问题 计算模型的等价性-图灵/Church命题 计算复杂性理论 在给定的计算模型下研究问题的复杂性 固有复杂性 上界 下界 平均 复杂性问题的分类: P=NP? 抽象复杂性研究,算法设计和分析 可计算问题的算法的设计与分析 设计算法的理论、方法和技术 分析算法的理论、方法和技术 计算机软件 系统软件 工具软件 应用软件,1.2 Concepts of Algorithm
2、s,算法的定义 问题的定义 算法的实例,定义1.2.1(计算) 可由一个给定计算模型机械地执行的规则或计算步骤序列称为该计算模型的一个计算 注意 一个计算机程序是一个计算(计算模型是计算机) 计算可能永远不停止不是算法,算法的定义, DB-LAB (2003),定义1.2.2 (算法) 算法是一个满足下列条件的计算: 有穷性/终止性:有限步内必须停止, 确定性:每一步都是严格定义和确定的动作, 能行性:每一个动作都能够被精确地机械执行, 输入:有一个满足给定约束条件的输入, 输出:满足给定约束条件的结果。 最早的算法是欧几里德的“求最大公因子算法” 直观地说,算法如下图所示: 算法的目的是求解问题。什么是问题?,定义1.2.3 (问题) 设Input和Output是两个集合。一个问题是一个关系RInputOutput,Input称为问题R的输入集合,Input的每个元素称为R的一个输入,Output称为问题R的输出或结果集合,Output的每个元素称为R的一个结果。 注意 问题定义了输入和输出的关系。,问题的定义,例:SORT问题定义如下: 输入集合Input=|ai是整数 输出集合O
3、utput=|bi是整数, b1.bn 问题SORT=(,)|Input, Output,a1, , an=b1, , bn 定义1.2.4(问题实例) 问题P的一个实例是P的一个二元组 注意 一个算法面向一个问题,而不是仅求解一个问题的一个或 几个实例,问题定义 Input= ai是整数 output= bi是整数,且b1.bn R=(,)Input, output,a1,.,an= b1,.,bn 算法的思想扑克牌游戏,算法示例,A1,n = 5,2,4,6,1,3 A1,n = 5,2,4,6,1,3 A1,n = 2,5,4,6,1,3 A1,n = 2,4,5,6,1,3 A1,n = 2,4,5,6,1,3 A1,n = 1,2,4,5,6,3 A1,n = 1,2,3,4,5,6,算法描述 Insertion-sort(A) Input: A1,.,n=n个数 output: A1,.,n=n个sorted数 1. FOR j=2 To n Do 2. keyAj; 3. ij-1 4. WHILE i0 AND Aikey Do 5. Ai+1Ai; 6. ii-1;
《算法设计与分析40学时课件ch1new》由会员E****分享,可在线阅读,更多相关《算法设计与分析40学时课件ch1new》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课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页