4183
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Задача распознавания свойств''' (''Decision problem'') - такие ''массовые задачи'', ко...) |
KEV (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
'''Задача распознавания свойств''' (''Decision problem'') - | '''Задача распознавания свойств''' (''[[Decision problem]]'') - такие ''массовые задачи'', которые имеют только два возможных решения "да" или "нет". '''З.р.с.''' состоит просто из двух множеств: всех ее индивидуальных задач и тех из них, ответ для которых "да". Поэтому стандартная форма, | ||
такие ''массовые задачи'', которые имеют только два возможных | применяемая для описания задачи распознавания свойств, состоит из двух частей: условия задачи в терминах подходящих объектов (множеств, [[граф|графов]], функций, чисел и т.д.) и вопроса, предполагающего один из возможных ответов --- "да" или "нет". | ||
решения "да" или "нет". '''З.р.с.''' состоит | |||
просто из двух множеств: всех ее индивидуальных задач и тех | |||
из них, ответ для которых "да". Поэтому стандартная форма, | |||
применяемая для описания задачи распознавания свойств, | |||
состоит из двух частей: условия задачи в терминах подходящих | |||
объектов (множеств, графов, функций, чисел и т.д.) и | |||
вопроса, предполагающего один из возможных ответов --- "да" | |||
или "нет". | |||
Имеется определенное соответствие между задачами | Имеется определенное соответствие между задачами распознавания и языками, которое осуществляется с помощью кодирования, обычно применяемого для представления задачи при ее решении на ЭВМ. Выбрав способ кодирования всех возможных индивидуальных задач в виде [[цепочка|цепочек]] в некотором | ||
распознавания и языками, которое осуществляется с помощью | фиксированном [[алфавит|алфавите]], можно переформулировать массовую задачу как задачу распознавания языка, состоящего из всех цепочек, представляющих индивидуальные задачи, ответ для | ||
кодирования, обычно применяемого для представления задачи | которых --- "да". При этом естественно требовать, чтобы способ кодирования давал "сжатое" представление индивидуальных задач и допускал "декодирование". Указанное соответствие позволяет отождествлять решение задачи распознавания свойств с распознаванием соответствующего | ||
при ее решении на ЭВМ. Выбрав способ кодирования всех | |||
возможных индивидуальных задач в виде цепочек в некотором | |||
фиксированном алфавите, можно переформулировать массовую | |||
задачу как задачу распознавания языка, состоящего из всех | |||
цепочек, представляющих индивидуальные задачи, ответ для | |||
которых | |||
способ кодирования давал "сжатое" представление | |||
индивидуальных задач и допускал "декодирование". Указанное | |||
соответствие позволяет отождествлять решение задачи | |||
распознавания свойств с распознаванием соответствующего | |||
языка. | языка. | ||
Рассматриваются определенные "стандартные" | Рассматриваются определенные "стандартные" представления задач, которые удовлетворяют описанным выше требованиям, и говорится, что задача принадлежит <math>{\mathcal P}</math> или <math>{\mathcal NP}</math>, если ее стандартный код принадлежит [[классы P и NP|классу языков <math>{\mathcal P}</math> или <math>{\mathcal NP}</math>]] соответственно. | ||
представления задач, которые удовлетворяют описанным выше | |||
требованиям, и говорится, что задача принадлежит <math>{\ | |||
или <math>{\ | |||
языков <math>{\ | |||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман], | [Ахо-Хопкрофт-Ульман], |