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

Debnatkh в 18:09, 28 октября 2020

2020-10-28T18:09:11Z

← Предыдущая версия		Версия от 18:09, 28 октября 2020
Строка 64:		Строка 64:
	<li> В течение каждого модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.		<li> В течение каждого модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.

	<li> За [[~~Алгоритмы_и_структуры_данных_пилотный_поток_2020~~/~~2021~~#Экзамены \| экзамен]]		<li> За [[Алгоритмы_и_структуры_данных_пилотный_поток_2019/2020#Экзамены \| экзамен]]
	студент получает оценку от 0 до 10, эта оценка будет являться О<sub>экз</sub>.		студент получает оценку от 0 до 10, эта оценка будет являться О<sub>экз</sub>.

Debnatkh в 18:08, 28 октября 2020

2020-10-28T18:08:21Z

← Предыдущая версия		Версия от 18:08, 28 октября 2020
Строка 64:		Строка 64:
	<li> В течение каждого модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.		<li> В течение каждого модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться О<sub>КР</sub>. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.

	<li> За [[~~Алгоритмы_и_структуры_данных_пилотный_поток_2019~~/~~2020~~#Экзамены \| экзамен]]		<li> За [[Алгоритмы_и_структуры_данных_пилотный_поток_2020/2021#Экзамены \| экзамен]]
	студент получает оценку от 0 до 10, эта оценка будет являться О<sub>экз</sub>.		студент получает оценку от 0 до 10, эта оценка будет являться О<sub>экз</sub>.

Debnatkh в 19:51, 20 октября 2020

2020-10-20T19:51:05Z

← Предыдущая версия		Версия от 19:51, 20 октября 2020
Строка 816:		Строка 816:
	## [https://e-maxx.ru/algo/ https://e-maxx.ru/algo/], раздел "Алгебра"		## [https://e-maxx.ru/algo/ https://e-maxx.ru/algo/], раздел "Алгебра"
	</div>		</div>




	==== 5 модуль ====		==== 5 модуль ====

Debnatkh в 14:19, 20 октября 2020

2020-10-20T14:19:50Z

Debnatkh в 14:19, 20 октября 2020

2020-10-20T14:19:01Z

@@ Строка 815: / Строка 815: @@
 ## Кормен, гл. 31, c. 968
 ## [https://e-maxx.ru/algo/ https://e-maxx.ru/algo/], раздел "Алгебра"
 </div>

Debnatkh в 16:17, 18 октября 2020

2020-10-18T16:17:55Z

← Предыдущая версия		Версия от 16:17, 18 октября 2020
Строка 603:		Строка 603:
	== Экзамены ==		== Экзамены ==

	=== Правила экзамена (2~~, 5 модули)~~ ===		=== Правила экзамена 2 модуль ===
	# Состоит из письменного теста и устной части.		# Состоит из письменного теста и устной части.
	# За тест ставится оценка от 1 до 8.		# За тест ставится оценка от 1 до 8.
Строка 613:		Строка 613:
	# Если попытки кончились, то экзамен для студента завершается.		# Если попытки кончились, то экзамен для студента завершается.

	=== Правила экзамена (3, 4 модули) ===		=== Правила экзамена (3, 4, 5 модули) ===
	[https://drive.google.com/file/d/1lwceIplTRQEQ0vvqjrjKgbrfmS027-TE/view?usp=sharing Правила экзамена]		[https://drive.google.com/file/d/1lwceIplTRQEQ0vvqjrjKgbrfmS027-TE/view?usp=sharing Правила экзамена]

Строка 634:		Строка 634:

	\|-		\|-
	\| rowspan="2" \| 3-4 модуль		\| rowspan="1" \| 3-4 модуль
	\| rowspan="2" \| 23 июня		\| rowspan="1" \| 23 июня
	\| Устная часть (дистанционно)		\| Устная часть (дистанционно)
	\| Не выходя из дома		\| Не выходя из дома
	\| rowspan="2" \| [https://drive.google.com/file/d/1XuVR9TUbJqF6AONzqIAtowMhHm-9j2r7/view?usp=sharing туц]		\| rowspan="1" \| [https://drive.google.com/file/d/1XuVR9TUbJqF6AONzqIAtowMhHm-9j2r7/view?usp=sharing туц]
			\|-
			\| rowspan="1" \| 5 модуль
			\| rowspan="1" \| 24 октября
			\| Устная часть (дистанционно)
			\| Не выходя из дома
			\| rowspan="1" \| TBD
	\|-		\|-
	\|}		\|}

Debnatkh в 16:15, 18 октября 2020

2020-10-18T16:15:15Z

← Предыдущая версия		Версия от 16:15, 18 октября 2020
Строка 548:		Строка 548:
	\| colspan="4" style="text-align: center; background-color:#dae8fc;" \| 5 модуль		\| colspan="4" style="text-align: center; background-color:#dae8fc;" \| 5 модуль
	\|-		\|-
	\| style="text-align:center;"\| 10 \|\| 25 сентября 2020 \|\| [https://official.contest.yandex.ru/contest/20084/enter/ 20084] \|\| полночь с 18 на 19 октября		\| style="text-align:center;"\| 10 \|\| 25 сентября 2020 \|\| [https://official.contest.yandex.ru/contest/20084/enter/ 20084] \|\| полночь с 21 на 22 октября
	\|-		\|-
	\|}		\|}

Debnatkh в 16:13, 18 октября 2020

2020-10-18T16:13:10Z

← Предыдущая версия		Версия от 16:13, 18 октября 2020
Строка 594:		Строка 594:
	\| Фурье, численные методы, вычислительная геометрия		\| Фурье, численные методы, вычислительная геометрия
	\| [https://official.contest.yandex.ru/contest/19905/ 19905]		\| [https://official.contest.yandex.ru/contest/19905/ 19905]
			\|-
			\| Полночь с 21 на 22 октября
			\| Приближённые и вероятностные алгоритмы, линейные задачи
			\| [https://official.contest.yandex.ru/contest/20843/ 20843]
	\|-		\|-
	\|}		\|}

Debnatkh в 16:11, 18 октября 2020

2020-10-18T16:11:47Z

← Предыдущая версия		Версия от 16:11, 18 октября 2020
Строка 513:		Строка 513:
	\|-		\|-
	\|}		\|}


	~~https://official.contest.yandex.ru/contest/20843/enter/~~

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

Debnatkh в 16:11, 18 октября 2020

2020-10-18T16:11:17Z

← Предыдущая версия		Версия от 16:11, 18 октября 2020
Строка 460:		Строка 460:
	\| style="text-align:center;"\| 4 \|\| Полночь с 12 на 13 февраля		\| style="text-align:center;"\| 4 \|\| Полночь с 12 на 13 февраля
	\| Структуры данных		\| Структуры данных
	\| [https://drive.google.com/file/d/~~18GseWMlkVcK1kq_9CafuQ5hnPtd5vjw~~-/view?usp=sharing бац]		\| [https://drive.google.com/file/d/18GseWMhttps://drive.google.com/file/d/1qHO9V3GIbC4B_q-rPisqakpCbCpbsykG/view?usp=sharinglkVcK1kq_9CafuQ5hnPtd5vjw-/view?usp=sharing бац]
	\|		\|
	\|-		\|-
Строка 497:		Строка 497:
	\| colspan="5" style="text-align: center; background-color:#dae8fc;" \| 5 модуль		\| colspan="5" style="text-align: center; background-color:#dae8fc;" \| 5 модуль
	\|-		\|-
	\| style="text-align:center;"\| 10 \|\| Полночь с 17 на 18 сентября		\| style="text-align:center;"\| 11 \|\| Полночь с 17 на 18 сентября
	\| Численные методы оптимизации и БПФ		\| Численные методы оптимизации и БПФ
	\| [https://drive.google.com/file/d/18SXjkjpu6PeSE-9i2KO97lfvAuoJbhtp/view?usp=sharing бар]		\| [https://drive.google.com/file/d/18SXjkjpu6PeSE-9i2KO97lfvAuoJbhtp/view?usp=sharing бар]
	\| <ul><li>В четвёртой задаче все точки различны. Добавлять нужно точки только с целочисленными координатами<li>Во второй задаче расстояние евклидово<li>В третьей можно менять на любые вещественные числа<li>В девятой задаче нужно найти целую часть<li>Суперсходимость и сходимость могут быть только на каком-то интервале. В этом случае надо указать, как мы в этот интервал попадём</ul>		\| <ul><li>В четвёртой задаче все точки различны. Добавлять нужно точки только с целочисленными координатами<li>Во второй задаче расстояние евклидово<li>В третьей можно менять на любые вещественные числа<li>В девятой задаче нужно найти целую часть<li>Суперсходимость и сходимость могут быть только на каком-то интервале. В этом случае надо указать, как мы в этот интервал попадём</ul>
	\|-		\|-
	\| style="text-align:center;"\| 10 \|\| Полночь с 5 на 6 октября		\| style="text-align:center;"\| 12 \|\| Полночь с 5 на 6 октября
	\| Методы оптимизации и вычислительная геометрия		\| Методы оптимизации и вычислительная геометрия
	\| [https://drive.google.com/file/d/1vnDIalRIaS0Nk2tcVQKf1wLrwmPnoIhg/view?usp=sharing ~~бар~~]		\| [https://drive.google.com/file/d/1vnDIalRIaS0Nk2tcVQKf1wLrwmPnoIhg/view?usp=sharing тык]
	\| <ul><li>В 10 задаче под словами дан многогранник имеются в виду вершины и грани</ul>		\| <ul><li>В 10 задаче под словами дан многогранник имеются в виду вершины и грани</ul>
			\|-
			\| style="text-align:center;"\| 13 \|\| Полночь с 20 на 21 октября
			\| Линейное программирование и приближённые задачи
			\| [https://drive.google.com/file/d/1qHO9V3GIbC4B_q-rPisqakpCbCpbsykG/view?usp=sharing :-(]
			\| <ul><li>В 4 задаче положительные рёбра</ul>
	\|-		\|-
	\|}		\|}


			https://official.contest.yandex.ru/contest/20843/enter/

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

← Предыдущая версия		Версия от 14:19, 20 октября 2020
Строка 824:		Строка 824:
	<div class="toccolours mw-collapsible" style=" overflow:auto;">		<div class="toccolours mw-collapsible" style=" overflow:auto;">
	# Алгоритм Карацубы: [https://ru.wikipedia.org/wiki/Алгоритм_Карацубы https://ru.wikipedia.org/wiki/Алгоритм_Карацубы]		# Алгоритм Карацубы: [https://ru.wikipedia.org/wiki/Алгоритм_Карацубы https://ru.wikipedia.org/wiki/Алгоритм_Карацубы]

	# Основная теорема о рекуррентных соотношениях (Master Theorem), метод Штрассена:		# Основная теорема о рекуррентных соотношениях (Master Theorem), метод Штрассена:
	## Кормен, гл. 4, стр 90		## Кормен, гл. 4, стр 90
	## [https://ru.wikipedia.org/wiki/Основная_теорема_о_рекуррентных_соотношениях https://ru.wikipedia.org/wiki/Основная_теорема_о_рекуррентных_соотношениях]		## [https://ru.wikipedia.org/wiki/Основная_теорема_о_рекуррентных_соотношениях https://ru.wikipedia.org/wiki/Основная_теорема_о_рекуррентных_соотношениях]

	# Быстрое преобразование Фурье:		# Быстрое преобразование Фурье:
	## Кормен, гл. 30, стр. 940		## Кормен, гл. 30, стр. 940
	## [https://e-maxx.ru/algo/fft_multiply https://e-maxx.ru/algo/fft_multiply]		## [https://e-maxx.ru/algo/fft_multiply https://e-maxx.ru/algo/fft_multiply]
	## Ньютоновские схемы для быстрого деления и извлечения корня: [https://arxiv.org/pdf/1004.3412.pdf https://arxiv.org/pdf/1004.3412.pdf]		## Ньютоновские схемы для быстрого деления и извлечения корня: [https://arxiv.org/pdf/1004.3412.pdf https://arxiv.org/pdf/1004.3412.pdf]

	# Про IEEE 754: [https://neerc.ifmo.ru/wiki/index.php?title=Представление_вещественных_чисел https://neerc.ifmo.ru/wiki/index.php?title=Представление_вещественных_чисел]		# Про IEEE 754: [https://neerc.ifmo.ru/wiki/index.php?title=Представление_вещественных_чисел https://neerc.ifmo.ru/wiki/index.php?title=Представление_вещественных_чисел]

	# Приближённые алгоритмы:		# Приближённые алгоритмы:
	## Кормен, гл. 35, стр. 1157		## Кормен, гл. 35, стр. 1157
Строка 842:		Строка 838:
	## MAXSAT: [https://en.wikipedia.org/wiki/Maximum_satisfiability_problem https://en.wikipedia.org/wiki/Maximum_satisfiability_problem], предпоследний раздел [https://www.mccme.ru/ium/postscript/s12/gasnikov-12.pdf https://www.mccme.ru/ium/postscript/s12/gasnikov-12.pdf]		## MAXSAT: [https://en.wikipedia.org/wiki/Maximum_satisfiability_problem https://en.wikipedia.org/wiki/Maximum_satisfiability_problem], предпоследний раздел [https://www.mccme.ru/ium/postscript/s12/gasnikov-12.pdf https://www.mccme.ru/ium/postscript/s12/gasnikov-12.pdf]
	## MAXCUT: начало [http://web.cs.iastate.edu/~pavan/633/lec14.pdf http://web.cs.iastate.edu/~pavan/633/lec14.pdf]		## MAXCUT: начало [http://web.cs.iastate.edu/~pavan/633/lec14.pdf http://web.cs.iastate.edu/~pavan/633/lec14.pdf]

	# Генетические алгоритмы: [https://ru.wikipedia.org/wiki/Генетический_алгоритм https://ru.wikipedia.org/wiki/Генетический_алгоритм]		# Генетические алгоритмы: [https://ru.wikipedia.org/wiki/Генетический_алгоритм https://ru.wikipedia.org/wiki/Генетический_алгоритм]

	# Алгоритм Каргера-Штайна: [https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Каргера_для_нахождения_минимального_разреза https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Каргера_для_нахождения_минимального_разреза]		# Алгоритм Каргера-Штайна: [https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Каргера_для_нахождения_минимального_разреза https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Каргера_для_нахождения_минимального_разреза]

	# Быстрая геометрия:		# Быстрая геометрия:
	## работа с примитивами, выпуклая оболочка, проверка принадлежности точек выпуклому многоугольнику, построение касательных к выпуклому многоугольнику, поиск двух ближайших точеки, поиск любых двух пересекающихся отрезков, алгоритмы пересечения полуплоскостей: см. задачи с семинаров + в разделе "Геометрия" [https://e-maxx.ru/algo/ https://e-maxx.ru/algo/]		## работа с примитивами, выпуклая оболочка, проверка принадлежности точек выпуклому многоугольнику, построение касательных к выпуклому многоугольнику, поиск двух ближайших точеки, поиск любых двух пересекающихся отрезков, алгоритмы пересечения полуплоскостей: см. задачи с семинаров + в разделе "Геометрия" [https://e-maxx.ru/algo/ https://e-maxx.ru/algo/]
Строка 852:		Строка 845:
	## минимальная накрывающая окружность: [https://ru.wikipedia.org/wiki/Задача_о_наименьшей_окружности https://ru.wikipedia.org/wiki/Задача_о_наименьшей_окружности], [https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек]		## минимальная накрывающая окружность: [https://ru.wikipedia.org/wiki/Задача_о_наименьшей_окружности https://ru.wikipedia.org/wiki/Задача_о_наименьшей_окружности], [https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек]
	## триангуляция методом отрезания ушей [https://neerc.ifmo.ru/wiki/index.php?title=Триангуляция_полигонов_(ушная_%2B_монотонная) https://neerc.ifmo.ru/wiki/index.php?title=Триангуляция_полигонов_(ушная_%2B_монотонная)]		## триангуляция методом отрезания ушей [https://neerc.ifmo.ru/wiki/index.php?title=Триангуляция_полигонов_(ушная_%2B_монотонная) https://neerc.ifmo.ru/wiki/index.php?title=Триангуляция_полигонов_(ушная_%2B_монотонная)]

	# Задача Point location:		# Задача Point location:
	## соответствующий раздел [http://www.csun.edu/~ctoth/Handbook/chap38.pdf http://www.csun.edu/~ctoth/Handbook/chap38.pdf]		## соответствующий раздел [http://www.csun.edu/~ctoth/Handbook/chap38.pdf http://www.csun.edu/~ctoth/Handbook/chap38.pdf]
Строка 858:		Строка 850:
	## глава 2 в [http://inis.jinr.ru/sl/vol1/CMC/Preparata http://inis.jinr.ru/sl/vol1/CMC/Preparata],Sheimos,Vychislitelnaya%20geometriya,%201989.pdf		## глава 2 в [http://inis.jinr.ru/sl/vol1/CMC/Preparata http://inis.jinr.ru/sl/vol1/CMC/Preparata],Sheimos,Vychislitelnaya%20geometriya,%201989.pdf
	## глава 6 книги "Computational Geometry - Algorithms and Applications", 3rd Ed. de Berg et all.		## глава 6 книги "Computational Geometry - Algorithms and Applications", 3rd Ed. de Berg et all.

	# k-d деревья: [https://neerc.ifmo.ru/wiki/index.php?title=К-d_деревья_и_перечисление_точек_в_произвольном_прямоугольнике_(статика) https://neerc.ifmo.ru/wiki/index.php?title=К-d_деревья_и_перечисление_точек_в_произвольном_прямоугольнике_(статика)]		# k-d деревья: [https://neerc.ifmo.ru/wiki/index.php?title=К-d_деревья_и_перечисление_точек_в_произвольном_прямоугольнике_(статика) https://neerc.ifmo.ru/wiki/index.php?title=К-d_деревья_и_перечисление_точек_в_произвольном_прямоугольнике_(статика)]

	# Выпуклая оболочка:		# Выпуклая оболочка:
	## глава 3 [http://inis.jinr.ru/sl/vol1/CMC/Preparata http://inis.jinr.ru/sl/vol1/CMC/Preparata],Sheimos,Vychislitelnaya%20geometriya,%201989.pdf		## глава 3 [http://inis.jinr.ru/sl/vol1/CMC/Preparata http://inis.jinr.ru/sl/vol1/CMC/Preparata],Sheimos,Vychislitelnaya%20geometriya,%201989.pdf
	## глава 11 книги "Computational Geometry - Algorithms and Applications", 3rd Ed. de Berg et all.		## глава 11 книги "Computational Geometry - Algorithms and Applications", 3rd Ed. de Berg et all.

	# Численные методы интегрирования. Метод Монте-Карло:		# Численные методы интегрирования. Метод Монте-Карло:
	## Самарский, Гулин "Численные методы", глава 4 [http://samarskii.ru/books/book1989.pdf http://samarskii.ru/books/book1989.pdf]		## Самарский, Гулин "Численные методы", глава 4 [http://samarskii.ru/books/book1989.pdf http://samarskii.ru/books/book1989.pdf]
	## [https://ru.wikipedia.org/wiki/Численное_интегрирование https://ru.wikipedia.org/wiki/Численное_интегрирование] - обзорная статья		## [https://ru.wikipedia.org/wiki/Численное_интегрирование https://ru.wikipedia.org/wiki/Численное_интегрирование] - обзорная статья
	## [https://ru.wikipedia.org/wiki/Метод_Монте-Карло https://ru.wikipedia.org/wiki/Метод_Монте-Карло]		## [https://ru.wikipedia.org/wiki/Метод_Монте-Карло https://ru.wikipedia.org/wiki/Метод_Монте-Карло]

	# Численные методы оптимизации. Троичный поиск, градиентный и покоординатный спуск, метод Ньютона:		# Численные методы оптимизации. Троичный поиск, градиентный и покоординатный спуск, метод Ньютона:
	## [https://e-maxx.ru/algo/ternary_search https://e-maxx.ru/algo/ternary_search]		## [https://e-maxx.ru/algo/ternary_search https://e-maxx.ru/algo/ternary_search]
Строка 876:		Строка 864:
	## градиентный спуск: [http://www.machinelearning.ru/wiki/index.php?title=Метод_градиентного_спуска http://www.machinelearning.ru/wiki/index.php?title=Метод_градиентного_спуска]		## градиентный спуск: [http://www.machinelearning.ru/wiki/index.php?title=Метод_градиентного_спуска http://www.machinelearning.ru/wiki/index.php?title=Метод_градиентного_спуска]
	## Самарский, Гулин "Численные методы", глава 5 [http://samarskii.ru/books/book1989.pdf http://samarskii.ru/books/book1989.pdf]		## Самарский, Гулин "Численные методы", глава 5 [http://samarskii.ru/books/book1989.pdf http://samarskii.ru/books/book1989.pdf]

	# Стриминговые алгоритмы:		# Стриминговые алгоритмы:
	## записки [https://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf https://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf]		## записки [https://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf https://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf]
	## материалы к [http://people.cs.georgetown.edu/jthaler/COSC548.html http://people.cs.georgetown.edu/jthaler/COSC548.html]		## материалы к [http://people.cs.georgetown.edu/jthaler/COSC548.html http://people.cs.georgetown.edu/jthaler/COSC548.html]
	## материалы к [https://people.cs.umass.edu/~mcgregor/courses/CS711S12/index.html https://people.cs.umass.edu/~mcgregor/courses/CS711S12/index.html]		## материалы к [https://people.cs.umass.edu/~mcgregor/courses/CS711S12/index.html https://people.cs.umass.edu/~mcgregor/courses/CS711S12/index.html]

	# Задача линейного программирования, симплекс-метод, двойственность:		# Задача линейного программирования, симплекс-метод, двойственность:
	## Кормен, гл. 29, стр. 883		## Кормен, гл. 29, стр. 883
	## трюк с булевыми функциями [http://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html http://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html]		## трюк с булевыми функциями [http://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html http://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html]


	</div>		</div>