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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Возникновение теории алгоритмов[править | править вики-текст]

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

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

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

Одной из лучших работ на эту тему является книга «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза И. Лейзерсона, Рональда Л. Ривеста, Клиффорда Штайна.

Модели вычислений[править | править вики-текст]

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

Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы[править | править вики-текст]

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

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

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

Современное состояние теории алгоритмов[править | править вики-текст]

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

Анализ трудоёмкости алгоритмов[править | править вики-текст]

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

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

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

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

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

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

при n > n0; иначе говоря, можно найти такие с1 и с2, что, — при достаточно больших n, — будет заключена между

и .

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

, то есть .

Из следует .

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

даёт одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности. Оценка представляет собой верхнюю асимптотическую оценку трудоёмкости алгоритма. Мы говорим, что , если

.

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

Оценка задает нижнюю асимптотическую оценку роста функции и определяет класс функций, которые растут не медленнее, чем с точностью до постоянного множителя. , если

.

Например, запись обозначает класс функций, которые растут не медленнее, чем ; в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы.

Равенство выполняется тогда и только тогда, когда и .

Асимптотический анализ алгоритмов имеет не только практическое, но и теоретическое значение. Так, например, доказано, что все алгоритмы сортировки, основанные на попарном сравнении элементов, отсортируют 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-полной задачи является «Задача о конъюнктивной форме».

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

Математические приложения теории алгоритмов[править | править вики-текст]

  1. Исследование массовых проблем;
  2. Приложения к основаниям математики: конструктивная семантика;
  3. Приложения к математической логике: анализ формализованных языков логики и арифметики;
  4. Вычислимый анализ;
  5. Нумерованные структуры;
  6. Приложения к теории вероятностей: определения случайной последовательности;
  7. Приложения к теории информации: алгоритмический подход к понятию количества информации;
  8. Оценки сложностей решения отдельных задач;
  9. Влияние теории алгоритмов на алгоритмическую практику.[3]

См. также[править | править вики-текст]

Литература[править | править вики-текст]

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

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Семёнов А. Л., Успенский В. А. Математическая логика в вычислительных науках и вычислительной практике. // Вестник Академии наук СССР, № 7, с. 93 — 103
  2. Успенский В. А., Семёнов А. Л. Решимые и нерешимые алгоритмические проблемы. // Квант, 1985, № 7, с. 9 — 15
  3. В. А. Успенский, А. Л. Семёнов Теория алгоритмов: основные открытия и приложения, М., Наука, 1987, 288 c.