http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=188.162.65.120&* Викиконспекты - Вклад участника [ru] 2026-05-23T07:48:19Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Shersh/%D0%A2%D0%B8%D0%BA%D0%B5%D1%82%D1%8B_%D0%BF%D0%BE_%D0%BA%D0%BE%D0%BD%D1%81%D0%BF%D0%B5%D0%BA%D1%82%D0%B0%D0%BC_year2013&diff=36483 Участник:Shersh/Тикеты по конспектам year2013 2014-04-27T07:45:54Z <p>188.162.65.120: /* 5. Дерево отрезков */</p> <hr /> <div>Тикеты индексируются как &quot;X-Y&quot;, где X — номер раздела, Y — номер конспекта внутри раздела.<br /> <br /> == 1. Амортизационный анализ ==<br /> # '''!!!''' [[Амортизационный анализ]]<br /> ## Можно добавить ещё по примеру на каждый метод.<br /> # [[Саморасширяющийся массив]]<br /> # [[Массив с увеличением/уменьшением размера]]<br /> ## Объединить с предыдущим, сделать всё красиво.<br /> # [[Список]]<br /> # [[Стек]]<br /> # [[Очередь]]<br /> ## Заменить ссылки в источника на интервики<br /> # '''взяли''' [[Персистентный стек]]<br /> # '''взяли''' [[Персистентная очередь]]<br /> # '''взяли''' [[Персистентный дек]]<br /> ## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)<br /> # [[Мажорирующий элемент]]<br /> # '''!!!''' [[Счетчик Кнута]]<br /> ## Добавить картинки с более понятным пояснением<br /> ## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)<br /> ## Может быть можно обобщить как-то на случай &lt;tex&gt;d&lt;/tex&gt;-ичной системы счисления? (используется в толстых кучах)<br /> ## Будет полезно добавить источники, если про это где-то можно почитать<br /> <br /> == 2. Приоритетные очереди ==<br /> <br /> # [[Двоичная куча]]<br /> ## Ссылки на википедию сделать через интервики<br /> # [[Биномиальная куча]]<br /> ## интервики<br /> # [[Фибоначчиева куча]]<br /> ## Ссылки заменить на интервики<br /> # [[Левосторонняя куча]]<br /> # [[Тонкая куча]]<br /> # [[Толстая куча на избыточном счетчике]]<br /> ## Расписать подробно операцию &quot;декремент&quot;. Можно как-то связать со счётчиком Кнута.<br /> # [[Куча Бродала-Окасаки]]<br /> <br /> == 3. Система непересекающихся множеств ==<br /> # [[СНМ (наивные реализации) | Наивные реализации]]<br /> # [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]<br /> # [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]<br /> ## Интервики<br /> <br /> == 4. Поисковые структуры данных ==<br /> <br /> # [[Упорядоченное множество]]<br /> # [[Дерево поиска, наивная реализация]]<br /> # [[АВЛ-дерево]]<br /> # [[2-3 дерево]]<br /> # [[B-дерево]]<br /> # [[Красно-черное дерево]]<br /> # [[Декартово дерево]]<br /> # [[Декартово дерево по неявному ключу]]<br /> # [[Splay-дерево]]<br /> # [[Рандомизированное бинарное дерево поиска]]<br /> # [[Дерево ван Эмде Боаса]]<br /> # [[Список с пропусками]]<br /> # [[Fusion tree]]<br /> # [[Сверхбыстрый цифровой бор]]<br /> * В каждом конспекте сделать ссылки на википедию через интервики<br /> <br /> == 5. Дерево отрезков ==<br /> <br /> # [[Статистики на отрезках. Корневая эвристика]]<br /> # '''!!!''' [[Дерево отрезков. Построение]]<br /> ## Добавить псевдокод персистентного дерева отрезков<br /> ## Заменить в псевдокоде f на бинарную операцию &lt;tex&gt; \circ &lt;/tex&gt;<br /> ## Поправить ссылки в источниках<br /> # [[Реализация запроса в дереве отрезков сверху]]<br /> # [[Реализация запроса в дереве отрезков снизу]]<br /> # [[Несогласованные поддеревья. Реализация массового обновления]]<br /> # [[Многомерное дерево отрезков]]<br /> # [[Сжатое многомерное дерево отрезков]]<br /> <br /> == 6. Дерево Фенвика ==<br /> # [[Дерево Фенвика]]<br /> # [[Встречное дерево Фенвика]]<br /> # [[Дерево Фенвика для некоммутативных операций]]<br /> # [[Многомерное дерево Фенвика]]<br /> <br /> == 7. Хеширование ==<br /> # [[Хеш-таблица]]<br /> # '''!!!''' [[Разрешение коллизий]]<br /> ## Добавить примеры каких-нибудь интересных и популярных хешей, поизучать их свойства<br /> # [[Хеширование кукушки]]<br /> # [[Идеальное хеширование]]<br /> # [[Перехеширование. Амортизационный анализ]]<br /> # [[Фильтр Блума]]<br /> # [[Универсальное семейство хеш-функций]]<br /> <br /> == 8. [[Сортировка]] ==<br /> # [[Сортировка выбором]]<br /> # [[Сортировка пузырьком]]<br /> # [[Сортировка вставками]]<br /> # [[Сортировка Шелла]]<br /> # [[Сортировка кучей]]<br /> # [[Быстрая сортировка]]<br /> # [[Сортировка слиянием]]<br /> # [[Cортировка слиянием с использованием O(1) дополнительной памяти]]<br /> # [[Теорема о нижней оценке для сортировки сравнениями]]<br /> # [[Сортировка подсчетом]]<br /> # [[Сортировка подсчетом сложных объектов]]<br /> # [[Цифровая сортировка]]<br /> # [[Карманная сортировка]]<br /> # [[Поиск k-ой порядковой статистики]]<br /> # [[Поиск k-ой порядковой статистики за линейное время]]<br /> # [[Сортировка Хана]]<br /> # [[Timsort]]<br /> <br /> == 9. Сортирующие сети ==<br /> # [[Сортирующие сети]]<br /> # [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]<br /> # [[Сортировочные сети с особыми свойствами]]<br /> # [[Сортирующие сети для квадратичных сортировок]]<br /> # [[Сеть Бетчера]]<br /> <br /> == 10. Алгоритмы поиска ==<br /> # [[Целочисленный двоичный поиск]]<br /> # [[Вещественный двоичный поиск]]<br /> # [[Троичный поиск]]<br /> # [[Поиск с помощью золотого сечения]]<br /> # [[Интерполяционный поиск]]</div> 188.162.65.120