ИВТ. Разработка и анализ алгоритмов весна 2026

Материал из Public ATP Wiki
Перейти к: навигация, поиск

Общие сведения

Команда курса

Руководитель курса: Троян-Головян Владислав @vhdev

Лектор: Троян-Головян Владислав

Семинаристы:

  • Бунин Лев
  • Троян-Головян Владислав

Учебные ассистенты

  • Прохорчук Екатерина
  • Черевичная Наталья

Контакт для организационных вопросов: @vhdev

План лекций

Презентации

  1. Линейные контейнеры, амортизационный анализ, два указателя, бинарный и тернарный поиск.
  2. Сортировки 1: Квадратичные сортировки, сортировка слиянием и быстрая сортировка.
  3. Сортировки 2: Бинарная куча, пирамидальная сортировка. Introsort. LSD sort, MSD sort
  4. Сортировки 3: Гибридные сортировки: TimSort и PDQSort.
  5. Кучи 1. Биномиальная куча.
  6. Кучи 2. Фибоначчиева куча.
  7. Хеш-таблицы 1. Таблицы с прямой адрессацией. Хеширование. Метод цепочек для решения коллизий. Универсальное семейство хэш-функций. Открытая адрессация.
  8. Хеш-таблицы 2. Идеальное хеширование. Фильтр Блума.
  9. Деревья 1. Наивное дерево поиска. AVL-дерево.
  10. Деревья 2. Декартово дерево, декартово дерево по неявному ключу. Список с пропусками.
  11. Деревья 3. Splay-дерево. B-дерево.
  12. Деревья 4. Красно-черное дерево
  13. Запросы на отрезках 1. Sparse Table и Дерево отрезков
  14. Запросы на отрезках 2. Дерево Фенвика, многомерный фенвик, Фенвик фенвиков.

Формула оценивания зачета

На курсе оценка состоит из трех частей:

  • C - число от 0 до 10, за контесты, которых 3: "Базовые алгоритмы", "Поисковые структуры", "RMQ/RSQ"
  • L - число от 0 до 10, за лабы, которых 7: "Работа с Git", "Стеки", "Сортировки", "Кучи", "Хеши", "Деревья", "RMQ/RSQ"
  • S - Работа на семинарах (от -1 до 1), метод выставления на усмотрение семинариста.
  • Также есть контест, составленный по мотивам алгоритмических собеседований в различные компании, за него оценка не ставится, он рекомендован к самостоятельному прорешиванию, многие задачи из него будут обсуждаться на семинарах.

Блокирующие условия: C >= 3, L >= 3, лабы "Стеки", "Сортировки" и "Хеши" сданы как минимум на половину баллов(пройдено код-ревью, сдана теория).

Итоговая оценка выставляется по формуле: 0.4C+0.6L+S.

Пороги для C и L из формулы:

  • >= 50%: 3
  • >= 55%: 4
  • >= 65%: 5
  • >= 70%: 6
  • >= 75%: 7
  • >= 85%: 8
  • >= 90%: 9
  • >= 95%: 10
Источник — «http://wiki.atp-fivt.org/index.php?title=ИВТ._Разработка_и_анализ_алгоритмов_весна_2026&oldid=4480»