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

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

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

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

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

• Машина Тьюринга — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
• Лямбда-исчисление — рассматривается пара: λ-выражение и его аргумент, — а вычислением считается применение, или апплицирование, первого члена пары ко второму. Это позволяет отделить функцию и то, к чему она применяется. В более общем случае вычислением считаются цепочки, начинающиеся с исходного λ-выражения, за которым следует конечная последовательность λ-выражений, каждое из которых получается из предыдущего применением β-редукции, то есть правила подстановки.
• Комбинаторная логика — трактовка вычисления сходна с λ-исчислением, но имеются и важные отличия (например, комбинатор неподвижной точки Y имеет нормальную форму в комбинаторной логике, а в λ-исчислении — нет). Комбинаторная логика была первоначально разработана для изучения природы парадоксов и для построения концептуально ясных оснований математики, причем представление о переменной исключалось вовсе, что помогало прояснить роль и место переменных в математике.
• Регистровые машины, в частности, RAM-машина — абстрактная вычислительная машина, моделирующая компьютер с произвольным доступом к памяти. Именно эта модель вычислений наиболее часто используется при анализе алгоритмов.

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

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

В течение первого десятилетия истории теории алгоритмов, неразрешимые массовые проблемы были обнаружены лишь в ней самой (в том числе, описанная выше «проблема применимости») и в математической логике («проблема выводимости» в классическом исчислении предикатов). Поэтому считалось, что теория алгоритмов представляет собой «обочину» математики, не имеющую значения для таких её классических разделов, как «алгебра» или «анализ». Положение изменилось после того, как Андрей Марков и Эмиль Пост в 1947 году установили алгоритмическую неразрешимость известной в алгебре проблемы равенства для конечнопорождённых и конечноопределённых полугрупп (проблема Туэ). Впоследствии, была установлена алгоритмическая неразрешимость и многих других «чисто математических» массовых проблем, наиболее известным результатом в этой области является доказанная Юрием Матиясевичем алгоритмическая неразрешимость десятой проблемы Гильберта.

Теория алгоритмов развивается, главным образом, по трём направлениям:

• Классическое:
  • Формальная формулировка задач;
  • Понятие проблемы разрешения;
  • Классификация уровней сложности («P», «NP» и другие).
• Анализ:
  • Асимптотический:
    • Оценка ресурсоёмкости и времени выполнения (в частности, для рекурсивных алгоритмов);
    • Оценка роста потребности в ресурсах (например, времени выполнения) с увеличением объёма данных.
  • Практический:
    • Получение «явных» функции трудоёмкости;
    • Интервальный анализ функций;
    • Поиск критериев качества;
    • Методика рационального выбора.

Цель анализа — нахождение оптимального алгоритма. Критерий — трудоёмкость (количество необходимых алгоритму элементарных операций). Функция трудоёмкости — соотношение трудоёмкости с входными данными.

На трудоёмкость могут в разной мере влиять свойства входных данных:

• Объём;
• Значения;
• Порядок поступления.

Один из упрощённых видов анализа затратности алгоритмов — асимптотический, с большим объёмом входных данных. Используемая оценка функции трудоёмкости — «сложность» алгоритма, позволяющая определить связь трудоёмкости с объёмом данных. В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Ниже перечислены основные оценки сложности.

Основной оценкой функции сложности алгоритма ${\displaystyle f(n)}$ (где n — величина объёма данных, «длина входа») является ${\displaystyle {\boldsymbol {\Theta }}}$:

${\displaystyle f(n)={\boldsymbol {\Theta }}(g(n))}$

если при g > 0 при n > 0 существуют положительные с₁, с₂, n₀, такие, что:

${\displaystyle c_{1}\cdot g(n)\leq \;f(n)\leq \;c_{2}\cdot g(n)}$

при ${\displaystyle n>n_{0}}$; иначе говоря, можно найти такие ${\displaystyle c_{1}}$ и ${\displaystyle c_{2}}$, что, — при достаточно больших ${\displaystyle n}$, — ${\displaystyle f(n)}$ будет заключена между:

${\displaystyle c_{1}\cdot \;g(n)}$ и ${\displaystyle c_{2}\cdot \;g(n)}$.

В таком случае говорят ещё, что функция ${\displaystyle g(n)}$ является асимптотически точной оценкой функции ${\displaystyle f(n)}$, так как по определению функция ${\displaystyle f(n)}$ не отличается от функции ${\displaystyle g(n)}$ с точностью до постоянного множителя (см. асимптотическое равенство). Например, для метода сортировки «heapsort», оценка трудоёмкости составляет:

${\displaystyle f(n)={\boldsymbol {\Theta }}(n\log n)}$, то есть ${\displaystyle g(n)=n\log n}$.

Из ${\displaystyle f(n)={\boldsymbol {\Theta }}(g(n))}$ следует ${\displaystyle g(n)={\boldsymbol {\Theta }}(f(n))}$.

${\displaystyle {\boldsymbol {\Theta }}(g(n))}$ представляет собой не функцию, а множество функций, описывающих рост ${\displaystyle f(n)}$ с точностью до постоянного множителя. ${\displaystyle {\boldsymbol {\Theta }}}$ даёт одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности. Оценка ${\displaystyle {\boldsymbol {O}}}$ представляет собой верхнюю асимптотическую оценку трудоёмкости алгоритма. Мы говорим, что ${\displaystyle f(n)={\boldsymbol {O}}(g(n))}$, если:

${\displaystyle \exists \;c>0,n_{0}>0:0\leq \;f(n)\leq \;cg(n),\forall \;n>n_{0}}$.

Иначе говоря, запись ${\displaystyle f(n)={\boldsymbol {O}}(g(n))}$ означает, что ${\displaystyle f(n)}$ принадлежит классу функций, которые растут не быстрее, чем функция ${\displaystyle g(n)}$ с точностью до постоянного множителя.

Оценка ${\displaystyle {\boldsymbol {\Omega }}}$ задает нижнюю асимптотическую оценку роста функции ${\displaystyle f(n)}$ и определяет класс функций, которые растут не медленнее, чем ${\displaystyle g(n)}$ с точностью до постоянного множителя. ${\displaystyle f(n)={\boldsymbol {\Omega }}(g(n))}$, если:

${\displaystyle \exists \;c>0,n_{0}>0:0\leq \;c\,g(n)\leq \;f(n),\forall \;n>n_{0}}$.

Например, запись ${\displaystyle f(n)={\boldsymbol {\Omega }}(n\,\log n)}$ обозначает класс функций, которые растут не медленнее, чем ${\displaystyle g(n)=n\,\log n}$; в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.

Равенство ${\displaystyle f(n)={\boldsymbol {\Theta }}(g(n))}$ выполняется тогда и только тогда, когда ${\displaystyle f(n)={\boldsymbol {O}}(g(n))}$ и ${\displaystyle f(n)={\boldsymbol {\Omega }}(g(n))}$.

Асимптотический анализ алгоритмов имеет не только практическое, но и теоретическое значение. Так, например, доказано, что все алгоритмы сортировки, основанные на попарном сравнении элементов, отсортируют n элементов за время, не меньшее ${\displaystyle {\boldsymbol {\Omega }}(n\,\log n)}$.

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

В рамках классической теории, осуществляется классификация задач по их сложности (P-сложные, NP-сложные, экспоненциально сложные и другие):

• «P» — могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, «машина Тьюринга»);
• «NP»:
  • Задачи, решение которых осуществимо за полиномиально выраженное время с помощью недетерминированной вычислительной машины (следующее состояние которой не всегда однозначно определяется предыдущими). Её работу можно представить как разветвляющийся на каждой неоднозначности процесс: задача решена, если хотя бы одна ветвь достигла ответа;
  • Задачи, решение которых с помощью дополнительной информации полиномиальной длины, данной нам свыше, мы можем проверить за полиномиальное время. В частности, к классу «NP» относятся все задачи, решение которых можно проверить за полиномиальное время.

Класс «P» содержится в «NP». Классическим примером NP-задачи является «Задача о коммивояжёре».

Поскольку «P» содержится в «NP», принадлежность той или иной задачи к классу «NP» зачастую отражает наше текущее представление о способах решения данной задачи и носит неокончательный характер. В общем случае нет оснований полагать, что для той или иной NP-задачи не может быть найдено P-решение. Вопрос о возможной эквивалентности классов «P» и «NP» (о возможности нахождения P-решения для любой NP-задачи) считается одним из основных в современной теории сложности алгоритмов; ответ на него не найден до сих пор. Сама его постановка возможна благодаря введению понятия NP-полных задач; любые NP-задачи могут быть к ним сведены — и если для NP-полной задачи будет найдено P-решение, то P-решение будет найдено для всех NP-задач. Примером NP-полной задачи является «Задача о конъюнктивной форме».

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

Некоторые приложения теории алгоритмов:

• исследование массовых проблем;
• приложения к основаниям математики: конструктивная семантика;
• приложения к математической логике: анализ формализованных языков логики и арифметики;
• вычислимый анализ;
• нумерованные структуры;
• приложения к теории вероятностей: определения случайной последовательности;
• приложения к теории информации: алгоритмический подход к понятию количества информации;
• оценки сложностей решения отдельных задач;
• влияние теории алгоритмов на алгоритмическую практику^[3].

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
• Дональд Кнут. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: Вильямс, 2006. — 720 с. — ISBN 0-201-89683-4.
• Колмогоров А. Н. Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.
• Марков А. А., Нагорный Н. М. Теория алгорифмов. — 2-е изд.. — М.: Фазис, 1996.

• Лекции по теории сложности и комбинаторным алгоритмам