Аноним

Задача распознавания свойств: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Задача распознавания свойств''' (''Decision problem'') - такие ''массовые задачи'', ко...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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>{\cal P}</math>
или <math>{\cal NP}</math>, если ее стандартный код принадлежит классу
языков <math>{\cal P}</math> или <math>{\cal NP}</math> соответственно.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],  
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.
 
* Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.


[Гэри-Джонсон],  
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
 
[Касьянов/95]