← К программе курса 7 семестр

Спецкурс: вычислительная геометрия

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

Фокус
Строгая теория + вычислительная реализация
Формат
Лекции, практикум, контрольные задачи
Цель
Уровень: самостоятельное решение сложных профильных задач

1. Карта курса

  • Ориентационные тесты и геометрические предикаты.
  • Выпуклые оболочки и sweep-line.
  • Пересечения и nearest-neighbor задачи.
  • Оценка сложности и обработка дегенеративных случаев.
Рекомендуемый режим освоения: теория \(\rightarrow\) 2-3 задачи вручную \(\rightarrow\) вычислительная проверка \(\rightarrow\) короткий конспект ошибок.

1.1. Лекционный маршрут и выходные компетенции

  • Недели 1-3: формализация задачи, выбор структур данных и инвариантов.
  • Недели 4-6: доказательство корректности и асимптотический анализ.
  • Недели 7-10: оптимизация производительности, профилирование и тестирование.
  • Недели 11-14: масштабирование, параллелизм и надёжность реализации.

2. Теоретический каркас

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

Базовая схема: формализация задачи → структура данных → алгоритм → доказательство корректности → анализ сложности → практическая оптимизация.
Критерий качества решения: не только асимптотика, но и предсказуемость поведения на реальных данных.

2.1. Строгий минимум раздела

  • Доказывать корректность алгоритма через инварианты цикла и разбор граничных случаев.
  • Явно выделять асимптотику по времени и памяти для худшего и среднего сценариев.
  • Перед оптимизацией фиксировать профиль производительности и метрики качества.
  • Покрывать критические ветки тестами регрессии и негативными сценариями.
Требование уровня "отлично": уметь не только выполнить вычисление, но и письменно обосновать корректность каждого шага с явным указанием условий применимости.

3. Ключевые формулы и зависимости

КонцептФормула / интерпретация
Временная сложность\(T(n)\in O(f(n))\)
Пространственная сложность\(M(n)\in O(g(n))\)
Амортизированная оценка\(\bar T = \frac{1}{m}\sum_{i=1}^m T_i\)
Ускорение\(S=\frac{T_{base}}{T_{opt}}\)
Ориентация\(\operatorname{cross}(b-a,c-a)\)
Graham scan\(O(n\log n)\)
Nearest pair\(O(n\log n)\) при divide-and-conquer

4. Методика решения типовых задач

  1. Фиксировать инварианты структуры данных и проверять их после операций.
  2. Сначала добиваться корректности, затем оптимизировать горячие участки.
  3. Использовать профилирование вместо предположений о bottleneck.
  4. Тестировать крайние случаи и случайные входы (fuzz/property-based).
  5. Сравнивать несколько реализаций на одном наборе бенчмарков.
  6. Документировать интерфейс и асимптотику публичных методов.

4.1. Формат эталонного решения

  1. Записать функциональные требования и ограничения по памяти/времени.
  2. Доказать корректность через инварианты и разбор крайних случаев.
  3. Оценить сложность и проверить оценку экспериментально.
  4. Добавить тесты на случайные и adversarial-входы.
  5. Профилированием подтвердить, что оптимизация улучшила нужный участок.
Оформление полного решения: постановка \rightarrow выбор метода \rightarrow вычисления \rightarrow контроль ошибки \rightarrow интерпретация результата.

5. Разбор прикладного кейса

Кейс: robust intersection для сегментов

Используются ориентационные тесты с учетом коллинеарных случаев и точек на границе. Для численной устойчивости добавляется epsilon-логика и тестирование на вырожденных конфигурациях.

Проверка результата: после вычислений обязательно фиксировать 1) численную стабильность, 2) чувствительность к параметрам, 3) интерпретацию в терминах исходной предметной задачи.

5.1. Углубление кейса

Усиленный разбор алгоритмического кейса включает архитектурные ограничения: модель памяти, конкурентный доступ, стоимость коммуникаций и накладные расходы абстракций. Это позволяет избежать «академически верного, но медленного» решения.

  • Сравнить две структуры данных на одинаковом наборе бенчмарков.
  • Проверить корректность на случайных и adversarial-входах.
  • Описать, какие инварианты защищают код от скрытых регрессий.

6. Типичные ошибки

  • Оптимизация без измерений.
  • Неправильная асимптотическая оценка из-за скрытых вложенных операций.
  • Утечки ресурсов и гонки данных в параллельном коде.
  • Использование неподходящей структуры данных.
  • Отсутствие тестов регрессии после рефакторинга.

6.1. Диагностика ошибок

  • Исключать ложные оптимизации без измерений до и после изменений.
  • Проверять отсутствие регрессий после рефакторинга структуры данных.
  • В параллельных задачах отслеживать гонки и ложное разделение cache line.
  • Контролировать корректность при пустых и предельных входах.

7. Практикум (3 уровня)

Уровень A: базовая техника

  • Решить 12-15 стандартных задач с полной записью решения.
  • Для каждой задачи указать примененный метод и почему он корректен.
  • Проверить 3 задачи альтернативным методом.

Уровень B: продвинутая отработка

  • Решить 8 задач с параметрами и анализом вырожденных случаев.
  • Оценить погрешность/устойчивость результата на вариациях входа.
  • Подготовить короткий отчёт с выводами (1-2 страницы).

Уровень C: мини-проект

  • Реализовать вычислительный прототип по теме курса.
  • Сравнить минимум 2 метода и обосновать выбор лучшего.
  • Подготовить репродуцируемый notebook с графиками и выводами.

8. Экзаменационный минимум и литература

Минимум к экзамену

  • Все базовые определения курса в строгой формулировке.
  • Ключевые теоремы/критерии и условия их применимости.
  • Алгоритм решения типовой задачи каждого раздела.
  • Умение объяснить источник ошибки и устойчивость метода.
  • Интерпретация результата в прикладном контексте.

Рекомендуемая литература

  • de Berg et al. Computational Geometry; O'Rourke J.
  • Материалы семинаров и практикумов кафедры.
  • Набор задач повышенной сложности (подготовка к экзамену).

Тренажер билетов

  1. Докажите корректность выбранного алгоритма и укажите, где используется инвариант.
  2. Оцените асимптотику и объясните, когда доминируют константы реализации.
  3. Разберите trade-off между скоростью, памятью и читаемостью API.
  4. Покажите, как диагностировать узкое место и подтвердить улучшение измерениями.

План повторения перед экзаменом

Эффективная подготовка строится циклом "теория \rightarrow задачи \rightarrow разбор ошибок". Для каждого раздела фиксируйте: формулировку ключевых определений, один эталонный алгоритм решения и типовую ловушку, которая чаще всего приводит к неверному ответу.

  • Сделать короткий one-page summary по каждому разделу с формулами и условиями применимости.
  • Решить минимум 2 задачи базового и 1 задачу повышенного уровня по каждому крупному блоку.
  • Провести устный прогон билета: формулировка теоремы, схема доказательства, прикладная интерпретация.

Конспект сделан в усиленном формате: теория, формулы, кейсы, ошибки, практикум и экзаменационный минимум. Вернуться к программе.