[工学]算法设计与分析第一章.pptVIP

注意!!! 与数据结构课程的不同 考察感兴趣的问题. 设计解决这些问题的算法. 证明这些算法的正确性. 分析其资源使用情况 (时间, 内存). 理解数据结构及核心算法. 了解解决问题的技巧. 观察在现实世界的应用情况. 非常熟知核心算法集. 熟练使用算法设计方法学： 分治，贪心，随机，动态规划，分支限界，回溯， 近似方法. 对给定算法要能够分析其正确性及运行性能. 能够将所学技巧应用于实际问题中. 算法设计与分析 王晓东编著 清华大学出版社 算法设计与分析基础 （美）Anany Levitin著 清华大学出版社 Introduction to Algorithms, 2nd Ed. by Cormen, Leiserson, Rivest, Stein (CLRS) 算法引论（6学时） 递归与分治策略（8学时） 动态规划（8学时） 贪心算法（6学时） 回溯法（6学时） 分支限界法（4学时） 概率算法（4学时） NP完全理论（4学时） 近似算法（4学时） 算法优化策略（4学时） 假如你因故迟到了或必要提早离开，请轻轻入座或离座。 作业要求工整，正式。请用A4纸，多页时请用钉书机订在一起。 请积极参与课堂讨论。 谢谢！ 算法是一系列解决问题的清晰指令，即对符合一定规范的输入，在有限时间内获得所要求的输出。 算法的每个步骤都必须清晰、明确，不允许有半点含糊。 算法所处理的值域必须仔细定义。 同样一种算法可以用不同的形式描述。 同一个问题可能存在不同的解决算法。 针对同一个问题的不同算法不仅会基于完全不同的解题思路，而且解题速度可能有显著差别。 计算两个整数的最大公约数 gcd(m,n) gcd(60,24) = 算法 Euclid(m，n) //使用欧几里德算法计算gcd(m,n) //输入：两个不全为零的非负整数m,n //输出：m,n的最大公约数 while n 0 do r ? m mod n m ? n n ? r return m 算法思想 基于最大公约数的定义：同时整除两个整数 显然，不会大于两数较小者。故令： t = min{m,n} 用t 除m，n，若除尽，t 即最大公约数；否则 令： t = t -1，继续尝试。 gcd(60,24) = gcd(60,24) = 算法思想 首先初始化一个2~n的连续序列，作候选质数。 第一个循环消去2的倍数； 然后，指向序列的下一个数字3，消去其倍数； 接下来指向5，消去其倍数； 按此方法不断做下去，直到序列中没有可消元素。 例子：找出不大于 n=24 的质数序列 算法 Sieve(n) //实现埃拉托色尼筛子 //输入：一个正整数 n ≧2 //输出：包含所有小于等于n的质数的数组L for p ? 2 to n A[p] ? p for p ? 2 to [√n ] do if A[p] ≠ 0 // p没有被前面步骤消去 j ? p*p while j ≦ n do A[j] ? 0 // 将该元素标注为已消去 j = j + p //将A中剩余的元素复制到质数数组L中 输入：有零个或多个输入量作为算法所要求的 初始信息，它们取自某一特定的集合。 输出：算法至少产生一个量作为输出。 确定性：组成算法的每个动作必须清晰无 歧义，且是基本可精确进行的。 有穷性：算法对任一合法输入，必须在执行有 穷步后终止。 从机器语言到高级语言的抽象 自然语言 提出疑问 冯.诺依曼机器 （RAM模型）：顺序算法 并行算法 精确算法 近似算法 算法的四大特性 1.2 算法的表达 表达算法的抽象机制 抽象数据类型 1.2 算法的表达 算法描述 伪代码 1.3 算法的设计和分析过程 一个好的算法是反复努力和重新修正的结果 理解问题 决策： 计算方法； 精确解和近似解； 数据结构； 算法设计技术 设计算法 正确性证明 分析算法 根据算法写代码 1.3 算法的设计和分析过程 寻找已知算法 理解问题 仔细确定算法的输入范围 了解计算设