ИВТ. Математические основания алгоритмов и сложность вычислений. 2026: различия между версиями
| Строка 20: | Строка 20: | ||
|- | |- | ||
| 1 | | 1 | ||
| | | Введение | ||
| | | | ||
|- | |- | ||
| 2 | | 2 | ||
| | | Теория множеств | ||
| | | | ||
|- | |- | ||
| 3 | | 3 | ||
| | | Бинарная арифметика | ||
| | | | ||
|- | |- | ||
| 4 | | 4 | ||
| | | O-нотация и мастер-теорема | ||
| | | | ||
|- | |- | ||
| 5 | | 5 | ||
| | | Индукция и комбинаторика | ||
| | | | ||
|- | |- | ||
| 6 | | 6 | ||
| | | Теория вероятностей I | ||
| | | | ||
|- | |- | ||
| 7 | | 7 | ||
| | | Теория вероятностей II | ||
| | | | ||
|- | |- | ||
| 8 | | 8 | ||
| | | Вещественная арифметика | ||
| | | | ||
|- | |- | ||
| 9 | | 9 | ||
| | | Теория чисел I | ||
| | | | ||
|- | |- | ||
| 10 | | 10 | ||
| | | Теория чисел II | ||
| | | | ||
|- | |- | ||
| 11 | | 11 | ||
| | | Графы I | ||
| | | | ||
|- | |- | ||
| 12 | | 12 | ||
| | | Графы II | ||
| | | | ||
|- | |- | ||
| 13 | | 13 | ||
| | | Вероятностные алгоритмы | ||
| | | | ||
|- | |- | ||
| 14 | | 14 | ||
| | | P/NP: основы | ||
| | | | ||
|} | |} | ||
Версия от 09:08, 16 июня 2026
О курсе
Математические основания алгоритмов и сложность вычислений — это первый семестр из четырёх, посвящённых алгоритмам.
Курс закладывает чисто математический фундамент, необходимый для понимания и анализа алгоритмов в следующих семестрах.
Команда курса
- Руководитель курса / лектор: Троян-Головян Владислав
- Преподаватели, семинаристы, ассистенты:
- Троян-Головян Владислав
- Бунин Лев Алексеевич
Программа курса
| Неделя | Лекции | Домашние задания и контест |
|---|---|---|
| 1 | Введение | |
| 2 | Теория множеств | |
| 3 | Бинарная арифметика | |
| 4 | O-нотация и мастер-теорема | |
| 5 | Индукция и комбинаторика | |
| 6 | Теория вероятностей I | |
| 7 | Теория вероятностей II | |
| 8 | Вещественная арифметика | |
| 9 | Теория чисел I | |
| 10 | Теория чисел II | |
| 11 | Графы I | |
| 12 | Графы II | |
| 13 | Вероятностные алгоритмы | |
| 14 | 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 баллов.
Материалы курса
Презентации и дополнительные материалы будут публиковаться по ходу занятий.