问题求解能力漫谈 陶先平马骏 南京大学计算机系 南京大学计算机软件研究所
问题求解能力漫谈 陶先平 马骏 南京大学计算机系 南京大学计算机软件研究所
问题求解能力的重要方面 程序设计能力 ·问题的形式化能力+数学建模能力+透视数据组织的能力 +算法设计能力+高级语言写作能力 ·程序设计能力是计算机专业从业者的终极追求目标。 ·广义上讲，它的能力构成是以上5个方面，其中高级语言写作 能力是实现能力 ·狭义上的程序设计能力就是指高级程序写作能力 ·语言的不同，写作方法也有不同
问题求解能力的重要方面 程序设计能力 • 问题的形式化能力+数学建模能力+透视数据组织的能力 +算法设计能力+高级语言写作能力 • 程序设计能力是计算机专业从业者的终极追求目标。 • 广义上讲，它的能力构成是以上5个方面，其中高级语言写作 能力是实现能力 • 狭义上的程序设计能力就是指高级程序写作能力 • 语言的不同，写作方法也有不同
形式化、建模与证明能力 ·问题的形式化能力 ·果挛癸或薯蹟定备常霸￥香整篷期裴鼻雒請 的非自然语言全面、精确地描 ·问题的建模能力 。 数学模型：对大量问题（现象）的本质要素、结构、性质进行的定性（定量） 抽象描述形成的数学系统 ·问题建模：运用数学模型，对具体问题的要素、 结构、性质进行形式化 规约形成的模型。比较关注具体问题解的表现和获取方法 ·数学证明 ·基于逻辑学的证明方法，提供了进行严格的数学证明的基本手段 。1 计算机科学中，数学证明常被用于求解算法/答案的正确性、性能的界的 严格证明
形式化、建模与证明能力 • 问题的形式化能力 • 用严格定义（语法良定义，语义无歧义）的非自然语言全面、精确地描 述一个事实或者规律，通常用于问题建模和数学证明 • 问题的建模能力 • 数学模型：对大量问题(现象)的本质要素、结构、性质进行的定性(定量) 抽象描述形成的数学系统 • 问题建模：运用数学模型，对具体问题的要素、结构、性质进行形式化 规约形成的模型。比较关注具体问题解的表现和获取方法 • 数学证明 • 基于逻辑学的证明方法，提供了进行严格的数学证明的基本手段 • 计算机科学中，数学证明常被用于求解算法/答案的正确性、性能的界的 严格证明
形式化基础-集合、逻辑 ·集合 ·最基本的数学模型（语言）、基本运算 ·罗素悖论 ·基本数据结构的数学基础 ·逻辑 ·命题逻辑：逻辑推理的基础 ·逻辑连接符（真值表）、逻辑表达式、范式 ·推理规则：证明方法的逻辑基础 ·什么叫argument?什么是正确的证明？什么是正确的结论？ ·谓词逻辑：现实问题的逻辑描述工具 ·全称和存在量词 ·谓词逻辑的逻辑推理基本方法 ·布尔逻辑：数字电路的数学基础
形式化基础-集合、逻辑 • 集合 • 最基本的数学模型(语言)、基本运算 • 罗素悖论 • 基本数据结构的数学基础 • 逻辑 • 命题逻辑：逻辑推理的基础 • 逻辑连接符(真值表)、逻辑表达式、范式 • 推理规则：证明方法的逻辑基础 • 什么叫argument？什么是正确的证明？什么是正确的结论？ • 谓词逻辑：现实问题的逻辑描述工具 • 全称和存在量词 • 谓词逻辑的逻辑推理基本方法 • 布尔逻辑：数字电路的数学基础
形式化基础-证明方法 ·证明方法 ·若干种证明方法 ·直接、间接：反证法、逆否证明法、分情形证明法 ·若干种证明需求 ·唯一性、存在性、全体性 ·上述证明方法的“逻辑法理” 若干个公认 ·数学归纳法 “美”的证 ·若干种数学归纳法的版本及其适用情形 明！ ·良序公理和数学归纳法的等价性 ·数学归纳法的“逻辑法理” ·课程学习过程，若干经典的数学归纳法证明样例 ·若干经典的错误命题”的错误数学归纳法证明
形式化基础-证明方法 • 证明方法 • 若干种证明方法 • 直接、间接：反证法、逆否证明法、分情形证明法 • 若干种证明需求 • 唯一性、存在性、全体性 • 上述证明方法的“逻辑法理” • 数学归纳法 • 若干种数学归纳法的版本及其适用情形 • 良序公理和数学归纳法的等价性 • 数学归纳法的“逻辑法理” • 课程学习过程，若干经典的数学归纳法证明样例 • 若干经典的“错误命题”的错误数学归纳法证明 若干个公认 “美”的证 明！
形式化基础-算法正确性 ·循环算法正确性证明 ·什么是循环不变式？ ·循环不变式一般设置在哪里？ ·如何确定”循环不变式？ ·解空间或者问题空间搜索过程中的不变特性！和问题有关、和结论有关！ ·如何证明循环不变式？ ·数学归纳法的隐式应用」 ·递归算法的正确性证明 ·数学归纳法 ·如何分析递归算法正确性的定理”？ ·若干典型案例！汉诺塔算法、欧几里得算法等
形式化基础-算法正确性 • 循环算法正确性证明 • 什么是循环不变式? • 循环不变式一般设置在哪里？ • 如何“确定”循环不变式？ • 解空间或者问题空间搜索过程中的不变特性！和问题有关、和结论有关！ • 如何证明循环不变式？ • 数学归纳法的隐式应用！ • 递归算法的正确性证明 • 数学归纳法 • 如何分析递归算法正确性的“定理”？ • 若干典型案例！汉诺塔算法、欧几里得算法等
形式化基础 ·难”的形式化表达 ·图灵机模型 ·七元组各元素之间的关系、状态转移函数 ·确定性图灵机、非确定性图灵机 ·语言、判定、优化问题 ·问题和语言的关系 ·如何形式化定义判定问题、优化问题？ ·常见的判定/优化问题的形式模型 ·优化问题的M集合、c0st函数分别代表什么意思？ ·P、NP、NPC(H)、NPO ·上述概念的基本意义及其关系 ·如何证明某个问题的难”：归约！
形式化基础 • “难”的形式化表达 • 图灵机模型 • 七元组各元素之间的关系、状态转移函数 • 确定性图灵机、非确定性图灵机 • 语言、判定、优化问题 • 问题和语言的关系 • 如何形式化定义判定问题、优化问题？ • 常见的判定/优化问题的形式模型 • 优化问题的M集合、cost函数分别代表什么意思？ • P、NP、NPC(H)、NPO • 上述概念的基本意义及其关系 • 如何证明某个问题的“难”：归约！
建模能力-经典集合模型 ·基础数学模型 ·警接是餐的oon(简单集合模型+对象之间的关系（集 因为数据管 。 集合的势=>计数（加减法原理、容斥、鸽笼）、无穷、可数 理的需要（往 ·代数系统的元素个数很特别 往是用空间 ·关系 换时间，用 素餐委程=>关系的型构：规约了两个集合上元素之问特定 联系的存在 数据管理的 ·关系的设计：规约了两个集合上元素之间的特定关系 时间换业务 ·关系的表示 。 等价关系、划分，非常重要 逻辑的时间)〉 ·分而治之的重要数学基础 而派生出的 ·函数 不同动态集 ·两个集合上元素之间结构良好的关系：函数的良定义 合数据结构 ·(具体)函数的设计及其性质： ·单、满、双射性质及其证明 的模型基础 ·同态、同构函数的定义和证明
建模能力-经典集合模型 • 基础数学模型 • 观察(处理)对象的collection(简单集合模型)+对象之间的关系(集 合模型的延伸) • 集合的势=>计数(加减法原理、容斥、鸽笼)、无穷、可数 • 代数系统的元素个数很特别 • 关系 • 笛卡尔乘积 => 关系的型构：规约了两个集合上元素之间特定 联系的存在 • 关系的设计：规约了两个集合上元素之间的特定关系 • 关系的表示： • 等价关系、划分，非常重要 • 分而治之的重要数学基础 • 函数 • 两个集合上元素之间结构良好的关系：函数的良定义 • (具体)函数的设计及其性质： • 单、满、双射性质及其证明 • 同态、同构函数的定义和证明 因为数据管 理的需要(往 往是用空间 换时间，用 数据管理的 时间换业务 逻辑的时间) 而派生出的 不同动态集 合数据结构 的模型基础
建模能力-经典模型偏序集 ·偏序集 ·序关系和等价关系具有不同的重要性 ·全序和无序之间的中间态 ·哈斯图及极点、最点 ·拓扑偏序算法 ·动态规划中的化递归”为“循环”的重要依据。能说说为什么吗？ ·格 ·Meet,join操作的含义，补元的含义 ·格的严格性质和格的哈斯图 有补分配格作为布尔代数的基础特性 ·布尔表达式的积和范式、布尔表达式的化简、卡诺图基础理论
建模能力-经典模型偏序集 • 偏序集 • 序关系和等价关系具有不同的重要性 • 全序和无序之间的中间态 • 哈斯图及极点、最点 • 拓扑偏序算法 • 动态规划中的化“递归”为“循环”的重要依据。能说说为什么吗？ • 格 • Meet, join操作的含义，补元的含义 • 格的严格性质和格的哈斯图 • 有补分配格作为布尔代数的基础特性 • 布尔表达式的积和范式、布尔表达式的化简、卡诺图基础理论
建模能力-经典图模型 ·图定义 ·点、边、权 ·本质上依然是集合、关系 ·图的（计算机）表示方法 ·图的基本属性：度、连通度（点/边）、路 ·特殊的图模型 ·树：层次结构 ·欧拉图、汉密尔顿图：旅行相关（遍历） ·传输网络：流量相关 ·平面图：区域相关
建模能力-经典图模型 • 图定义 • 点、边、权 • 本质上依然是集合、关系 • 图的(计算机)表示方法 • 图的基本属性：度、连通度(点/边)、路 • 特殊的图模型 • 树：层次结构 • 欧拉图、汉密尔顿图：旅行相关(遍历) • 传输网络：流量相关 • 平面图：区域相关