Алгоритмы и структуры данных пилотный поток 2022/2023 - История изменений

Ifsmirnov в 11:35, 12 апреля 2023

2023-04-12T11:35:26Z

← Предыдущая версия		Версия от 11:35, 12 апреля 2023
Строка 20:		Строка 20:
	После 3-го, 4-го и 5-го модулей будут экзамены.		После 3-го, 4-го и 5-го модулей будут экзамены.

	~~Предварительные правила~~ выставления оценок за модули:		Правила выставления оценок за модули:

	'''2 модуль:''' О<sub>итог</sub> = '''0.4286''' · О<sub>контесты</sub> + '''0.3571''' · O<sub>листки</sub> + '''0.2143''' · О<sub>КР</sub> + O<sub>бонус</sub>		'''2-й модуль:''' О<sub>итог</sub> = '''0.4286''' · О<sub>контесты</sub> + '''0.3571''' · O<sub>листки</sub> + '''0.2143''' · О<sub>КР</sub> + O<sub>бонус</sub>

	'''3-4 модуль:''' О<sub>итог</sub> = '''0.3''' · О<sub>контесты</sub> + '''0.25''' · O<sub>листки</sub> + '''0.15''' · О<sub>КР</sub> + '''0.3''' · О<sub>экзамен</sub> + O<sub>бонус</sub>		'''3-й модуль:''' О<sub>итог</sub> = '''0.3''' · О<sub>контесты</sub> + '''0.25''' · O<sub>листки</sub> + '''0.15''' · О<sub>КР</sub> + '''0.3''' · О<sub>экзамен</sub> + O<sub>бонус</sub>

			'''4-й модуль:''' О<sub>итог</sub> = '''0.3''' · О<sub>контесты</sub> + '''0.25''' · O<sub>листки</sub> + '''0.15''' · О<sub>КР</sub> + '''0.3''' · О<sub>экзамен</sub> + O<sub>бонус</sub>

			В ведомость за каждый модуль идёт округлённое значение из формулы выше. Для подсчёта итоговой оценки за год берётся среднее арифметическое по '''неокруглённым''' оценки за модули 2, 3, 4. Если оценка за модуль превышает 10, она считается равной 10.

			'''Итог за год (1-й курс):''' (min(10, O<sub>2-й модуль</sub>) + min(10, O<sub>3-й модуль</sub>) + min(10, O<sub>4-й модуль</sub>)) / 3

	<ul>		<ul>

Ifsmirnov в 11:27, 12 апреля 2023

2023-04-12T11:27:53Z

← Предыдущая версия		Версия от 11:27, 12 апреля 2023
Строка 417:		Строка 417:
	! Видео		! Видео
	\|-		\|-
	\| rowspan="2" \| 03.04.2023 (вт)		\| rowspan="1" \| 03.04.2023 (вт)
			\| colspan="4" \| Занятий не было
			\|-
			\| rowspan="2" \| 05.04.2023 (чт)
	\| Семинар		\| Семинар
	\| ~~Антихештесты~~		\| colspan="3" \| Семинара не было
	~~\| [https://disk.yandex.ru/i/xetD-j0S_pmn-A Листок]~~
	\|
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~Блум-фильтр. B-деревья.~~		\| Потоки минимальной стоимости
	\|		\|
	\|		\|
	\|-		\|-
	\| rowspan="2" \| 12.01.2023 (чт)		\| rowspan="2" \| 11.04.2023 (чт)
	\| Семинар		\| Семинар
	\| ~~Деревья поиска~~		\| Потоки. Оценки Карзанова.
	\| ~~[https://disk.yandex.ru/i/WwtNchX-N01hlg Листок]~~		\|
	\|		\|
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~Splay-дерево~~		\| Поиск потока минимальной стоимости за полиномиальное время
	\|		\|
	\|		\|

Ifsmirnov в 11:24, 12 апреля 2023

2023-04-12T11:24:24Z

@@ Строка 404: / Строка 404: @@
 | Лекция
 | Доказательство log* n для СНМ. Введение в потоки.
+|
+|

Ifsmirnov: Темы к экзамену 3-го модуля

2023-03-24T10:01:57Z

Темы к экзамену 3-го модуля

← Предыдущая версия		Версия от 10:01, 24 марта 2023
Строка 171:		Строка 171:

	== Экзамены ==		== Экзамены ==
			=== Темы к экзамену 3-го модуля ===

			* Бинарные деревья поиска. Определение, базовые свойства.
			* B+-дерево. Простейшие операции. Операции Split и Merge.
			* Splay-дерево. Операции. Доказательство амортизированного времени работы.
			* Декартово дерево. Операции Split и Merge. Оценка матожидания глубины вершины. Декартово дерево по неявному ключу.
			* Запросы на отрезках. Дерево отрезков, общие идеи. Sparse table. Disjoint sparse table.
			* Персистентность. Общие идеи, примеры частично и полностью персистентных структур данных. Применение в задачх.
			* Методы Path copying и Fat nodes. Их комбинирование для получения частично персистентного списка без штрафа по времени и памяти.
			* LCA. Метод двоичных подъёмов. Алгоритм Тарьяна с СНМ. Алгоритм Фараха-Колтона и Бендера.
			* Запросы на деревьях. Heavy-light декомпозиция, оптимизация времени работы до O(log n) на запрос.
			* Переборные алгоритмы. Подходы через поиск в глубину и поиск в ширину. Способы хеширования состояний. Iterative deepening. Примеры отсечений.
			* Кратчайшие пути в графах. Алгоритмы Дейкстры и Форда-Беллмана. Двусторонний алгоритм Дейкстры.
			* Алгоритм Contraction Hierarchies для поиска кратчайших путей в графах, возникающих на практике.
			* Альфа-бета отсечение в антагонистических играх.
			* Мосты, точки сочленения. Построение деревьев компонент рёберной и вершинной двусвязности.
			* Конденсация ориентированного графа. Алгоритм Тарьяна.
			* Система непересекающихся множеств. Доказательство амортизированного времени работы O(log* n) на запрос.
			* Минимальные остовные деревья. Алгоритмы Прима, Краскала, Борувки.
			* Линейный вероятностный алгоритм построения MST (в предположении существования алгоритма проверки минимальности за линейное время). Проверка остовного дерева на минимальность за O(m log log n).
			* Потоки в сетях. Теорема Форда-Фалкерсона. Примеры решения задач через сведение к минимальному разрезу или максимальному потоку.
			* Теорема Кёнига-Эгервари, лемма Холла. Доказательство через теорему Форда-Фалкерсона.
			* Алгоритм Эдмондса-Карпа. Алгоритм Диница, доказательство времени работы O(E sqrt(V)) при поиске максимального двудольного паросочетания.

	== Лекции и семинары ==		== Лекции и семинары ==

Ifsmirnov в 20:04, 11 марта 2023

2023-03-11T20:04:38Z

← Предыдущая версия		Версия от 20:04, 11 марта 2023
Строка 173:		Строка 173:

	== Лекции и семинары ==		== Лекции и семинары ==

			Записи семинаров, сделанные силами студентов: https://disk.yandex.ru/d/yVmC7VRuXWblIw

	=== 2 модуль ===		=== 2 модуль ===

Ifsmirnov в 19:47, 11 марта 2023

2023-03-11T19:47:50Z

← Предыдущая версия		Версия от 19:47, 11 марта 2023
Строка 251:		Строка 251:
	\| Семинар		\| Семинар
	\| Запросы на отрезках		\| Запросы на отрезках
	\| [https://disk.yandex.ru/d/NCP3V4mzYMXMUA ~~Листок~~]		\| Листки: [https://disk.yandex.ru/d/NCP3V4mzYMXMUA базовый], <br/> [https://disk.yandex.ru/i/RDrpfaX1AQwKQA бонусный]
	\|		\|
	\|-		\|-
Строка 273:		Строка 273:
	\| Семинар		\| Семинар
	\| Задачи на деревья		\| Задачи на деревья
	\|		\| [https://disk.yandex.ru/d/uI1OKKPl7fgpEw Листок]
	\|		\|
	\|-		\|-
Строка 284:		Строка 284:
	\| Семинар		\| Семинар
	\| Простое ДП, задачи о рюкзаке		\| Простое ДП, задачи о рюкзаке
	\|		\| [https://disk.yandex.ru/i/AGMSwsEX3GdUYw Листок]
	\|		\|
	\|-		\|-
Строка 301:		Строка 301:
	\| Семинар		\| Семинар
	\| ДП, переборы		\| ДП, переборы
	\|		\| [https://disk.yandex.ru/i/d7oZjXEJv56a4A Листок]
	\|		\|
	\|-		\|-
Строка 312:		Строка 312:
	\| Семинар		\| Семинар
	\| ДП, альфа-бета отсечение		\| ДП, альфа-бета отсечение
	\|		\| [https://disk.yandex.ru/i/cb63noVLHGy7zg Листок]
	\|		\|
	\|-		\|-
Строка 320:		Строка 320:
	\|		\|
	\|-		\|-
	~~\| rowspan="1"~~ \| 14.02.2023 (вт)		\| 14.02.2023 (вт)
	\| Занятий не было		\| colspan="4" \| Занятий не было
	\|
	\|
	\|
	\|-		\|-
	\| 16.02.2023 (чт)		\| 16.02.2023 (чт)
	\| Бонусный семинар		\| Бонусный семинар
	\| Модель внешней памяти		\| Модель внешней памяти
	\|		\| [https://disk.yandex.ru/d/3euDXNlol-JcBQ Листок]
	\|		\|
	\|-		\|-
Строка 335:		Строка 332:
	\| Семинар		\| Семинар
	\| Пути в графах, кратчайшие и не очень		\| Пути в графах, кратчайшие и не очень
	\|		\| [https://disk.yandex.ru/i/NdlcB-1sm9cFlg Листок]
	\|		\|
	\|-		\|-
Строка 366:		Строка 363:
	\| Семинар		\| Семинар
	\| Минимальные остовы		\| Минимальные остовы
	\|		\| [https://disk.yandex.ru/d/D3OrHuMgiEzLiw Листок]
	\|		\|
	\|-		\|-
Строка 377:		Строка 374:
	\| Семинар		\| Семинар
	\| Задачи на графы, конденсация, 2-SAT		\| Задачи на графы, конденсация, 2-SAT
	\|		\| [https://disk.yandex.ru/i/B7IW1Rr6wS_Byg Листок]
	\|		\|
	\|-		\|-

Ifsmirnov в 19:25, 11 марта 2023

2023-03-11T19:25:22Z

← Предыдущая версия		Версия от 19:25, 11 марта 2023
Строка 229:		Строка 229:
	\| Семинар		\| Семинар
	\| Деревья поиска		\| Деревья поиска
	\|		\| [https://disk.yandex.ru/i/WwtNchX-N01hlg Листок]
	\|		\|
	\|-		\|-
	\| Лекция		\| Лекция
	\| Splay-дерево.		\| Splay-дерево
	\|		\|
	\|		\|
Строка 240:		Строка 240:
	\| Семинар		\| Семинар
	\| Деревья поиска, запросы на отрезках		\| Деревья поиска, запросы на отрезках
	\|		\| [https://disk.yandex.ru/i/LUFR0E6yqgclGg Листок]
	\|		\|
	\|-		\|-
Строка 250:		Строка 250:
	\| rowspan="2" \| 19.01.2023 (чт)		\| rowspan="2" \| 19.01.2023 (чт)
	\| Семинар		\| Семинар
	\| ~~Персистентность, запросы~~ на отрезках		\| Запросы на отрезках
	\|		\| [https://disk.yandex.ru/d/NCP3V4mzYMXMUA Листок]
	\|		\|
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[4]~~ Частичная персистентность		\| Частичная персистентность: path copying, fat nodes
	\|		\|
	\|		\|

Ifsmirnov в 19:17, 11 марта 2023

2023-03-11T19:17:33Z

← Предыдущая версия		Версия от 19:17, 11 марта 2023
Строка 218:		Строка 218:
	\| Семинар		\| Семинар
	\| Антихештесты		\| Антихештесты
	\|		\| [https://disk.yandex.ru/i/xetD-j0S_pmn-A Листок]
	\|		\|
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[1] [Филипп]~~		\| Блум-фильтр. B-деревья.
	\|		\|
	\|		\|
Строка 233:		Строка 233:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[2] [Филипп]~~		\| Splay-дерево.
	\|		\|
	\|		\|
Строка 244:		Строка 244:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[3] ДД, доказательство~~ высоты ~~(?)~~		\| Декартово дерево. Доказательство логарифмической высоты.
	\|		\|
	\|		\|
Строка 266:		Строка 266:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[5]~~ List order maintenance (?)		\| List order maintenance (?)
	\|		\|
	\|		\|
Строка 277:		Строка 277:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[6]~~ HLD ~~(?)~~		\| <!-- HLD -->
	\|		\|
	\|		\|
Строка 288:		Строка 288:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[7]~~ Подсчёт количества клик в графе ~~(?)~~		\| Оптимизация переборов. Подсчёт количества клик в графе.
	\|		\|
	\|		\|
	\|-		\|-
	~~\| rowspan="2"~~ \| 2.02.2023 (чт)		\| 2.02.2023 (чт)
	~~\| Семинар~~		\| Бонусный семинар
	\| Бонусный семинар ~~— архитектура~~		\| Архитектура, system design
	\|
	\|
	\|-
	\| ~~Лекция~~
	~~\| Бонус (рассказ)~~
	\|		\|
	\|		\|
Строка 310:		Строка 305:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[8]~~ Переборы~~,альфа~~-бета отсечение		\| Переборы. Альфа-бета отсечение
	\|		\|
	\|		\|
Строка 321:		Строка 316:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[9]~~		\|
	\|		\|
	\|		\|
Строка 330:		Строка 325:
	\|		\|
	\|		\|
			\|-
	\| 16.02.2023 (чт)		\| 16.02.2023 (чт)
	\| Бонусный семинар		\| Бонусный семинар
Строка 343:		Строка 339:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[10]~~ Contraction Hierarchies: поиск кратчайших путей на практике		\| Contraction Hierarchies: поиск кратчайших путей на практике
	\|		\|
	\|		\|
			\|-
	\| 23.02.2023 (чт)		\| 23.02.2023 (чт)
	\| Выходной		\| colspan="4" \| Выходной
	\|
	\|
	\|
	\|-		\|-
	\| rowspan="2" \| 28.02.2023 (вт)		\| rowspan="2" \| 28.02.2023 (вт)
Строка 359:		Строка 353:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[11]~~ Линейный алгоритм поиска MST		\| Линейный алгоритм поиска MST
	\|		\|
	\|		\|
			\|-
	\| 2.03.2023 (чт)		\| 2.03.2023 (чт)
	\| Бонусный контест		\| Бонусный контест
			\|
	\|		\|
	\|		\|
Строка 374:		Строка 370:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[12]~~ Алгоритм Тарьяна для поиска КСС. Неудачное доказательство log* n для СНМ.		\| Алгоритм Тарьяна для поиска КСС. Неудачное доказательство log* n для СНМ.
	\|		\|
	\|		\|
Строка 385:		Строка 381:
	\|-		\|-
	\| Лекция		\| Лекция
	\| ~~[13]~~ Доказательство log* n для СНМ. Введение в потоки.		\| Доказательство log* n для СНМ. Введение в потоки.
	\|		\|
	\|		\|

Ifsmirnov: Материалы 3-го модуля

2023-03-11T19:07:03Z

Материалы 3-го модуля

Внесённые изменения

Grphil в 15:14, 4 декабря 2022

2022-12-04T15:14:00Z

← Предыдущая версия		Версия от 15:14, 4 декабря 2022
Строка 133:		Строка 133:
	== Длинные контесты ==		== Длинные контесты ==

	Все длинные контесты доступны [https://~~hsealgo2223~~.~~contest~~.~~codeforces.com~~/~~enter~~ по ссылке].		Все длинные контесты доступны [https://hse.grphil.ru/ по ссылке].

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