屈婉玲版算法分析与设计课件 1309-1401学期

在所提供的文档中，有关“算法分析与设计”课程的相关知识点被详细地展示了出来。下面将根据文件提供的信息来详细说明这些知识点。 文档开头提到了课程的授课教师屈婉玲教授以及其在北大邮箱地址，这为我们了解课程的师资背景提供了一个途径。随后，提到了课程的具体信息，包括课程名称、课号、基本目的，以及课程的主要内容。这些信息强调了算法分析与设计课程在培养计算思维方面的核心作用，课程通过讲授组合算法设计基本技术、算法分析基本方法，以及计算复杂性理论，旨在让学生掌握一系列重要的算法知识和技巧。 紧接着，文档中介绍了计算思维的定义及其重要性。计算思维是一种运用计算机科学的基础概念去求解问题、设计系统和理解人类行为的思维活动。它不仅涉及到数学和工程思维的融合，还包括了抽象与实现、编程评价和程序优化等技能。计算思维的三种基本思维包括：用语言文字表达、具有语法与语义规则、以及推理逻辑。这些思维的共同特点在于能够用于实验观察、归纳建立概念、提出定理并验证过程。这为理解计算思维与算法设计之间的联系提供了一个理论框架。 随后，文档详细地描述了算法分析与设计课程所涉及的关键内容，包括近似算法、NP完全问题、随机算法以及计算复杂性理论等。课程内容覆盖了算法问题处理策略，比如回溯、分治策略、动态规划和贪心算法等。此外，还包含了算法设计中的数学基础知识和数据结构的基础知识。 为了方便学生深入学习，文档中还列出了相关的教材和参考书目。其中《算法设计与分析》一书由屈婉玲教授及其同事编著，是该课程的官方教材。另外，还推荐了几本在算法领域具有重要影响力的其他书籍，例如由Jon Kleinberg 和Eva Tardos撰写的《Algorithm Design》，以及由Thomas H. Cormen 等人编写的《Introduction to Algorithms》。 课程的学习安排也在此部分有所介绍，强调了课上讲授与视频答疑相结合的教学方式，并指出了成绩评定的方式，包括平时成绩和期末笔试。为了方便学生参与在线答疑，还提供了相应的网址和操作指南。 文档通过一系列“为什么要学习算法”的讨论，给出了算法研究内容和目标的实例，如调度问题、排序问题和货郎问题等。这些问题不仅仅是理论上的探讨，同时也是实际应用中常见的挑战。在这些讨论中，强调了算法设计技术、算法分析方法、问题复杂度的界定以及计算复杂性理论在算法研究中的重要性。 整个文档详细地说明了屈婉玲版算法分析与设计课程的课程目标、教学内容、教学方法和学习资源，为学生提供了丰富的学习材料和明确的学习路径。通过这些内容，学生不仅能够掌握算法分析与设计的基本知识，还能够在实际问题中应用计算思维，解决实际问题。