面向问题求解的学习和实践

1、面向问题求解的学习和实践陶先平南京大学计算机科学与技术系目录为什么我们命名这个两年的课程是“问题求解”我们学习过哪些问题求解的基本知识？我们的问题求解能力训练到底如何？围绕问题求解的课程体系课程体系的线索课程体系主线之一：理论与方法（解决问题的方法）；课程体系主线之二：支撑与平台（平台与系统支撑）准入计算思维程序基础离散数学数字逻辑电路准出数据结构算法设计与分析计算机系统基础操作系统计算机网络计算机科学与技术专业平台课程计算机系统设计综合实验大数据处理综合实验软件工程综合实验综合实验理论与算法平台与系统“问题的求解”能力是什么？什么叫“问题的求解”？解问题的基本方法Polya的Problem

2、solving基本方法如何理解问题和制定计划问题的形式化模糊问题的数学描述基础理论数学模型算法的设计、分析及优化含设计策略、正确性证明数据结构的设计及算法的实现程序设计及优化理解问题制定计划计划执行回顾检查问题基础理论1基础理论2基础理论n1基础理论知识模型1模型2模型n1面向问题的数学模型精巧、简明、高效的编码算法1算法2算法n1面向问题的算法数据结构1数据结构2数据结构n1面向问题的数据结构程序=数据结构+算法但是：背后的数学、逻辑更为关键传统的课程体系存在的不足在于知识点及其应用在时序上有错位程序设计课程总是难以定位复杂程序难度太大，toy级程序实在无趣知识点及其应用在时序上被脱节书到用

3、时已忘了数理逻辑中的命题符号化、数学归纳法和循环不变式概率论和算法时间渐进复杂度分析知识点及其应用在安排上各自为营，效率低下课程之间边界模糊，教学目标不明确重复太多，缺失不知我们的答案是：重构知识体系：尽量围绕具体问题，从理论到模型到算法到实现开展组织和学习消除重复，避免遗漏强化应用训练，知识点学习中始终贯穿应用场景在解问题中，不断运用以前学过的知识点以程序设计能力培养为贯穿全课程的基础目标将程序语言及编程的训练隐藏到课堂讲解（引导环节）的”背面”穿插在各个课堂讲授中自学、自练将自学能力培养放到足够的高度问题1基础理论1基础理论2基础理论n1算法1算法2算法n3基础理论知识面向问题的算法模型1

4、模型2模型n2面向问题的数学模型数据结构1数据结构2数据结构n4精巧、简明、高效的编码面向问题的数据结构问题2问题n0形成全新的课程内容体系整个课程内容不是按照传统数学与计算机类课程各自的横向体系划分，而是围绕问题求解组织成四个“论域”：第一个论域“计算入门与数学证明”安排在1年级上学期；第二个论域“经典数据结构与算法”安排在1年级下学期;第三个论域“典型应用问题及其求解方法”安排在2年级上学期;第四个论域“复杂性理论初步与难问题的算法”安排在2年级下学期。上述内容涵盖了传统基础课程：程序设计、离散数学、数据结构、算法设计与分析希望新体系带来的好处：学以致用，缓解“学这些东西有啥用”的焦虑；压

5、缩冗余，接触更多的内容；学会学习，开启终身学习模式。四个论域论域1：计算入门与数学证明帮助学生理解计算思维最核心的概念，接受基本的形式化训练，掌握抽象数学证明的基本方法。论域2：经典数据结构与算法帮助学生理解抽象数据类型，理解并应用常用的数据结构掌握重要的算法设计策略以及算法设计与分析的基本理论与方法理解并能够应用支持上述内容的离散数学工具与方法。论域3：典型应用问题及其求解方法引导学生掌握典型应用中抽象出来的重要算法问题的求解方法，理解并能够应用支持上述内容的离散数学工具与方法。论域4：复杂性理论基础与“难”问题的算法涵盖问题求解中复杂性理论的基本内容与问题规约方法，解决“难”问题的主要方法

6、、技术以及相关的重要理论结果。论题的结构模型及实施方案解题能力学习能力自学材料(教材)课程讲义课外作业编程训练研讨内容经典教材摘选学生课前自学以解题为目的以深度为优先以启发为手段教师选题学生讲解教材中的习题为主覆盖全部自学内容围绕论题选编题目问题求解2年中的核心价值点形式化和证明方法抽象数据类型及数据结构算法复杂度评估算法设计策略若干经典问题的数学模型及算法难问题的“难” 以及我们的妥协妥协中的坚持所有的一切，归根结底，体现为：程序设计能力（狭义上的问题求解）形式化及证明方法命题逻辑及谓词逻辑如何用人工（数学）语言重述自然语言的事实或者过程消除歧义、严谨过程如何建立一个一致的、完备的系统基本证

7、明方法及这些方法的逻辑基础推理/演绎归纳递归、数学归纳法算法正确性证明算法复杂度评估组合和计数在算法分析中也经常用到离散概率模型随机变量、指示器随机变量、期望算法的时间渐进复杂度Worst case VS Average case VS Best case递归式求解O标记算法复杂度的若干话题问题的难度和算法的复杂度容易的问题 VS 难的问题我们的妥协数学模型、抽象数据类型及数据结构典型的离散数学模型集合及其上的关系、函数偏序、格图、树ADT的“抽象” VS 数据结构的“具体”ADT：动态集合的基本数据类型 + 独有的数据特性和基本操作维持数据特性的“建增删查改”特别的操作经典的数据结构：队列、

8、堆、栈、链表、树（基本的经典）、并查集红黑树、B树图算法设计基本策略暴力法分治法归并、快速排序、Strassen算法递归和分治的天然关联Master定理动态规划法任何一个动态规划算法都和一个递归表达式关联最优子结构特性用空间换时间：子问题拓扑排序或者子问题结果被暂存Rod-cut问题（每个人心中都必须有一个经典场景）贪心法贪心选择性质最小生成树、哈夫曼编码算法的正确性证明循环不变式反证法若干经典问题的数学模型及算法图模型及其算法集：图的建模：图本身+问题的抽象遍历：skeleton of almost every graph algorithm路径相关算法: 最短路旅行算法最大流最小割原理：最

9、大流算法匹配和覆盖算法着色若干经典问题的数学模型及算法编码及纠错代数系统、群（群的对称性）码字和Hamming 距离编码和纠错Hashing方法作用和基本原理冲突解决我们学到的仅仅是“冰山一角”矩阵计算：LUP算法线性规划松弛，simplex算法若干经典问题的数学模型及算法数论算法模算术、扩充的GCD算法，还有？费马定理和欧拉定理素数判定算法伪素数密码算法公钥体系的数学和算法基础我们把什么公布出去了？把什么藏起来了？难问题的“难” 以及我们的妥协形式化描述文字、语言、元组P、NP、NPC判定、优化问题如何证明一个问题的难我们的妥协近似、随机、启发我们在妥协中的坚持你能说出多少？问题求解能力：程序设计能力曲不离口，拳不离手程序设计能力是每个专业人才的终极能力程序设计能力的形成，始终贯穿于每一门课程中程序设计能力