南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）算法问题的形式化描述

计算机问题求解一论题4.6算 法问题的形式化 陶先平 2017年4月17日

计算机问题求解—论题4.6算 法问题的形式化 陶先平 2017年4月17日

算法问题编码-“渡河问题” 问题：人、狼、羊、莱用一条只能同时载两位的小船渡河，“狼羊”、“羊莱” 不能在无人在场时共处，当然只有人能驾船。 图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河 “操作”能够实现该状态的转变。 起始状态是“人狼羊莱”，结束状态是“空”。“允许状态”只有10个。 问题的解：找到一条从起始状态到结束状态的尽可能短的通路。 人羊狼菜人狼菜人羊狼人羊菜人羊 0 狼菜 狼 菜 空（成功

算法问题编码– “渡河问题” 问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜” 不能在无人在场时共处，当然只有人能驾船。 图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河 “操作”能够实现该状态的转变。 起始状态是“人狼羊菜”，结束状态是“空”。“允许状态”只有10个。 问题的解：找到一条从起始状态到结束状态的尽可能短的通路。 空(成功) 人羊狼菜 人狼菜 人羊狼 人羊菜 狼菜 狼 菜 人羊 羊

算法问题编码 狼菜 空 人羊狼菜00000100007 问题1：如何使用{0,1，} 人狼菜000001110 0 人羊狼000000101 0 编码这个问题？ 0000000110 人羊0000000011 1100000000 问题1.1：如何使用{0,1,9，# 011000000 0 0101000000 编码这个问题？ 0011100000 空0000100000 这个问题可以编码为：0000010000#0000011100#0000001010#0000000110#.… 或者，也可以表示成符号串：16#28#10#6#3#768#384#320#112#32

算法问题编码 问题1：如何使用{0,1,#} 编码这个问题？ 这个问题可以编码为：0000010000#0000011100#0000001010#0000000110#…… 或者，也可以表示成符号串：16#28#10#6#3#768#384#320#112#32                                 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 人羊狼菜 0 0 0 0 0 1 0 0 0 0 人狼菜 人羊狼 空 狼菜 空 人羊 问题1.1：如何使用{0,1,…,9,#} 编码这个问题？

Code formulaes: Which formula 一个“word” 所有的word“放在”一起，是什么？ is represented by the word wΦ=(x1V(x100)Vx111)A(x10V(x1)A(x100∧(x1000) 0 ver Slogic={0,1,(,),Λ，V,,x}. 问题2：如果只用{0,1，，如何编码上面的逻辑表达式？ 问题2.1：为什么我们举的例子，总是聚焦在字母表{0,1，#}上？

Code formulaes: Which formula 问题2：如果只用{0,1,#},如何编码上面的逻辑表达式？ 问题2.1：为什么我们举的例子，总是聚焦在字母表{0,1,#}上？ 一个“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 Si to 2 for some alphabets S1 and 2

如何理解下面的这句话？

什么是难问题？ 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,>where is an alphabet and L UC*.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)=0讨x∈U-L(c年L). the word "decide" 问题5：如果x不在U中，怎么解释？ For many decision problems (L,U,D)we assume U=D*.In that case we shall use the short notation(L,∑)instead of(L,∑*，)

判定问题的形式化表达 Pay attention to the word “decide” 问题5：如果x不在U中，怎么解释？

以下两种形式是等价的？ 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)=0fx∈U-L(x生L Problem (L,U, Input:Anx∈U. Output:"yes"ifx∈L, "no"otherwise

以下两种形式是等价的？