Конспект: куда вернуться после итоговой

МЫСЛЬ                                                      РАЗДЕЛ
инвариант + завершаемость = полная корректность            1
логарифм - сколько раз n делится пополам                   2
рекуррентность -> дерево рекурсии, главная теорема         3
удвоение массива - константа амортизированно               3, 4
нижняя граница сортировки сравнениями - log₂ n!            5
выбор k-го: в среднем линия, медиана медиан - всегда       6
совпадения хешей у корня из числа значений                 7
дерево без балансировки на возрастающих ключах - список    8
union-find со сжатием - почти константа                    9
порядок, мосты, компоненты, слои обхода                    10
отрицательные рёбра - Беллман-Форд                       11
максимальный поток = минимальный разрез                    12
Карацуба: три умножения вместо четырёх, n^1,585            13
жадность доказывается обменом                              14
динамика: подзадачи оптимальны и повторяются               15
отсечение режет дерево перебора, а не класс                16
префикс-функция под КМП и Ахо-Корасик                    17
малая теорема Ферма сокращает степень                      18
x & (x - 1) снимает младший бит, x & -x оставляет его      19
Лас-Вегас верен всегда, Монте-Карло быстр всегда           20
останов неразрешим - предел снаружи                        21
NP-трудно - приближение с гарантией                        22
поворот - знак векторного произведения                     23
последовательная доля ограничивает ускорение               24
из повторов замера берут наименьший                        25
спецификация до кода, проверка после                       26
стыки модулей: инвариант мира, правило конфликтов          27

ПОРЯДОК РАБОТЫ С ЛЮБОЙ ЗАДАЧЕЙ
1. вход, вид ответа, «лучше», края
2. бюджет: наибольший размер против операций в секунду
3. структура под частые операции
4. доказательство / сертификат / стресс-тест / предел
5. профиль и тест удвоения на собранном