💻Теоретическая информатика

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

От счётных палочек до теории вычислений

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

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

Структуры данных: как организовать информацию

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

Массив — последовательность элементов с доступом по индексу за O(1). Массив из 10 миллионов чисел находит элемент по номеру мгновенно, но вставка в середину требует сдвига всех последующих элементов — O(n).

Связный список — цепочка узлов, где каждый хранит ссылку на следующий. Вставка за O(1), но поиск элемента — O(n): нужно пройти цепочку от начала.

Хеш-таблица — структура, вычисляющая позицию элемента через хеш-функцию. Поиск, вставка и удаление в среднем за O(1). Словари Python, объекты JavaScript, HashMap в Java — реализации хеш-таблиц.

Дерево — иерархическая структура с корнем и ветвями. Двоичное дерево поиска (BST) хранит элементы упорядоченно: поиск за O(log n). Сбалансированные деревья (AVL, красно-чёрные) гарантируют логарифмическое время даже в худшем случае. B-деревья используются в базах данных — PostgreSQL, MySQL, Oracle хранят индексы именно в B-деревьях.

Граф — набор вершин и рёбер, моделирующий связи: социальные сети, маршруты, зависимости. Алгоритм Дейкстры находит кратчайший путь в графе с неотрицательными весами — его используют GPS-навигаторы и Google Maps.

Алгоритмы и их анализ: скорость имеет цену

Алгоритм — конечная последовательность инструкций, решающая определённую задачу. Два алгоритма могут решать одну задачу, но один обрабатывает миллион элементов за секунду, а другой — за час. Анализ алгоритмов оценивает эту разницу через Big-O нотацию, введённую Паулем Бахманом в 1894 году и популяризированную Эдмундом Ландау.

O(1) — константное время: не зависит от размера входа. Пример: доступ к элементу массива по индексу.

O(log n) — логарифмическое время: удвоение входа добавляет одну операцию. Пример: бинарный поиск в отсортированном массиве. Среди миллиарда элементов находит нужный за ~30 шагов.

O(n) — линейное время: пропорционально размеру входа. Пример: поиск максимума в неотсортированном массиве.

O(n log n) — время лучших алгоритмов сортировки сравнением. Mergesort (1945, Джон фон Нейман) и Quicksort (1960, Тони Хоар) работают за O(n log n) в среднем случае. Доказано, что быстрее сортировать сравнением невозможно.

O(2^n) — экспоненциальное время: каждый дополнительный элемент удваивает число операций. Задача коммивояжёра перебором для 20 городов — более миллиона вариантов; для 50 — больше, чем атомов во Вселенной.

Проблема P vs NP, сформулированная Стивеном Куком в 1971 году, спрашивает: если решение задачи легко проверить (класс NP), значит ли это, что его легко найти (класс P)? Институт Клэя включил этот вопрос в список семи «задач тысячелетия» с призом $1 000 000 за решение. На февраль 2026 года задача остаётся открытой.

Криптография и безопасность: математика на страже данных

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

В 1977 году Ривест, Шамир и Адлеман опубликовали алгоритм RSA — первую практичную систему шифрования с открытым ключом. RSA основан на сложности факторизации: перемножить два больших простых числа (по 300 цифр каждое) — доля секунды, а разложить произведение обратно на множители — миллиарды лет на суперкомпьютере. Каждый HTTPS-запрос в браузере начинается с обмена ключами по протоколу, наследующему идеи RSA.

Симметричное шифрование (AES, принят как стандарт NIST в 2001 году) использует один ключ для шифрования и расшифровки. AES-256 с длиной ключа 256 бит защищает государственные секреты США — полный перебор потребовал бы 2^256 операций, что превышает возможности любого компьютера.

Хеш-функции (SHA-256, используемая в Bitcoin) превращают данные произвольной длины в строку фиксированного размера. Изменение одного бита во входных данных меняет хеш до неузнаваемости — лавинный эффект. Цифровые подписи, блокчейн, проверка целостности файлов — всё строится на хешировании.

Квантовые компьютеры угрожают RSA: алгоритм Шора (1994) факторизует числа за полиномиальное время на квантовом компьютере. Постквантовая криптография — активная область исследований: NIST в 2024 году утвердил первые стандарты (CRYSTALS-Kyber, CRYSTALS-Dilithium), устойчивые к квантовым атакам.

Теория искусственного интеллекта: от формальных моделей к обучению

Искусственный интеллект как научное направление берёт начало с Дартмутского семинара 1956 года, организованного Джоном Маккарти, Марвином Минским, Натаниэлем Рочестером и Клодом Шенноном. Они предложили гипотезу: любой аспект обучения и мышления может быть описан настолько точно, что машина сможет его имитировать.

Символьный ИИ (1950-е — 1980-е) кодировал знания явными правилами. Экспертные системы (MYCIN для диагностики инфекций, 1976) работали по принципу «если-то»: тысячи правил, составленных вручную. Подход упёрся в «проклятие знаний» — невозможность формализовать все правила сложного мира.

Машинное обучение перевернуло подход: вместо явных правил — обучение на данных. Фрэнк Розенблатт построил перцептрон в 1958 году — простейшую нейронную сеть. Метод обратного распространения ошибки (backpropagation), описанный Румельхартом, Хинтоном и Уильямсом в 1986 году, позволил обучать многослойные сети.

Глубокое обучение стало прорывом после 2012 года, когда сеть AlexNet (Алекс Крижевский, Илья Суцкевер, Джеффри Хинтон) выиграла конкурс ImageNet с отрывом в 10 процентных пунктов от ближайших конкурентов. Трансформеры (Vaswani et al., 2017, статья «Attention Is All You Need») легли в основу GPT, BERT и других языковых моделей.

Теоретические вопросы ИИ остаются открытыми. PAC-обучение (Probably Approximately Correct, Лесли Вэлиант, 1984) формализует вопрос: сколько примеров нужно модели, чтобы обобщать с заданной точностью? VC-размерность (Вапник и Червоненкис, 1971) измеряет выразительную мощность модели. Эти результаты не просто абстракции — они определяют, когда нейросеть обучится, а когда переобучится.

Связи между разделами

Четыре направления теоретической информатики переплетены. Криптография опирается на теорию сложности: безопасность RSA следует из предполагаемой трудности факторизации (задачи, которая, по гипотезе, не принадлежит классу P). Алгоритмы машинного обучения используют структуры данных — k-d деревья для поиска ближайших соседей, графы для нейросетей. Анализ алгоритмов задаёт границы того, что ИИ-системы могут вычислить за разумное время.

Теоретическая информатика — не изолированная дисциплина. Каждый запрос к поисковой системе, каждая онлайн-транзакция, каждый ответ голосового помощника опирается на идеи, заложенные Тьюрингом, Шенноном, Куком и их последователями.