561
个编辑
更改
跳到导航
跳到搜索
第97行：
第97行： − + − −
→Decision problems as formal languages作为形式语言的决策问题
An example of a decision problem is the following. The input is an arbitrary graph. The problem consists in deciding whether the given graph is connected or not. The formal language associated with this decision problem is then the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings.
An example of a decision problem is the following. The input is an arbitrary graph. The problem consists in deciding whether the given graph is connected or not. The formal language associated with this decision problem is then the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings.
'''<font color="#ff8000"> 决策问题</font>'''的一个例子如下。输入是一个任意的图。问题是判断给定的图是否连通。与这个决策问题相关的形式语言是所有连通图的集合ーー为了获得这种语言的精确定义，必须决定图是如何编码成二进制字符串的。
'''<font color="#ff8000"> 决策问题</font>'''的一个例子如下。输入是一个任意的'''<font color="#ff8000"> 图</font>'''。问题是判断给定的图是否连通。与这个决策问题相关的形式语言是所有连通图的集合ーー为了获得这种语言的精确定义，必须决定图是如何编码成二进制字符串的。
===Function problems函数问题===
===Function problems函数问题===