Участник:Shersh/Тикеты по конспектам year2013 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(7. Хеширование)
 
(не показано 87 промежуточных версий 3 участников)
Строка 1: Строка 1:
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
+
#перенаправление [[Участник:Shersh/Тикеты ко 2ому терму]]
 
 
== 1. Амортизационный анализ ==
 
# '''!!!''' [[Амортизационный анализ]]
 
## Можно добавить ещё по примеру на каждый метод.
 
# [[Саморасширяющийся массив]]
 
# [[Массив с увеличением/уменьшением размера]]
 
## Объединить с предыдущим, сделать всё красиво.
 
# '''!!!''' [[Список]]
 
## Можно добавить интересные задачи на списки, которые дают на собеседованиях. Для согласования связаться сначала с куратором.
 
# [[Стек]]
 
# [[Очередь]]
 
## Заменить ссылки в источника на интервики
 
# '''!!!''' [[Персистентный стек]]
 
# [[Персистентная очередь]]
 
# [[Персистентный дек]]
 
## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)
 
# [[Мажорирующий элемент]]
 
# '''!!!''' [[Счетчик Кнута]]
 
## Добавить картинки с более понятным пояснением
 
## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)
 
## Может быть можно обобщить как-то на случай <tex>d</tex>-ичной системы счисления? (используется в толстых кучах)
 
## Будет полезно добавить источники, если про это где-то можно почитать
 
 
 
== 2. Приоритетные очереди ==
 
 
 
# [[Двоичная куча]]
 
## Ссылки на википедию сделать через интервики
 
# [[Биномиальная куча]]
 
## интервики
 
# [[Фибоначчиева куча]]
 
## Ссылки заменить на интервики
 
# [[Левосторонняя куча]]
 
# [[Тонкая куча]]
 
# [[Толстая куча на избыточном счетчике]]
 
## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
 
# [[Куча Бродала-Окасаки]]
 
 
 
== 3. Система непересекающихся множеств ==
 
# [[СНМ (наивные реализации) | Наивные реализации]]
 
# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 
# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 
## Интервики
 
 
 
== 4. Поисковые структуры данных ==
 
 
 
# [[Упорядоченное множество]]
 
# [[Дерево поиска, наивная реализация]]
 
# [[АВЛ-дерево]]
 
# [[2-3 дерево]]
 
# [[B-дерево]]
 
# [[Красно-черное дерево]]
 
# [[Декартово дерево]]
 
# [[Декартово дерево по неявному ключу]]
 
# [[Splay-дерево]]
 
# [[Рандомизированное бинарное дерево поиска]]
 
# [[Дерево ван Эмде Боаса]]
 
# [[Список с пропусками]]
 
# [[Fusion tree]]
 
# [[Сверхбыстрый цифровой бор]]
 
* В каждом конспекте сделать ссылки на википедию через интервики
 
 
 
== 5. Дерево отрезков ==
 
 
 
# [[Статистики на отрезках. Корневая эвристика]]
 
# [[Дерево отрезков. Построение]]
 
# [[Реализация запроса в дереве отрезков сверху]]
 
# [[Реализация запроса в дереве отрезков снизу]]
 
# [[Несогласованные поддеревья. Реализация массового обновления]]
 
# [[Многомерное дерево отрезков]]
 
# [[Сжатое многомерное дерево отрезков]]
 
 
 
== 6. Дерево Фенвика ==
 
# [[Дерево Фенвика]]
 
# [[Встречное дерево Фенвика]]
 
# [[Дерево Фенвика для некоммутативных операций]]
 
# [[Многомерное дерево Фенвика]]
 
 
 
== 7. Хеширование ==
 
# [[Хеш-таблица]]
 
# '''!!!''' [[Разрешение коллизий]]
 
## Добавить примеры каких-нибудь интересных и популярных хешей, поизучать их свойства
 
# [[Хеширование кукушки]]
 
# [[Идеальное хеширование]]
 
# [[Перехеширование. Амортизационный анализ]]
 
# [[Фильтр Блума]]
 
# [[Универсальное семейство хеш-функций]]
 
 
 
== 8. [[Сортировка]] ==
 
# [[Сортировка выбором]]
 
# [[Сортировка пузырьком]]
 
# [[Сортировка вставками]]
 
# [[Сортировка Шелла]]
 
# [[Сортировка кучей]]
 
# [[Быстрая сортировка]]
 
# [[Сортировка слиянием]]
 
# [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 
# [[Теорема о нижней оценке для сортировки сравнениями]]
 
# [[Сортировка подсчетом]]
 
# [[Сортировка подсчетом сложных объектов]]
 
# [[Цифровая сортировка]]
 
# [[Карманная сортировка]]
 
# [[Поиск k-ой порядковой статистики]]
 
# [[Поиск k-ой порядковой статистики за линейное время]]
 
# [[Сортировка Хана]]
 
# [[Timsort]]
 
 
 
== 9. Сортирующие сети ==
 
# [[Сортирующие сети]]
 
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
# [[Сортировочные сети с особыми свойствами]]
 
# [[Сортирующие сети для квадратичных сортировок]]
 
# [[Сеть Бетчера]]
 
 
 
== 10. Алгоритмы поиска ==
 
# [[Целочисленный двоичный поиск]]
 
# [[Вещественный двоичный поиск]]
 
# [[Троичный поиск]]
 
# [[Поиск с помощью золотого сечения]]
 
# [[Интерполяционный поиск]]
 

Текущая версия на 17:28, 31 августа 2014