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

Ryabchikov.andrey: /* План курса */

2022-12-04T14:47:06Z

План курса

← Предыдущая версия		Версия от 14:47, 4 декабря 2022
Строка 160:		Строка 160:

	\|21\|\| Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.		\|21\|\| Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.
			\|}

			{\| class="wikitable"
			\|-
			! №
			! Часть 3. Вероятностные алгоритмы и Ко
			\|-

			\|1\|\| QSort, OrderStatistics: время работы в среднем и худшем случаях. Вероятностное определение цены игры на дереве. Алгоритм RandomGameTreeEval, его среднее время работы.

			\|-

			\|2\|\| Задача о минимальном разрезе, алгоритм Каргера.

			\|-

			\|3\|\| Задача о минимальном разрезе, алгоритм Каргера-Штайна.

			\|-

			\|4\|\| Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в среднем случае. Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в худшем случае.

			\|-

			\|5\|\| Задачи APD и APSP. APD для невзвешенных неориентированных графов, алгоритм APD-MM. Свидетели булевого перемножения матриц, алгоритм BPWM. Решение задачи APSP при помощи BPWM.
	\|}		\|}

Ryabchikov.andrey: /* План курса */

2022-12-04T14:46:04Z

План курса

← Предыдущая версия		Версия от 14:46, 4 декабря 2022
Строка 71:		Строка 71:

	\|13\|\| Суффиксный автомат. Линейный алгоритм построения.		\|13\|\| Суффиксный автомат. Линейный алгоритм построения.
			\|}

			{\| class="wikitable"
			\|-
			! №
			! Часть 2. Геометрия
			\|-

			\|1\|\| Прямые, отрезки, плоскости. Скалярное произведение, векторное произведение, их свойства. Угол между векторами, функция atan2. Коллинеарность прямых. Проверка принадлежности точки прямой, отрезку.

			\|-

			\|2\|\| Поиск пересечения прямых - два способа: система уравнений и векторное произведение. Поиск пересечения окружности и прямой: два способа. Проверка наличия пересечения отрезков без вычисления точки пересечения прямых.

			\|-

			\|3\|\| Поиск ориентированной площади многоугольника: метод “векторных произведений” и “метод трапеций”.. Знак площади и проверка того факта, что вершины многоугольника заданы в порядке обхода против часовой стрелки. Поиск площади пересечения многоугольника и круга как модификация метода “векторных произведений”.

			\|-

			\|4\|\| Проверка принадлежности точки многоугольнику. Проблема вершины на луче. Три способа решения проблемы: случайный луч, вычисление “хорошего” луча, решение с горизонтальным лучом. Проверка принадлежности точки выпуклому многоугольнику за O(log n). Поиск правой касательной из точки к выпуклому многоугольнику за O(log n).

			\|-

			\|5\|\| Выпуклая оболочка. Алгоритмы Джарвиса, Грэхема, Эндрю, Киркпатрика, Чена.

			\|-

			\|6\|\| Convex Hull Trick: версия с добавлением в структуру точек и поиском точки с минимальной проекцией на заданное направление.

			\|-

			\|7\|\| Convex Hull Trick: версия с добавлением в структуру прямых и поиском прямой с минимальным y при заданном х. Дерево Ли-Чао.

			\|-

			\|8\|\| Выпуклая оболочка 3D. Построение за O(n4), за O(n2).

			\|-

			\|9\|\| Тернарный поиск. Выпуклые функции и их свойства, необходимые для корректного применения тернарного поиска. Вложенный тернарный поиск. Примеры: задача о фотографии, задача о максимальной вложенной в выпуклый многоугольник окружности..

			\|-

			\|10\|\| Поиск пары ближайших точек на плоскости. Алгоритм Препараты. O(n log n). Поиск треугольника с минимальным периметром за O(n log n).

			\|-

			\|11\|\| Поиск диаметра множества на плоскости за O(n log n). Поиск накрывающего прямоугольника минимального периметра за O(n log n). Поиск накрывающего прямоугольника минимальной площади за O(n log n).

			\|-

			\|12\|\| Поиск граней связного плоского графа за O(n log n).

			\|-

			\|13\|\| Нахождение суммы Минковского двух выпуклых многоугольников за O(m + n).Проверка наличия пересечения двух выпуклых многоугольников и поиск расстояния между ними за O(m + n). Задача о роботе и препятствиях (“задача про коридор и столы”; требуемое время O(n2*B), где n - число препятствий; робот и препятствия - выпуклые многоугольники с не более чем В вершинами)

			\|-

			\|14\|\| Сканирующая прямая. Поиск наибольшего креста. Проверка факта пересечения отрезков. Площадь объединения прямоугольников за O(n log n).

			\|-

			\|15\|\| Пересечение полуплоскостей: O(n3), O(n2), O(n log n).

			\|-

			\|16\|\| Статическая задача поиска точек в подпрямоугольнике. Решения за (O(n^5), O(log n)), (O(n^3), O(log n)), (O(n^2), O(log n)). Fractional Cascading. Времена построения и вычисления ответа на запрос.

			\|-

			\|17\|\| KD-дерево. Времена построения и вычисления ответа на запрос. Поиск ближайших точек множества с помощью KD-дерева, “контрпример”.

			\|-

			\|18\|\| Диаграмма Вороного. Базовые свойства: структура ячеек, связность, оценки на количества ребер и вершин. Критерий совпадения точки с вершиной ДВ, попадания на внутреннюю часть ребра.

			\|-

			\|19\|\| Построение диаграммы Вороного: O(n3), O(n2 log n), O(n2). Алгоритм Форчуна за O(n log n).

			\|-

			\|20\|\| Триангуляция Делоне. Определение триангуляции. Теорема Фалеса. Флипы. Неправильное ребро, критерий неправильности.

			\|-

			\|21\|\| Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.
	\|}		\|}

Ryabchikov.andrey: /* План курса */

2022-12-04T14:44:09Z

План курса

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

Ryabchikov.andrey: Ryabchikov.andrey переименовал страницу Data Structures and Algorithms 2022 (advanced) в Алгоритмы и структуры данных (продвинутый поток)

2022-12-04T14:27:57Z

Ryabchikov.andrey переименовал страницу Data Structures and Algorithms 2022 (advanced) в Алгоритмы и структуры данных (продвинутый поток)

← Предыдущая версия		Версия от 14:27, 4 декабря 2022
(нет различий)

Ryabchikov.andrey: /* Важные ссылки */

2022-12-04T13:58:25Z

Важные ссылки

← Предыдущая версия		Версия от 13:58, 4 декабря 2022
Строка 4:		Строка 4:

	== Важные ссылки ==		== Важные ссылки ==
	* '''[Регистрация на курс]''' (доступ для физтех-аккаунтов)		* '''Регистрация на курс''' (доступ для физтех-аккаунтов)
	* '''[Материалы курсa]''' (доступ для физтех-аккаунтов)		* '''Материалы курсa''' (доступ для физтех-аккаунтов)
	* '''[Чат курса]'''		* '''Чат курса'''
	* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''		* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''

Ryabchikov.andrey: /* Важные ссылки */

2022-12-04T13:58:00Z

Важные ссылки

← Предыдущая версия		Версия от 13:58, 4 декабря 2022
Строка 4:		Строка 4:

	== Важные ссылки ==		== Важные ссылки ==
	* '''[#/ Регистрация на курс]''' (доступ для физтех-аккаунтов)		* '''[Регистрация на курс]''' (доступ для физтех-аккаунтов)
	* '''[# Материалы курсa]''' (доступ для физтех-аккаунтов)		* '''[Материалы курсa]''' (доступ для физтех-аккаунтов)
	* '''[#]'''		* '''[Чат курса]'''
	* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''		* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''

Ryabchikov.andrey: /* Важные ссылки */

2022-12-04T13:56:52Z

Важные ссылки

← Предыдущая версия		Версия от 13:56, 4 декабря 2022
Строка 4:		Строка 4:

	== Важные ссылки ==		== Важные ссылки ==
	* '''#/ Регистрация на курс]''' (доступ для физтех-аккаунтов)		* '''[#/ Регистрация на курс]''' (доступ для физтех-аккаунтов)
	* '''# Материалы курсa]''' (доступ для физтех-аккаунтов)		* '''[# Материалы курсa]''' (доступ для физтех-аккаунтов)
	* '''#'''		* '''[#]'''
	* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''		* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''

Ryabchikov.andrey: /* Общие сведения */

2022-12-04T13:56:21Z

Общие сведения

← Предыдущая версия		Версия от 13:56, 4 декабря 2022
Строка 1:		Строка 1:
	= Общие сведения =		= Общие сведения =
	* Семестр: 1 (~~первый~~ курс)		* Семестр: 3 (второй курс курс)
	* Форма контроля: дифференцированный зачет		* Форма контроля: дифференцированный зачет

Ryabchikov.andrey: /* План курса */

2022-12-04T13:55:50Z

План курса

← Предыдущая версия		Версия от 13:55, 4 декабря 2022
Строка 82:		Строка 82:
	\|-		\|-

	\|16\|\| Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — \|-		\|16\|\| Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — б/д.
			\|-

	~~б/д.~~

	\|-		\|-

Ryabchikov.andrey: /* План курса */

2022-12-04T13:54:55Z

План курса

← Предыдущая версия		Версия от 13:54, 4 декабря 2022
Строка 264:		Строка 264:
	\|-		\|-

	\|61\| Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.		\|61\|\| Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы.

	\|-		\|-