Теория алгоритмов — формальные основы
В практическом введении в алгоритмы мы говорили о шагах, блок-схемах и свойствах "дискретность — определённость — конечность". Этого достаточно, чтобы писать программы. Теория алгоритмов отвечает на другой вопрос: что вообще считается алгоритмом в математике и почему одни задачи принципиально не решаются кодом.
Эта статья — первая в цепочке по теории автоматов и формальных языков. Дальше: рекурсивные функции, машина Тьюринга.
Формальное определение объясняет, почему нельзя "написать универсальный анализатор без false positive", почему regex не разбирает вложенные скобки и почему спецификация "алгоритм должен завершиться" — не пустые слова в контракте SLA.
Термины главы — в словаре.
Для читателя без математического фона
Если вы уже писали циклы и функции — вы уже пользовались алгоритмами. Эта статья показывает, как математики записывают ту же идею строго, чтобы можно было доказывать пределы — "такую проверку для всех программ написать нельзя", "этот язык описывает только regex, а для скобок нужен парсер".
Как читать по шагам:
- "Общее понятие" и таблица задача / экземпляр — базовый словарь на весь курс ТАФЯ.
- "Требования к алгоритмам" — сверяйте с реальным кодом: есть ли выход из цикла, один ли метод на всех входах.
- "Математическое определение" и "алфавитный оператор" — плотнее; при первом проходе достаточно идеи, детали доберёте в статье 42.
- Разбор скобок и упражнение связывают теорию с regex и стеком.
Достаточно знать из школьного курса: "функция" как правило "вход → ответ", "для любого n" в формулировках. Доказательства на первом чтении можно пропустить — важнее понять смысл слов.
Общее понятие алгоритма
Алгоритм в быту — понятная инструкция: "вскипятить воду → залить в чашку". В информатике добавляется требование массовости: один и тот же метод должен применяться к классу задач, а не к единственному чаю.
Пример массового алгоритма: "найти максимум в конечном списке чисел". Вход — список произвольной длины (но конечной); выход — одно число. Конкретный список [3, 1, 9] — лишь экземпляр задачи.
| Понятие | Смысл |
|---|---|
| Задача (проблема) | Семейство пар "вход → ожидаемый ответ" |
| Экземпляр (вход) | Конкретные данные для одного запуска |
| Алгоритм | Правило, которое для каждого допустимого входа за конечное число шагов выдаёт ответ (или корректно сообщает, что вход недопустим) |
Программа на Python — реализация алгоритма на конкретной машине с ограниченной памятью. Теория же часто рассматривает идеализированную машину с неограниченной памятью, чтобы отделить "невозможно в принципе" от "не влезло в RAM".
Разбор на пальцах — "максимум в списке"
Задача: для любого конечного списка целых чисел вернуть наибольший элемент (если список пуст — сообщить об ошибке).
| Уровень | Что это |
|---|---|
| Экземпляр | [3, 1, 9, 2] |
| Алгоритм | "взять первый как текущий максимум; для каждого следующего, если он больше — обновить максимум; в конце вернуть" |
| Программа | def max_in_list(a): ... на Python |
| Запуск | один вызов с конкретным массивом в памяти 16 ГБ |
Один и тот же алгоритм работает для списка из 3 и из 3 000 000 элементов — меняется только время (см. анализ сложности), а схема шагов та же. Если бы вы вручную расписали "для [3,1,9] сделай так, для [0,5] — иначе" без общего правила — это была бы инструкция для одного экземпляра, без массовости.
Основные требования к алгоритмам
В учебниках и стандартах (в духе ГОСТ 19.701 для блок-схем) перечисляют свойства, в духе учебных определений. В теории алгоритмов их уточняют:
Дискретность
Процесс разбит на отдельные шаги, между которыми система находится в одном из конечного набора состояний. Переходы дискретны: между шагами нет "полушага" — только скачок. Именно поэтому модели вроде конечного автомата и машины Тьюринга естественны: состояние + правило перехода.
Аналогия: игра в шахматы — ход за ходом, после каждого хода позиция полностью определена. Компьютер между инструкциями тоже в конкретном состоянии (значения переменных, счётчик команд). Непрерывная физика процессора скрыта под дискретной моделью "одна машинная инструкция — один шаг".
В коде: for, присваивание, вызов функции — шаги. sleep(0.5) в спецификации алгоритма сортировки обычно лишний: он про реальное время, а про логику преобразования данных.
Определённость (детерминированность)
На каждом шаге однозначно известно, что делать дальше. Если правило допускает ветвление, выбор должен быть задан формально (условие на данные), а не "на усмотрение исполнителя".
В коде
ifс чётким условием — детерминированность. Фраза "обработай по ситуации" в постановке задачи — не алгоритм, пока ситуации не классифицированы.
Недетерминированные модели (например, НКА) в теории тоже есть, но они описывают язык через "существует допустимый путь"; реализация на железе обычно детерминизирует их (см. конечные автоматы).
Конечность (завершаемость)
Для каждого допустимого входа число шагов конечно. Алгоритм сортировки, который на некоторых массивах крутится вечно, — дефект, а не "особый режим".
В теории вычислимости отдельно рассматривают частичные алгоритмы: на части входов ответ есть, на части — зацикливание. Это связано с рекурсивно перечислимыми множествами.
Массовость и конструктивность
Алгоритм задан схемой, не зависящей от размера входа: "для любого n" повторить тело цикла, а не "для n = 5 сделай пять раз вручную". Конструктивность: результат не только существует, но и получен явной процедурой.
Результативность
После остановки остаётся понятный результат — число, строка, "да/нет", изменённая лента. Пустая трата времени без выхода не считается алгоритмом в строгом смысле.
Массовость (формально)
В учебниках по теории алгоритмов массовость означает: описание не привязано к одному фиксированному входу. Параметр n (длина строки, размер массива) может быть любым натуральным, а схема шагов одна и та же.
| Постулат | Инженерный аналог |
|---|---|
| Один алгоритм — бесконечно много входов | одна функция sort(arr), а не развернутый код для arr длины 5 |
| Длина входа конечна | файл не бесконечен, но "на сколько угодно большой" |
Время может расти с n | O(n log n) — норма; бесконечный цикл на части входов — уже частичный случай |
Эффективная вычислимость
Тезис Чёрча–Тьюринга говорит о существовании алгоритма. Отдельно вводят эффективную (разумно быструю) вычислимость — это уже теория сложности (P, NP), см. анализ алгоритмов. Важно не смешивать — задача может быть вычислима, но практически неприемлема (например, перебор 2^n состояний).
Сводка для сопоставления с кодом:
| Свойство | В программе | Если нарушено |
|---|---|---|
| Дискретность | инструкции, тики event loop | неформализуемая "непрерывная" логика |
| Определённость | нет random без seed в спецификации | гонки, недетерминированные тесты |
| Конечность | цикл с условием выхода | зависание, OOM без прогресса |
| Массовость | параметризованный вход | хардкод под один файл |
| Результативность | return, запись в БД | silent hang |
Подробнее о школьной традиции: раздел 21 «Базовой информатики», Алгоритмы, языки и программирование.
Математическое определение алгоритма
Интуиция "алгоритм = инструкция" недостаточна для доказательств. В XX веке предложили эквивалентные формальные модели:
| Модель | Идея | Где читать у нас |
|---|---|---|
| Машина Тьюринга | Лента, головка, таблица переходов | статья 42 |
| Машина Поста | Маркировка и сдвиг по ленте; две элементарные команды | раздел 21 — краткий обзор |
| Лямбда-исчисление | Функции и подстановка | Великие люди — Чёрч |
| Частично-рекурсивные функции | Базовые функции + схемы | статья 41 |
| Нормальные алгоритмы Маркова | Подстановки в строке | ниже, кратко |
Тезис Чёрча–Тьюринга (научная гипотеза) — всё, что интуитивно эффективно вычислимо, реализуемо на машине Тьюринга (и в других перечисленных моделях). Отсюда — одна "граница вычислимости" для проблемы остановки, эквивалентности программ и т.д.
Для разработчика тезис означает: любой ваш код на Тьюринг-полном языке не сильнее абстрактной МТ — а значит, общие "волшебные" проверки всего поведения невозможны.
Нормальный алгоритм Маркова
Работают со словами над алфавитом. Есть набор правил подстановки: "если в строке встретился фрагмент α, замени его на β". Применяют правила по фиксированной стратегии (например, первое сработавшее слева направо), пока ни одно не применимо — результат.
Пример (учебный) — алфавит {a, b}, правило a → ab на слове a даёт рост строки; важно доказать завершение или зацикливание подстановок.
Марковские алгоритмы удобны для доказательств в теории строк; компиляторы напрямую на них не пишут, но это ещё один способ сказать: алгоритм = чёткое преобразование символов.
Развёрнутый пример. Алфавит {a, b}, правила (слева направо, первое применимое):
a → bab → ab
Старт со слова a. Цепочка подстановок может расти; в учебных задачах доказывают завершение (алгоритм Маркова применим к слову) или описывают предел. Сравните с макросами в редакторе — "замени все foo на bar" — тот же дух, но без гарантии остановки, если правила цикличны.
Связь с компилятором: фаза оптимизации "подстановка шаблонов в AST" — не Марков в чистом виде, но последовательные переписывания дерева по правилам — та же идея нормального алгоритма на структурах, а не только на строках.
Понятие алфавитного оператора
В классических курсах по теории алгоритмов и ТАФЯ часто вводят алфавитный оператор — правило, которое преобразует слова (конечные последовательности символов из алфавита Σ).
Обозначение в духе: Op : Σ* → Σ* (от множества всех слов в себя).
Читается так: Σ* — "все возможные конечные строки из букв алфавита Σ" (звёздочка — "ноль и больше повторений"). Оператор берёт такую строку и выдаёт новую строку того же алфавита (или расширенного).
Пошаговый микропример. Алфавит {a, b}. Оператор "удалить все a":
| Вход | Выход | Что произошло |
|---|---|---|
aba | b | убрали обе a |
bbb | bbb | a не было |
ε (пустая строка) | ε | нечего удалять |
Оператор детерминирован, если один вход всегда даёт один выход. Распознаватель языка можно записать как оператор Σ* → {да, нет} — "да", если строка входит в язык (например, только цифры).
| Пример оператора | Описание |
|---|---|
| reverse | abc → cba |
удалить все a | aba → b |
| инкремент в двоичной записи | 1011 → 1100 (с переносом) |
Алгоритм над словами — композиция конечного числа таких операторов, где каждый шаг однозначен. Машина Тьюринга — частный случай: один "супер-оператор" с доступом к ленте и состоянию.
Связь с формальными языками: язык — множество слов L ⊆ Σ*. Распознаватель (автомат) — алфавитный оператор, который переводит вход в "принято / отклонено" (часто через достижение принимающего состояния).
Распознавание и вычисление
| Тип задачи | Вход | Выход | Модель |
|---|---|---|---|
| Распознавание (decision) | слово w | да/нет: w ∈ L? | ДКА, МПА, МТ |
| Вычисление (function) | данные x | значение f(x) | рекурсивные функции, МТ с декодированием ленты |
| Преобразование | слово | другое слово | алфавитный оператор, трансдуктор |
Язык программирования задаёт и синтаксис (распознать программу), и семантику (вычислить результат) — два разных алфавитных оператора на разных уровнях.
Кодирование входов
Чтобы машина Тьюринга "считала" программу, строку JSON или число, всё кодируют словом над фиксированным алфавитом — биты, UTF-8, разделители. Универсальный интерпретатор получает на ленте ⟨код программы⟩ # ⟨вход⟩. Отсюда вся мощь сведений (reduction): "если бы задача X решалась алгоритмом, то и остановку можно было бы решить".
От алгоритма к программе
На этапе C выбирают модель по удобству: доказать неразрешимость — через машину Тьюринга; описать синтаксис — через грамматику; проверить токены — через конечный автомат.
Типичные ошибки понимания
- "Алгоритм = программа" — программа может содержать библиотеки, ОС, прерывания; алгоритм — логическое ядро преобразования входа.
- "Недетерминизм в коде = нарушение определённости алгоритма" — в спецификации задачи может быть "вернуть любой из оптимальных ответов"; важно, что множество допустимых выходов задано.
- "Бесконечный цикл всегда ошибка" — сервер и event loop бесконечны по дизайну; алгоритм "обслуживать запросы" формулируют иначе (частичная вычислимость, реактивные системы).
Связь с остальным курсом (карта)
| Вопрос новичка | Статья |
|---|---|
| Почему regex не для JSON? | Конечные автоматы и регулярные языки, Формальные грамматики и разбор |
| Что такое "вычислимо"? | Рекурсивные и вычислимые функции, Машина Тьюринга |
| Почему анализатор не найдёт все баги? | Машина Тьюринга, теорема Райса в Рекурсивные и вычислимые функции |
Разбор — "алгоритм проверки скобок"
Regex без памяти — не описывает сбалансированные (). Стек — МП-автомат. Грамматика S → (S) | ε — тип 2. Одна задача — три уровня иерархии.
def is_balanced(s: str, pairs="()[]{}") -> bool:
openers = {pairs[i]: pairs[i + 1] for i in range(0, len(pairs), 2)}
closers = {v: k for k, v in openers.items()}
stack: list[str] = []
for ch in s:
if ch in openers:
stack.append(ch)
elif ch in closers:
if not stack or stack.pop() != closers[ch]:
return False
return not stack
Явный стек — уровень магазинного автомата; чистый регулярный распознаватель памяти для счётчика вложенности не имеет.
Проследим вручную вход ([)] (ошибка):
| Символ | Действие | Стек после |
|---|---|---|
( | положить | ( |
[ | положить | (, [ |
) | вершина [, ожидали ( | отклонить |
Для () стек в конце пуст — принять.
Упражнение
- "Max в массиве" как таблица состояний на каждом элементе.
- Алфавитный оператор "удалить
//до конца строки". - Для e-mail: что регулярно, что требует парсера.
Вопросы для самопроверки
- Чем задача отличается от экземпляра входа?
- Почему "налить чай один раз" — пример, а не массовый алгоритм?
- Назовите три формальных модели алгоритма и что объединяет тезис Чёрча–Тьюринга.
- Что делает алфавитный оператор и как он связан с распознавателем языка?
Дальше: Рекурсивные и вычислимые функции.
Базовый разбор HTTP и HTTPS находится в отдельной статье — HTTP как основа веб-интеграций.