数学归纳法与解题之道.ppt
《数学归纳法与解题之道.ppt》由会员分享,可在线阅读,更多相关《数学归纳法与解题之道.ppt(16页珍藏版)》请在三一文库上搜索。
1、数学归纳法与解题之道,道,贪心,构造,优化,如此之多的算法,是怎样想到的? 这些算法巧诚巧矣,可正确性怎么证明呢?,引言,道生一,一生二,二生三,三生万物。,老子:道德经,数学归纳法,概览,2.在证明算法正确性上的应用 贪心算法 其他算法,3.在构造性算法中的应用 数据结构的恢复性构造 策略与解决方案的构造,4.数学归纳法与算法优化 巧妙选择归纳对象 力求完善归纳基础 慎重选择归纳方向 适当加强归纳假设,5.启发作用与美学价值,6.问题与缺陷 理论上是否欠完备 应用上是否较繁琐 不适用的问题,1.关于数学归纳法 简短的回顾 基本的定理、概念与方法 是总结更是探索,例5(线性结构)Set Cov
2、er 例6(树状结构)Roman Roads,难,缺乏固定套路 依赖于具体的数据结构,通用灵活 适用于各种数据结构,易,构造性问题,数学归纳法,【例5】Set Cover 数据结构的恢复性构造,子集覆盖问题定义为选出尽量少的子集,使已知集合中的每个元素至少属于其中的一个。 线段覆盖问题定义为选出尽量少的整点,使给定的每条线段上都至少有其中的一个。 以整点为子集,所有包含这个整点的线段为子集中的元素,可以把一个线段覆盖问题归约到子集覆盖问题。如果给定一个由线段覆盖问题归约成的子集覆盖问题,该怎么解决呢?,线段覆盖问题,在数轴上选出尽量少的整点 给定的每条线段上必须至少有其中的一个 按左端点排序后
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 归纳法 解题
链接地址:https://www.31doc.com/p-4295637.html