ИВТ. Математические основания алгоритмов и сложность вычислений. 2026 — различия между версиями
(→Программа курса) |
(→Штрафы) |
||
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 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: основы |
| − | | | + | | Контрольная работа |
|- | |- | ||
| 15 | | 15 | ||
| − | | | + | | Вопрос-ответ |
| | | | ||
|} | |} | ||
| Строка 136: | Строка 136: | ||
* Просрочка до 3 дней — штраф '''50%'''. | * Просрочка до 3 дней — штраф '''50%'''. | ||
* Просрочка более 3 дней — '''0 баллов'''. | * Просрочка более 3 дней — '''0 баллов'''. | ||
| − | + | '''Исключение:''' официальный допуск или медицинская справка. | |
* За списывание оба участника получают оценку '''−10 баллов'''. | * За списывание оба участника получают оценку '''−10 баллов'''. | ||
Текущая версия на 12:30, 17 июня 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 баллов.
Материалы курса
Презентации и дополнительные материалы будут публиковаться по ходу занятий.
