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

Debnatkh: /* Семинары */

2019-11-01T13:04:12Z

Семинары

@@ Строка 139: / Строка 139: @@
 ! Дата семинара !! Темы !! Листок
 |-
-| 29 октября || Понятие асимптотического времени работы алгоритма <br /> Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω || [https://drive.google.com/file/d/13YjOHteA-XsX2l7IWvnFj7rQDGKxtaTq/view?usp=sharing тык]
+| 30 октября || Понятие асимптотического времени работы алгоритма <br /> Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω || [https://drive.google.com/file/d/1t8mHek9NBzRNtAWHib02C0mcY_x_nAzc/view?usp=sharing тык]
 |-
-| 31 октября || Совместное решение задач по теории вероятностей || [https://drive.google.com/file/d/13YjOHteA-XsX2l7IWvnFj7rQDGKxtaTq/view?usp=sharing тыц]
+| 31 октября || Совместное решение задач по теории вероятностей || [https://drive.google.com/file/d/1nxeLwcV11h7VqmSgYGKpIYlXJHpxSfst/view?usp=sharing тыц]
 |-
 |}

Debnatkh в 13:03, 1 ноября 2019

2019-11-01T13:03:11Z

@@ Строка 139: / Строка 139: @@
 ! Дата семинара !! Темы !! Листок
 |-
-| 30 октября || Понятие асимптотического времени работы алгоритма <br /> Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω || [https://drive.google.com/file/d/1t8mHek9NBzRNtAWHib02C0mcY_x_nAzc/view?usp=sharing тык]
+| 29 октября || Понятие асимптотического времени работы алгоритма <br /> Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω || [https://drive.google.com/file/d/13YjOHteA-XsX2l7IWvnFj7rQDGKxtaTq/view?usp=sharing тык]
 |-
-| 31 октября || Совместное решение задач по теории вероятностей || [https://drive.google.com/file/d/1nxeLwcV11h7VqmSgYGKpIYlXJHpxSfst/view?usp=sharing тыц]
+| 31 октября || Совместное решение задач по теории вероятностей || [https://drive.google.com/file/d/13YjOHteA-XsX2l7IWvnFj7rQDGKxtaTq/view?usp=sharing тыц]
 |-
 |}

Wrg0ababd в 19:13, 15 октября 2019

2019-10-15T19:13:28Z

← Предыдущая версия		Версия от 19:13, 15 октября 2019
Строка 278:		Строка 278:
	\| полночь с 17 на 18 октября \|\| Относительно простые задачи \|\| [https://drive.google.com/open?id=1Meoke0ynj3xThnR51OQRaGjC9wrYPd_V туц]		\| полночь с 17 на 18 октября \|\| Относительно простые задачи \|\| [https://drive.google.com/open?id=1Meoke0ynj3xThnR51OQRaGjC9wrYPd_V туц]
	\|}		\|}

			Правки по последнему листку:

			2) Кратные ребра запрещены.

			9б) В рамках этой задачи можете считать комбинаторным алгоримом всё, что не обращается к задачам линейного программирования. Если жадный алгоритм не использует метод Гаусса или сведение к задаче линейного программирования, то он комбинаторный.

	== Короткие контесты ==		== Короткие контесты ==

Wrg0ababd в 15:59, 15 октября 2019

2019-10-15T15:59:51Z

← Предыдущая версия		Версия от 15:59, 15 октября 2019
Строка 123:		Строка 123:
	\|-		\|-
	\| 24 сентября \|\| Классы BPP, ZPP, RP. Введение в приближённые и вероятностные алгоритмы: 0.5-приближение для MAXCUT, MAXSAT; 2-приближения для минимального вершинного покрытия, 2-приближение для коммивояжёра, 1.5-приближение для коммивояжёра		\| 24 сентября \|\| Классы BPP, ZPP, RP. Введение в приближённые и вероятностные алгоритмы: 0.5-приближение для MAXCUT, MAXSAT; 2-приближения для минимального вершинного покрытия, 2-приближение для коммивояжёра, 1.5-приближение для коммивояжёра
			\|-
			\| 1 октября \|\| ln(n)-приближение задачи SETCOVER, поиск глобального минимального разреза алгоритмом Каргера и алгоритмом Каргера-Штайна
			\|-
			\| 4 октября \|\| Формулировка задачи ЛП и приближения с помощью ЛП. Приближение k-SETCOVER и (e - 1)/e приближение MAXSAT.
			\|-
			\| 8 октября \|\| Приближения с ЛП, доказательство 3/4-приближение MAXSAT, стриминг, задача о тяжёлых элементах и k-min.
			\|-
			\| 15 октября \|\| Hyper-Log, Hyper-LogLog, count-min sketch и count-sketch.
	\|}		\|}

Строка 224:		Строка 232:
	\|-		\|-
	\| 24 сентября \|\| Упражняемся в доказательстве NP-полноты \|\| [https://drive.google.com/open?id=1MoNJf9wVypUrAW0i1zkHXzHxS2X8dzM3 тык]		\| 24 сентября \|\| Упражняемся в доказательстве NP-полноты \|\| [https://drive.google.com/open?id=1MoNJf9wVypUrAW0i1zkHXzHxS2X8dzM3 тык]
			\|-
			\| 1 октября \|\| Приближенные алгоритмы \|\| [https://drive.google.com/open?id=1m-NWfX38y29gSLs7GuH3RpVmLziYsuT8 тыц]
			\|-
			\| 4 октября \|\| Разные задачи \|\| [https://drive.google.com/open?id=1e_50T84PF4B8R-NtPz7MPy-4HH9xmuog туц]
			\|-
			\| 8 октября \|\| Разбор первого (в этом году) листка \|\| не было
			\|-
			\| 15 октября \|\| Напутствия по дизайну и архитектуре \|\| не было
	\|}		\|}

Строка 259:		Строка 275:
	\|-		\|-
	\| полночь с 7 на 8 октября \|\| Разное \|\| [https://drive.google.com/open?id=1xvs3G_11-c4hOCmFLsgGklciXsbkxHfA тыц]		\| полночь с 7 на 8 октября \|\| Разное \|\| [https://drive.google.com/open?id=1xvs3G_11-c4hOCmFLsgGklciXsbkxHfA тыц]
			\|-
			\| полночь с 17 на 18 октября \|\| Относительно простые задачи \|\| [https://drive.google.com/open?id=1Meoke0ynj3xThnR51OQRaGjC9wrYPd_V туц]
	\|}		\|}

Строка 292:		Строка 310:
	\|-		\|-
	\| 13 сентября \|\| [https://official.contest.yandex.ru/contest/13891 тыц] \|\| Можно		\| 13 сентября \|\| [https://official.contest.yandex.ru/contest/13891 тыц] \|\| Можно
			\|-
			\| 11 октября \|\| [https://oﬃcial.contest.yandex.ru/contest/14618/enter/ тык] \|\| Нельзя (бонусный)
	\|}		\|}

Строка 313:		Строка 333:
	\|-		\|-
	\| Полночь с 4 на 5 октября \|\| Неточная задача \|\| [https://official.contest.yandex.ru/contest/14108 туц]		\| Полночь с 4 на 5 октября \|\| Неточная задача \|\| [https://official.contest.yandex.ru/contest/14108 туц]
			\|-
			\| Полночь с 18 на 19 октября \|\| Классы сложности, автоматы, приближённые алгоритмы, линейное программирование \|\| [https://official.contest.yandex.ru/contest/14415/enter/ тык]
	\|}		\|}

Wrg0ababd в 19:28, 24 сентября 2019

2019-09-24T19:28:27Z

← Предыдущая версия		Версия от 19:28, 24 сентября 2019
Строка 257:		Строка 257:
	\|-		\|-
	\| полночь с 25 на 26 июня \|\| Строки \|\| [https://drive.google.com/open?id=116ttmU33W26vx1hpGwsJuOFS1x4_d67M тык]		\| полночь с 25 на 26 июня \|\| Строки \|\| [https://drive.google.com/open?id=116ttmU33W26vx1hpGwsJuOFS1x4_d67M тык]
			\|-
			\| полночь с 7 на 8 октября \|\| Разное \|\| [https://drive.google.com/open?id=1xvs3G_11-c4hOCmFLsgGklciXsbkxHfA тыц]
	\|}		\|}

Wrg0ababd в 16:40, 24 сентября 2019

2019-09-24T16:40:50Z

← Предыдущая версия		Версия от 16:40, 24 сентября 2019
Строка 121:		Строка 121:
	\|-		\|-
	\| 20 сентября \|\| Классы P, NP, NP-hard, NP-complete, теорема Кука-Левина		\| 20 сентября \|\| Классы P, NP, NP-hard, NP-complete, теорема Кука-Левина
			\|-
			\| 24 сентября \|\| Классы BPP, ZPP, RP. Введение в приближённые и вероятностные алгоритмы: 0.5-приближение для MAXCUT, MAXSAT; 2-приближения для минимального вершинного покрытия, 2-приближение для коммивояжёра, 1.5-приближение для коммивояжёра
	\|}		\|}

Строка 220:		Строка 222:
	\|-		\|-
	\| 20 сентября \|\| Машина Тьюринга, классы задач \|\| [https://drive.google.com/open?id=1Km2fYHj6l08oNAa5iOykjYIbPKvQR0aX тыц]		\| 20 сентября \|\| Машина Тьюринга, классы задач \|\| [https://drive.google.com/open?id=1Km2fYHj6l08oNAa5iOykjYIbPKvQR0aX тыц]
			\|-
			\| 24 сентября \|\| Упражняемся в доказательстве NP-полноты \|\| [https://drive.google.com/open?id=1MoNJf9wVypUrAW0i1zkHXzHxS2X8dzM3 тык]
	\|}		\|}

Wrg0ababd в 16:49, 20 сентября 2019

2019-09-20T16:49:19Z

← Предыдущая версия		Версия от 16:49, 20 сентября 2019
Строка 119:		Строка 119:
	\|-		\|-
	\| 17 сентября \|\| Алгоритм Хопкрофта минимизации ДКА		\| 17 сентября \|\| Алгоритм Хопкрофта минимизации ДКА
			\|-
			\| 20 сентября \|\| Классы P, NP, NP-hard, NP-complete, теорема Кука-Левина
	\|}		\|}

Строка 216:		Строка 218:
	\|-		\|-
	\| 17 сентября \|\| Еще автоматы \|\| [https://drive.google.com/open?id=113lU1vKlNPoTTMzpBbg3_7Maxv_fK0zw тык]		\| 17 сентября \|\| Еще автоматы \|\| [https://drive.google.com/open?id=113lU1vKlNPoTTMzpBbg3_7Maxv_fK0zw тык]
			\|-
			\| 20 сентября \|\| Машина Тьюринга, классы задач \|\| [https://drive.google.com/open?id=1Km2fYHj6l08oNAa5iOykjYIbPKvQR0aX тыц]
	\|}		\|}

Wrg0ababd в 21:18, 19 сентября 2019

2019-09-19T21:18:09Z

← Предыдущая версия		Версия от 21:18, 19 сентября 2019
Строка 301:		Строка 301:
	\|-		\|-
	\| Полнчь с 26 на 27 июня \|\| Геометрия, теория чисел, БПФ, строки \|\| [https://official.contest.yandex.ru/contest/12917/enter/ тыц]		\| Полнчь с 26 на 27 июня \|\| Геометрия, теория чисел, БПФ, строки \|\| [https://official.contest.yandex.ru/contest/12917/enter/ тыц]
			\|-
			\| Полночь с 4 на 5 октября \|\| Неточная задача \|\| [https://official.contest.yandex.ru/contest/14108 туц]
	\|}		\|}

Wrg0ababd в 19:22, 19 сентября 2019

2019-09-19T19:22:04Z

← Предыдущая версия		Версия от 19:22, 19 сентября 2019
Строка 117:		Строка 117:
	\|-		\|-
	\| 10 сентября \|\| Языки и автоматы		\| 10 сентября \|\| Языки и автоматы
			\|-
			\| 17 сентября \|\| Алгоритм Хопкрофта минимизации ДКА
	\|}		\|}

Строка 212:		Строка 214:
	\|-		\|-
	\| 10 сентября \|\| Языки и автоматы \|\| [https://drive.google.com/open?id=1QPw-mvDlH75j39eLOXyWtUvwNN4qWgH0 туц]		\| 10 сентября \|\| Языки и автоматы \|\| [https://drive.google.com/open?id=1QPw-mvDlH75j39eLOXyWtUvwNN4qWgH0 туц]
			\|-
			\| 17 сентября \|\| Еще автоматы \|\| [https://drive.google.com/open?id=113lU1vKlNPoTTMzpBbg3_7Maxv_fK0zw тык]
	\|}		\|}

Wrg0ababd в 14:51, 16 сентября 2019

2019-09-16T14:51:43Z

← Предыдущая версия		Версия от 14:51, 16 сентября 2019
Строка 276:		Строка 276:
	\|-		\|-
	\| 13 июня \|\| [https://official.contest.yandex.ru/contest/13013/enter/ тык] \|\| Нельзя (бонусный)		\| 13 июня \|\| [https://official.contest.yandex.ru/contest/13013/enter/ тык] \|\| Нельзя (бонусный)
			\|-
			\| 13 сентября \|\| [https://official.contest.yandex.ru/contest/13891 тыц] \|\| Можно
	\|}		\|}