Тестовая страница — различия между версиями
Rybak (обсуждение | вклад) |
Rybak (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | + | = Второй семестр = | |
| − | == | + | == Амортизационный анализ == |
| − | + | * [[Амортизационный анализ. Метод предоплаты]] | |
| − | + | * [[Саморасширяющийся массив]] | |
| − | + | * [[Массив с увеличением/уменьшением размера]] | |
| − | + | * [[Стек]] | |
| − | + | * [[Очередь]] | |
| + | * [[Список]] | ||
| − | === | + | == Приоритетные очереди == |
| − | + | * [[Двоичная куча|Двоичная куча]] | |
| − | + | * [[Биномиальная куча|Биномиальная пирамида]] | |
| − | + | * [[Фибоначчиевы кучи|Фибоначчиевы кучи]] | |
| − | |||
| − | |||
| − | |||
| − | == | + | == Система непересекающихся множеств == |
| − | + | * [[СНМ(наивные реализации) | Наивные реализации]] | |
| − | + | * [[СНМ(списки с весовой эвристикой) | Списки с весовой эвристикой]] | |
| + | * [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] | ||
| + | * [[Анализ реализации с ранговой эвристикой | Анализ реализации с ранговой эвристикой]] | ||
| − | === | + | == Деревья поиска == |
| − | + | * [[Упорядоченное множество]] | |
| − | + | * [[Дерево поиска, наивная реализация]] | |
| − | + | * [[АВЛ-дерево]] | |
| − | + | * [[2-3 дерево]] | |
| − | * [[ | + | * [[B-дерево]] |
| − | * [[ | + | * [[Красно-черное дерево]] |
| + | * [[Декартово дерево]] | ||
| + | * [[Splay-дерево]] | ||
| + | * [[Декартово дерево по неявному ключу]] | ||
| + | * [[Дерево ван Эмде Боаса]] | ||
| + | |||
| + | == Дерево отрезков == | ||
| + | * [[Статистики на отрезках. Корневая эвристика]] | ||
| + | * [[Дерево отрезков. Построение]] | ||
| + | * [[Реализация запроса в дереве отрезков сверху]] | ||
| + | * [[Реализация запроса в дереве отрезков снизу]] | ||
| + | * [[Несогласованные поддеревья. Реализация массового обновления]] | ||
| + | * [[Многомерное дерево отрезков]] | ||
| + | * [[Сжатое многомерное дерево отрезков]] | ||
| + | |||
| + | |||
| + | == Дерево Фенвика == | ||
| + | * [[Дерево Фенвика]] | ||
| + | * [[Встречное дерево Фенвика]] | ||
| + | * [[Дерево Фенвика для некоммутативных операций]] | ||
| + | * [[Многомерное дерево Фенвика]] | ||
| + | |||
| + | == Хеширование == | ||
| + | * [[Хеширование]] | ||
| + | * [[Различные алгоритмы хеширования]] | ||
| + | * [[Открытое и закрытое хеширование]] | ||
| + | * [[Поиск свободного места при закрытом хешировании]] | ||
| + | * [[Хеширование кукушки]] | ||
| + | * [[Двойное хеширование]] | ||
| + | * [[Перехеширование. Амортизационный анализ]] | ||
| + | * [[Фильтр Блума]] | ||
| + | * [[Универсальное семейство хеш-функций]] | ||
| + | |||
| + | == Сортировка == | ||
| + | * [[Сортировка пузырьком]] | ||
| + | * [[Сортировка слиянием]] | ||
| + | * [[Cортировка слиянием с использованием O(1) дополнительной памяти]] | ||
| + | * [[Сортировка вставками]] | ||
| + | * [[Сортировка подсчетом]] | ||
| + | * [[Сортировка подсчетом сложных объектов]] | ||
| + | * [[Цифровая сортировка]] | ||
| + | * [[Поиск k-ой порядковой статистики]] | ||
| + | * [[Поиск k-й порядковой статистики за линейное время]] | ||
| + | * [[Теорема о нижней оценке для сортировки сравнениями]] | ||
| + | * [[Быстрая сортировка]] | ||
| + | |||
| + | == [[Сортирующие сети]] == | ||
| + | * [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] | ||
| + | * [[Сортирующие сети для квадратичных сортировок]] | ||
| + | * [[Сеть Бетчера]] | ||
| + | |||
| + | == Алгоритмы поиска == | ||
| + | * [[Троичный поиск]] | ||
| + | * [[Поиск с помощью золотого сечения]] | ||
| + | * [[Интерполяционный поиск]] | ||
| + | * [[Вещественный двоичный поиск]] | ||
Версия 00:41, 30 июня 2011
Содержание
Второй семестр
Амортизационный анализ
- Амортизационный анализ. Метод предоплаты
- Саморасширяющийся массив
- Массив с увеличением/уменьшением размера
- Стек
- Очередь
- Список
Приоритетные очереди
Система непересекающихся множеств
- Наивные реализации
- Списки с весовой эвристикой
- Реализация с помощью леса корневых деревьев
- Анализ реализации с ранговой эвристикой
Деревья поиска
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево
- Красно-черное дерево
- Декартово дерево
- Splay-дерево
- Декартово дерево по неявному ключу
- Дерево ван Эмде Боаса
Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления
- Многомерное дерево отрезков
- Сжатое многомерное дерево отрезков
Дерево Фенвика
- Дерево Фенвика
- Встречное дерево Фенвика
- Дерево Фенвика для некоммутативных операций
- Многомерное дерево Фенвика
Хеширование
- Хеширование
- Различные алгоритмы хеширования
- Открытое и закрытое хеширование
- Поиск свободного места при закрытом хешировании
- Хеширование кукушки
- Двойное хеширование
- Перехеширование. Амортизационный анализ
- Фильтр Блума
- Универсальное семейство хеш-функций
Сортировка
- Сортировка пузырьком
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти
- Сортировка вставками
- Сортировка подсчетом
- Сортировка подсчетом сложных объектов
- Цифровая сортировка
- Поиск k-ой порядковой статистики
- Поиск k-й порядковой статистики за линейное время
- Теорема о нижней оценке для сортировки сравнениями
- Быстрая сортировка
Сортирующие сети
- Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
- Сортирующие сети для квадратичных сортировок
- Сеть Бетчера
