韩启龙 hqlwxm2002@yahoo.com.cn 计算理论 第0章 绪 论 韩启龙 hqlwxm2002@yahoo.com.cn

序 言 一. 本课的性质以及研究的内容 任何一门学科都有它的基础和它的基本问题，如物质的本质是什么？有机体生命的基础和起源是什么？ 序 言 一. 本课的性质以及研究的内容 任何一门学科都有它的基础和它的基本问题，如物质的本质是什么？有机体生命的基础和起源是什么？ 什么是计算机科学的基础？什么是计算机科学的基本问题？ 诸如什么是形式语言？什么是计算？什么是能计算的？什么是不能计算的？什么是算法？如何评价算法？什么样的算法是可行的？这些问题能否判定？这又引出什么是可判定的？什么是不可判定的？ 这些问题就是计算理论要讨论的问题。

序 言 性质：该课是计算机科学的理论课。 计算理论：就是研究理论计算机的科学。 理论计算机：是研究计算机的理论模型，研究计算机 序 言 性质：该课是计算机科学的理论课。 计算理论：就是研究理论计算机的科学。 理论计算机：是研究计算机的理论模型，研究计算机 的本质，也就是把计算机看成一个数学系统。(因为计算 机科学的基本思想和模型在本质上是数学——离散的。) 内容： 形式语言与自动机理论： 正规文法与有限自动机(正规语言) 、 上下文无关文法与下推自动机(上下文无关语言) 图灵机(递归可枚举语言) 可计算性理论： 什么是可计算？ 计算复杂性理论： 时间复杂性 、 空间复杂性。

序 言 二. 学习目的： 了解这些计算理论 我们知道计算机不论从它的诞生还是它的快速发展过程 序 言 二. 学习目的： 了解这些计算理论 我们知道计算机不论从它的诞生还是它的快速发展过程 都没有离开计算理论，也就是它是在计算理论指导下诞生 和发展的。本课所涉及的都是计算机科学的基本问题。不 首先了解它们，是很难理解计算机科学的。作为计算机科 学与技术专业的本科生和研究生应该了解这些计算理论。 培养能力 此外此课可以培养学生抽象逻辑思维和形式化思维的能 力。

序 言 三.学时、学分 32学时/2学分 四.基础 离散数学(数理逻辑，集合论，图论)

序 言 教材 & 参考书 Textbook 英文版，（美）MICHAEL SIPSER， 中文第2版：唐常杰等译 References 序 言 教材 & 参考书 Textbook Introduction to the Theory of Computation (2nd Edition), by Michael Sipser 《计算理论导引 》 英文版，（美）MICHAEL SIPSER， 中文第2版：唐常杰等译 We will follow very closely to this book References Computational Complexity, by C. Papadimitiou Introduction to Automata Theory, Languages, and Computation, by J. Hopcroft, R. Motwani, and J. Ullman.

序 言 考 核 Homework: 40% Theorem Proof: 30% Final Exam: 30% 序 言 考 核 Homework: 40% Theorem Proof: 30% Final Exam: 30% ------------------------------------------ Total 100%

序 言 授课计划 教材详略处理 讲要点，前后次序有少数调整， 序 言 授课计划 教材详略处理 讲要点，前后次序有少数调整， 教学计划，大致8周 最后两章不讲或用讨论班形式讨论，有了基础，如果需要，已经能自学。（通常其它院校，如川大16-18周） 参考国内外同行（如Berkeley, MIT、四川大学等）对这门课程教材的处理经验，准备：  略讲或自学的部分，要求了解主要思想  快讲的部分，要求一般了解的章节，要求了解主要方法和演绎框架 要求深入掌握的部分——能作题目或作难题，通过考试

What will you learn from this course? 序 言 What will you learn from this course? How to define a computer? Are there problems that a computer cannot solve? If so, can we find one such problem? Automata theory Computability theory Complexity Theory

序 言 Complexity Theory 现实中计算的问题是多种多样的，有容易的，有困难的。 复杂性理论的核心问题： 序 言 Complexity Theory 现实中计算的问题是多种多样的，有容易的，有困难的。 排序问题，相对较简单 课程表问题，复杂（需要满足合理的限制） 复杂性理论的核心问题： What makes some problems computationally hard and others easy? 目前重要成果之一：按照计算难度将问题分类 即使不能证明问题是难计算的，但也能给出某些问题是难计算的证据的方法。

序 言 Complexity Theory You have several options when you confront a problem that appears to be computationally hard. 弄清问题困难的根源——变动——容易解决； 求问题的并不完美的解——近似解； 某些问题在最坏情况下是困难的，通常易解； 可以选择其他计算类型，如随机计算，可加速某些计算工作。

序 言 Computability theory Automata theory 一些基本问题是不能用计算机解决的 如：确定一个命题是真是假 序 言 Computability theory 一些基本问题是不能用计算机解决的 如：确定一个命题是真是假 可计算理论PK复杂性理论： 复杂性理论——把问题分成容易计算与难计算的 可计算理论——把问题分成可解的和不可解的 Automata theory 康托尔集合、罗素悖论、哥德尔定理 阐述了计算的数学模型的定义和性质

目 录 第0章 绪论——2学时 第1章 正则语言——5学时 第2章 上下文无关文法——3学时 第3章 丘奇-图灵论题——2学时 目 录 第0章 绪论——2学时 第1章 正则语言——5学时 第2章 上下文无关文法——3学时 第3章 丘奇-图灵论题——2学时 第4章 可判定性——2学时 第5章 可归约性——2学时 第6章 可计算理论高级专题——2学时 第7章 时间复杂性——4学时 第8章 空间复杂性——3学时 第9章 难解性——3学时 第10章 复杂性理论高级专题——4学时

序 言 Mathematics Review Unlike other CS courses, this course is a MATH course… We will look at a lot of definitions, theorems and proofs 基本数学概念与术语回顾 Set, Sequence, Function, Graph, String… 证明技术 By construction, induction, contradiction

Set（集合） A set is a group of items 集合描述方法之一: list every item in the group inside { } E.g., { 12, 24, 5 } is a set with three items When the items in the set has trend: use … E.g., { 1, 2, 3, 4, … } means the set of natural numbers 描述方法之二： state the rule E.g., { n | n = m2 for some positive integer m } means the set { 1, 4, 9, 16, 25, … } A set with no items is an empty set denoted by { } or 

Set（集合） Conditional: A = { x | x  N , f(x)=0 } Union: AB Intersection: AB Complement: Cartesian Product: AB Power set（幂集）: P (A) 或 2A

Set（集合） The power set of A is the set of all subsets of A, denoted by 2A E.g., A = { 0, 1 } 2A = { {}, {0}, {1}, {0,1} } How many items in the above power set of A? If A has n items, how many items does its power set contain? Why? 000…00 000…01 … 111…11 子集编码：

Sequence（序列） A sequence of items is a list of these items in some order（某种顺序） One way to describe a sequence: list the items inside ( ) ( 5, 12, 24 ) Order of items inside ( ) matters ( 5, 12, 24 ) ≠ ( 12, 5, 24 ) Repetition also matters ( 5, 12, 24 ) ≠ ( 5, 12, 12, 24 ) Finite sequences are also called tuples（元组） ( 5, 12, 24 ) is a 3-tuple ( 5, 12, 12, 24 ) is a 4-tuple

Sequence（序列） Given two sets A and B The Cartesian product of A and B, denoted by A x B, is the set of all possible 2-tuples with the first item from A and the second item from B E.g., A = {1, 2} and B = {x, y, z} A x B = { (1,x), (1,y), (1,z), (2,x), (2,y), (2,z) } The Cartesian product of k sets, A1, A2, …, Ak, denoted by A1 x A2 x … x Ak, is the set of all possible k-tuples with the ith item from Ai

Functions A function takes an input and produces an output If f is a function, which gives an output b when input is a, we write f(a) = b For a particular function f, the set of all possible input is called f’s domain（定义域） The outputs of a function come from a set called f’s range（值域）

Functions To describe the property of a function that it has domain D and range R, we write f : D  R E.g., The function add (to add two numbers) will have an input of two integers, and output of an integer We write: add: Z x Z  Z

Functions Guess: What does the following DOW function do? What are the domain and the range of DOW?

Graphs A graph is a set of points with lines connecting some of the points Points are called vertices, lines are called edges E.g.,

Graphs The number of edges at a particular vertex is the degree of the vertex In the previous example, 3 vertices have degree = 2 A graph can be described by telling what are its vertices, and what are its edges. Formally, a graph G can be written as G = (V, E), where V is the set of vertices, and E is the set of edges

Graphs We say a graph G is a subgraph of H if vertices of G are a subset of the vertices of H, and all edges in G are the edges of H on the corresponding vertices Graph H Subgraph G shown darker

Graphs A path is a sequence of vertices connected by edges If every two nodes have a path between them, the graph is connected A cycle is a path that starts and ends at the same vertex A tree is a connected graph with no cycles

Graphs Is the following graph connected? Is it a tree? Are there any cycles? How about the darker subgraph?

Directed Graphs If lines are replaced by arrows, the graph becomes directed The number of arrows pointing into a vertex is called in-degree of the vertex The number of arrows pointing from a vertex is called out-degree of the vertex A directed path is a path from one vertex to the other vertex, following the direction of the “arrows”

Directed Graphs Is there a directed path from a to b? a b

Strings An alphabet = a set of characters E.g., The English Alphabet = {A,B,C,…,Z} A string = a sequence of characters A string over an alphabet S A sequence of characters, with each character coming from S The length of a string w, denoted by |w|, is the number of characters in w The empty string (written as ) is a string of length 0

语言：字符串的集合 Strings Let w = w1w2…wn be a string of length n A substring of w is a consecutive（连续的） subsequence of w (that is, wiwi+1…wj for some i  j) The reverse of w, denoted by wR, is the string wn…w2 w1 A set of strings is called a language 语言：字符串的集合

Proof techniques（证明技术） By construction（构造法） By contradiction（反证法） By induction（归纳法）

Proof By Construction 许多定理声明存在一种特定类型的对象。通过说明如何构造这样的对象是证明这种定理的一种方法，这种方法就是构造性证明方法 proof by construction

By Construction [Example 1] Let us define a graph to be k-regular （k-正则的）if every vertex of the graph has degree k E.g., 2-regular 3-regular

By Construction [Example 1] Theorem: For each even number n  4, there exists a 3-regular graph with n vertices. How to prove it?

By Construction [Example 1] Proof Idea: 构造出一个n个顶点的3正则图。将n个点均匀排列在一个圆上，对每一个顶点，连接其左右邻点各为一条边，第三条边与其相对点相连。 证明: Label the vertices by 1,2,…, n. The edge set E is the union of E1 = { {x,x+1} | for x = 1,2,…,n-1 } E2 = { {1,n} } E3 = { {x, x+ (n/2)} | for x = 1,2,…,n/2 } Then, it is easy to check that the degree of each vertex is exactly 3.

By Contradiction [Example 2] Page 13 By Contradiction [Example 3] Page 14

Homework 0.1 0.2 0.5 0.6 0.9 0.10 0.11