Теоретическая информатика: что и как можно вычислить
Теоретическая информатика изучает алгоритмы, формальные языки, вычислимость и сложность задач. Она задаёт модели и доказывает свойства процедур, включая решаемость и требуемые ресурсы.
Разработка ПО и работа системы связаны с теорией, но сосредоточены на реализации и поведении.
Теоретическая информатика
1. Структуры данных
Структура данных задаёт способ представить и организовать данные так, чтобы поддерживать нужные операции: поиск, добавление, удаление, обход или обновление.
Массив даёт быстрый доступ по индексу, связный список облегчает вставки в известных позициях, а дерево или хеш-таблица предлагают иные компромиссы между временем, памятью и порядком элементов. «Оптимальной» структуры без задачи не существует: выбор зависит от частоты операций, объёма данных и требований к корректности.
2. Алгоритмы и их анализ
Пошаговые инструкции и их «цена» (скорость и память). Фундамент эффективных вычислений.
3. Криптография и безопасность
Защита данных с помощью математических барьеров. Наука о шифровании и обеспечении конфиденциальности.
4. Теория Искусственного Интеллекта
Математические модели обучения. Создание систем, способных к обучению и принятию решений.
Формальные языки и автоматы
Теория формальных языков и автоматов изучает множества строк и способы их задания или распознавания. Грамматики описывают правила порождения, а автоматы — вычислительные модели обработки строк; возможности модели зависят, в частности, от доступной памяти.
Формальная семантика языков программирования
Формальная семантика задаёт математическое значение выражений и программных конструкций. Она помогает точно описывать вычисление и доказывать свойства программы.
Операционная семантика задаёт переходы между состояниями, денотационная сопоставляет конструкции математическим объектам, а аксиоматическая связывает программу с логическими утверждениями. Это отличается от синтаксиса, который описывает допустимую форму записи.
Теория вычислимости
Что можно вычислить алгоритмически? Машина Тьюринга (1936): универсальная модель вычислений. Тезис Чёрча-Тьюринга: всё интуитивно вычислимое = тьюринг-вычислимое. Неразрешимость: проблема остановки (Halting problem). Рекурсивные и рекурсивно перечислимые множества.
Теория сложности
Теория вычислительной сложности изучает ресурсы, необходимые для решения задач, прежде всего время и память. Класс NP включает задачи распознавания с полиномиальной проверкой свидетельства положительного ответа; принадлежность к NP сама по себе не доказывает неполиномиальную трудность.