课程内容 课程内容 围绕学科理论体系中的模型理论，程序理论和计算理论 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