算法分析与设计
算法分析与设计
屈婉玲
l@ k d
qw
l@
p
k
u.e
d
u.cn
计算
思
维与
人
才
培
养
计算 维与 才 养
• 2006
年
3
月
周
以
真
(J
eannette M. Win
g
，
卡内
基
⋅
梅隆大
年
月
周真
(J g
卡内
梅隆大
学计算机系系主任)首次提出Coputational Thinking的
概念：运用计算机科学的基础概念去求解问题、设计系
统和理解人类的行为
它包括了涵盖计算机科学之广度
统和理解人类的行为
，
它包括了涵盖计算机科学之广度
的一系列思维活动。
数学思维与工程思维的互补与融合：抽象与实现
编程
评价程序
优化程序
问题分析
方法确定
技能：会做
能力：做得好
思维：认知、方法论
三种基本的思维
• 三种思维的共同特点：
用语言文字表达
有语法与语义规则
推逻辑
用语言文字表达
、
有语法与语义规则
、
推
理
逻辑
实验思维
理论思维
计算思维
实验思维
理论思维
计算思维
起源 物理学 数学 计算机科学
1
实验观察归纳建
1
定义概念
1
建模
(
约简
嵌入
转
过程
步骤
1
.
实验观察归纳建
立简单数学公式
2.导出数量关系
实验验证
1
.
定义概念
2.提出定理
3.给出证明
1
.
建模
(
约简
、
嵌入
、
转
化、仿真、…）
2.抽象与分解,控制系统
复杂性
步骤
3.
实验验证
复杂性
3.自动化实现…
解释以往现象
公理集
结论表示有限性
特点
解释以往现象
无矛盾
预见新的现象
公理集
可靠协调推演规则
正确性依赖于公理
结论表示有限性
语义确定性
实现机械性
3
算
法
与计算
思
维
算 与计算 维
•
算法课程是训练计算思维的重要课程
；
涉及到对
算法课程是训练计算思维的重要课程
；
涉及到对
问题的抽象，建模，设计好的求解方法，复杂性
的控制
的控制
，…
•
可计算性与计算复杂性
：
形式化
、
确定性
、
有限
可计算性与计算复杂性
：
形式化
、
确定性
、
有限
性，抽象与逻辑证明
• 算法设计与分析：抽象建模、归约、正确性证明
、效率分析、…
4
课程简介
课程名称：
算法分析与设计
Design and Analysis of Algorithms
课号：
0A002
基本目的：
掌握组合算法设计的基本技术
掌握组合算法设计的基本技术
掌握算法分析的基本方法
算复杂性 论的 本概念 其应
了解计
算
复
杂性
理
论
的基
本概念
及
其
应用
5
