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

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

Версия 18:34, 15 апреля 2014

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.

1. Амортизационный анализ

  1. Амортизационный анализ
  2. Саморасширяющийся массив
  3. Массив с увеличением/уменьшением размера
  4. Список
  5. Стек
  6. Очередь
  7. Персистентный стек
  8. Персистентная очередь
  9. Персистентный дек
  10. Мажорирующий элемент
  11. Счетчик Кнута

2. Приоритетные очереди

  1. Двоичная куча
  2. Биномиальная куча
  3. Фибоначчиева куча
  4. Левосторонняя куча
  5. Тонкая куча
  6. Толстая куча на избыточном счетчике
  7. Куча Бродала-Окасаки

3. Система непересекающихся множеств

  1. Наивные реализации
  2. Списки с весовой эвристикой
  3. Реализация с помощью леса корневых деревьев

4. Поисковые структуры данных

  1. Упорядоченное множество
  2. Дерево поиска, наивная реализация
  3. АВЛ-дерево
  4. 2-3 дерево
  5. B-дерево
  6. Красно-черное дерево
  7. Декартово дерево
  8. Декартово дерево по неявному ключу
  9. Splay-дерево
  10. Рандомизированное бинарное дерево поиска
  11. Дерево ван Эмде Боаса
  12. Список с пропусками
  13. Fusion tree
  14. Сверхбыстрый цифровой бор

5. Дерево отрезков

  1. Статистики на отрезках. Корневая эвристика
  2. Дерево отрезков. Построение
  3. Реализация запроса в дереве отрезков сверху
  4. Реализация запроса в дереве отрезков снизу
  5. Несогласованные поддеревья. Реализация массового обновления
  6. Многомерное дерево отрезков
  7. Сжатое многомерное дерево отрезков

6. Дерево Фенвика

  1. Дерево Фенвика
  2. Встречное дерево Фенвика
  3. Дерево Фенвика для некоммутативных операций
  4. Многомерное дерево Фенвика

7. Хеширование

  1. Хеш-таблица
  2. Разрешение коллизий
  3. Хеширование кукушки
  4. Идеальное хеширование
  5. Перехеширование. Амортизационный анализ
  6. Фильтр Блума
  7. Универсальное семейство хеш-функций

8. Сортировка

  1. Сортировка выбором
  2. Сортировка пузырьком
  3. Сортировка вставками
  4. Сортировка Шелла
  5. Сортировка кучей
  6. Быстрая сортировка
  7. Сортировка слиянием
  8. Cортировка слиянием с использованием O(1) дополнительной памяти
  9. Теорема о нижней оценке для сортировки сравнениями
  10. Сортировка подсчетом
  11. Сортировка подсчетом сложных объектов
  12. Цифровая сортировка
  13. Карманная сортировка
  14. Поиск k-ой порядковой статистики
  15. Поиск k-ой порядковой статистики за линейное время
  16. Сортировка Хана
  17. Timsort

9. Сортирующие сети

  1. Сортирующие сети
  2. Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
  3. Сортировочные сети с особыми свойствами
  4. Сортирующие сети для квадратичных сортировок
  5. Сеть Бетчера

10. Алгоритмы поиска

  1. Целочисленный двоичный поиск
  2. Вещественный двоичный поиск
  3. Троичный поиск
  4. Поиск с помощью золотого сечения
  5. Интерполяционный поиск