Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. == 1. Амортизационный анализ ==# '''!!!''' перенаправление [[Амортизационный анализ]]## Можно добавить ещё по примеру на каждый метод.# [[Саморасширяющийся массив]]# [[Массив с увеличениемУчастник:Shersh/уменьшением размера]]## Объединить с предыдущим, сделать всё красиво.# '''!!!''' [[Список]]## Можно добавить интересные задачи на списки, которые дают на собеседованиях. Для согласования связаться сначала с куратором.# [[Стек]]# [[Очередь]]## Заменить ссылки в источника на интервики# '''!!!''' [[Персистентный стек]]# [[Персистентная очередь]]# [[Персистентный дек]]## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)# [[Мажорирующий элемент]]# '''!!!''' [[Счетчик Кнута]]## Добавить картинки с более понятным пояснением## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)## Может быть можно обобщить как-то на случай <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. Алгоритмы поиска ==# [[Целочисленный двоичный поиск]]# [[Вещественный двоичный поиск]]# [[Троичный поиск]]# [[Поиск с помощью золотого сечения]]# [[Интерполяционный поискТикеты ко 2ому терму]]
