Участник:Shersh/Тикеты по конспектам year2013

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

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

1. !!! Амортизационный анализ
   1. Можно добавить ещё по примеру на каждый метод.
2. Саморасширяющийся массив
3. Массив с увеличением/уменьшением размера
   1. Объединить с предыдущим, сделать всё красиво.
4. !!! Список
   1. Можно добавить интересные задачи на списки, которые дают на собеседованиях. Для согласования связаться сначала с куратором.
5. Стек
6. Очередь
7. !!! Персистентный стек
8. Персистентная очередь
9. Персистентный дек
   1. Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)
10. Мажорирующий элемент
11. !!! Счетчик Кнута
    1. Добавить картинки с более понятным пояснением
    2. Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)
    3. Может быть можно обобщить как-то на случай [math]d[/math]-ичной системы счисления? (используется в толстых кучах)

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

1. Двоичная куча
2. Биномиальная куча
3. Фибоначчиева куча
4. Левосторонняя куча
5. Тонкая куча
6. Толстая куча на избыточном счетчике
   1. Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
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. Интерполяционный поиск