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

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


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

Навигация