问题求解能力漫谈 陶先平马骏 南京大学计算机系 南京大学计算机软件研究所
问题求解能力漫谈 陶先平 马骏 南京大学计算机系 南京大学计算机软件研究所
问题求解能力的重要方面 程序设计能力 ·问题的形式化能力+数学建模能力+透视数据组织的能力 +算法设计能力+高级语言写作能力 ·程序设计能力是计算机专业从业者的终极追求目标。 ·广义上讲，它的能力构成是以上5个方面，其中高级语言写作 能力是实现能力 ·狭义上的程序设计能力就是指高级程序写作能力 ·语言的不同，写作方法也有不同
问题求解能力的重要方面 程序设计能力 • 问题的形式化能力+数学建模能力+透视数据组织的能力 +算法设计能力+高级语言写作能力 • 程序设计能力是计算机专业从业者的终极追求目标。 • 广义上讲，它的能力构成是以上5个方面，其中高级语言写作 能力是实现能力 • 狭义上的程序设计能力就是指高级程序写作能力 • 语言的不同，写作方法也有不同
形式化、建模与证明能力 ·问题的形式化能力 ·果挛癸或薯蹟定备常霸￥香整篷期裴鼻雒請 的非自然语言全面、精确地描 ·问题的建模能力 。 数学模型：对大量问题（现象）的本质要素、结构、性质进行的定性（定量） 抽象描述形成的数学系统 ·问题建模：运用数学模型，对具体问题的要素、 结构、性质进行形式化 规约形成的模型。比较关注具体问题解的表现和获取方法 ·数学证明 ·基于逻辑学的证明方法，提供了进行严格的数学证明的基本手段 。1 计算机科学中，数学证明常被用于求解算法/答案的正确性、性能的界的 严格证明
形式化、建模与证明能力 • 问题的形式化能力 • 用严格定义（语法良定义，语义无歧义）的非自然语言全面、精确地描 述一个事实或者规律，通常用于问题建模和数学证明 • 问题的建模能力 • 数学模型：对大量问题(现象)的本质要素、结构、性质进行的定性(定量) 抽象描述形成的数学系统 • 问题建模：运用数学模型，对具体问题的要素、结构、性质进行形式化 规约形成的模型。比较关注具体问题解的表现和获取方法 • 数学证明 • 基于逻辑学的证明方法，提供了进行严格的数学证明的基本手段 • 计算机科学中，数学证明常被用于求解算法/答案的正确性、性能的界的 严格证明
形式化基础-集合、逻辑 ·集合 ·最基本的数学模型（语言）、基本运算 ·罗素悖论 ·基本数据结构的数学基础 ·逻辑 ·命题逻辑：逻辑推理的基础 ·逻辑连接符（真值表）、逻辑表达式、范式 ·推理规则：证明方法的逻辑基础 ·什么叫argument?什么是正确的证明？什么是正确的结论？ ·谓词逻辑：现实问题的逻辑描述工具 ·全称和存在量词 ·谓词逻辑的逻辑推理基本方法 ·布尔逻辑：数字电路的数学基础
形式化基础-集合、逻辑 • 集合 • 最基本的数学模型(语言)、基本运算 • 罗素悖论 • 基本数据结构的数学基础 • 逻辑 • 命题逻辑：逻辑推理的基础 • 逻辑连接符(真值表)、逻辑表达式、范式 • 推理规则：证明方法的逻辑基础 • 什么叫argument？什么是正确的证明？什么是正确的结论？ • 谓词逻辑：现实问题的逻辑描述工具 • 全称和存在量词 • 谓词逻辑的逻辑推理基本方法 • 布尔逻辑：数字电路的数学基础
形式化基础-证明方法 ·证明方法 ·若干种证明方法 ·直接、间接：反证法、逆否证明法、分情形证明法 ·若干种证明需求 ·唯一性、存在性、全体性 ·上述证明方法的“逻辑法理” 若干个公认 ·数学归纳法 “美”的证 ·若干种数学归纳法的版本及其适用情形 明！ ·良序公理和数学归纳法的等价性 ·数学归纳法的“逻辑法理” ·课程学习过程，若干经典的数学归纳法证明样例 ·若干经典的错误命题”的错误数学归纳法证明
形式化基础-证明方法 • 证明方法 • 若干种证明方法 • 直接、间接：反证法、逆否证明法、分情形证明法 • 若干种证明需求 • 唯一性、存在性、全体性 • 上述证明方法的“逻辑法理” • 数学归纳法 • 若干种数学归纳法的版本及其适用情形 • 良序公理和数学归纳法的等价性 • 数学归纳法的“逻辑法理” • 课程学习过程，若干经典的数学归纳法证明样例 • 若干经典的“错误命题”的错误数学归纳法证明 若干个公认 “美”的证 明！