ИВТ. Математические основания алгоритмов и сложность вычислений. 2026
Содержание
О курсе
Математические основания алгоритмов и сложность вычислений — это первый семестр из четырёх, посвящённых алгоритмам.
Курс закладывает чисто математический фундамент, необходимый для понимания и анализа алгоритмов в следующих семестрах.
Команда курса
- Руководитель курса / лектор: Троян-Головян Владислав
- Преподаватели, семинаристы, ассистенты:
- Троян-Головян Владислав
- Бунин Лев Алексеевич
Программа курса
| Неделя | Лекции | Домашние задания и контест |
|---|---|---|
| 1 | Асимптотика. Бинарный поиск. | Бинарный поиск, два указателя. |
| 2 | MergeSort. QuickSort. | |
| 3 | Derandomized QuickSort. LSDSort. | Сортировки. |
| 4 | Кучи. HeapSort. | |
| 5 | Кучи (продолжение). Динамический массив. | Кучи, линейные контейнеры. |
| 6 | Связные списки. Кучи Фибоначчи. | |
| 7 | Стеки. Очередь. | |
| 8 | Дерево отрезков. | Дерево отрезков, дерево Фенвика. |
| 9 | Динамическое ДО. Персистентные структуры данных. | |
| 10 | Деревья поиска: AVL-деревья, Splay-дерево. | Деревья поиска. |
| 11 | Неявное дерево поиска. | |
| 12 | Декартово дерево. B-дерево. | |
| 13 | Красно-чёрное дерево. | |
| 14 | Хэш-таблицы. | Хэш-таблицы. |
| 15 | Хэш-таблицы (продолжение). |
Коммуникация
- Ссылка на чат курса в мессенджере (будет опубликована ближе к старту семестра).
Прогресс студентов
- Ссылка на таблицу студентов с оценками (будет опубликована ближе к старту семестра).
Критерии оценивания и формы контроля успеваемости
Домашние задания
По каждой теме выдаётся домашнее задание, оцениваемое от 0 до 10 баллов.
- Срок выполнения: 2 недели
- Формат выполнения: TeX
Контрольные работы
В течение семестра проводятся две контрольные работы:
- после лекции 8;
- после лекции 14.
Каждая контрольная работа оценивается от 0 до 10 баллов.
Допуск к зачёту
Если:
- средний балл за контрольные работы меньше 3, и/или
- средний балл за домашние задания меньше 3,
то итоговая оценка за курс — неудовлетворительно.
Семинарский балл
На семинарах преподаватель проводит квизы по материалам лекций, а также учитывает:
- посещаемость;
- активность на занятиях;
- выходы к доске.
По итогам семестра выставляется семинарский балл в диапазоне от −1 до +1, который добавляется к итоговой оценке.
Итоговая оценка за зачёт
0.5*AVG(ДЗ)+0.5*AVG(КР) + Балл от семинариста.
Если итоговая оценка равна 11, студент получает бонус к экзамену.
Штрафы
- Просрочка сдачи до 24 часов — штраф 25%.
- Просрочка до 3 дней — штраф 50%.
- Просрочка более 3 дней — 0 баллов.
- Исключение: официальный допуск или медицинская справка.
- За списывание оба участника получают оценку −10 баллов.
Материалы курса
Презентации и дополнительные материалы будут публиковаться по ходу занятий.
