计算机问题求解 一4.8算法问题的形式化 2021年4月26日
计算机问题求解 —4.8算法问题的形式化 2021年4月26日
问题1：语言是什么？我们在讨论难问题求 解的时候，语言帮助我们描述什么了？
问题1：语言是什么？我们在讨论难问题求 解的时候，语言帮助我们描述什么了？
Formulae represent: 一个“word” Which formula 所有的word“放在”一起，是什么？ is represented by the word wΦ=(x1V(x100)Vx111)∧(x10V(x1)∧(x100∧(x1000) over Slogic ={0,1,()A,V,-,2}. 问题2：如果只用{0,1，#粉，如何编码一个逻辑表达式， 如(x1∧x2)V(x2∧x3)?
Formulae represent: Which formula 问题2：如果只用{0,1,#},如何编码一个逻辑表达式， 如(x1 ∧ 𝑥2) ∨ (𝑥2 ∧ ¬𝑥3)？ 一个“word” 所有的word“放在”一起，是什么？
语言！ Definition 2.3.1.9.Let S be an alphabet.Every set L is called a lan- guage over >The complement of the language L according to is LC=∑*-L. A language can be used to describe a set of consistent input instances of an algorithmic problem. For instance,the set of all representations of formu- lae in CNF as a set of words over Logic or the set {u#u2#...#um ui E 10,1)m,m E NN}as the set of representations of all directed graphs over 10,1,#are examples of such languages
语言！
问题3：你能举一些类似的例子来帮助理 解“语言”的作用吗？ PRIM={w∈{0，l}*|Number(w)is a prime}. SAT=ww is a code of a satisfiable formula in CNF). CLIQUE={x#w∈{0，l,#}*|x∈{0,1}*and w represents a graph that contains a clique of size Number(c)}. VCP={u#w∈{0，l,#}+|u∈{0，l}f and w represents a graph that contains a vertex cover of size Number(u)
问题3：你能举一些类似的例子来帮助理 解“语言”的作用吗？
如何理解下面的这句话？ Every algorithm (computer program)can be viewed as an execution of a mapping from a subset of t to for some alphabets and 2 A consistent input instance of the first language an output instance of the second language
如何理解下面的这句话？ A consistent input instance of the first language an output instance of the second language
什么是难问题？ We consider a problem to be hard if there is no known deterministic algorithm(computer program)that solves it efficiently. 我们将难问题分解为两类来研究： decision problems optimization problems
什么是难问题？ 我们将难问题分解为两类来研究：
判定问题的形式化表达 Definition 2.3.2.1.A decision problem is a triple (L,U,S)where is an alphabet and L CUC*.An algorithm A solves (decides)the decision problem (L,U,>if,for every x EU, ()A(x)=1fx∈L,amd Pay attention to )A(x)=0fx∈U-L(x年L. the word "decide" For many decision problems (L,U,>we assume U =*In that case we shall use the short notation (L,instead of (L,*S)
判定问题的形式化表达 Pay attention to the word “decide
以下两种形式是等价的 Definition 2.3.2.1.A decision problem is a triple (L,U,>where is an alphabet and LU *An algorithm A solves (decides)the decision problem (L,U,>if,for every x EU, ()A(x）=1fx∈L,amd ()A(x)=0过x∈U-Lx走L). Problem (L,U,S) Input:Anx∈U. Output:"yes”ifx∈L, "no"otherwise
以下两种形式是等价的
问题6：如何形式化描述一个decision problem (L,Σ) PRIMALITY TESTING Σ：∑bool L:PRIM ={w E(0,1]*Number(w)is a prime} Primality testing Input::Anx∈2tol Output:"yes"if Number(x)is a prime, "no"otherwise. 为什么书中要加这么一句话？ For primality testing we always consider(PRIM,Sooo)as the formal definition of this decision problem
问题6：如何形式化描述一个decision problem？ 为什么书中要加这么一句话？ ( L , ∑ ) ∑: ∑bool L: