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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Задача распознавания свойств''' (''Decision problem'') - такие ''массовые задачи'', ко...)
 
Нет описания правки
Строка 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> соответственно.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],  
[Ахо-Хопкрофт-Ульман],  

Версия от 17:56, 20 октября 2009

Задача распознавания свойств (Decision problem) - такие массовые задачи, которые имеют только два возможных решения "да" или "нет". З.р.с. состоит просто из двух множеств: всех ее индивидуальных задач и тех из них, ответ для которых "да". Поэтому стандартная форма, применяемая для описания задачи распознавания свойств, состоит из двух частей: условия задачи в терминах подходящих объектов (множеств, графов, функций, чисел и т.д.) и вопроса, предполагающего один из возможных ответов --- "да" или "нет".

Имеется определенное соответствие между задачами распознавания и языками, которое осуществляется с помощью кодирования, обычно применяемого для представления задачи при ее решении на ЭВМ. Выбрав способ кодирования всех возможных индивидуальных задач в виде цепочек в некотором фиксированном алфавите, можно переформулировать массовую задачу как задачу распознавания языка, состоящего из всех цепочек, представляющих индивидуальные задачи, ответ для которых --- "да". При этом естественно требовать, чтобы способ кодирования давал "сжатое" представление индивидуальных задач и допускал "декодирование". Указанное соответствие позволяет отождествлять решение задачи распознавания свойств с распознаванием соответствующего языка.

Рассматриваются определенные "стандартные" представления задач, которые удовлетворяют описанным выше требованиям, и говорится, что задача принадлежит [math]\displaystyle{ {\mathcal P} }[/math] или [math]\displaystyle{ {\mathcal NP} }[/math], если ее стандартный код принадлежит классу языков [math]\displaystyle{ {\mathcal P} }[/math] или [math]\displaystyle{ {\mathcal NP} }[/math] соответственно.

Литература

[Ахо-Хопкрофт-Ульман],

[Гэри-Джонсон],

[Касьянов/95]