课程内容 课程内容 围绕学科理论体系中的模型理论，程序理论和计算理论 1.模型理论关心的问题 给定模型M,哪些问题可以由模型M解决；如何 比较模型的表达能力 本讲座用简单的例子来扼要 2.程序理论关心的问题介绍计算复杂性和算法分析 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3.计算理论关心的问题 给定模型M和一类问题，解决该类问题需多少资源
课 程 内 容 • 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何 比较模型的表达能力 2. 程序理论关心的问题 – 给定模型M，如何用模型M解决问题 – 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源 本讲座用简单的例子来扼要 介绍计算复杂性和算法分析 2
讲座提纲 基本知识 可计算理论，计算资源，计算复杂性理论，算法分析 复杂性的计量 问题规模、复杂性函数、最坏、最好和平均三种 情况的时间复杂性 复杂性的渐近行为及其阶 复杂性的渐近行为、渐近意义下的记号O、记号O 的运算规则、复杂性渐近阶分析的重要性 算法复杂性渐近阶的分析 算法的复杂性渐近阶的分析、语句规则的例举
讲 座 提 纲 • 基本知识 – 可计算理论, 计算资源, 计算复杂性理论, 算法分析 • 复杂性的计量 – 问题规模、复杂性函数、最坏、最好和平均三种 情况的时间复杂性 • 复杂性的渐近行为及其阶 – 复杂性的渐近行为、渐近意义下的记号O、记号O 的运算规则、复杂性渐近阶分析的重要性 • 算法复杂性渐近阶的分析 – 算法的复杂性渐近阶的分析、语句规则的例举3
基本知识 ·可计算理论 研究计算的一般性质的数学理论，也称算法理论 通过建立计算的数学模型，区分可计算与不可计算 可计算函数：能够在抽象计算机上编出程序计算 其值的函数。这样的程序称为算法 这样就可以讨论哪些函数是可计算的，哪些函数 是不可计算的 可计算性：指一个实际问题是否可以使用计算机 来解决（能解决一定是指有限步内解决） -上一讲介绍的就是计算模型和可计算函数
基 本 知 识 • 可计算理论 – 研究计算的一般性质的数学理论，也称算法理论 – 通过建立计算的数学模型, 区分可计算与不可计算 – 可计算函数：能够在抽象计算机上编出程序计算 其值的函数。这样的程序称为算法 – 这样就可以讨论哪些函数是可计算的，哪些函数 是不可计算的 – 可计算性：指一个实际问题是否可以使用计算机 来解决（能解决一定是指有限步内解决） – 上一讲介绍的就是计算模型和可计算函数 4
基本知识 ·计算资源 在计算复杂性理论内，计算资源是指在某个计算 模型之下，求解一个问题所要消耗的资源 时间资源：求解问题所需花费的时间，通常用计 算步数来度量 空间资源：求解问题所需占用的空间，通常用存 储器空间的大小来度量 计算所需资源的多少是衡量计算复杂性的依据 实际应用关心的资源与理论上的有区别：硬件资 源（如计算机、存储器）、软件资源、网络资源 (如通信带宽)等
基 本 知 识 • 计算资源 – 在计算复杂性理论内，计算资源是指在某个计算 模型之下，求解一个问题所要消耗的资源 – 时间资源：求解问题所需花费的时间，通常用计 算步数来度量 – 空间资源：求解问题所需占用的空间，通常用存 储器空间的大小来度量 – 计算所需资源的多少是衡量计算复杂性的依据 实际应用关心的资源与理论上的有区别：硬件资 源（如计算机、存储器）、软件资源、网络资源 （如通信带宽）等 5
基本知识 ·计算复杂性理论 是理论计算机科学和数学的一个分支，它致力于 将可计算问题根据其本身固有的难度进行分类， 以及把这些类别相互联系起来 它尝试把问题分成两类：在适当的资源限制下能 解（容易）和不能解（困难）的问题。一个问题，若求 解需很多资源无论什么算法)，则被认为是难解的 通过入计算模型来研究这些问题，并给出定量 计算解决问题所需的资源时间和空间)的方法， 由此把确定资源的方法数学化 -作用之一是确定计算机能解和不能解的实际界线
基 本 知 识 • 计算复杂性理论 – 是理论计算机科学和数学的一个分支，它致力于 将可计算问题根据其本身固有的难度进行分类， 以及把这些类别相互联系起来 – 它尝试把问题分成两类：在适当的资源限制下能 解(容易)和不能解(困难)的问题。一个问题，若求 解需很多资源(无论什么算法), 则被认为是难解的 – 通过引入计算模型来研究这些问题，并给出定量 计算解决问题所需的资源 (时间和空间) 的方法， 由此把确定资源的方法数学化 – 作用之一是确定计算机能解和不能解的实际界线6
基本知识 计算复杂性理论 研究问题之一：NP=?P -P(Polynomic):在确定型图灵机上有多项式时间 算法的问题的集合 P (Nondeterministic Polynomial):在非确定型图 灵机上有多项式时间算法的问题的集合 一】 NP=?P:是计算机科学中非常重要而又经历了几 十年始终未解决的一个问题 -它的解决可导致一系列理论问题的解决
基 本 知 识 • 计算复杂性理论 研究问题之一：NP =? P – P (Polynomial)：在确定型图灵机上有多项式时间 算法的问题的集合 – NP (Nondeterministic Polynomial)：在非确定型图 灵机上有多项式时间算法的问题的集合 – NP =? P：是计算机科学中非常重要而又经历了几 十年始终未解决的一个问题 – 它的解决可导致一系列理论问题的解决 7
基本知识 算法分析 确定执行一个算法需要消耗的计算资源的数量的 分析过程 算法的效率或复杂度表示为一个函数，其定义域 是输入数据的规模（长度，算法大都设计成允许 任意长的输入)，值域通常是执行步数（时间复 杂度)或所需存储空间数量（空间复杂度 在算法的理论分析中，通常是估计算法渐近意义 上的复杂度 精确分析算法的复杂度有时也可行，但它通常基 于一些与具体实现相关的假设
基 本 知 识 • 算法分析 – 确定执行一个算法需要消耗的计算资源的数量的 分析过程 – 算法的效率或复杂度表示为一个函数，其定义域 是输入数据的规模（长度，算法大都设计成允许 任意长的输入），值域通常是执行步数（时间复 杂度）或所需存储空间数量（空间复杂度） – 在算法的理论分析中，通常是估计算法渐近意义 上的复杂度 – 精确分析算法的复杂度有时也可行，但它通常基 于一些与具体实现相关的假设 8
基本知识 ·可计算性、计算复杂性和算法分析的区别 算法分析致力于分析求解一个问题的某个具体算 法所需的资源量 一计算复杂性理论关注的是用所有可能算法解决同 一类问题层面上的一般性议题 可计算性理论关注的是原则上可以用算法求解的 问题（把问题区分为可计算和不可计算） 资源受限和不受限是区分计算复杂性理论和可计 算性理论的一个重要标志
基 本 知 识 • 可计算性、计算复杂性和算法分析的区别 – 算法分析致力于分析求解一个问题的某个具体算 法所需的资源量 – 计算复杂性理论关注的是用所有可能算法解决同 一类问题层面上的一般性议题 – 可计算性理论关注的是原则上可以用算法求解的 问题（把问题区分为可计算和不可计算） – 资源受限和不受限是区分计算复杂性理论和可计 算性理论的一个重要标志 9
复杂性的计量 两种查找算法的效率比较 int search(int val){/顺序查找 int j=0; int a m无重复且已按从小到大排序 while(ali]val &j<m -1){ j=j+1; if (alil =val) return j; else return -1; }∥在最坏情况下，需要把val与a的所有分量比较
复杂性的计量 • 两种查找算法的效率比较 int search(int val) { // 顺序查找 int j = 0; //int a[m]无重复且已按从小到大排序 while(a[j] < val && j < m −1) { j = j +1; } if (a[j] == val) { return j; } else { return −1; }// 在最坏情况下，需要把val与a的所有分量比较 } 10
复杂性的计量 两种查找算法的效率比较 int search(int val){∥二分查找 int i,j,k; ,/int a m无重复且已按从小到大排序 i=0;j=m-1; while(i a k)i=k+1; 3 if (j-i==-1)freturn 1;}else {return k;} }∥在最坏情况下，只需要把val与a的1og2m个 ∥分量比较，显然效率高于前一个算法
复杂性的计量 • 两种查找算法的效率比较 int search(int val) { // 二分查找 int i, j, k; //int a[m]无重复且已按从小到大排序 i = 0; j = m −1; while(i = a[k]) i = k + 1; } if (j − i == − 1) {return − 1;} else {return k;} } // 在最坏情况下，只需要把val与a的log2 m个 // 分量比较，显然效率高于前一个算法 11
