授课内容【按照层次分】 设计理论 算法分析与设计 分析方法 实现技术 测试技术 应用范围 请华大学 宋斌恒 Contents【按照内容分】 教学目的 ■ Divide and conquer【分治】 理论分析能力培养:掌握算法分析与设计的基 ■ Dynamic Programming【动态规划】 本理论和方法,具有设计新算法和分析复杂性 ■ Greedy method【贪婪算法】 的能力 ■ Amortized Analysis【均摊分析法】 ■实践能力的培养:学会如何实现设计好的算 ■ Algorithms in Graphics【图论中算法】 法,如何测试其正确性和效率,应用与实际问 ■ NP-Completeness【NP完全问题,算法理 题 团队能力培养:和各种人员合作工作能力 ■ Selected Topics【专题讲座】 ■交流能力的培养:表达和接受能力 ■ Comprehensive Training【综合训练】 ■独立研究能力培养:具有独立开展研究的能力 上课的必要条件 基本要求 ■数据结构(没修过的请修过后再选) 上课不应迟到,迟到一次扣1分,自己申报,如果迟到 ■掌握一门对面向对象编程语言(C+十或 没有申报被发现扣10分 不得抄袭、剽窃。参考文献、著作、教材和包括其它 Java 同学的作业在内的所有资 ■文献、著作、教材类公开出版的参考资料,按照文献索 网络资料,除指出网络路徑URL,还应当提供资料电子 参考同学作业应当指出作业编号和提供原作业拷贝。多 人讨论的成果,应当在作业中反映 ■引用他人成果而没有指出出处的以抄袭论处。如有 次发现,总成绩减去该阶段分值 现,成绩记0分,并以考试作弊向上汇报
1 算法分析与设计 清华大学 宋斌恒 清华大学 宋斌恒 2 授课内容【按照层次分】 n 设计理论 n 分析方法 n 实现技术 n 测试技术 n 应用范围 清华大学 宋斌恒 3 Contents【按照内容分】 n Divide and conquer【分治】 n Dynamic Programming【动态规划】 n Greedy method【贪婪算法】 n Amortized Analysis【均摊分析法】 n Algorithms in Graphics【图论中算法】 n NP-Completeness【NP完全问题，算法理 论】 n Selected Topics【专题讲座】 n Comprehensive Training【综合训练】 清华大学 宋斌恒 4 教学目的 n 理论分析能力培养：掌握算法分析与设计的基 本理论和方法，具有设计新算法和分析复杂性 的能力 n 实践能力的培养：学会如何实现设计好的算 法，如何测试其正确性和效率，应用与实际问 题 n 团队能力培养：和各种人员合作工作能力 n 交流能力的培养：表达和接受能力 n 独立研究能力培养：具有独立开展研究的能力 清华大学 宋斌恒 5 上课的必要条件 n 数据结构（没修过的请修过后再选） n 掌握一门对面向对象编程语言（C＋＋或 Java） 清华大学 宋斌恒 6 基本要求 n 上课不应迟到，迟到一次扣1分，自己申报，如果迟到 没有申报被发现扣10分。 n 不得抄袭、剽窃。参考文献、著作、教材和包括其它 同学的作业在内的所有资料，必须指明出处。其中 n 文献、著作、教材类公开出版的参考资料，按照文献索 引方式引用。有可能的话最好提供电子拷贝。 n 网络资料，除指出网络路径URL，还应当提供资料电子 拷贝。 n 参考同学作业应当指出作业编号和提供原作业拷贝。多 人讨论的成果，应当在作业中反映。 n 引用他人成果而没有指出出处的以抄袭论处。如有抄 袭，第一次发现，总成绩减去该阶段分值，第二次发 现，成绩记0分，并以考试作弊向上汇报
鼓励 教学网站 ■创新 ■清华大学网络学堂 ■提出问题 ■讨论 ■根据平时情况,可以得到加分 主要参考书 综合训练报告框架和要求 m Introduction to algorithms, Thomas H. Cormen, etc. second edition. the mit Press 这问药签漆(密是委要的扫细 m The Art of Computer Programming, Donald E. 该向念 Knuth. Volume 1-3. Second m Data Structures, Algorithms 4法考与需(影是用hc in C++(Part 3)Sartaj Sahni ■算法设计与分析,王晓东,清华大学出版社 6"提出 综合训练问题集 综合练习问题集【续】 ■大整数运算【大整数 法、减法、乘法、除 字符串【模式】匹配 法、密指数,及其模运算下的上述运算】 字符串相似度理论【字符串距离编辑等】 ■密码支撑运算1【随机数生成】 ■密码支撑运算2【素数生成算法】 索引与查找 ■密码支撑运算3【标准和经典文献算法5个左右Hash运 图文排版优化 网络任务调度 ■对称加密算法【标准和经典文献算法5个左右对称加密 算法】 ■非对称加密算法【标准和经典文献算法5个左右非对称 加密算法】
2 清华大学 宋斌恒 7 鼓励 n 创新 n 提出问题 n 讨论 n 根据平时情况，可以得到加分。 清华大学 宋斌恒 8 教学网站 n 清华大学网络学堂 清华大学 宋斌恒 9 主要参考书 n Introduction to algorithms, Thomas H. Cormen, etc., second edition, The MIT Press. n The Art of Computer Programming, Donald E. Knuth. Volume 1-3, Second Edition. n Data Structures, Algorithms, and Applications in C++(Part 3) Sartaj Sahni, China Machine Press n 算法设计与分析，王晓东，清华大学出版社 清华大学 宋斌恒 10 综合训练报告框架和要求 1. 问题表述 2. 该问题的研究历史综述【该问题与参考资料的关系】 1. 该问题的最新算法【如果有比上述典型算法效率更好的算法】介绍 3. 该问题的典型算法介绍： 1. 该算法主要思想 2. 算法描述 3. 算法正确性说明或者证明 4. 算法复杂度理论分析 5. *涉及到的理论方法总结和推广 4. 算法的实现与测试【分别用Java和C＋＋】： 1. 算法接口设计 2. 算法使用说明 3. 典型算法的实现，包括异常处理和性能估计 4. 典型算法实现的测试分析报告： 1. 结果是否正确？ 2. 不同规模输入情况下的效率分析 ，是否与理论分析一致 ，如果不一致， 为什么 ？ 5. 该问题的应用介绍： 1. 应用背景，使用条件等等 2. *部分典型算法的演示软件。 6. *提出该问题自己的算法 7. 参考资料 清华大学 宋斌恒 11 综合训练问题集 n 大整数运算【大整数表示、加法、减法、乘法、除 法、密指数，及其模运算下的上述运算】 n 密码支撑运算1【随机数生成】 n 密码支撑运算2【素数生成算法】 n 密码支撑运算3【标准和经典文献算法5个左右Hash运 算】 n 对称加密算法【标准和经典文献算法5个左右对称加密 算法】 n 非对称加密算法【标准和经典文献算法5个左右非对称 加密算法】 清华大学 宋斌恒 12 综合练习问题集【续】 n 字符串【模式】匹配 n 字符串相似度理论【字符串距离编辑等】 n 索引与查找 n 图文排版优化 n 网络任务调度
综合练习问题集【续2】 课程安排介绍 ■图的所有点最短距离问题 ■前面以介绍设计方法为主 应用:纹理合成中的缝合法。 ■后面以解决问题为主 ■贪婪算法理论: Matroid、 Greedoid、 GreedSet ■旅行商问题【精确解、近似解】 ■背包问题【同上】 算法简介 本课程要回答算法的几个基本问题 ■什么是算法 一个定义好的用来计算,或者 会停下来吗? 駕过奚家最黑架过寯鳇锽焱踅聳榮蕈♂ 进制的加法来说明问题 它的结果正确吗? 1001101110 它运算快吗? +111011010001 它使用了多少内存? ■=1001110101110 进一步我们需要回答: ■i=0;计++;i< Length(第二个数) 它能够应用到那些领域? ■如果第二个数=1plus(第一个数,D) 利用不同语言实现需要那些技巧? ■plus(数,i): ∥在数的第位加1 ■如果数[]==1数=0plus(数,计+1) 算术 进制问题 ■历史上,算术运算是一件非常有意思的工作, ■中国一直使用十进制来表示数字,而通过算盘 见在看起来人人都会用的算术,其广泛应用也 这种2-5-10进制可以进行快速算术计算,宋 只是最近的事。算术的关键是表示,如十进 朝开始普及。 制、罗马进制。利用罗马进制进行算术运算并 不是一件轻松的事
3 清华大学 宋斌恒 13 综合练习问题集【续2】 n 图的所有点最短距离问题 n 应用：纹理合成中的缝合法。 n 图的单源最短路径 n 贪婪算法理论：Matroid、Greedoid、GreedSet n 旅行商问题【精确解、近似解】 n 背包问题【同上】 n 自选 清华大学 宋斌恒 14 课程安排介绍 n 前面以介绍设计方法为主 n 后面以解决问题为主 清华大学 宋斌恒 15 算法简介 n 什么是算法：算法是一个定义好的用来计算，或者更 加一般地说，是用于把一定的输入转换成需要的输出 的过程。大家最熟悉不过的算法就是算术中的加法和 乘法。下面我们通过一个二进制的加法来说明问题： n 10011011101 n ＋ 111011010001 n ＝1001110101110 n 算法：一个循环： n i=0; i++; i<length(第二个数): n 如果第二个数[i]==1 plus(第一个数, i) n plus(数，i)： //在数的第i位加1 n 如果 数[i]==1 数[i]=0; plus（数，i＋1）； 清华大学 宋斌恒 16 本课程要回答算法的几个基本问题 n 它会停下来吗？ n 它的结果正确吗？ n 它运算快吗？ n 它使用了多少内存？ n 进一步我们需要回答： n 它能够应用到那些领域？ n 利用不同语言实现需要那些技巧? 清华大学 宋斌恒 17 算术 n 历史上，算术运算是一件非常有意思的工作， 现在看起来人人都会用的算术，其广泛应用也 只是最近的事。算术的关键是表示，如十进 制、罗马进制。利用罗马进制进行算术运算并 不是一件轻松的事。 清华大学 宋斌恒 18 进制问题 n 中国一直使用十进制来表示数字，而通过算盘 这种2－5－10进制可以进行快速算术计算，宋 朝开始普及
半坡时代 商朝 ■中国最早使用十进制,可以追溯到半坡时代 ■到了商朝(约公元前1400年),出现了甲骨 (约公元前4000年,陕西地区) ■根据出土的陶器上面记录的数字符号,半坡人 京:自甲学片街专计将粤进弃通进这出得考 至少掌握了三十以内的自然数,并且使用十进 基本数字的组合可以记录高达几万的整数(1) 制计数(1) ■说明这时的人已经有了“位”的概念。周朝《周 ■不过这时候的计数称之为十进制有一些勉强。 易》书中,就有“万有一千五百二十”的记载 因为它还没有“零”和“空位”的概念 ■半坡人只会记录“10°,“"20",“30”这些整十倍的 数,而对于其他十以上的数就没有办法了。 春秋战国时期 汉代 ■到春秋战国时期出现了“算筹”这种计算工具。算筹分横 ■汉代蔡伦(约公元100年)发明造纸术,大大 式和纵式两种摆法。在计数时个位放纵式,十位放横 推动了数学的发展。不久之后为了避免混淆采 就表示中间存在一个空位1)。空位”概念的出现,应 用方框来表示空位,后来又演变为圆圈(1)。可 该是现代计数方法的一个里程碑。根据《孙子算经》 以说,完备的十进制计数法最终形成了 中记载:“凡算之法,先识其位,一从十横,百立 僵,千十相望,万百相当”。可以说,这时候的计数虽 然还没有表示“零”的符号,但已经意识到了“零”这个概 念。除了不能准确表达多个连续的空位等问题以外 与阿拉伯十进制计数已己经没什么区别了。这个时期的 田齐量制,也采用了 石"的十进位制(4),可见 十进制在这个时期开始已经开始被广泛应用了 全球 参考文献 ■作为四大文明古国之一,中国在十进制计数方 ■(1)潘天骥,十进位值制的记数法首创于中国,九江 面走在了最前面。古巴比伦人(公元前2400~ 师专学报,1995年05期 前1600年)使用的是六十进制:古埃及(公元 (2)王永建,进位制的由来,江苏教育,1997年01期 前1850~前1650年)的数学虽然以十为基 (3) C Marchal,刘义燧,计数法的简史及展望,自然 数,但没有形成“位”的概念:而印度直到公元 825年才有著作描述了“完备的印度数系1),我 ■(4)宁可,有关汉代农业生产的几个数字 们所采用的阿拉伯数字及计数法,便是这之前 sp? (约公元600年)由印度经阿拉伯流传到 NewsID=455&BigclassID=26&SmalIC 世界各地的(3)。 ■(⑤)数学大事年表 ttp: l/ ljamesjoe 51. net/refrence/matheven html
4 清华大学 宋斌恒 19 半坡时代 n 中国最早使用十进制，可以追溯到半坡时代 （约公元前4000年，陕西地区）。 n 根据出土的陶器上面记录的数字符号，半坡人 至少掌握了三十以内的自然数，并且使用十进 制计数⑴。 n 不过这时候的计数称之为十进制有一些勉强。 因为它还没有“零”和“空位”的概念。 n 半坡人只会记录“10”，“20”，“30”这些整十倍的 数，而对于其他十以上的数就没有办法了。 清华大学 宋斌恒 20 商朝 n 到了商朝（约公元前1400年），出现了甲骨 文。甲骨文比半坡计数更进了一步，出现了表 示“百”“千”“万”的专门符号，并通过这些符号与 基本数字的组合可以记录高达几万的整数⑴。 n 说明这时的人已经有了“位”的概念。周朝《周 易》书中，就有“万有一千五百二十”的记载。 清华大学 宋斌恒 21 春秋战国时期 n 到春秋战国时期出现了“算筹”这种计算工具。算筹分横 式和纵式两种摆法。在计数时个位放纵式，十位放横 式，依此类推。若是两个横式或者纵式连在了一起， 就表示中间存在一个“空位”⑴。“空位”概念的出现，应 该是现代计数方法的一个里程碑。根据《孙子算经》 中记载：“凡算之法，先识其位，一从十横，百立千 僵，千十相望，万百相当”。可以说，这时候的计数虽 然还没有表示“零”的符号，但已经意识到了“零”这个概 念。除了不能准确表达多个连续的空位等问题以外， 与阿拉伯十进制计数已经没什么区别了。这个时期的 田齐量制，也采用了“升— 斗— 石”的十进位制⑷，可见 十进制在这个时期开始已经开始被广泛应用了。 清华大学 宋斌恒 22 汉代 n 汉代蔡伦（约公元100年）发明造纸术，大大 推动了数学的发展。不久之后为了避免混淆采 用方框来表示空位，后来又演变为圆圈⑴。可 以说，完备的十进制计数法最终形成了。 清华大学 宋斌恒 23 全球 n 作为四大文明古国之一，中国在十进制计数方 面走在了最前面。古巴比伦人（公元前2400～ 前1600年）使用的是六十进制；古埃及（公元 前1850～前1650年）的数学虽然以十为基 数，但没有形成“位”的概念；而印度直到公元 825年才有著作描述了“完备的印度数系”⑴，我 们所采用的阿拉伯数字及计数法，便是这之前 不久（约公元600年）由印度经阿拉伯流传到 世界各地的⑶。 清华大学 宋斌恒 24 参考文献 n ⑴ 潘天骥，十进位值制的记数法首创于中国，九江 师专学报，1995年05期 n ⑵ 王永建，进位制的由来，江苏教育，1997年01期 n ⑶ C.Marchal.，刘义燧，计数法的简史及展望，自然 杂志，1995年05期 n ⑷ 宁可，有关汉代农业生产的几个数字 n http://www.guoxue.com/economics/ReadNews.asp? NewsID=455&BigClassID=26&SmallClassID=44&Sp ecialID=120 n ⑸ 数学大事年表 http://jamesjoe.51.net/refrence/matheven.html
算盘 陈聪同学2004年秋天的文献综述 ■算盘被誉作中国贡献于世界的“第五大发明”, 陶丸是珠算工具的这种说法,可以在网上搜索到很 谓地道中国特产了 多,姑且找一个比较权威的网站。新华网2003年10月 ■随着对陕西歧山出土文物西周陶丸的研究,中 2日报道“记者日前在岐山县采访时获悉,全县最小的 乡一-一京当乡近年来出土了大批的珍贵文物,其中 国算盘的发明时间已经提前到二千多年前的西 有18件占据了中国考古之最”,“出土的陶丸,是我国 周时期。陕西岐山县西周宫室遗址中出土的90 最早的计算工具算珠"。标明稿件来源:西安晚报。① “中国珠算协会副会长、陕西数学史研究会会长李培业 有学术争论】 对数学史最大的贡献是在珠算史研究方面”,“根据陕西 岐山县西周宫室遗址中出土的90粒青黄两色陶丸 合《数术记遗》中对珠算算具的文字注释,证明了这 是珠算工具,从而把中国古珠算的历史年代推前了 1000余年,证明中国是最早发明珠算的国家② 续 ■可见,新华网的这种说法的根据是李培业先生 的研究结果。而李培业的文章《对西周宫室j 法。1996年12月11日至13日在陕西省岐山县召开的 址出土陶丸之考察》发表于1984年《珠算》04 珠算协会第四届珠算史 员会暨陶丸鉴定 同时期研究者发表类似意见的文章还 算"有关,而不是珠算 西周原岐山文管所刘亮的《试说周原遗址出 世玉的《驳西周陶丸异义》 土的陶丸》(《珠算》1984年04期),户谷清 期)也认为陶丸与珠算无关 (日本)的《从西周宫室遗址出土的陶丸探 芋深算存法关使楚陶充建为种球算的 索算盘的起源》(《珠算》1985年05期,《齐 算珠"⑤:王为桐,王世玉和公维萍更是认为西周陶丸 鲁珠坛》1994年04期)③,以及姜克华的《西 不是珠算用珠,而是弹丸⑥ 周陶丸之研究》(《齐鲁珠坛》1994年02期) ■从以上资料可以看出,学术界对于西周陶丸究竟何用 等等。 并无一个统一的说 参考文献 Some of major successes field 生网两续山最小台出31物 中国考古之最》 a Parsing algorithms-these form the basis of the field of programming languages a Fast Fourier transform-the field of digital signal processing is built upon this algorith ■③齐鲁珠坛,1997年04期,王为榈,王世玉,贺西周陶丸研究的 ■ Line: rithm is ■④齐鲁珠坛,1997年06期,王为榈,王世玉,驳西周陶丸异义 extensively used in resource scheduling ⑤陕西经贸学院 E学报, 7年03期,张福汉,肖宗史,岐山西 a Sorting algorithms-until recently, sorting used up the bulk of computer cycles 齐鲁珠坛,1999年01期,王为桐,王世玉,公维萍,西周陶丸 用途的结论 a String matching algorithms-these are extensively used in computational biology
5 清华大学 宋斌恒 25 算盘 n 算盘被誉作中国贡献于世界的“第五大发明”， 可谓地道中国特产了。 n 随着对陜西歧山出土文物西周陶丸的研究，中 国算盘的发明时间已经提前到二千多年前的西 周时期。陕西岐山县西周宫室遗址中出土的90 粒青黄两色陶丸，青色20粒，黄色70粒。【但 有学术争论】 清华大学 宋斌恒 26 陈聪同学2004年秋天的文献综述 n “陶丸是珠算工具”的这种说法，可以在网上搜索到很 多，姑且找一个比较权威的网站。新华网2003年10月 2日报道“记者日前在岐山县采访时获悉，全县最小的 乡―――京当乡近年来出土了大批的珍贵文物，其中 有18件占据了中国考古之最”，“出土的陶丸，是我国 最早的计算工具算珠”。标明稿件来源：西安晚报。① “中国珠算协会副会长、陕西数学史研究会会长李培业 对数学史最大的贡献是在珠算史研究方面”，“根据陕西 岐山县西周宫室遗址中出土的90粒青黄两色陶丸，结 合《数术记遗》中对珠算算具的文字注释，证明了这 是珠算工具，从而把中国古珠算的历史年代推前了 1000余年，证明中国是最早发明珠算的国家”② 清华大学 宋斌恒 27 续 n 可见，新华网的这种说法的根据是李培业先生 的研究结果。而李培业的文章《对西周宫室遗 址出土陶丸之考察》发表于1984年《珠算》04 期，同时期研究者发表类似意见的文章还有： 陕西周原岐山文管所刘亮的《试说周原遗址出 土的陶丸》（《珠算》1984年04期），户谷清 一（日本）的《从西周宫室遗址出土的陶丸探 索算盘的起源》（《珠算》1985年05期，《齐 鲁珠坛》1994年04期）③，以及姜克华的《西 周陶丸之研究》（《齐鲁珠坛》1994年02期） 等等。 清华大学 宋斌恒 28 n 而近十年来考古界的研究成果，很多都否定了这种说 法。1996 年12 月11 日至13 日在陕西省岐山县召开的 “中国珠算协会第四届珠算史专业委员会暨陶丸鉴定会” 认为陶丸与“三才算”有关，而不是珠算。④王为桐和王 世玉的《驳西周陶丸异义》（《齐鲁珠坛》1997年06 期）也认为陶丸与珠算无关。 n 考古界对此看法纷纭。张福汉和肖宗史认为“三才算”也 属于“珠算”的范畴，关键是确定陶丸是“哪一种珠算的 算珠”⑤；王为桐，王世玉和公维萍更是认为“西周陶丸 不是珠算用珠, 而是弹丸”⑥ n 从以上资料可以看出，学术界对于西周陶丸究竟何用 并无一个统一的说法。 清华大学 宋斌恒 29 参考文献 n ①新华网《陕西岐山最小乡出土18件文物居中国考古之最 》 http://www.xinhuanet.com/chinanews/2003- 10/23/content_1094597.htm n ②新华网《康熙数学专著发现经过大解密》 http://news.xinhuanet.com/newscenter/2003- 03/03/content_755023.htm n ③齐鲁珠坛，1997年04期，王为桐，王世玉，贺西周陶丸研究的 突破 n ④齐鲁珠坛，1997年06期，王为桐，王世玉，驳西周陶丸异义 n ⑤陕西经贸学院学报，1997年03期，张福汉，肖宗史，岐山“西 周陶丸”再考 n ⑥齐鲁珠坛，1999年01期，王为桐，王世玉，公维萍，西周陶丸 用途的结论 清华大学 宋斌恒 30 Some of major successes fields n Parsing algorithms - these form the basis of the field of programming languages n Fast Fourier transform - the field of digital signal processing is built upon this algorithm. n Linear programming - this algorithm is extensively used in resource scheduling. n Sorting algorithms - until recently, sorting used up the bulk of computer cycles. n String matching algorithms - these are extensively used in computational biology
Number of major successes fields Related aspect a Number theoretic algorithms-these a Abstract model of computer: algorithms make it possible to implement a High level of languanges cryptosystems such as the RSA public key cryptosystem ion algorithms-these algorithms allow us to transmit data more efficiently over for example phone lines a Geometric algorithms- displaying images quickly on a screen often makes use of nIques Divide and conquer Example of a divide and conquer a Divide and Conquer is a method Problem: sorting{12,3455,21,7,9,1,10} m Applying cases a Divide: it is too big to solve if it is smaller we A large size problem, how to solve it may solve it, so we divide it into two problem We can solve small size problems a Sub-problem1: sorting( 12, 3, 45, 5, 211 Divide it into several small size problems Solve these small size sub-problems a Sub-problem2: sorting(7, 9, 1, 101 a Next, what shall we do? the original problem 1. Merge(A, B)lIA and B are two sorted Arrays C lito store the result =0∥ index of o I Conquer: we use some methods(any kind of While not end of A and B /r<A length& S<Blength to solve it and get the sub-problems'solutions If(Ar]<B(s) then that means we sort the two sub-problems Solution of sub-problem 1: (3, 5, 12, 21, 45) a Solution of 1,7,9,10} we should use these two solutions Append B(s,., B length-1]to C see next page Append A(r, -. Alength-1]to C
6 清华大学 宋斌恒 31 Number of major successes fields n Number theoretic algorithms - these algorithms make it possible to implement cryptosystems such as the RSA public key cryptosystem. n Compression algorithms - these algorithms allow us to transmit data more efficiently over, for example, phone lines. n Geometric algorithms - displaying images quickly on a screen often makes use of sophisticated algorithmic techniques. 清华大学 宋斌恒 32 Related aspect n Abstract model of computer: n High level of languanges 清华大学 宋斌恒 33 Divide and Conquer n Divide and Conquer is a method n Applying cases: n A large size problem, how to solve it? n We can solve small size problems! n Divide it into several small size problems, n Solve these small size sub-problems! n Next, what shall we do? n Combine the sub-solution to get the solution of the original problem. 清华大学 宋斌恒 34 Example of a Divide and Conquer n Problem: sorting {12,3,45,5,21,7,9,1,10} n Divide: it is too big to solve, if it is smaller we may solve it, so we divide it into two problem: n Sub-problem1: sorting{12,3,45,5,21} n Sub-problem2: sorting{7,9,1,10} 清华大学 宋斌恒 35 n Conquer: we use some methods (any kind of) to solve it and get the sub-problems’solutions, that means we sort the two sub-problems: n Solution of sub-problem1:{3,5,12,21,45} n Solution of sub-problem2:{1,7,9,10} n Combine: we should use these two solutions to construct the solution of the original problem, see next page 清华大学 宋斌恒 36 1. Merge(A, B) //A and B are two sorted Arrays 1. r=s=0; 2. Create array C //to store the result 3. i=0 //index of C 4. While not end of A and B //r<A.length & s<B.length 1. If(A[r]<B[s]) then 1. C[i]=A[r]; 2. r++; i++; 2. Else 1. C[i]=B[s]; 2. s++; i++; 5. If(r==A.length) 1. Append B[s,… ,B.length-1] to C 6. Else 1. Append A[r,… ,A.length-1] to C 7. Return C
Solution Correctness a Using the merge algorithm we get the Is your solution correct? olution:{1,357,910.122145} erge algorithm ■ Any left problems? array in any case? a How to fulfill the condition m Using other method a Using the same divide and conquer method To a trivial state: for example there are only one element for sorting Complexity Analysis Notation e a How many memories does the algorithm use? a If there exists two positive constants c and d such a How many steps does the algorithm use? that when n tends to infinity we have cg(n)sf(n)< m Let T(n) be the number of steps used in the algorithm g(n) then we call g(n) is an asymptotically tigh an array of length n, then we know that by the divide and conquer that f(n)=e(g(n)) B T(n=2T(n/2)+en), where e is an asymptotic a Other notations ofnot tight upper bound o(upper expression means tighten bound, its definition will be bound] and Q lower bound], o[not tight lower bound the next page【我们假设每次均分,而且正好 can be found in p. 41 in the reference book. 可以均分】 Left problems Exercise a What is the upper bounds and lower bounds for the a Big integers expression, addition and orting problem? multiplication in a 32-bits microcomputer. a How to solve the recursive equality(or inequality)? (n)=2T(n2)+n) a How to express a big integer? a How to converge the above equality to a well posed a We use an n-length of array of integers A[O,... n-1]to express a big integer which is a How to solve the problem? (Master theorem see p 76 less than or equal to 232(n+1-1 but is bigger than 232n
7 清华大学 宋斌恒 37 Solution! n Using the merge algorithm we get the solution:{1,3,5,7,9,10,12,21,45} n Any left problems? 清华大学 宋斌恒 38 Correctness n Is your solution correct? n Does your merge algorithm outcome a sorted array in any case? n Is the condition for merge algorithm fulfilled? n How to fulfill the condition? n Using other method n Using the same divide and conquer method n To a trivial state: for example there are only one element for sorting. 清华大学 宋斌恒 39 Complexity Analysis n How many memories does the algorithm use? n How many steps does the algorithm use? n Let T(n) be the number of steps used in the algorithm for an array of length n, then we know that by the divide and conquer that: n T(n)=2T(n/2)+Q(n), where Q is an asymptotic expression means tighten bound, its definition will be given in the next page【我们假设每次均分，而且正好 可以均分】 清华大学 宋斌恒 40 Notation Q n If there exists two positive constants c and d such that when n tends to infinity we have cg(n) ≤ f(n) ≤ dg(n) then we call g(n) is an asymptotically tight bounds of f(n) and denote it as f(n)= Q(g(n)) n Other notations o[not tight upper bound], O[upper bound] and W [lower bound], w[not tight lower bound] can be found in p.41 in the reference book. 清华大学 宋斌恒 41 Left problems n What is the upper bounds and lower bounds for the sorting problem? n How to solve the recursive equality(or inequality)? n T(n)=2T(n/2)+Q(n) n How to converge the above equality to a well posed problem? n How to solve the problem?[Master theorem see p.76] 清华大学 宋斌恒 42 Exercise n Big integer’s expression, addition and multiplication in a 32-bits microcomputer. n How to express a big integer? n We use an n-length of array of integers A[0,… ,n-1] to express a big integer which is less than or equal to 232(n+1)-1 but is bigger than 232n n Attention! We use 232 radix
Addition of big integer Multiplication of big integers n Can you ever do a plus for big integers? ■A=a123+a a can you do a plus for small integers which is ■B=b12325+b 32-bits or less? a Where r=A length/2, s=B length/2, hence th a How to divide the big integers summation to a size of a1. a2 are half size of a it is similar fo series of small integers summations? B, b, b2 a How to combine it together? ■AB=a1b1232++b1a2325+a1b223+a2b2 a How many steps do you use in your algorithm? Complexity analysis The above performance can be obtained by a directed method IT(n, m)the steps used for multiplication of a a Can you give a naIve algorithm for 32n-bits and 32m-bits integers multiplication of big integers? I T(n, m)=4T(n/2, m/2)+e(m+n) ■Letn= m then ■T(n)=4T(n/2)+e) ■T(n)=e(n2) An improved algorithm We need only 3 multiplications ■A=a123+a2 ■U=a1b1 ■B=b1232+b2 I Let n=A length= B length and r=n/2, (b1a2+a1b2)=(a1+a2)(b1+b2)uv m AB=a, b,264+(b, a2 +a, b2)232+a2 b2 a We needs only 3 multiplications to get: a We can converge the multiplication to 4 smaller integers multiplications and 3 a,b,,a2 b2,(b,a2 +a, b2) summations ■ Can we do better? 身手武学城制
8 清华大学 宋斌恒 43 Addition of big integer n Can you ever do a plus for big integers? n can you do a plus for small integers which is 32-bits or less? n How to divide the big integers summation to a series of small integers summations? n How to combine it together? n How many steps do you use in your algorithm? 清华大学 宋斌恒 44 Multiplication of big integers n A=a1 232r + a2 n B=b1 232s + b2 n Where r=A.length/2, s=B.length/2, hence the size of a1, a2 are half size of A, it is similar for B, b1 , b2 n AB=a1 b1 232(s+r) +b1 a2 232s +a1 b2 232r +a2 b2 n Converge the multiplication to 4 smaller integers multiplications and summations 清华大学 宋斌恒 45 Complexity analysis n T(n,m)----the steps used for multiplication of a 32n-bits and 32m -bits integers n T(n,m)=4T(n/2,m/2)+Q(m+n) n Result? n Let n=m then n T(n)=4T(n/2)+Q(n) n T(n)= Q( n2 ) 清华大学 宋斌恒 46 The above performance can be obtained by a directed method n Can you give a naïve algorithm for multiplication of big integers? 清华大学 宋斌恒 47 An improved algorithm n A=a1 232r + a2 n B=b1 232r + b2 n Let n=A.length= B.length and r=n/2, n AB=a1 b1 264r +(b1 a2 +a1 b2 ) 232r +a2 b2 n We can converge the multiplication to 4 smaller integers multiplications and 3 summations n Can we do better? 清华大学 宋斌恒 48 We need only 3 multiplications! n u= a1 b1 n v= a2 b2 n (b1 a2 +a1 b2 ) =(a1 + a2 ) (b1 + b2 )-u-v n We needs only 3 multiplications to get: n a1 b1 , a2 b2 , (b1 a2 +a1 b2 )
More Divide conquer examples a Can you give more? 二路归并排序 ■最接近点对 ■二分搜索
9 清华大学 宋斌恒 49 More Divide Conquer Examples n Can you give more? n 二路归并排序 n 最接近点对 n 二分搜索