ИВТ. Математические основания алгоритмов и сложность вычислений. 2026
Содержание
О курсе
Математические основания алгоритмов и сложность вычислений — это первый семестр из четырёх, посвящённых алгоритмам.
Курс закладывает чисто математический фундамент, необходимый для понимания и анализа алгоритмов в следующих семестрах.
Команда курса
- Руководитель курса / лектор: Троян-Головян Владислав
- Преподаватели, семинаристы, ассистенты:
- Троян-Головян Владислав
- Бунин Лев Алексеевич
Программа курса
- Введение
- Теория множеств
- Бинарная арифметика
- O-нотация и мастер-теорема
- Индукция и комбинаторика
- Теория вероятностей I
- Теория вероятностей II
- Вещественная арифметика
- Теория чисел I
- Теория чисел II
- Графы I
- Графы II
- Вероятностные алгоритмы
- P/NP: основы
Коммуникация
- Ссылка на чат курса в мессенджере (будет опубликована ближе к старту семестра).
Прогресс студентов
- Ссылка на таблицу студентов с оценками (будет опубликована ближе к старту семестра).
Критерии оценивания и формы контроля успеваемости
Домашние задания
По каждой теме выдаётся домашнее задание, оцениваемое от 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 баллов.
Материалы курса
Презентации и дополнительные материалы будут публиковаться по ходу занятий.
