算法设计与分析_屈婉玲_北京大学课件.pdf

发布时间：2022-06-14 发布人：admin 分类：说明书资料大小：3.29M 资料格式：pdf 举报版权申诉

a9ae7fcd-384b-4e25-872a-929cf0b504d3.pdf-第1页.png

第1页 / 共468页

a9ae7fcd-384b-4e25-872a-929cf0b504d3.pdf-第2页.png

第2页 / 共468页

a9ae7fcd-384b-4e25-872a-929cf0b504d3.pdf-第3页.png

第3页 / 共468页

a9ae7fcd-384b-4e25-872a-929cf0b504d3.pdf-第4页.png

第4页 / 共468页

a9ae7fcd-384b-4e25-872a-929cf0b504d3.pdf-第5页.png

第5页 / 共468页

a9ae7fcd-384b-4e25-872a-929cf0b504d3.pdf-第6页.png

第6页 / 共468页

a9ae7fcd-384b-4e25-872a-929cf0b504d3.pdf-第7页.png

第7页 / 共468页

a9ae7fcd-384b-4e25-872a-929cf0b504d3.pdf-第8页.png

第8页 / 共468页

ss-lecture1

ss-lecture2

ss-lecture3

ss-lectuer4

ss-lecture5

ss-lecture6

ss-lecture7

ss-lecture8

ss-lecture9

算法分析与设计算法分析与设计屈婉玲 d l@ k qwl@pku.edu.cn

计算思维与人才培养计算维与才养年月周真(J • 2006年3月周以真(Jeannette M. Wing，卡内基⋅梅隆大 g 卡内梅隆大学计算机系系主任)首次提出Coputational Thinking的概念：运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为它包括了涵盖计算机科学之广度统和理解人类的行为，它包括了涵盖计算机科学之广度的一系列思维活动。数学思维与工程思维的互补与融合：抽象与实现编程评价程序优化程序问题分析方法确定技能：会做能力：做得好思维：认知、方法论

三种基本的思维 • 三种思维的共同特点：用语言文字表达有语法与语义规则推逻辑用语言文字表达、有语法与语义规则、推理逻辑实验思维实验思维理论思维理论思维计算思维计算思维起源物理学数学计算机科学 1 实验观察归纳建 1 定义概念 1.实验观察归纳建 1.定义概念 2.提出定理立简单数学公式 3.给出证明 2.导出数量关系 3.实验验证实验验证过程步骤步骤特点解释以往现象解释以往现象无矛盾预见新的现象公理集公理集可靠协调推演规则正确性依赖于公理 1 建模(约简嵌入转 1.建模(约简、嵌入、转化、仿真、…） 2.抽象与分解,控制系统复杂性复杂性 3.自动化实现… 结论表示有限性结论表示有限性语义确定性实现机械性 3

算法与计算思维算与计算维 • 算法课程是训练计算思维的重要课程；涉及到对算法课程是训练计算思维的重要课程；涉及到对问题的抽象，建模，设计好的求解方法，复杂性的控制的控制，… • 可计算性与计算复杂性：形式化、确定性、有限可计算性与计算复杂性：形式化、确定性、有限性，抽象与逻辑证明 • 算法设计与分析：抽象建模、归约、正确性证明、效率分析、… 4

课程简介课程名称：算法分析与设计 Design and Analysis of Algorithms 课号： 0A002 基本目的：掌握组合算法设计的基本技术掌握组合算法设计的基本技术掌握算法分析的基本方法了解计算复杂性理论的基本概念及其应用算复杂性论的本概念其应 5

课程主要内容近似算法 NP 完全随机理论简介理论简介算法算法问题处理策略计算复杂性理论计算复杂性理论算法分析与问题的计算复杂性算法分析方法回溯与分治策略策略规划算法分支限界分支限界动态规划贪心算法算法设计技术数学基础、数据结构数学基础、数据结构基础知识 6

教材书名:书名: 《算法设计与分析》作者：作者：屈婉玲, 刘田, 张立昂, 王捍贫出版社：出版社：清华大学出版社出版时间出版时间： 2011，2013重印 7

参考书 1. Jon Kleinberg, Eva Tardos, Algorithm Design, Addison- Wesley 清华大学出版社影印版，2006 Wesley, 清华大学出版社影印版，2006. 2. Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Introduction to Algorithms(Second Edtion), The L.Rivest, Introduction to Algorithms(Second Edtion), The MIT Press 2009. 3. 张立昂，可计算性与计算复杂性导引（第3版），北京大学出版社，2011. 4*. 堵丁柱，葛可一，王洁，计算复杂性导论，高教出版社 2002. 5*. Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press，2009. 8

分享到：

赞收藏

资料库

算法设计与分析_屈婉玲_北京大学课件.pdf

相关推荐

开发技术

热门标签

最新资料