ИВТ. Математические основания алгоритмов и сложность вычислений. 2026: различия между версиями
| Строка 14: | Строка 14: | ||
== Программа курса == | == Программа курса == | ||
{| class="wikitable" | |||
! Неделя | |||
! Лекции | |||
! Домашние задания и контест | |||
|- | |||
| 1 | |||
| Асимптотика. Бинарный поиск. | |||
| Бинарный поиск, два указателя. | |||
|- | |||
| 2 | |||
| MergeSort. QuickSort. | |||
| | |||
|- | |||
| 3 | |||
| Derandomized QuickSort. LSDSort. | |||
| Сортировки. | |||
|- | |||
| 4 | |||
| Кучи. HeapSort. | |||
| | |||
|- | |||
| 5 | |||
| Кучи (продолжение). Динамический массив. | |||
| Кучи, линейные контейнеры. | |||
|- | |||
| 6 | |||
| Связные списки. Кучи Фибоначчи. | |||
| | |||
|- | |||
| 7 | |||
| Стеки. Очередь. | |||
| | |||
|- | |||
| 8 | |||
| Дерево отрезков. | |||
| Дерево отрезков, дерево Фенвика. | |||
|- | |||
| 9 | |||
| Динамическое ДО. Персистентные структуры данных. | |||
| | |||
|- | |||
| 10 | |||
| Деревья поиска: AVL-деревья, Splay-дерево. | |||
| Деревья поиска. | |||
|- | |||
| 11 | |||
| Неявное дерево поиска. | |||
| | |||
|- | |||
| 12 | |||
| Декартово дерево. B-дерево. | |||
| | |||
|- | |||
| 13 | |||
| Красно-чёрное дерево. | |||
| | |||
|- | |||
| 14 | |||
| Хэш-таблицы. | |||
| Хэш-таблицы. | |||
|- | |||
| 15 | |||
| Хэш-таблицы (продолжение). | |||
| | |||
|} | |||
== Коммуникация == | == Коммуникация == | ||
Версия от 09:05, 16 июня 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 баллов.
Материалы курса
Презентации и дополнительные материалы будут публиковаться по ходу занятий.