§ 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 = n0, выполняется условие Т(n) <=c•f(n).
• Задачи оптимизации, которые решаются только полным перебором вариантов, могут иметь, например, асимптотическую сложность О(2n) или O(n!). Эти функции при больших п возрастают быстрее, чем многочлен любой степени.
• Чтобы обеспечить надёжность программы, используют методы доказательного программирования: разработка программы ведётся одновременно с доказательством её правильности.
• Инвариант цикла — это соотношение между величинами, которое остаётся справедливым после завершения любого шага цикла.