Аноним

Задача легко разрешимая: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Задача легко разрешаемая''' (''Tractable problem'') - Большинство из алгоритмов, им...)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Задача легко разрешаемая''' (''[[Tractable problem]]'') - Большинство из алгоритмов, имеющих экспоненциальную временную сложность, --- это просто варианты полного перебора, в то время как полиномиальные алгоритмы для решения той или иной задачи удается построить лишь тогда,
'''Задача легко разрешаемая''' (''[[Tractable problem]]'') Большинство из [[алгоритм|алгоритмов]], имеющих экспоненциальную временную сложность, это просто варианты полного перебора, в то время как полиномиальные алгоритмы для решения той или иной задачи удается построить лишь тогда,
когда глубоко понята суть решаемой задачи. Поэтому задача не считается "хорошо решаемой" до тех пор, пока для нее не построен полиномиальный алгоритм, и обычно задачу называют ''труднорешаемой'', если для ее решения не существует такого алгоритма.
когда глубоко понята суть решаемой задачи. Поэтому задача не считается "хорошо решаемой" до тех пор, пока для нее не построен полиномиальный алгоритм, и обычно задачу называют ''труднорешаемой'', если для ее решения не существует такого алгоритма.


Строка 13: Строка 13:
реальных ЭВМ, то класс труднорешаемых задач не будет зависеть от выбора конкретной модели, и такой выбор можно осуществлять, исходя из интересов дела и не уменьшая при этом сферы применимости полученных результатов.
реальных ЭВМ, то класс труднорешаемых задач не будет зависеть от выбора конкретной модели, и такой выбор можно осуществлять, исходя из интересов дела и не уменьшая при этом сферы применимости полученных результатов.
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.


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