ИВТ. Математические основания алгоритмов и сложность вычислений. 2026

О курсе

Математические основания алгоритмов и сложность вычислений — это первый семестр из четырёх, посвящённых алгоритмам.

Курс закладывает чисто математический фундамент, необходимый для понимания и анализа алгоритмов в следующих семестрах.

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

• Руководитель курса / лектор: Троян-Головян Владислав
• Преподаватели, семинаристы, ассистенты:
  • Троян-Головян Владислав
  • Бунин Лев Алексеевич

Программа курса

Неделя	Лекции	Домашние задания и контест
1	Введение
2	Теория множеств
3	Бинарная арифметика
4	O-нотация и мастер-теорема
5	Индукция и комбинаторика
6	Теория вероятностей I
7	Теория вероятностей II
8	Вещественная арифметика	Контрольная работа
9	Теория чисел I
10	Теория чисел II
11	Графы I
12	Графы II
13	Вероятностные алгоритмы
14	P/NP: основы	Контрольная работа
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 баллов.

Материалы курса

Презентации и дополнительные материалы будут публиковаться по ходу занятий.