Теория алгоритмов


Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук[1][2], теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники.

Развитие теории алгоритмов начинается с доказательства Куртом Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 году. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 1930-е годы в работах Алана Тьюринга, Эмиля Поста и Алонзо Чёрча. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление оказались эквивалентными друг другу. Основываясь на работах Гёделя, Стивен Клини ввёл понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.

Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое Андреем Марковым понятие нормального алгоритма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.

В последующие годы значительный вклад в теорию алгоритмов внесли Дональд Кнут, Aльфред Ахо и Джеффри Ульман.

Алан Тьюринг высказал предположение (известное как «тезис Чёрча — Тьюринга»), что любой алгоритм, — в интуитивном смысле слова, — может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия такой машины (и других эквивалентных ей понятий) открыло возможность строгого доказательства алгоритмической неразрешимости различных массовых проблем (проблем нахождения единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах).

Простейший пример алгоритмически-неразрешимой массовой проблемы — проблема применимости алгоритма, проблема остановки, которая заключается в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить — завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго?