计算机问题求解 一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：你能举一些类似的例子来帮助理 解“语言”的作用吗？