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

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

2022-12-04T14:47:06Z

‎План курса

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

2022-12-04T14:46:04Z

‎План курса

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) в Алгоритмы и структуры данных (продвинутый поток)

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

2022-12-04T13:58:25Z

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

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

2022-12-04T13:58:00Z

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

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

2022-12-04T13:56:52Z

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

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

2022-12-04T13:56:21Z

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

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

2022-12-04T13:55:50Z

‎План курса

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

2022-12-04T13:54:55Z

‎План курса

← Предыдущая		Версия 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.
	\|}		\|}

← Предыдущая		Версия 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\|\| Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.
	\|}		\|}

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

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

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

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

@@ Строка 1: / Строка 1: @@
 = Общие сведения =
-* Семестр: 1 (первый курс)
+* Семестр: 3 (второй курс курс)
 * Форма контроля: дифференцированный зачет

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

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