Спецсеминар «Теория алгоритмов» — осень 2026
Спецсеминар для 3 курса: основной жанр — ваши доклады. Каждый выбирает тему, глубоко в ней разбирается, выступает и оставляет после себя конспект и задачи. Ведёт Александр Уланов; вопросы — a.ulanov@spbu.ru или Telegram @aulanov.
Баллы и зачёт
Балл семестра (максимум 100) складывается из трёх частей — каждую вы контролируете сами:
- Выступление — до стоимости темы (35–60). Стоимость указана в списке тем и отражает сложность; оценка = качество × стоимость: идеальный доклад приносит стоимость целиком, средний — около половины.
- Артефакты — до 20: конспект на 1–2 страницы (markdown — публикуется здесь, на сайте) и задачи по теме для аудитории; сдаются в течение недели после выступления.
- Оппонирование — до 20: каждый один раз оппонирует чужой доклад.
Бонус — до +5 сверх набранного (но не выше 100): содержательные вопросы на парах, решения задач из чужих докладов.
Шкала: зачёт от 50 баллов; с оценкой — E: 50–59, D: 60–69, C: 70–79, B: 80–89, A: 90–100.
Доклад обязателен
Без доклада зачёта нет — сколько бы баллов ни набралось по остальным пунктам.
Потолок оценки задаёт выбранная тема:
| стоимость темы | максимум (тема + 20 + 20) | потолок |
|---|---|---|
| 60 | 100 | A |
| 50–55 | 90–95 | A (впритык) |
| 45 | 85 | B |
| 40 | 80 | B (ровно) |
| 35 | 75 | C |
Квот по трекам нет — выбор полностью свободный. Но самые дорогие темы (потолок A) — в теоретических треках A–C: доказательства окупаются.
Выбор темы и оппонирование
- Запись — в общей Google-таблице (ссылка — в чате группы), first come — first served, одна тема в одни руки.
- Каждый записывается дважды: докладчиком на одну тему и оппонентом на другую. Нельзя оппонировать себе, своему со-докладчику и взаимно (если A оппонирует доклад B, то B не оппонирует доклад A).
- Дедлайн записи — неделя после первой пары; не записавшимся темы и оппонирования достанутся назначением.
- Оппонент читает материал заранее (план — за неделю, слайды — за день до пары) и на паре задаёт минимум 3 содержательных вопроса + даёт мини-рецензию в три предложения. Неявка без причины — 0 баллов за оппонирование.
Ритм одного доклада
- За 7 дней — план преподавателю (структура + источники + что будет в демо или какое доказательство). Без согласованного плана доклад переносится.
- За 1 день — готовые слайды оппоненту.
- День X — выступление: соло 30–35 минут (в парном формате 40) + 10 минут вопросов, сначала оппонент, потом зал.
- В течение 7 дней после — артефакты: конспект и задачи.
Демо-правило
В инженерных темах утверждение «X быстрее Y» принимается только с собственным замером или работающим демо. В теоретических — минимум одна теорема доказывается вживую и полностью, от формулировки до последнего шага.
Темы
Шесть треков, 58 тем. Баллы — стоимость выступления.
Трек A — вычислимость
| тема | баллы |
|---|---|
| Машины Тьюринга и их варианты (многоленточные, недетерминированные), эквивалентность; тезис Чёрча–Тьюринга | 50 |
| Другие модели вычислимости: алгорифмы Маркова, лямбда-исчисление, частично рекурсивные функции — и почему все они совпадают | 55 |
| Проблема останова, теорема Райса, m-сводимость; следствие: почему статический анализ программ принципиально неполон | 55 |
| Десятая проблема Гильберта и теорема Матиясевича (1970, решена в Ленинграде — ЛОМИ, ныне ПОМИ РАН) | 60 |
| Busy Beaver: невычислимо быстрорастущие функции; как в 2024 сообщество доказало BB(5) = 47 176 870 | 55 |
| Проблема соответствий Поста; неразрешимые задачи в формальных языках и грамматиках | 50 |
| Колмогоровская сложность: несжимаемость, связь со случайностью, применение как метода доказательства | 55 |
Трек B — сложность
| тема | баллы |
|---|---|
| P, NP, EXP; NP-полнота и теорема Кука–Левина (с доказательством) | 60 |
| Зоопарк NP-полных задач: 21 задача Карпа, техника полиномиальных сведений на 4–5 примерах | 50 |
| Как NP-задачи решают на практике: SAT-солверы (DPLL → CDCL), применение в верификации | 50 |
| Теоремы об иерархиях по времени и памяти; теорема Сэвича; PSPACE и игры (TQBF) | 60 |
| Fine-grained complexity: гипотеза SETH, 3SUM; почему edit distance застрял на O(n²) (Backurs–Indyk, 2015) | 60 |
| Параметризованная сложность: FPT, кернелизация, W-иерархия | 60 |
| Коммуникационная сложность: нижние оценки через прямоугольники, дизъюнктность | 60 |
Трек C — рандомизированное, приближённое, за пределами классики
| тема | баллы |
|---|---|
| Вероятностные классы RP/BPP; лемма Шварца–Циппеля и проверка тождеств; что такое дерандомизация | 55 |
| Проверка простоты: Миллер–Рабин и история AKS («PRIMES is in P», 2002) | 50 |
| Приближённые алгоритмы: вершинное покрытие ×2, TSP с неравенством треугольника; пределы аппроксимации и PCP-теорема (обзорно) | 60 |
| Онлайн-алгоритмы и конкурентный анализ: ski rental, кэширование (LRU k-конкурентно), k-server | 55 |
| Квантовые алгоритмы: Гровер, Шор, класс BQP — что реально угрожает криптографии | 60 |
| Интерактивные доказательства и zero-knowledge: от «пещеры Али-Бабы» до zk-SNARK (обзорно) | 60 |
| Алгоритмическая теория игр: равновесие Нэша, класс PPAD, цена анархии | 55 |
Трек D — структуры данных
| тема | баллы |
|---|---|
| B / B+ / B*-деревья: операции, применение в СУБД и файловых системах | 40 |
| LSM-деревья и SS-таблицы (RocksDB, Cassandra): амортизационная цена compaction | 50 |
| Дерево Фенвика и дерево отрезков (+ lazy propagation) | 45 |
| R-деревья и геопространственные индексы: R*, quadtree, geohash, S2 | 50 |
| van Emde Boas: поиск за O(log log U) | 55 |
| Splay-деревья: амортизация, статическая оптимальность + rope | 45 |
| Декартово дерево (treap), scapegoat-tree, рандомизированные BST | 45 |
| Skip list: рандомизированный поиск, применение в Redis | 35 |
| Персистентные структуры данных: path copying, применения (git, immutable-коллекции) | 50 |
| Фибоначчиева куча: амортизированный анализ, зачем Дейкстре | 45 |
| Skew heap, pairing heap, Brodal queue: теория против практики | 50 |
| Фильтры принадлежности: Bloom, Quotient, Cuckoo filter | 50 |
| Потоковые алгоритмы: Count-Min Sketch, HyperLogLog, Misra–Gries | 55 |
| Хеш-таблицы на пределе: open addressing, Robin Hood, Swiss tables / F14 (+ замеры против классики) | 55 |
Трек E — алгоритмы: строки, графы, числа
| тема | баллы |
|---|---|
| Поиск подстроки: Рабин-Карп, КМП, Z-функция | 35 |
| Множественный поиск: Ахо-Корасик (+ Commentz-Walter) | 45 |
| Суффиксные структуры: суффиксный массив + LCP; суффиксное дерево и Укконен (обзорно) | 55 |
| Остовные деревья: Крускал, Прим, Борувка + DSU с анализом α(n) | 45 |
| Кратчайшие пути: Дейкстра + индексная куча, Беллман-Форд | 45 |
| A* и эвристики; contraction hierarchies — почему навигатор отвечает мгновенно | 50 |
| Максимальный поток: Форд-Фалкерсон → Эдмондс-Карп → Диниц; паросочетания | 50 |
| RSA: математика, корректность, атаки на неправильное использование | 45 |
| Пост-квантовая криптография: решётки и LWE, ML-KEM/ML-DSA — что стандартизовал NIST в 2024 | 60 |
| Коды коррекции ошибок: Рид–Соломон и поля Галуа; QR-коды, RAID | 60 |
| Быстрое умножение: Карацуба → Тоом-Кук → FFT/NTT; Штрассен и AlphaTensor (2022) | 55 |
| Сортировки на практике: timsort, introsort, pdqsort; PSRS для параллельной | 45 |
Трек F — системы и ML
| тема | баллы |
|---|---|
| Энтропия Шеннона и универсальное сжатие: Хаффман, арифметическое кодирование, ANS; почему zstd победил | 55 |
| Трансформ-кодирование изображений: DCT и вейвлеты, JPEG → AVIF (один доклад вместо двух прошлогодних) | 55 |
| Криптографические хеши: SHA-2, SHA-3; почему MD5 и SHA-1 мертвы (SHAttered) | 55 |
| Невозможность консенсуса: теорема FLP — и как Paxos/Raft живут с ней на практике | 60 |
| CRDT: полурешётки и strong eventual consistency; как Figma сливает правки | 55 |
| Merkle-деревья и content-addressable storage: git изнутри | 45 |
| Модели параллелизма: PRAM, work-span (теорема Брента), законы Амдала и Густафсона | 45 |
| LSH, MinHash, SimHash: поиск похожих и дедупликация датасетов для LLM | 55 |
| Consistent hashing и DHT (Chord, Kademlia, BitTorrent) | 50 |
| Attention как алгоритм: O(n²), KV-cache, FlashAttention, speculative decoding | 60 |
| Approximate nearest neighbors: HNSW, IVF, product quantization — векторные БД | 55 |
Как готовить технический доклад
- Скелет: проблема → наивное решение и почему его мало → идея → как работает (пример руками!) → сложность или доказательство → где живёт в реальном софте → демо → 3 вопроса аудитории.
- Один пример, прослеженный до конца, лучше трёх начатых.
- Источники: первоисточник (статья) + одна хорошая вторичка; Википедия — точка входа, не источник.
- Хронометраж: 30–40 минут — это 15–20 слайдов, не 40. Прогоните доклад вслух хотя бы раз.
Про ИИ
Готовиться с ассистентом можно. Понимать каждый слайд — обязательно: оппонент и зал спросят любой.
Конспекты прозвучавших докладов будут появляться в этом разделе по мере семестра.