第一章 绪论.ppt

计算机算法设计与分析
North China Electric Power University
Computer Algorithms Design & Analysis
Dept. of Computer Science&Engineering of North China Electric Power University
本课程解决哪些问题
本课程主要介绍在实践应用中行之有效的解决非数值数据处理问题的若干经典的计算机算法，以帮助学生提高运行计算机解决具体问题的能力！
基本内容如下
1、算法简介
2、递归
3、分治法
4、动态规划法 ——石子合并问题
5、贪心法——最少硬币个数问题
6、回溯法——数字组合问题
算法学习之乐趣
1、久违的小学生成功解决应用题般的兴奋
2、难言之隐、十周根治
我已学习语言很多年，编程仍然不过关的苦恼。去玩玩数据结构和算法吧。
3、考学、升级之必经之路
数据结构和算法是各种考试的座上客
4、认清问题本质
是否对日新月异的开发工具跟得疲惫，当初对学计算机的兴趣大大降低，设计的软件是否存在一些问题，你难以快速理清它的逻辑，并给出高效的解决方案，玩算法吧！它能使你快速看清楚一些常见问题的本质，并提供你各种解决方案进行选择！也是使你区别于代码工人的方式之一。
5、计算机科学之最终武器
算法的优化与处理
6、玩网游攻关般的快感
在这里不讨论具体编程语言，只分析问题，设计算法，分析算法！当然，实践是检验真理的客观标准，C++或Java语法你得先了解，我们通过北大在线测评网站提交程序，机器判断你的算法是否正确，耗时如何，耗内存如何？去注册帐号练级吧！
1、理论上可计算
2、现实上可计算
理论上可计算-------可计算性理论
提出很多合理的计算模型，（递归函数、图灵机、post系统等等）由这些模型规定哪些问题是可计算的。
现实上可计算--------计算复杂性理论
这个问题涉及到算法的时间、空间复杂性等
算法主要研究的问题及其课程目的
North China Electric Power University
课程目的:
以算法设计为主，介绍算法设计的主要方法和基本思想； 并简要介绍算法分析概念
不是程序设计课，也不是数学课
第一章 算法简介
★ 算法的基本概念
★ 算法的设计与分析
★ 算法的复杂性
North China Electric Power University
★ 算法描述语言(C++)的说明
算法+数据结构=程序 (Niklaus Wirth)
（Algorithms+Data Structure=Program)
程序设计：为计算机处理问题编写的一组指令。
算法：处理问题的方法和策略。
数据结构：问题的数学模型。
程序设计的实质是数据的表示和数据处理,为此
应提出问题的数学模型和设计相应的算法。
数据结构是基础，算法是灵魂
§1 算法的基本概念
North China Electric Power University
算法：解决问题的方法和策略，指为解决一个或
一类问题给出的一个确定的、有限长的操作序列。
算法的特性:
1. 有穷性
2. 确定性
3. 可行性
4. 有输入
5. 有输出
North China Electric Power University
算法与算法设计
问题求解(Problem Solving)
证明正确性
分析算法
设计程序
理解问题
精确解或近似解
选择数据结构
算法设计策略
设计算法
8
算法分析的基本原则
正确性
定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。
正确性证明的内容：
方法的正确性证明——算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。
程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。
程序正确性证明的方法：
大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块，分别验证。
小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。
9
算法分析的基本原则
工作量——时间复杂性分析
计量工作量的标准: 对于给定问题，该算法所执行的基本运算的次数。
基本运算的选择：根据问题选择适当的基本运算。
问题
基本运算
在