Алгоритмы на графах и динамическое программирование 2026 - История изменений

Spirina.es: /* Коммуникация */

2026-10-30T10:01:51Z

Коммуникация

← Предыдущая версия		Версия от 10:01, 30 октября 2026
Строка 70:		Строка 70:
	== Коммуникация ==		== Коммуникация ==

	Ссылка на чат курса в мессенджере ~~(ближе к старту семестра)~~		Ссылка на чат курса в мессенджере
			[https://t.me/+79xMH16hnIU5MTFi [2026<nowiki>]</nowiki>[ИВТ, 2 курс<nowiki>]</nowiki> [Алгоритмы на графах и ДП<nowiki>]</nowiki>]

	== Прогресс студентов ==		== Прогресс студентов ==

Spirina.es: /* Программа курса */

2026-08-28T14:08:30Z

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

← Предыдущая версия		Версия от 14:08, 28 августа 2026
Строка 13:		Строка 13:
	Дисциплина состоит из:		Дисциплина состоит из:

	* ~~Математические основания алгоритмов~~ и ~~сложность вычислений~~		* Алгоритмы на графах и динамическое программирование

	'''Форма контроля:''' экзамен		'''Форма контроля:''' экзамен
	* Практикум по ~~математическим основаниям алгоритмов~~
			* Практикум по алгоритмам на графах и динамическому программированию

	'''Форма контроля:''' Дифференцированный зачет		'''Форма контроля:''' Дифференцированный зачет

Spirina.es: /* Программа курса */

2026-08-28T14:04:01Z

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

← Предыдущая версия		Версия от 14:04, 28 августа 2026
Строка 11:		Строка 11:

	==Программа курса==		==Программа курса==
			Дисциплина состоит из:

	'''Форма контроля:''' Дифференцированный зачет ~~и экзамен~~		* Математические основания алгоритмов и сложность вычислений
			'''Форма контроля:''' экзамен
			* Практикум по математическим основаниям алгоритмов
			'''Форма контроля:''' Дифференцированный зачет

	{\| class="wikitable"		{\| class="wikitable"

Spirina.es в 13:44, 28 августа 2026

2026-08-28T13:44:14Z

← Предыдущая версия		Версия от 13:44, 28 августа 2026
Строка 107:		Строка 107:
	<br> >= 95%: отл 10,		<br> >= 95%: отл 10,
	<br> Иначе: неуд 1		<br> Иначе: неуд 1

			== Политика списывания ==
			'''Политика списывания:''' при подозрении на списывание семинарист/ассистент проводит устную беседу, если факт списывания подтверждается, то зануляется весь контест целиком. При повторном списывании ставится итоговая оценка неуд. 2.

Spirina.es: /* Команда курса */

2026-08-28T13:40:50Z

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

← Предыдущая версия		Версия от 13:40, 28 августа 2026
Строка 7:		Строка 7:

	Андреев Ярослав Андреевич		Андреев Ярослав Андреевич

	Прохорчук Екатерина Александровна		Прохорчук Екатерина Александровна

Spirina.es в 13:38, 28 августа 2026

2026-08-28T13:38:59Z

← Предыдущая версия		Версия от 13:38, 28 августа 2026
Строка 68:		Строка 68:
	Ссылка на таблицу студентов с оценками (ближе к старту семестра)		Ссылка на таблицу студентов с оценками (ближе к старту семестра)

	== ~~Система~~ оценивания ==		==Критерии оценивания и формы контроля успеваемости==

	В течение семестра проводится '''6 контестов''', в каждом из которых одна задача выполняется с последующим '''код-ревью'''.		В течение семестра проводится '''6 контестов''', в каждом из которых одна задача выполняется с последующим '''код-ревью'''.

	~~==Критерии оценивания и формы контроля успеваемости==~~

	По задачам на ревью опрелеляется верхняя граница оценки(далее X):		По задачам на ревью опрелеляется верхняя граница оценки(далее X):

Spirina.es в 13:37, 28 августа 2026

2026-08-28T13:37:11Z

← Предыдущая версия		Версия от 13:37, 28 августа 2026
Строка 59:		Строка 59:
	\| Min-cost flow. Задача о назначениях		\| Min-cost flow. Задача о назначениях
	\|}		\|}

			== Коммуникация ==

			Ссылка на чат курса в мессенджере (ближе к старту семестра)

			== Прогресс студентов ==

			Ссылка на таблицу студентов с оценками (ближе к старту семестра)

			== Система оценивания ==

			В течение семестра проводится '''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.5A+0.5B+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

Spirina.es в 13:27, 27 августа 2026

2026-08-27T13:27:30Z

← Предыдущая версия		Версия от 13:27, 27 августа 2026
Строка 1:		Строка 1:
			==Команда курса==
			Лектор: Троян-Головян Владислав

			Семинарист: Аксёненко Денис

			Ассистенты:

			Андреев Ярослав Андреевич
			Прохорчук Екатерина Александровна

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

Spirina.es: Новая страница: «==Программа курса== '''Форма контроля:''' Дифференцированный зачет и экзамен {| class="wikitable" ! № недели ! Лекция / семинар |- | 1 | Основные идеи, базовые задачи: НОП, НВП, Банкомат |- | 2 | Динамическое программирование 2: матричное ДП, алгоритм Хиршберга, задача о рюк...»

2026-08-13T12:56:35Z

Новая страница: «==Программа курса== '''Форма контроля:''' Дифференцированный зачет и экзамен {| class="wikitable" ! № недели ! Лекция / семинар |- | 1 | Основные идеи, базовые задачи: НОП, НВП, Банкомат |- | 2 | Динамическое программирование 2: матричное ДП, алгоритм Хиршберга, задача о рюк...»

Новая страница

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

'''Форма контроля:''' Дифференцированный зачет и экзамен

{| class="wikitable"
! № недели
! Лекция / семинар
|-
| 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. Задача о назначениях
|}