4625
правок
Задача легко разрешимая: различия между версиями
Перейти к навигации
Перейти к поиску
Задача легко разрешимая (посмотреть исходный код)
Версия от 13:39, 11 февраля 2011
, 11 февраля 2011нет описания правки
KEV (обсуждение | вклад) (Создана новая страница размером '''Задача легко разрешаемая''' (''Tractable problem'') - Большинство из алгоритмов, им...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Задача легко разрешаемая''' (''[[Tractable problem]]'') | '''Задача легко разрешаемая''' (''[[Tractable problem]]'') — Большинство из [[алгоритм|алгоритмов]], имеющих экспоненциальную временную сложность, — это просто варианты полного перебора, в то время как полиномиальные алгоритмы для решения той или иной задачи удается построить лишь тогда, | ||
когда глубоко понята суть решаемой задачи. Поэтому задача не считается "хорошо решаемой" до тех пор, пока для нее не построен полиномиальный алгоритм, и обычно задачу называют ''труднорешаемой'', если для ее решения не существует такого алгоритма. | когда глубоко понята суть решаемой задачи. Поэтому задача не считается "хорошо решаемой" до тех пор, пока для нее не построен полиномиальный алгоритм, и обычно задачу называют ''труднорешаемой'', если для ее решения не существует такого алгоритма. | ||
| Строка 13: | Строка 13: | ||
реальных ЭВМ, то класс труднорешаемых задач не будет зависеть от выбора конкретной модели, и такой выбор можно осуществлять, исходя из интересов дела и не уменьшая при этом сферы применимости полученных результатов. | реальных ЭВМ, то класс труднорешаемых задач не будет зависеть от выбора конкретной модели, и такой выбор можно осуществлять, исходя из интересов дела и не уменьшая при этом сферы применимости полученных результатов. | ||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||