Алгоритмы и структуры данных

Что такое алгоритм, Python и математика, на которых стоит курс, что считается задачей, и как доказать, что программа делает то, что обещает, - инвариантом, а не тремя примерами.

1. 1.1 Алгоритм и исполнитель 35 мин

   Отличишь алгоритм от инструкции, которая только похожа на него, и проследишь работу программы по таблице трассировки.

2. 1.2 Python для курса 50 мин

   Прочитаешь и напишешь любую программу курса, не спотыкаясь там, где Python ведёт себя не так, как твой язык.

3. 1.3 Математика и логика для курса 55 мин

   Прикинешь в уме логарифм, степень, число пар и вариантов, найдёшь остаток и честно отрицаешь условие цикла.

4. 1.4 Задача и модель стоимости 35 мин

   Напишешь спецификацию задачи и объяснишь, за что мы платим в модели вычислителя.

5. 1.5 Правильность и инвариант цикла 40 мин

   Докажешь правильность цикла инвариантом и найдёшь контрпример к неверному алгоритму.

6. 1.6 Индукция и рекурсия 40 мин

   Свяжешь рекурсивный алгоритм с индукцией и докажешь его правильность по структуре самой рекурсии.

7. 1.7 Конспект раздела 12 мин

   Соберёшь раздел в одну карту: спецификация, инвариант, мера убывания, индукция.

Θ, O и Ω как определения, а не как значки; суммы и логарифмы; худший, средний и лучший случай; память рядом со временем.

1. 2.1 Счёт операций и модель стоимости 35 мин

   Посчитаешь время алгоритма как функцию от размера входа и объяснишь, что считаешь.

2. 2.2 Асимптотика: Θ, O, Ω и их правила 40 мин

   Дашь формальное определение O и докажешь принадлежность классу по определению.

3. 2.3 Суммы, логарифмы и оценки сверху 35 мин

   Свернёшь ряд, встречающийся в анализе цикла, и оценишь его сверху интегралом.

4. 2.4 Худший, средний, лучший случай и память 35 мин

   Отличишь средний случай от случая «в среднем по входам» и посчитаешь вспомогательную память.

5. 2.5 Конспект раздела 12 мин

   Соберёшь раздел в таблицу порядков роста и правил обращения с ними.

Три способа решить рекуррентность, главная теорема со всеми тремя случаями и амортизированный анализ, без которого динамический массив выглядит дорогим.

1. 3.1 Рекуррентности - дерево и подстановка 40 мин

   Запишешь рекуррентность алгоритма, решишь её деревом и докажешь ответ подстановкой.

2. 3.2 Главная теорема и её три случая 35 мин

   Применишь главную теорему во всех трёх случаях и распознаешь случай, к которому она неприменима.

3. 3.3 Амортизированный анализ - три метода 40 мин

   Докажешь, что вставка в динамический массив стоит константу в среднем, методом потенциалов.

4. 3.4 Конспект раздела 12 мин

   Соберёшь дерево решений «какая рекуррентность каким методом».

Абстрактный тип данных против его реализации, и почему одна и та же очередь бывает дешёвой и дорогой.

1. 4.1 Абстрактный тип и его реализация 30 мин

   Опишешь структуру набором операций и их стоимостью, не заглядывая внутрь.

2. 4.2 Массив, динамический массив, связный список 40 мин

   Выберешь между массивом и списком по набору операций, а не по привычке.

3. 4.3 Стек, очередь, дека и кольцевой буфер 40 мин

   Реализуешь очередь без сдвига хвоста и докажешь константу на операцию.

4. 4.4 Конспект раздела 12 мин

   Соберёшь таблицу «операция - массив - список - дека».

Восемь сортировок, нижняя граница сравнений и то, что на самом деле стоит в стандартных библиотеках.

1. 5.1 Вставками, выбором, пузырьком и Шелла 40 мин

   Объяснишь, почему сортировка вставками выигрывает на почти упорядоченных данных.

2. 5.2 Слиянием и быстрая 45 мин

   Разберёшь разбиение Хоара и объяснишь, откуда у быстрой сортировки худший случай.

3. 5.3 Пирамидальная сортировка 35 мин

   Построишь кучу за линию и отсортируешь на месте.

4. 5.4 Нижняя граница сравнений и сортировки без сравнений 40 мин

   Докажешь границу n·log n деревом решений и обойдёшь её подсчётом.

5. 5.5 Устойчивость, ключ и то, что стоит в библиотеках 35 мин

   Выберешь сортировку под данные и объяснишь, зачем нужна устойчивость.

6. 5.6 Конспект раздела 12 мин

   Соберёшь таблицу сортировок по времени, памяти и устойчивости.

Двоичный поиск во всех его границах и выбор k-го элемента без сортировки.

1. 6.1 Двоичный поиск и его границы 40 мин

   Напишешь поиск левой и правой границы и докажешь обе инвариантом.

2. 6.2 Выбор k-го элемента 40 мин

   Найдёшь медиану за линейное время в среднем и объяснишь медиану медиан.

3. 6.3 Конспект раздела 12 мин

   Соберёшь шаблоны двоичного поиска, которые не ломаются на границе.

Как из ключа получается номер ячейки, что делать с коллизиями и почему словарь всё-таки не константа.

1. 7.1 Хеш-функция и коллизии 35 мин

   Оценишь число коллизий и объяснишь, почему они неизбежны.

2. 7.2 Цепочки и открытая адресация 40 мин

   Сравнишь два способа по числу проб при заданном заполнении.

3. 7.3 Универсальное и идеальное хеширование 35 мин

   Объяснишь, что даёт случайный выбор хеш-функции и от чего он защищает.

4. 7.4 Словарь настоящего языка и фильтр Блума 35 мин

   Прикинешь размер фильтра Блума под заданную долю ложных срабатываний.

5. 7.5 Конспект раздела 12 мин

   Соберёшь дерево решений «когда словарь, когда дерево, когда фильтр».

От двоичного дерева поиска до красно-чёрного и B-дерева, и что именно делает вращение.

1. 8.1 Двоичное дерево поиска и его вырождение 40 мин

   Реализуешь вставку и обход и покажешь вход, на котором дерево становится списком.

2. 8.2 Вращения, АВЛ и красно-чёрное дерево 45 мин

   Объяснишь, какое свойство поддерживает баланс, и проследишь вращение по шагам.

3. 8.3 2-3 деревья и B-деревья на диске 40 мин

   Посчитаешь высоту B-дерева и объяснишь, почему на диске выигрывает именно оно.

4. 8.4 Декартово дерево, splay и списки с пропусками 40 мин

   Объяснишь, как случайность заменяет явную балансировку.

5. 8.5 Дополненные деревья - порядковая статистика и интервалы 35 мин

   Добавишь к дереву поле и получишь новую операцию, не ломая старые.

6. 8.6 Дерево отрезков и дерево Фенвика 45 мин

   Ответишь на запрос по диапазону и обновишь элемент - оба за логарифм, а не за n.

7. 8.7 Конспект раздела 12 мин

   Соберёшь таблицу деревьев по гарантиям и цене операций.

Структуры, которые умеют мало, но очень быстро, и от этого держат половину графовых алгоритмов.

1. 9.1 Двоичная куча и очередь с приоритетами 40 мин

   Соберёшь очередь с приоритетами на куче и выберешь, чем закрыть уменьшение ключа.

2. 9.2 Биномиальная куча, куча Фибоначчи, слияние 40 мин

   Объяснишь, зачем нужна дешёвая операция уменьшения ключа.

3. 9.3 Непересекающиеся множества, ранг и сжатие пути 40 мин

   Реализуешь union-find и объяснишь, откуда берётся почти константа.

4. 9.4 Конспект раздела 12 мин

   Соберёшь таблицу приоритетных структур и их применений.

Хранение графа, обход в глубину как инструмент доказательства и свойства, которые из обхода вычитываются: компоненты, мосты, двудольность, раскраска.

1. 10.1 Как хранить граф и чем платить за выбор 35 мин

   Выберешь представление по плотности графа и набору операций.

2. 10.2 Обход в глубину, времена входа и выхода 40 мин

   Классифицируешь рёбра по временам и найдёшь цикл.

3. 10.3 Топологическая сортировка и компоненты сильной связности 45 мин

   Разложишь ориентированный граф на компоненты за два обхода.

4. 10.4 Мосты, точки сочленения, двусвязность 40 мин

   Найдёшь ребро, разрыв которого разваливает сеть.

5. 10.5 Раскраска, двудольность и планарность 45 мин

   Проверишь граф на двудольность обходом и оценишь, скольких цветов хватит в худшем случае.

6. 10.6 Запросы к дереву - LCA, RMQ и разреженная таблица 45 мин

   Ответишь на запрос «наименьший общий предок» за логарифм после предподсчёта.

7. 10.7 Конспект раздела 12 мин

   Соберёшь карту «что можно вытащить из одного обхода в глубину».

Пять алгоритмов пути и три остовного дерева, и требование, при нарушении которого каждый из них врёт.

1. 11.1 Поиск в ширину и алгоритм Дейкстры 45 мин

   Объяснишь, почему Дейкстре нужны неотрицательные веса, и покажешь контрпример.

2. 11.2 Беллман-Форд, ДАГ и отрицательные циклы 40 мин

   Найдёшь отрицательный цикл и объяснишь, почему после него задача теряет смысл.

3. 11.3 Все пары - Флойд-Уоршелл и Джонсон 40 мин

   Посчитаешь все расстояния и выберешь между двумя способами по плотности графа.

4. 11.4 Эвристический поиск и A* 35 мин

   Объяснишь, что делает эвристику допустимой, и покажешь, что бывает без этого.

5. 11.5 Минимальное остовное дерево - Прим, Крускал, Борувка 45 мин

   Докажешь свойство разреза и выведешь из него оба алгоритма разом.

6. 11.6 Конспект раздела 12 мин

   Соберёшь дерево решений «какой алгоритм пути под какие веса».

Один общий язык для десятка непохожих задач и теорема, которая связывает поток с разрезом.

1. 12.1 Максимальный поток и минимальный разрез 45 мин

   Найдёшь максимальный поток и предъявишь разрез, доказывающий, что больше нельзя.

2. 12.2 Паросочетания и покрытия 40 мин

   Сведёшь задачу о назначениях к потоку и объяснишь, что даёт двудольность.

3. 12.3 Линейное программирование, симплекс, двойственность 45 мин

   Запишешь задачу в виде ЛП и объяснишь смысл двойственной задачи.

4. 12.4 Потоки минимальной стоимости 45 мин

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

5. 12.5 Выпуклые потоки: модели, остаточная сеть и масштабирование 80 мин

   Построить разделимую выпуклую сетевую модель, различить целый и непрерывный оптимум, вычислить остаточные приращения и обосновать ремонт масштаба и число дополнений.

6. 12.6 Обобщённые потоки: преобразования, леса и симплекс 110 мин

   Проверить баланс с множителями, вычислить поток и потенциалы хорошего дополненного леса, подтвердить двойственный сертификат и выполнить допустимый симплексный шаг с учётом вырождения.

7. 12.7 Конспект раздела 12 мин

   Соберёшь список задач, которые сводятся к потоку или к ЛП.

Схема, из которой выросли сортировка слиянием, Карацуба, Штрассен и быстрое преобразование Фурье.

1. 13.1 Схема и её стоимость 35 мин

   Оценишь стоимость деления пополам и найдёшь, где выигрыш исчезает.

2. 13.2 Карацуба, Штрассен и цена одного лишнего умножения 40 мин

   Объяснишь, почему экономия одного умножения меняет порядок роста.

3. 13.3 Ближайшая пара точек 35 мин

   Разберёшь полосу вокруг разреза и объяснишь, почему в ней мало точек.

4. 13.4 Быстрое преобразование Фурье 45 мин

   Умножишь два многочлена за n·log n и объяснишь, что здесь делают корни из единицы.

5. 13.5 Конспект раздела 12 мин

   Соберёшь признаки задачи, которая поддаётся делению пополам.

Приём, который чаще всего оказывается неверным, и два способа доказать, что в этот раз он верен.

1. 14.1 Жадный выбор и доказательство обменом 40 мин

   Докажешь безопасность жадного шага обменным аргументом.

2. 14.2 Расписания, Хаффман, покрытие множеств 40 мин

   Построишь код Хаффмана и объяснишь, почему он оптимален.

3. 14.3 Матроиды - когда жадность работает всегда 35 мин

   Проверишь задачу на свойство матроида и предскажешь исход жадности.

4. 14.4 Конспект раздела 12 мин

   Соберёшь чек-лист «можно ли здесь жадничать».

Два условия применимости, порядок вычисления, восстановление ответа и цена по памяти.

1. 15.1 Перекрытие подзадач и оптимальная подструктура 40 мин

   Проверишь задачу на оба условия и объяснишь, почему без второго ответ будет неверным.

2. 15.2 Классика - рюкзак, LCS, расстояние редактирования 45 мин

   Составишь таблицу подзадач и восстановишь по ней сам ответ, а не только число.

3. 15.3 Порядок вычисления, память и ДП по маскам 40 мин

   Сократишь память до одной строки таблицы и объяснишь, чем за это платишь.

4. 15.4 Конспект раздела 12 мин

   Соберёшь порядок действий «от рекурсии к таблице» из пяти шагов.

Когда перебор - единственный честный ответ, и как урезать его так, чтобы он всё-таки закончился.

1. 16.1 Генерация комбинаторных объектов 40 мин

   Переберёшь подмножества, перестановки и сочетания без повторов и пропусков.

2. 16.2 Поиск с возвратом и отсечения 40 мин

   Добавишь отсечение и измеришь, во сколько раз уменьшилось дерево перебора.

3. 16.3 Ветви и границы 35 мин

   Построишь оценку снизу и отбросишь по ней ветку целиком.

4. 16.4 Перебор в играх - минимакс и альфа-бета 40 мин

   Оценишь позицию минимаксом и объяснишь, что именно отсекает альфа-бета.

5. 16.5 Конспект раздела 12 мин

   Соберёшь приёмы сокращения перебора по силе и цене.

Поиск подстроки от наивного до Ахо-Корасика, индексы над текстом и сжатие.

1. 17.1 Наивный поиск, Рабин-Карп, КМП 55 мин

   Объяснишь, что запоминает префикс-функция и почему после неё не нужен откат.

2. 17.2 Бойер-Мур и поиск конечным автоматом 45 мин

   Объяснишь, почему поиск может пропускать символы и когда это выгодно.

3. 17.3 Много образцов сразу - бор и Ахо-Корасик 45 мин

   Построишь бор со ссылками отката и найдёшь все образцы за один проход.

4. 17.4 Суффиксный массив, LCP и суффиксное дерево 45 мин

   Ответишь на запрос «есть ли такая подстрока» за log по готовому индексу.

5. 17.5 Сжатие - RLE, Хаффман, LZ77, арифметическое 45 мин

   Сожмёшь строку и объяснишь, откуда берётся предел сжатия.

6. 17.6 Контекстное моделирование, BWT и словарные методы 55 мин

   Развернёшь преобразование Барроуза-Уилера и объяснишь, почему после него текст жмётся лучше.

7. 17.7 Изображения с потерями: JPEG и фрактальное сжатие 110 мин

   Посчитаешь искажение и квантование, разложишь JPEG на обратимые и необратимые шаги и объяснишь сходимость фрактального декодера.

8. 17.8 Вейвлеты и JPEG 2000 100 мин

   Построишь многоуровневое разложение, восстановишь целые отсчёты lifting-преобразованием и различишь обратимое кодирование и обрезку битовых плоскостей.

9. 17.9 Цвет, фильтры и область интереса 105 мин

   Обратишь целочисленное цветовое преобразование, вычислишь шаги9/7 с заданной нормировкой и выберешь коэффициенты для числовой ROI-маски.

10. 17.10 Сжатие видео: движение, зависимости и формат 130 мин

    Выберешь блочное предсказание по ошибке и цене, восстановишь кадр в замкнутом контуре и обоснуешь порядок декодирования, задержку и совместимость потока.

11. 17.11 Режимы видеопредсказания 95 мин

    Восстановишь skip и intra-блоки, различишь PB и B, построишь деформированную опору и сравнишь предсказание и преобразование по полям и кадру.

12. 17.12 События сцены и зависимые слои видео 70 мин

    Проследишь событие до отрисованного кадра, восстановишь базовый и уточняющий слои и объяснишь обязанности описания содержания, синтеза и профиля.

13. 17.13 Конспект раздела 12 мин

    Соберёшь таблицу «задача о строке - подходящий инструмент».

Арифметика длинных чисел, модульная арифметика, простота, разложение и то, на чём стоит вся современная криптография.

1. 18.1 Длинные числа и цена арифметики 45 мин

   Оценишь стоимость сложения и умножения через число разрядов, а не через одну операцию.

2. 18.2 Модульная арифметика, НОД и обратный элемент 70 мин

   Найдёшь обратный элемент по модулю расширенным Евклидом.

3. 18.3 Простота, решето и вероятностные тесты 60 мин

   Объяснишь, что именно проверяет тест Миллера-Рабина и с какой вероятностью ошибается.

4. 18.4 RSA и обмен ключами 50 мин

   Разберёшь RSA до последнего шага и объяснишь, на какой трудной задаче он стоит.

5. 18.5 Матрицы, системы уравнений и погрешность 50 мин

   Решишь систему методом Гаусса и покажешь, где накапливается ошибка.

6. 18.6 Конспект раздела 12 мин

   Соберёшь список числовых приёмов и их стоимости.

Слой, на котором работают структуры и компиляторы: маски, счёт единиц, арифметика без ветвлений, код Грея и биты дробных чисел.

1. 19.1 Маски, сдвиги и множество на битах 75 мин

   Заменишь множество небольших чисел одним целым и переберёшь его подмножества.

2. 19.2 Счёт единиц, младший бит, степень двойки 75 мин

   Посчитаешь единицы без цикла по битам и объяснишь приём.

3. 19.3 Арифметика без ветвлений и деление на константу 65 мин

   Заменишь ветвление арифметикой, а деление на константу - умножением, и объяснишь, зачем это делает компилятор.

4. 19.4 Код Грея, CRC и биты плавающей точки 65 мин

   Пройдёшь по коду Грея без повторов и вытащишь порядок прямо из битов дробного числа.

5. 19.5 Необычные основания систем счисления 105 мин

   Переведёшь целые в отрицательное и комплексное основание, выведешь перенос из весов и проверишь выбор основания при заданной цене хранения.

6. 19.6 Коды исправления ошибок: Хэмминг и SEC-DED 100 мин

   Построишь код Хэмминга и декодер SEC-DED, обоснуешь гарантии расстоянием и отличишь границу числа кодовых слов от точного оптимума.

7. 19.7 Конспект раздела 12 мин

   Соберёшь справочник битовых приёмов с проверкой каждого.

Случайность не как источник ошибок, а как способ получить гарантию, которой детерминированно не добиться.

1. 20.1 Вероятностный анализ и матожидание 90 мин

   Посчитаешь ожидаемое число операций через индикаторы.

2. 20.2 Хвостовые оценки - Марков, Чебышёв, Чернов 70 мин

   Оценишь вероятность большого отклонения и поймёшь, когда трёх запусков достаточно.

3. 20.3 Монте-Карло, Лас-Вегас и рандомизированный quicksort 95 мин

   Отличишь алгоритм, который может ошибиться, от того, который может задуматься.

4. 20.4 Фильтр Блума, count-min, HyperLogLog 70 мин

   Обменяешь точность на память осознанно и посчитаешь цену обмена.

5. 20.5 Потоковые алгоритмы и резервуарная выборка 70 мин

   Выберешь k случайных элементов из потока неизвестной длины за один проход.

6. 20.6 Частые элементы и квантили в потоке 70 мин

   Найдёшь тяжёлых за один проход и назовёшь цену, которой платишь за точность.

7. 20.7 Марковские цепи, случайные блуждания и MCMC 90 мин

   Найдёшь стационарное распределение и оценишь, за сколько шагов блуждание его достигает.

8. 20.8 Непрерывная вероятность: плотности и время ожидания 110 мин

   Переведёшь плотность в вероятность интервала, вычислишь условное распределение и обоснуешь свойства равномерного и экспоненциального ожидания.

9. 20.9 Потоки Пуассона и очереди в непрерывном времени 120 мин

   Построишь модель потока событий, разделишь её по типам и найдёшь распределение нагрузки в очередях M/M/1, M/M/1/K и M/M/∞.

10. 20.10 Нормальное распределение, предельные законы и обучение смеси 180 мин

    Проверишь условия нормального приближения, построишь многомерную модель и генератор, выведешь оценки правдоподобия и выполнишь шаг EM с проверкой его ограничений.

11. 20.11 Конспект раздела 15 мин

    Соберёшь карту «где случайность даёт выигрыш и чем он оплачен».

Границы: что нельзя вычислить вовсе, что нельзя вычислить быстро и как доказывают и то, и другое.

1. 21.1 Конечные автоматы и регулярные языки 55 мин

   Построишь автомат по регулярному выражению и покажешь язык, который автомату не по силам.

2. 21.2 Контекстно-свободные языки и магазинные автоматы 65 мин

   Разберёшь выражение по грамматике и скажешь, чего КС-язык не умеет в принципе.

3. 21.3 Машина Тьюринга и что считается вычислением 60 мин

   Объяснишь, зачем нужна формальная модель, если программы и так работают.

4. 21.4 Проблема останова и неразрешимые задачи 60 мин

   Проведёшь доказательство неразрешимости и покажешь, где в нём диагональ.

5. 21.5 P, NP, сведения и NP-полнота 70 мин

   Докажешь NP-полноту задачи сведением к уже известной.

6. 21.6 Каталог NP-полных задач и как им пользоваться 65 мин

   Узнаешь в новой задаче переодетую известную и сошлёшься на неё.

7. 21.7 Память как ресурс - PSPACE, L, NL и иерархии 65 мин

   Отличишь класс по времени от класса по памяти и объяснишь, зачем нужен второй.

8. 21.8 Квантовая модель - кубит, интерференция, алгоритм Шора 65 мин

   Объяснишь, что квантовый компьютер ускоряет, а что нет.

9. 21.9 Конспект раздела 15 мин

   Соберёшь карту классов и известных связей между ними.

Задача NP-полна - и её всё равно надо решать сегодня. Честные выходы, цена каждого и граница, за которую не пускает уже сама теория.

1. 22.1 Приближённые алгоритмы - гарантия через нижнюю границу 60 мин

   Докажешь, что решение хуже оптимума не больше чем вдвое, ни разу не узнав самого оптимума.

2. 22.2 Локальный поиск, отжиг, эвристики 60 мин

   Настроишь локальный поиск и объяснишь, что такое застревание в локальном минимуме.

3. 22.3 Точные методы на практике - целочисленные программы и SAT-решатели 75 мин

   Решишь NP-полную задачу точно на входе, который встречается в жизни.

4. 22.4 ЛП-округление и прямо-двойственный метод 60 мин

   Получишь приближение с доказанной гарантией из решения линейной релаксации.

5. 22.5 Пределы приближения - PTAS, APX и почему дальше нельзя 60 мин

   Скажешь, у какой задачи схема приближения есть, а у какой её не будет никогда.

6. 22.6 Онлайн-алгоритмы и конкурентный анализ 65 мин

   Оценишь решение, принимаемое без знания будущего, отношением к лучшему из возможных.

7. 22.7 Параметризованные алгоритмы - FPT, дерево поиска, ядро 60 мин

   Отделишь размер входа от параметра и решишь NP-полную задачу быстро при малом параметре.

8. 22.8 Древесная ширина, цветное кодирование и нижние границы 65 мин

   Посчитаешь ДП по древесному разложению и назовёшь, что запрещает гипотеза ETH.

9. 22.9 Конспект раздела 12 мин

   Соберёшь дерево решений «что делать, если задача сложная».

Поворот трёх точек и определитель окружности - и всё, что из них собирается: оболочка, пересечения, Вороной и Делоне, триангуляция многоугольника, поиск по диапазону. Предикаты считаем точно.

1. 23.1 Точки, векторы, ориентация и пересечения 60 мин

   Определишь взаимное расположение отрезков без деления и без потери точности.

2. 23.2 Выпуклая оболочка 60 мин

   Построишь оболочку за n·log n и объяснишь, что делает сортировка.

3. 23.3 Заметающая прямая - пересечения отрезков и двойственность 60 мин

   Применишь заметающую прямую к задаче о пересечениях отрезков.

4. 23.4 Локализация точки, kd-дерево, диаграмма Вороного 60 мин

   Ответишь на запрос «ближайший объект» быстрее полного перебора.

5. 23.5 Триангуляция Делоне и её свойства 45 мин

   Построишь Делоне переворотами рёбер и объяснишь, чем она связана с Вороным.

6. 23.6 Триангуляция многоугольника и задача о галерее 60 мин

   Разрежешь многоугольник на треугольники и оценишь, сколько нужно охранников.

7. 23.7 Поиск по диапазону и BSP-деревья 45 мин

   Ответишь на запрос прямоугольником быстрее перебора точек.

8. 23.8 Конспект раздела 12 мин

   Соберёшь набор геометрических примитивов и ловушек точности.

Что меняется, когда исполнителей много или когда данные не помещаются в память.

1. 24.1 PRAM, работа и глубина 40 мин

   Оценишь параллельный алгоритм двумя числами вместо одного.

2. 24.2 Префиксные суммы, слияние, сортирующие сети 40 мин

   Посчитаешь префиксные суммы за логарифмическую глубину.

3. 24.3 Взаимное исключение и модели согласованности 50 мин

   Разберёшь замок Петерсона, проверишь протокол перебором состояний и объяснишь, зачем ему барьер памяти.

4. 24.4 Разделяемая память - блокировки, CAS и линеаризуемость 45 мин

   Объяснишь, чем атомарные операции сильнее чтений и записей, и проверишь историю вызовов на линеаризуемость.

5. 24.5 Коллективные операции и распределённая память 40 мин

   Оценишь цену рассылки и сборки на p узлах и поймёшь, откуда там логарифм.

6. 24.6 Внешняя память, кеш и локальность 40 мин

   Объяснишь, почему одна и та же сортировка на диске ведёт себя иначе.

7. 24.7 Конспект раздела 12 мин

   Соберёшь список величин, которые меняются при смене модели.

Что на самом деле лежит внутри списка, словаря и множества настоящего языка, и почему замер иногда спорит с асимптотикой.

1. 25.1 Что внутри list, dict и set 40 мин

   Объяснишь поведение стандартных контейнеров через их устройство.

2. 25.2 Timsort, introsort и почему в библиотеке гибрид 35 мин

   Объяснишь, зачем библиотечная сортировка склеена из трёх алгоритмов.

3. 25.3 Память, локальность и честный замер 40 мин

   Замеришь две реализации так, чтобы результат что-то значил.

4. 25.4 Персистентные структуры и ленивая амортизация 50 мин

   Сохранишь прежнюю версию структуры и посчитаешь амортизацию, которая переживает повторный доступ.

5. 25.5 Неблокирующие структуры, консенсус и ABA 50 мин

   Соберёшь стек на CAS и поймаешь на нём ABA.

6. 25.6 Конспект раздела 12 мин

   Соберёшь мост между асимптотикой и секундомером.

Порядок действий, когда задача новая: как её понять, где искать готовое и как не изобрести медленное.

1. 26.1 Как читать задачу и как её переформулировать 35 мин

   Вытащишь из формулировки вход, выход и ограничения и оценишь допустимую сложность.

2. 26.2 Как узнать задачу и найти готовое решение 35 мин

   Сведёшь новую задачу к известной и сошлёшься на известный результат.

3. 26.3 Разборы: пять задач из практики 45 мин

   Пройдёшь путь от формулировки до выбора алгоритма на пяти чужих задачах.

4. 26.4 Инженерия алгоритмов и проверка результата 40 мин

   Проверишь ответ независимо от алгоритма, который его выдал.

5. 26.5 Конспект раздела 12 мин

   Соберёшь чек-лист разработки алгоритма из десяти вопросов.

Своя пошаговая игра «Архипелаг» от техзадания до сервера: карта, путь, экономика, игроки и моды. Каждая механика - задача из курса со своей моделью, структурой, доказательством и замером; в конце - итоговая контрольная по всему курсу.

1. 27.1 Техзадание: игра как набор задач 45 мин

   Разложишь игру на модули и для каждого запишешь спецификацию, бюджет хода и структуру данных до первой строки кода.

2. 27.2 Карта мира: генерация, острова и путь 50 мин

   Построишь карту, на которой все острова связаны, и проведёшь по ней отряд кратчайшим путём в пределах бюджета хода.

3. 27.3 Экономика: рецепты, склад, рынок и рейтинг 50 мин

   Посчитаешь сырьё по дереву рецептов, загрузишь трюм, найдёшь выгодный круг обмена и место игрока в рейтинге.

4. 27.4 Игроки: соперники, чат, сохранения и ИИ 50 мин

   Подберёшь соперников, отфильтруешь чат за один проход, сравнишь сохранения по хешу и научишь компьютерного соперника смотреть на ходы вперёд.

5. 27.5 Сборка: ход сервера целиком 60 мин

   Соберёшь решение, которое проходит и по правильности, и по числу шагов.

6. 27.6 Итоговая контрольная 40 мин

   Проверишь курс целиком.

7. 27.7 Конспект раздела 12 мин

   Соберёшь разбор финального проекта и типовых потерь.

Всё, ради чего в курс возвращаются через полгода, на одной странице.

1. 28.1 Сводная шпаргалка 25 мин

   Найдёшь нужный алгоритм, его стоимость и его ограничение за полминуты.