Понятие задачи распознавания

   
На этом шаге мы рассмотрим понятие задачи распознавания.

   
Задачи обычно формулируются так: дан набор исходных данных X; требуется найти результат Y,
удовлетворяющий условиям задачи. Для некоторых задач в качестве результата удобно рассматривать только значения
"да" и "нет". Такие задачи формулируются как вопрос. Например, задача синтаксического анализа текста программы
X: "Соответствует ли программа X правилам языка Паскаль?". Множество всех возможных программ
L разделяется на два подмножества Lyes (множество всех правильных программ,
ответ "да") и Lno (множество всех остальных программ, ответ "нет"). Алгоритм, решающий
задачу, т. е. отвечающий "да" или "нет", по существу распознает, принадлежит ли программа X множеству
Lyes. То же можно сказать и о других задачах с двумя возможными ответами. Поэтому такие
задачи называются задачами распознавания или, точнее, задачами распознавания свойств.
Имеется в виду свойство, которым обладает (или не обладает) вход X.

   
С точки зрения математической логики задаче распознавания свойств соответствует предикат P(Х).

   
Если, формулируя задачу, настраиваться на то, что она будет решаться алгоритмическим способом с помощью
некоторого вычислителя (а не с помощью, например, озарения), то следует договориться, что исходные данные
X будут задаваться на языке, понятном вычислителю. Пусть A - алфавит символов, воспринимаемых
вычислителем, L - А* - множество всех возможных цепочек (слов) в алфавите A. Тогда
Lyes - множество слов, кодирующих вход X, для которых вычислитель выдает ответ
"да". Поскольку в теории формальных языков множество Lyes⊂L
называется языком, то любую задачу распознавания можно сформулировать как задачу распознавания языка.
Этот вывод нам потребуется далее при доказательстве теоремы С.Кука.

   
На следующем шаге мы рассмотрим понятие полиномиальной сводимости.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий