华中科技大学：《计算机算法基础》第一章 导引与基本数据结构（王多强）

●●●●● ●●●● ●●0 ●●● ●●●● 计算机算波基础 (课件V0.1) 王多强 华中科技大学计算杋学院 2021/2/20

2021/2/20 计算机算法基础 (课件V0.1) 王多强 华中科技大学计算机学院

●●●●● 序 ●●●● ●●0 ●●● ●●●● 专业基础课程: 数据结构、计算机语 操作系统、编译 如何编写计算机程序: 数据结构+算法=程序 算法:计算机软件的“灵魂” 算法是计算机科学和计算机应用的核心 2021/2/20

2021/2/20 序 专业基础课程： 数据结构、计算机语言 操作系统、编译 如何编写计算机程序： ⚫ 数据结构+算法 = 程序 ⚫ 算法：计算机软件的“灵魂” 算法是计算机科学和计算机应用的核心

●●●●● ●●●● ●●0 ●●● ●●●● 教材: 计算机算法基础余祥宣等编著华中科技大学出版社 参考书: 算法设计与分析王晓东编著清华大学出版社 计算机算法导引——设计与分析卢开澄编著清华大 学出版社 Introduction To Algorithm高教出版社, MITPress 学时:32+8学时 2021/2/20

2021/2/20 教材： 计算机算法基础 余祥宣等编著 华中科技大学出版社 参考书： 算法设计与分析 王晓东编著 清华大学出版社 计算机算法导引——设计与分析 卢开澄编著 清华大 学出版社 Introduction To Algorithm 高教出版社，MIT Press 学时：32+8学时

●●●●● ●●●● 章节安排 ●●0 ●●● ●●●● ●第一章导引与基本数据结构√ 第二章分治法 第三章贪心方法 ●第四章动态规划 ●第五章检索与周游 √√√ ●第六章回溯法 ●第七章分枝-限界 第八章NP-问题 2021/2/20

2021/2/20 章节安排 ⚫ 第一章 导引与基本数据结构 √ ⚫ 第二章 分治法 √ ⚫ 第三章 贪心方法 √ ⚫ 第四章 动态规划 √ ⚫ 第五章 检索与周游 √ ⚫ 第六章 回溯法 ⊙ ⚫ 第七章 分枝-限界 ⊙ ⚫ 第八章 NP-问题 ?

●●●●● ●●●● 第一章导引与基本数据结构 ●●0 ●●● ●●●● 1.1算法的定义及特性 1.什么是算法? ★算法如数字、计算一样,是一个基本概念 ★算法是解一确定类问题的任意一种特殊的方法。 ★在计算杋科学中,算法是使用计算机解一类问题 的精确、有效方法的代名词; 算法是一组有穷的规则,它规定了解决某一特定类型 问题的一系列运算。 2021/2/20

2021/2/20 第一章 导引与基本数据结构 1.1 算法的定义及特性 1. 什么是算法？ ★ 算法如数字、计算一样，是一个基本概念。 ★ 算法是解一确定类问题的任意一种特殊的方法。 ★ 在计算机科学中，算法是使用计算机解一类问题 的精确、有效方法的代名词； 算法是一组有穷的规则，它规定了解决某一特定类型 问题的一系列运算

●●●●● ●●●● 2.算法的五个重要特性 ●●0 ●●● ●●●● 确定性、能行性、输入、输出、有穷性 1)确定性:算法的每种运算必须要有确切的定 义,不能有二义性。 例:不符合确定性的运算 5/0 将6或7与x相加 未赋值变量参与运算 2021/2/20

2021/2/20 2. 算法的五个重要特性 确定性、能行性、输入、输出、有穷性 1）确定性：算法的每种运算必须要有确切的定 义，不能有二义性。 例：不符合确定性的运算 ⚫ 5/0 ⚫ 将6或7与x相加 ⚫ 未赋值变量参与运算

●●●●● ●●●● ●●0 ●●● ●●●● 2)能行性 算法中有待实现的运算都是基本的运算, 原理上每种运算都能由人用纸和笔在“有限”的 时间内完成。 例:整数的算术运算是“能行”的 实数的算术运算是“不能行”的 2021/2/20

2021/2/20 2）能行性 算法中有待实现的运算都是基本的运算， 原理上每种运算都能由人用纸和笔在“有限”的 时间内完成。 例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的

●●●●● ●●●● ●●0 ●●● ●●●● 3)输入 每个算法有0个或多个输入。这些输入是在算法开始之前 给出的量,取自于特定的对象集合——一定义域(或值域) 4)输出 个算法产生一个或多个输出,这些输出是同输入有某种 特定关系的量 2021/2/20

2021/2/20 3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前 给出的量，取自于特定的对象集合——定义域（或值域） 4）输出 一个算法产生一个或多个输出，这些输出是同输入有某种 特定关系的量

●●●●● ●●●● ●●0 5)有穷性 ●●● ●●●● 个算法总是在执行了有穷步的运算之后终止 计算过程:只满足确定性、能行性、输入、输出四个特 性的一组规则 ●算法和计算过程的区别: 计算过程:操作系统(不终止的运行过程) >算法是“可以终止的计算过程 算法的时效性:只能把在相当有穷步内终止的算法投 入到计算机上运行 2021/2/20

2021/2/20 5）有穷性 一个算法总是在执行了有穷步的运算之后终止。 计算过程：只满足确定性、能行性、输入、输出四个特 性的一组规则。 ⚫ 算法和计算过程的区别： ➢ 计算过程：操作系统(不终止的运行过程) ➢ 算法是“可以终止的计算过程” ⚫ 算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行

●●●●● 4.我们的主要任务 ●●●● ●●0 算法学习将涉及5个方面的内容: ●●● ●●●● 1)设计算法:创造性的活动 2)表示算法:思想的表示形式, SPARKS语言 3)确认算法:证明算法对所有可能的合法输入都能得出正确的答案。 算法证明:证明算法的正确性,与语言无关 程序证明:证明程序的正确性 4)分析算法:对算法的时、空特性做定量分析,以了解算法的好坏 5)测试程序 调试:“调试只能指出有错误,而不能指出它们不存在错误” 作时空分布图:验证分析结论,优化算法设计 本课程集中于学习算法的设计与分析。通过学习,掌握计算机算 法设计和分析基本策略与方法,为设计更复杂、更有效的算法奠定基 础 2021/2/20

2021/2/20 4. 我们的主要任务 算法学习将涉及5个方面的内容： 1）设计算法：创造性的活动 2）表示算法：思想的表示形式，SPARKS语言 3）确认算法：证明算法对所有可能的合法输入都能得出正确的答案。 算法证明：证明算法的正确性，与语言无关 程序证明：证明程序的正确性 4）分析算法：对算法的时、空特性做定量分析，以了解算法的好坏 5）测试程序： 调试：“调试只能指出有错误，而不能指出它们不存在错误” 作时空分布图：验证分析结论，优化算法设计 本课程集中于学习算法的设计与分析。通过学习，掌握计算机算 法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基 础