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