Конспект раздела: правильность

Карта раздела

Раздел отвечает на один вопрос: что значит «алгоритм работает» и как это доказать, не запуская его на всех входах. Первые три главы готовят язык разговора: что такое алгоритм, Python, на котором он записан, и математика, которой он считается. Дальше ответ распадается на четыре инструмента, и каждый следующий вырастает из предыдущего.

подготовка    ->  алгоритм, трассировка, Python, логарифм, логика
     |
спецификация  ->  что именно требуется
     |
инвариант     ->  результат верен, ЕСЛИ цикл кончился
     |
мера          ->  цикл кончится
     |
индукция      ->  та же схема для рекурсии, без цикла вовсе

Дерево решений: чем доказывать

Как это выглядит на одном алгоритме

Двоичный поиск проходит через весь раздел, и на нём видно все четыре инструмента сразу.

Спецификация. Вход: неубывающий список a и число x. Выход: наименьший индекс, где a[i] >= x, или len(a).

Инвариант. Левее levo всё строго меньше x; правее или равное pravo - не меньше x. Из него сразу следует, где ставить +1: середина, оказавшаяся меньше x, доказанно принадлежит левой части и обязана выйти из отрезка.

Мера. pravo - levo. Строго убывает, ограничена нулём. Дополнительно видно, что убывает примерно вдвое, откуда log₂ n кругов.

Контрпример. Заготовка с levo = s вместо levo = s + 1 не нарушает инвариант ни разу и всё равно негодна: она не останавливается.

Связи с остальным курсом

Раздел «Анализ» превращает счёт шагов из этого раздела в формальные оценки сверху и снизу. Модель стоимости, которая здесь введена словами, там станет определением.

Раздел «Рекуррентности» берёт дерево вызовов и делает из него метод: T(n) = 2·T(n-1) + 1 для Ханоя и T(n) = 2·T(n/2) + n для сортировки слиянием решаются одинаково.

Раздел «Сортировки» доказывает каждую сортировку инвариантом, и первым же идёт тот, который разобран здесь.

Раздел «Жадные алгоритмы» держится на контрпримере из этой главы: размен монетами 1, 3, 4 показывает, что жадность требует доказательства, а не веры.

Раздел «Что вообще вычислимо» доводит до конца замечание про проблему останова: почему меру обязан называть автор и почему инструмент этого сделать не может.

Чек-лист: объясни своими словами

1. Чем алгоритм отличается от инструкции, которая только похожа на него.
2. Почему -7 // 2 в Python равно -4 и где это ломает перенесённый код.
3. Почему b = a для списка не копирует, а [[0] * 3] * 3 - ловушка.
4. Почему в оценке двоичного поиска стоит логарифм, а у перебора пар - n(n - 1)/2.
5. Как отрицается условие while A and B и что такое контрпример.
6. Из каких трёх частей состоит спецификация задачи и что делает каждая.
7. Почему постусловие «список упорядочен» пропускает мусор и чем это чинится.
8. Почему шагом стоимости считается операция, не зависящая от размера данных.
9. Чем частичная корректность отличается от полной и зачем их разделять.
10. Три шага доказательства инвариантом и что делает каждый.
11. Инвариант сортировки вставками целиком, с обеими половинами.
12. Инвариант двоичного поиска и откуда из него берётся асимметрия +1.
13. Что такое мера убывания и почему она не обязана быть счётчиком.
14. Почему отсутствие меры не означает, что цикл бесконечен.
15. Чем сильная индукция отличается от обычной и когда она нужна.
16. Что такое контракт рекурсивной функции и зачем он нужен.
17. Какие две величины считают по дереву вызовов и за что отвечает каждая.
18. Чем экспонента ханойских башен отличается от экспоненты наивного fib.
19. Где искать контрпример: назови шесть мест из списка.

Что дальше

Следующий раздел отвечает на второй вопрос про алгоритм - не «верен ли», а «сколько стоит». Там появятся O, Θ и Ω как определения, суммы, которые приходится сворачивать при анализе циклов, и разница между худшим случаем и средним, которую путают чаще всего.