Алгоритмы на графах и динамическое программирование 2026: различия между версиями
Нет описания правки |
|||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 7: | Строка 7: | ||
Андреев Ярослав Андреевич | Андреев Ярослав Андреевич | ||
Прохорчук Екатерина Александровна | Прохорчук Екатерина Александровна | ||
==Программа курса== | ==Программа курса== | ||
Дисциплина состоит из: | |||
* Алгоритмы на графах и динамическое программирование | |||
'''Форма контроля:''' экзамен | |||
* Практикум по алгоритмам на графах и динамическому программированию | |||
'''Форма контроля:''' Дифференцированный зачет | '''Форма контроля:''' Дифференцированный зачет | ||
{| class="wikitable" | {| class="wikitable" | ||
| Строка 59: | Строка 67: | ||
| Min-cost flow. Задача о назначениях | | Min-cost flow. Задача о назначениях | ||
|} | |} | ||
== Коммуникация == | |||
Ссылка на чат курса в мессенджере | |||
[https://t.me/+79xMH16hnIU5MTFi [2026<nowiki>]</nowiki>[ИВТ, 2 курс<nowiki>]</nowiki> [Алгоритмы на графах и ДП<nowiki>]</nowiki>] | |||
== Прогресс студентов == | |||
Ссылка на таблицу студентов с оценками (ближе к старту семестра) | |||
==Критерии оценивания и формы контроля успеваемости== | |||
В течение семестра проводится '''6 контестов''', в каждом из которых одна задача выполняется с последующим '''код-ревью'''. | |||
По задачам на ревью опрелеляется верхняя граница оценки(далее X): | |||
Если пройдено | |||
<br> Для порога уд. 4 нужно пройти(получить approve) 3, | |||
<br> Для порога хор. 7, нужно пройти 4, | |||
<br> Для порога отл. 8-9, нужно пройти 5 | |||
<br> Для порога отл. 10, нужно пройти 6. | |||
=== Контрольные работы === | |||
В течение семестра проводится '''2 контрольные работы'''. За каждую контрольную можно получить от '''0 до 10 баллов'''. | |||
'''Блокирующее условие на неуд:''' сумма оценок по двум контрольным должна быть хотя бы 6б. | |||
Итоговая оценка рассчитывается на основе трёх составляющих: | |||
* A - контесты(от 1 до 10, выставляется по порогам) | |||
* B - AVG контрольные(от 1 до 10) | |||
* C - оценка от семинариста(от -1 до +1) | |||
Далее вычисляется Y=0.5*A+0.5*B+C | |||
И выставляется Min(X,Y) | |||
Пороги для оценки A: | |||
<br> >= 50%: уд3, | |||
<br> >= 55%: уд4, | |||
<br> >= 65%: хор 5, | |||
<br> >= 70%: хор 6, | |||
<br> >= 75%: хор 7, | |||
<br> >= 85%: отл 8, | |||
<br> >= 90%: отл 9, | |||
<br> >= 95%: отл 10, | |||
<br> Иначе: неуд 1 | |||
== Политика списывания == | |||
'''Политика списывания:''' при подозрении на списывание семинарист/ассистент проводит устную беседу, если факт списывания подтверждается, то зануляется весь контест целиком. При повторном списывании ставится итоговая оценка неуд. 2. | |||
Текущая версия от 10:01, 30 октября 2026
Команда курса
Лектор: Троян-Головян Владислав
Семинарист: Аксёненко Денис
Ассистенты:
Андреев Ярослав Андреевич
Прохорчук Екатерина Александровна
Программа курса
Дисциплина состоит из:
- Алгоритмы на графах и динамическое программирование
Форма контроля: экзамен
- Практикум по алгоритмам на графах и динамическому программированию
Форма контроля: Дифференцированный зачет
| № недели | Лекция / семинар |
|---|---|
| 1 | Основные идеи, базовые задачи: НОП, НВП, Банкомат |
| 2 | Динамическое программирование 2: матричное ДП, алгоритм Хиршберга, задача о рюкзаке, ДП по цифрам |
| 3 | ДП по битмаскам, гамильтоновы пути, клики; ДП по профилю, скошенному профилю |
| 4 | Convex Hull Trick |
| 5 | Графы 1: способы хранения, DFS, BFS, цвета вершин |
| 6 | Графы 2: DFS и времена входа и выхода, топологическая сортировка, поиск КСС, 2-SAT, мосты и точки сочленения |
| 7 | Остовные деревья, СНМ, алгоритм Крускала, алгоритм Прима, матроиды |
| 8 | Алгоритм Борувки, LCA: поиск при помощи двух указателей, бинарных подъёмов, сведение LCA к RMQ. Алгоритм Фарака–Колтона и Бендера. Сведение RMQ к LCA |
| 9 | Кратчайшие пути 1: алгоритм Дейкстры, алгоритм A*, алгоритм Форда–Беллмана, алгоритм Флойда–Уоршелла |
| 10 | Кратчайшие пути 2: алгоритм Джонсона, улучшения алгоритма Дейкстры, двунаправленный A*, алгоритм IDA* |
| 11 | Паросочетания: алгоритм Куна, теорема Бержа, теорема Кёнига. Построение минимального вершинного покрытия |
| 12 | Потоки 1: основные понятия, теорема о максимальном потоке и минимальном разрезе, метод Форда–Фалкерсона, алгоритм Эдмондса–Карпа. Поиск максимального паросочетания при помощи поиска потока |
| 13 | Алгоритмы Диница и Хопкрофта–Карпа |
| 14 | Min-cost flow. Задача о назначениях |
Коммуникация
Ссылка на чат курса в мессенджере [2026][ИВТ, 2 курс] [Алгоритмы на графах и ДП]
Прогресс студентов
Ссылка на таблицу студентов с оценками (ближе к старту семестра)
Критерии оценивания и формы контроля успеваемости
В течение семестра проводится 6 контестов, в каждом из которых одна задача выполняется с последующим код-ревью.
По задачам на ревью опрелеляется верхняя граница оценки(далее X):
Если пройдено
Для порога уд. 4 нужно пройти(получить approve) 3,
Для порога хор. 7, нужно пройти 4,
Для порога отл. 8-9, нужно пройти 5
Для порога отл. 10, нужно пройти 6.
Контрольные работы
В течение семестра проводится 2 контрольные работы. За каждую контрольную можно получить от 0 до 10 баллов.
Блокирующее условие на неуд: сумма оценок по двум контрольным должна быть хотя бы 6б.
Итоговая оценка рассчитывается на основе трёх составляющих:
- A - контесты(от 1 до 10, выставляется по порогам)
- B - AVG контрольные(от 1 до 10)
- C - оценка от семинариста(от -1 до +1)
Далее вычисляется Y=0.5*A+0.5*B+C
И выставляется Min(X,Y)
Пороги для оценки A:
>= 50%: уд3,
>= 55%: уд4,
>= 65%: хор 5,
>= 70%: хор 6,
>= 75%: хор 7,
>= 85%: отл 8,
>= 90%: отл 9,
>= 95%: отл 10,
Иначе: неуд 1
Политика списывания
Политика списывания: при подозрении на списывание семинарист/ассистент проводит устную беседу, если факт списывания подтверждается, то зануляется весь контест целиком. При повторном списывании ставится итоговая оценка неуд. 2.