Неразрешимые задачи и сложность вычислений
Чего не может ни один алгоритм — и сколько стоит то, что он может.
11 класс, углублённый уровень — пара четырнадцатая.
Уроки 27–28 поурочного плана: «Алгоритмически неразрешимые задачи. Задача
останова. Невозможность автоматической отладки программ» и «Сложность
вычислений». На прошлых парах мы строго определили, что такое алгоритм: машины
Тьюринга и Поста, алгорифмы Маркова. Теперь, когда определение есть, можно
доказать, что для некоторых задач алгоритма нет вообще.
Алгоритмически неразрешимая задача
Задача алгоритмически неразрешима, если не существует
алгоритма, который решает её при любых входных данных.
Это не «пока не придумали» и не «компьютеры медленные». Доказано, что такого
алгоритма не может быть — ни на каком компьютере, ни за какое время.
Задача останова (А. Тьюринг, 1936): по тексту любой
программы и её входным данным узнать, завершится ли она. Самая известная
неразрешимая задача — и она как раз про программы.
«Запустить и подождать» не помогает: если программа не остановилась за час,
неизвестно, остановится ли она через два.
Почему анализатора не бывает
Допустим, есть программа-анализатор: дай ей текст любой программы и
входные данные — она ответит «остановится» или «не остановится».
Напишем программу Наоборот. Она берёт текст программы P и
спрашивает анализатор: остановится ли P, если дать ей на вход её собственный
текст? Ответ «остановится» — Наоборот уходит в вечный цикл. Ответ «нет» — сразу
останавливается.
Дадим Наоборот её собственный текст.
Остановилась? Значит, анализатор сказал «не остановится» —
ошибся.
Зациклилась? Значит, анализатор сказал «остановится» —
ошибся.
Анализатор ошибается в любом случае. Значит, такой
программы нет: задача останова неразрешима.
А конкретную программу проверить можно
Неразрешима задача для всех программ сразу. Про одну программу часто
можно рассуждать.
Всё, что программа помнит, — одно число n. Выписываем его значения по
виткам:
Дошли до выхода из цикла — программа завершится.
Значение повторилось — дальше всё пойдёт по тому же кругу: программа не
завершится никогда. При n = 5: 5 → 10 → 5 — круг.
Невозможность автоматической отладки
Не бывает программы, которая про любую программу скажет,
верно ли та работает на всех входах: с её помощью решалась бы задача останова.
Остаются тесты. Но тестирование показывает наличие ошибок, а не их
отсутствие (Э. Дейкстра): тестов конечное число, входов — бесконечно
много.
простое ли n
Ищем первую ошибку, а не проверяем всё подряд: подумай,
какое число функция не видит. Здесь — составное без делителей 2, 3, 5, 7,
наименьшее такое 11 · 11 = 121.
Сложность вычислений
Время
Число элементарных действий в зависимости от размера данных n. Не
секунды: секунды зависят от компьютера, а число действий — только от
алгоритма.
Память
Число хранимых значений в зависимости от n. Таблица n × n — это n² чисел.
Важен порядок роста, а не точная формула. Запись 
:
при больших n число действий растёт не быстрее, чем c·n² для некоторой
постоянной c. Поэтому 3n² + 5n и n² — один порядок.
Одна задача может решаться алгоритмами разной сложности —
и выбор между ними важнее, чем быстрый компьютер.
Сколько раз выполнится тело
| что в программе | сколько раз тело | порядок |
|---|
| цикл по n, в нём цикл по m | n · m | n² |
| внутренний цикл до i (или от i до n) | 0 + 1 + … + (n − 1) = n(n − 1)/2 | n² |
| три цикла, i < j < k | n(n − 1)(n − 2)/6 | n³ |
| i умножается на 2, пока i < n | сколько раз удвоить 1, чтобы дорасти до n | log n |
| цикл по n, в нём деление пополам | n · (число делений) | n · log n |
Приём: таблица по виткам внешнего цикла — для
каждого i выпиши, сколько раз сработает внутренний, и сложи. Не умножай вслепую
n · n, если внутренний цикл зависит от i.
Пример: внутренний цикл до i
Сколько раз выполнится 
?
0 + 1 + 2 + 3 + 4 + 5 = 6 · 5 / 2 = 15. Полоски
складываются в треугольник — половина квадрата n × n, поэтому порядок
n².
Как растут время и память
| n | n | n² | n³ | 2ⁿ |
|---|
| 10 | 10 | 100 | 1 000 | 1 024 |
| 20 | 20 | 400 | 8 000 | 1 048 576 |
| 40 | 40 | 1 600 | 64 000 | ≈ 1,1 · 10¹² |
| сложность | n выросло в r раз |
|---|
| n | время × r |
| n² | время × r² — вдвое больше n, вчетверо дольше |
| n³ | время × r³ |
| 2ⁿ (перебор) | n выросло на d — время × 2^d |
Паролей длины L из k знаков — k^L. Длиннее на один знак —
перебор в k раз дольше. Память так же: таблица n × n при вдвое большем n
занимает вчетверо больше.
Какой алгоритм выгоднее
Поиск
Линейный — n сравнений. Двоичный — около log₂n, но только в
упорядоченном массиве.
Сортировка
Выбором — n(n − 1)/2 сравнений. Слиянием — около n · log₂n.
Сравнить a·n² и b·n: сократи на n — a·n > b, то есть n > b/a.
Дальше перебирать не нужно: наименьшее n — первое целое больше b/a.
Экспонента против многочлена — считай подряд. При
малых n перебор бывает выгоднее: 2⁵ = 32 < 5³ = 125. Но с какого-то n
2ⁿ обгоняет любой многочлен — и навсегда: шаг n → n + 1 удваивает 2ⁿ, а n³
растёт меньше чем вдвое.
Зачем это на экзамене
В заданиях 26–27 ЕГЭ данных много — сотни тысяч и миллионы чисел, а время
работы программы ограничено.
Перебор всех пар при n = 10⁶ — это около 10¹²
действий. Программа не успеет.
Алгоритм порядка n — около 10⁶ действий: доли
секунды.
Поэтому, прежде чем писать программу, прикинь: сколько раз выполнится самый
глубокий цикл при настоящем n?
Что верно, а что нет
Верно
- Неразрешимость не мешает разобраться с конкретной программой.
- Тесты могут найти ошибку, но не доказать, что её нет.
- n вдвое больше при n² — время вчетверо.
Неверно
- «Неразрешима, потому что компьютеры медленные». Алгоритма нет в
принципе.
- «Прошла все тесты — ошибок нет».
- «2ⁿ всегда дольше n³». При малых n бывает наоборот.
- «Сложность — число строк программы».
Что делаем дальше
- Обзорный практикум — шесть задач, все сразу на странице, в любом
порядке: понятия, остановится ли программа, сколько раз выполнится тело,
рост времени и памяти, какой алгоритм выгоднее, где впервые ошибётся
функция.
- Значения n по виткам и таблицу по внешнему циклу — на черновике, как
на слайдах. Программы не запускаем: код на странице — картинкой.
- Ответ везде — целое число.
Отметка: закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Исправленная задача не
засчитывается — за ошибку приходит новая, добирать можно до пятёрки.
За работу
Практикум «Неразрешимые задачи и сложность вычислений» — в общей
папке и на сайте. Не успел на уроке — пройди дома: вариант будет другой, сдаётся
тем же кодом.
Карточку в тетрадь можно взять с собой: на ней доказательство через программу
Наоборот, приём «значение повторилось» и таблица «сколько раз выполнится тело».