第一单元 算法引论.pptVIP

* 算法不是程序设计课，也不是数学课 * 离散型随机变量的一切可能的取值xi与对应的概率Pi(=xi)之积的和称为的数学期望（设级数绝对收敛），记为E。随机变量最基本的数学特征之一。它反映随机变量平均取值的大小。又称期望或均值。 关于本课程 1．课程学时 总学时：24学时；其中讲课：18学时； 上机：6学时 2．课程目的和要求 本课程为计算机学科本科生的学科基础课程。 设计：以算法设计为主，介绍算法设计的主要方法和基本思想；掌握通用算法的一般设计方法。 分析：学会对算法的时间和空间的复杂度进行分析，掌握提高算法效率的方法和途径。 关于本课程 3．课程用处 建立计算机领域常见问题的解决思路 比赛：如ACM（ICPC）、TopCoder 考硕士(复试科目)或博士（考试科目） 关于本课程 4．参考资料 [1] 王晓东.算法设计与分析（第二版）.清华大学出版社，2008.1 [2]算法设计与分析习题解答 王晓东编著 清华大学出版社 2006 [3] Sara Baase等.计算机算法-设计与分析导论（英文第三版影印版）.高等教育出版社，2001.7 Web资源 , , … 关于本课程 4．课程主要内容 第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 第7章 概率算法 第8章 NP完全性理论 第9章 近似算法 第10章 算法优化策略 第1章 算法引论 1.1 算法与程序 1.2 算法与数据结构 1.3 表达算法的抽象机制 1.4 描述算法与算法设计 1.5 算法分析的基本原则 1.6 算法复杂性分析 本章主要知识点： 1.0 算法概述 很难给算法（algorithm）给出精确的定义。 “算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。” 计算机科学中，算法已逐渐成了用计算机解一类问题的精确、有效方法的代名词。 1.1 算法与程序 算法：是满足下述性质（特性）的指令序列。 输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 程序： 程序是算法的某种程序设计语言的描述。 程序可以不满足算法的性质(4)即有限性。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。 1.2 算法与数据结构 描述算法可以有多种方式 自然语言方式、表格方式、图示形式等 本书采用Java与自然语言相结合的方式； 本人对语言不做任何限制：C++、C#、VB…… 算法与数据结构的关系 不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂； 反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。 算法＋数据结构＝程序 1.3 表达算法的抽象机制 从机器语言到高级语言的抽象 高级程序设计语言的主要好处是： 高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁琐的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 1.3 表达算法的抽象机制 抽象数据类型 抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： 算法顶层设计与底层实现分离； 算法设计与数据结构设计隔开，允许数据结构自由选择； 数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； 用抽象数据类型表述的算法具有很好的可维护性； 算法自然呈现模块化； 为自顶向下逐步求精和模块化提供有效途径和工具； 算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 1.4 描述算法与算法设计 描述算法可以有多种方式，如自然语言方式、图形表格方式等。 本书采用Java与自然语言相结合的方式； 本人对语言不做任何限制：C++、C#、VB…… 1.4 描述算法与算法设计 问题求解(Problem Solving) 证明正确性 分析算法 设计程序 理解问题 精确解或近似解 选择数据结构和 算法设计策略 设计算法 1.5