Глава 5. Элементы теории алгоритмов

§ 34. Уточнение понятия алгоритма
§ 35. Алгоритмически неразрешимые задачи
§ 36. Сложность вычислений
§ 37. Доказательство правильности программ

текст главы 5 https://yadi.sk/i/VXx73ecmfrkDy

 

В оглавление

Практические работы к главе 5

---

Работа № 36 «Машина Тьюринга»

Работа № 37 «Машина Поста»

Работа № 38 «Нормальные алгоритмы Маркова»

Работа № 39 «Вычислимые функции»

Работа № 40 «Инвариант цикла»

ЭОР к главе 5 на сайте ФЦИОР (http://fcior.edu.ru)

• Алгоритмически неразрешимые задачи

Самое важное в главе 5

---

• Интуитивное понятие алгоритма, которое мы использовали ранее, непригодно для математического доказательства неразрешимости задач.

• Входные и выходные данные любого алгоритма можно закодировать в виде последовательностей символов некоторого алфавита (и даже двоичного алфавита). Про любой алгоритм можно сказать следующее:

-алгоритм получает на вход дискретный объект (например, слово);

-алгоритм обрабатывает входной объект по шагам (дискретно), строя на каждом шаге промежуточные дискретные
объекты; этот процесс может закончиться или не закон-

-если выполнение алгоритма заканчивается, его результат — это объект, построенный на последнем шаге;

-если выполнение алгоритма не заканчивается (алгоритм зацикливается) или заканчивается аварийно, то результат его работы при данном входе не определён.

• Алгоритм — это программа для некоторого исполнителя.

•Универсальный исполнитель — это исполнитель, который может моделировать работу любого другого исполнителя. Это значит, что для любого алгоритма, написанного для лю​бого исполнителя, существует эквивалентный алгоритм для универсального исполнителя.

• Все универсальные исполнители эквивалентны между собой. Каждый алгоритм задаёт (вычисляет) функцию, которая преобразует входное слово в результат (выходное слово). Алгоритмы называются эквивалентными, если они задают одну и ту же функцию.

• Вычислимая функция — это функция, для вычисления которой существует алгоритм. Любая вычислимая функция может задаваться разными алгоритмами.

• Алгоритмически неразрешимая задача — это задача, соответствующая невычислимой функции.

• Говорят, что алгоритм имеет асимптотическую сложность O(f(n)), если найдётся такая постоянная с, что, начиная с некоторого n = n₀, выполняется условие Т(n) <=c•f(n).

• Задачи оптимизации, которые решаются только полным перебором вариантов, могут иметь, например, асимптотиче​скую сложность О(2ⁿ) или O(n!). Эти функции при больших п возрастают быстрее, чем многочлен любой степени.

• Чтобы обеспечить надёжность программы, используют ме​тоды доказательного программирования: разработка программы ведётся одновременно с доказательством её пра​вильности.

• Инвариант цикла — это соотношение между величинами, которое остаётся справедливым после завершения любого шага цикла.