Составители:
Рубрика:
положить x=λ, то
λ
∈ R
λ
⇔ λ ∉∈ R
λ
, т.е. приходим к противоречию.
Теорема доказана.
Дополнительные сведения по теории алгоритмов и
алгоритмической разрешимости можно найти в [3, 7, 8, 9, 11, 12, 15,
16].
Глава 5
ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ
Сложность вычислений и эффективность алгоритмов
составляют одну из важнейших проблем современной теории
вычислительных систем. В области теории и практики
программирования выработано много различных подходов к
проблеме сложности вычислений. Задача настоящей главы –
познакомить читателя с основами современных точных методов
оценки сложности задач и эффективности алгоритмов. Изучение
таких методов полезно для развития интуитивных представлений об
эффективном (с точки зрения стоимости) использовании
вычислительных машин и для выработки практических навыков
оценки потребности в вычислительных ресурсах (таких, как память и
время), необходимых при наиболее благоприятных условиях для
вычисления функции данной сложности на универсальных
вычислительных машинах.
5.1. Переборные задачи и сложность вычислений
Задача распознавания Π – это множество Z
п
всевозможных
индивидуальных задач и подмножество Z
⊂ Z
п.да п
задач с ответом
“да”. Задача распознавания Π называется переборной, если каждая
индивидуальная задача z формулируется следующим образом:
существует ли такой объект y, что выполняется свойство,
выражаемое предикатом R(z,y)? При этом предполагается, что
проверка истинности R(z,y) имеет полиномиальную сложность.
167
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
