|
|
| (не показаны 94 промежуточные версии 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. Алгоритмы поиска ==
| |
| − | # [[Целочисленный двоичный поиск]]
| |
| − | # [[Вещественный двоичный поиск]]
| |
| − | # [[Троичный поиск]]
| |
| − | # [[Поиск с помощью золотого сечения]]
| |
| − | # [[Интерполяционный поиск]]
| |
