Теория алгоритмов отвечает на два вопроса: что вообще может быть вычислено и насколько быстро. Первый ответ неожиданный — существуют задачи, неразрешимые никаким алгоритмом в принципе.
Что нужно знать
- Машина Тьюринга — формальная модель алгоритма: бесконечная лента, головка и таблица переходов.
- На каждом шаге головка читает символ, записывает новый, сдвигается и меняет состояние.
- Тезис Чёрча — Тьюринга: всё, что интуитивно вычислимо, вычислимо на машине Тьюринга.
- Существуют алгоритмически неразрешимые задачи; классический пример — проблема остановки.
- Сложность алгоритма оценивают ростом числа операций от размера входных данных.
- Типичные порядки: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$.
- Линейный поиск — $O(n)$, двоичный по отсортированному массиву — $O(\log n)$.
Где чаще всего ошибаются
- Считают неразрешимость следствием нехватки вычислительной мощности — это принципиальный запрет, а не технический.
- Применяют двоичный поиск к неотсортированному массиву.
- Сравнивают алгоритмы по числу строк кода, а не по порядку роста.
- Считают $O(n^2)$ вдвое хуже $O(n)$ — разница растёт с размером данных.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информатика · 11 класс · Поляков, 2023 · Глава 5 · Элементы теории алгоритмов