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

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

История

Предыстория и интуитивное понятие алгоритма

Понятие алгоритма существовало задолго до появления теории: древние вавилоняне использовали алгоритмы для вычислений, Евклид описал алгоритм нахождения наибольшего общего делителя (алгоритм Евклида), а в IX веке персидский математик аль-Хорезми систематизировал правила арифметических действий. Однако до начала XX века алгоритм понимался интуитивно как последовательность инструкций, не требующая формального определения.

Формализация в начале XX века

В 1900 году Давид Гильберт сформулировал проблему разрешения (Entscheidungsproblem): существует ли алгоритм, который для любого утверждения в формальной арифметике определяет, истинно оно или ложно? Для ответа на этот вопрос потребовалось строго определить, что такое «алгоритм».

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

Развитие теории сложности

В 1960-х годах, с появлением электронных вычислительных машин, акцент сместился с вопроса «что можно вычислить?» на вопрос «как эффективно это сделать?». Были введены классы сложности P (задачи, решаемые за полиномиальное время) и NP (задачи, решение которых можно проверить за полиномиальное время). Стивен Кук в 1971 году сформулировал P vs NP — одну из главных нерешённых задач современной информатики. В 1970-х годах Ричард Карп и другие исследователи разработали теорию NP-полноты, позволяющую классифицировать задачи по их вычислительной сложности.

Основные понятия

Алгоритм

Алгоритм — это точное и конечное описание последовательности действий, предназначенное для преобразования входных данных в выходные. Ключевые свойства алгоритма:

• Дискретность — разбиение на отдельные шаги.
• Детерминированность (в классическом случае) — однозначность результата каждого шага.
• Результативность — завершение за конечное число шагов.
• Массовость — применимость к целому классу задач.

Вычислимость

Функция называется вычислимой, если существует алгоритм, который для любого допустимого входа выдаёт правильный результат за конечное время. Функции, для которых такого алгоритма не существует, называются невычислимыми. Классический пример — функция, определяющая, остановится ли произвольная программа (проблема остановки). Невычислимость доказывается методами диагонализации (аналогично канторовскому доказательству несчётности вещественных чисел).

Формальные модели вычислений

Теория алгоритмов использует несколько эквивалентных моделей, каждая из которых удобна для разных задач:

• Машина Тьюринга — ленточная модель с конечным автоматом управления.
• λ-исчисление — модель, основанная на подстановке и аппликации функций.
• Рекурсивные функции (по Клини) — функции, заданные через базовые операции (нуль, след, проекция) и операторы суперпозиции, примитивной рекурсии и минимизации.
• Нормальные алгоритмы Маркова — система подстановок строк.
• Машина с произвольным доступом (RAM) — модель, приближенная к реальным компьютерам.

Все эти модели эквивалентны по вычислительной мощности (тезис Чёрча — Тьюринга).

Классификация задач по сложности

Классы сложности

Теория сложности вычислений делит задачи на классы в зависимости от необходимых ресурсов:

• P — задачи, решаемые детерминированным алгоритмом за полиномиальное время (например, проверка простоты числа, сортировка).
• NP — задачи, решение которых можно проверить за полиномиальное время (например, задача выполнимости булевых формул (SAT), задача о коммивояжёре в формулировке «существует ли маршрут короче K?»).
• EXPTIME — задачи, решаемые за экспоненциальное время.
• PSPACE — задачи, решаемые с полиномиальным объёмом памяти.

P vs NP

Вопрос о равенстве классов P и NP является одной из семи «Проблем тысячелетия» (за решение назначен приз в 1 млн долларов от Института Клэя). Подавляющее большинство специалистов полагает, что P ≠ NP, то что существуют задачи, которые можно проверить быстро, но нельзя быстро решить. Доказательство или опровержение этого утверждения имеет огромное практическое значение для криптографии, оптимизации и искусственного интеллекта.

NP-полные задачи

Задача называется NP-полной, если она принадлежит классу NP и к ней можно свести любую другую задачу из NP за полиномиальное время. Если для какой-либо NP-полной задачи будет найден полиномиальный алгоритм, то P = NP. Примеры NP-полных задач:

• Задача о выполнимости булевых формул (SAT).
• Задача о вершинном покрытии.
• Задача о клике.
• Задача о рюкзаке.
• Задача коммивояжёра (в формулировке поиска точного оптимума).

Некоторые неразрешимые проблемы

Проблема остановки

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

Теорема Гёделя о неполноте и её связь с алгоритмами

Первая теорема Гёделя о неполноте (1931) утверждает, что в любой достаточно богатой формальной системе (например, арифметике Пеано) существуют истинные, но недоказуемые утверждения. Это означает, что не существует алгоритма, который мог бы вывести все истинные математические утверждения. Теорема Гёделя является фундаментальным ограничением для автоматического доказательства теорем.

Проблема эквивалентности программ

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

Применение теории алгоритмов

Разработка программного обеспечения

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

Криптография

Стойкость большинства современных криптосистем (RSA, ECC) основана на предположении, что некоторые задачи (факторизация больших чисел, дискретное логарифмирование) не имеют эффективных алгоритмов решения (то есть не лежат в классе P). Если будет доказано, что P = NP, многие криптографические схемы окажутся уязвимыми.

Искусственный интеллект

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

Биоинформатика

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

Интересные факты

• Колмогоровская сложность — раздел теории алгоритмов, изучающий минимальную длину программы, способной воспроизвести заданную строку. Она является мерой «случайности» данных.
• Квантовые вычисления не опровергают тезис Чёрча — Тьюринга, но могут решать некоторые задачи (например, факторизацию чисел) экспоненциально быстрее классических компьютеров (алгоритм Шора).
• В 2022 году российский математик Александр Разборов (признан иноагентом в РФ) получил премию Тьюринга за работы по теории сложности вычислений, в частности за доказательство нижних оценок для схемной сложности.

Источники

• Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи». — М.: Мир, 1982.
• Хопкрофт Дж., Мотвани Р., Ульман Дж. «Введение в теорию автоматов, языков и вычислений». — М.: Вильямс, 2002.
• Ахо А., Хопкрофт Дж., Ульман Дж. «Структуры данных и алгоритмы». — М.: Вильямс, 2000.
• Тьюринг А. «О вычислимых числах с приложением к проблеме разрешения» (1936).
• Клини С. «Введение в метаматематику». — М.: ИЛ, 1957.
• Марков А. А. «Теория алгоритмов». — М.: Наука, 1954.