南京大学：《计算机问题求解》课程教学资源（课件讲稿）关于问题求解的几个思考

关于问题求解的 几个回顾思考

关于问题求解的 几个回顾思考

思考1： ·什么是计算机科学与技术意义下的计算？ ·物理世界的数字化 ·有时候，也有意识世界的数字化 ·但凡是数字化 ·计算机能否超越人？ ·数学模型和物理世界的数字化的关系 ·多数是离散数学模型 ·集合、图、代数 ·数字的组织和管理 ·经典数据结构 ·经典结构上的经典算法 ·数学结构的计算机表示 ·空间和时间的权衡

思考1： • 什么是计算机科学与技术意义下的计算？ • 物理世界的数字化 • 有时候，也有意识世界的数字化 • 但凡是数字化 • 计算机能否超越人？ • 数学模型和物理世界的数字化的关系 • 多数是离散数学模型 • 集合、图、代数 • 数字的组织和管理 • 经典数据结构 • 经典结构上的经典算法 • 数学结构的计算机表示 • 空间和时间的权衡

什么是计算机科学与技术意义下的计算？ ·算法的定义是什么？ ·为什么我们定义算法时，给了算法五个性质？ ·输入 ·输出 ·确定 ·有穷 ·能行 ·算法和计算是什么关系？ ·程序=数据结构+算法 ·指令 ·高级语言程序

什么是计算机科学与技术意义下的计算？ • 算法的定义是什么？ • 为什么我们定义算法时，给了算法五个性质？ • 输入 • 输出 • 确定 • 有穷 • 能行 • 算法和计算是什么关系？ • 程序=数据结构+算法 • 指令 • 高级语言程序

思考2：什么是问题？什么是问题的解？ ·计算机要解的问题有且仅有两类吗？ ·判定问题 ·优化问题 ·如何描述一个判定问题/优化问题？ ·我们关心问题的解，但是，我们更关心解问题的算法。 ·实现算法的语言和计算模型也挺重要

思考2：什么是问题？什么是问题的解？ • 计算机要解的问题有且仅有两类吗？ • 判定问题 • 优化问题 • 如何描述一个判定问题/优化问题？ • 我们关心问题的解，但是，我们更关心解问题的算法。 • 实现算法的语言和计算模型也挺重要

思考3：问题的难度和解问题算法的复杂 度 ·通常我们以时间开销来讨论难度和复杂度 ·问题的难度是固有的： ·我们只能关心问题难度的上、下界 ·问题难度的上界是什么含义？ ·为什么用存在量词来确定上界？ ·问题难度的下界是什么含义？ ·我们用全称还是存在量词来确定下界？ ·为什么确定问题的非平凡下界很难，但意义重大？ ·解问题算法是可以被优化的 More info,more efficient ·算法的渐进增长/限定，是什么意思？ ·我们会谈“算法的上界/下界是什么”吗？

思考3：问题的难度和解问题算法的复杂 度 • 通常我们以时间开销来讨论难度和复杂度 • 问题的难度是固有的： • 我们只能关心问题难度的上、下界 • 问题难度的上界是什么含义？ • 为什么用存在量词来确定上界？ • 问题难度的下界是什么含义？ • 我们用全称还是存在量词来确定下界？ • 为什么确定问题的非平凡下界很难，但意义重大？ • 解问题算法是可以被优化的 • More info, more efficient • 算法的渐进增长/限定，是什么意思？ • 我们会谈“算法的上界/下界是什么”吗？

思考4：设计算法有策略吗？相应的算法 正确性如何证明？ ·我们常常想起的算法设计策略有哪些？ ·暴力 ·分治 ·动态规划 ·贪心 ·递归和循环是什么关系？ ·算法正确性证明的基本思路是什么？ ·关键路径的断言/不变式！

思考4：设计算法有策略吗？相应的算法 正确性如何证明？ • 我们常常想起的算法设计策略有哪些？ • 暴力 • 分治 • 动态规划 • 贪心 • 递归和循环是什么关系？ • 算法正确性证明的基本思路是什么？ • 关键路径的断言/不变式！

作业： ·如果回忆起问题求解，你给出的思考5、思考6是什么？

作业： • 如果回忆起问题求解，你给出的思考5、思考6……是什么？