Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. == 1. Амортизационный анализ ==# '''fixed''' [[Амортизационный анализ]]## Увеличить маленькие дроби## Добавить ссылок## Добавить интервики## Список в стеке с multipop поправить {{---}} он очень некрасиво смотрится## Исправить tex, а ещё некоторые речевые ошибки в конспекте## Функции взять в \mathrm## Добавить парочку примеров на методы.# [[Саморасширяющийся массив]]# '''взяли''' перенаправление [[Массив с увеличением/уменьшением размера]]## Объединить с предыдущим## Поправить texУчастник: неравенства поменять, дроби увеличить## Добавить информацию о том, какие структуры данных в современных языках программирования используют саморасширяющийся массив# [[Список]]# [[Стек]]# [[Очередь]]## Заменить ссылки в источника на интервики# '''взяли''' [[Персистентный стек]]# '''взяли''' [[Персистентная очередь]]# '''взяли''' [[Персистентный дек]]## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)# [[Мажорирующий элемент]]# '''взяли''' [[Счетчик Кнута]]## Добавить картинки с более понятным пояснением## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)## Может быть можно обобщить как-то на случай <tex>d<Shersh/tex>-ичной системы счисления? (используется в толстых кучах)## Будет полезно добавить источники, если про это где-то можно почитать## Полностью переписать конспект, он очень невнятный == 2. Приоритетные очереди == # [[Двоичная куча]]## Ссылки на википедию сделать через интервики# [[Биномиальная куча]]## интервики# [[Фибоначчиева куча]]## Ссылки заменить на интервики# [[Левосторонняя куча]]# [[Тонкая куча]]# [[Толстая куча на избыточном счетчике]]## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.# [[Куча Бродала-Окасаки]] == 3. Система непересекающихся множеств ==# [[СНМ (наивные реализации) | Наивные реализации]]# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]## Интервики == 4. Поисковые структуры данных == # [[Упорядоченное множество]]# [[Дерево поиска, наивная реализация]]# [[АВЛ-дерево]]# [[2-3 дерево]]# [[B-дерево]]# [[Красно-черное дерево]]# [[Декартово дерево]]# [[Декартово дерево по неявному ключу]]# [[Splay-дерево]]# [[Рандомизированное бинарное дерево поиска]]# [[Дерево ван Эмде Боаса]]# [[Список с пропусками]]# [[Fusion tree]]# [[Сверхбыстрый цифровой бор]]* В каждом конспекте сделать ссылки на википедию через интервики == 5. Дерево отрезков == # [[Статистики на отрезках. Корневая эвристика]]# '''взяли''' [[Дерево отрезков. Построение]]## Добавить псевдокод персистентного дерева отрезков## Заменить в псевдокоде f на бинарную операцию <tex> \circ </tex>## Поправить ссылки в источниках## Поправить tex: знаки неравенств, дроби и т. п.## Отрефакторить псевдокод# [[Реализация запроса в дереве отрезков сверху]]# [[Реализация запроса в дереве отрезков снизу]]# [[Несогласованные поддеревья. Реализация массового обновления]]# [[Многомерное дерево отрезков]]# [[Сжатое многомерное дерево отрезков]] == 6. Дерево Фенвика ==# [[Дерево Фенвика]]# [[Встречное дерево Фенвика]]# [[Дерево Фенвика для некоммутативных операций]]# [[Многомерное дерево Фенвика]] == 7. Хеширование ==# [[Хеш-таблица]]# '''!!!''' [[Разрешение коллизий]]## Добавить примеры каких-нибудь интересных и популярных хешей, поизучать их свойства# [[Хеширование кукушки]]# [[Идеальное хеширование]]# [[Перехеширование. Амортизационный анализ]]# [[Фильтр Блума]]# [[Универсальное семейство хеш-функций]] == 8. [[Сортировка]] ==# [[Сортировка выбором]]## Ссылку через интервики# '''взяли''' [[Сортировка пузырьком]]## Добавить ещё оптимизаций этой сортировки (шейкерная сортировка, расчёской, odd-even и прочие {{---}} полный список есть на [[ wikipedia:en:Bubble_sort | википедии ]]) {{---}} полностью расписывать не надо, только ссылки и краткое описание. Об уменьшии константы в асимптотике можно пару слов сказать, если только она и уменьшается.## Дать точные оценки на число сравнений в худшем случае## Отформатировать псевдокод## Ссылка на вики# '''взяли''' [[Сортировка вставками]]## То же самое, что и в предыдущем тикете# [[Сортировка Шелла]]# '''!!!''' [[Сортировка кучей]]## Можно добавить всякие модификации сортировки кучей, например, JSort.# [[Быстрая сортировка]]## Тут вообще ссылки ужасные# '''взяли''' [[Сортировка слиянием]]## Эта сортировка хорошо параллелится. Но вдруг можно придумать, как манипулировать потоками, чтобы достичь наибольшей эффективности, особенно если одновременно может работать ограниченное число потоков.## Написать псевдокод многопоточной сортировки# [[Cортировка слиянием с использованием O(1) дополнительной памяти]]# [[Теорема о нижней оценке для сортировки сравнениями]]# [[Сортировка подсчетом]]# [[Сортировка подсчетом сложных объектов]]# '''fixed''' [[Цифровая сортировка]]## Добавить модификацию для сортировки цифр в порядке от старших к младшим## Убрать ; из псевдокода# [[Карманная сортировка]]# [[Поиск k-ой порядковой статистики]]# [[Поиск k-ой порядковой статистики за линейное время]]# '''взяли''' [[Сортировка Хана]]## Привести конспект в порядок! ## Добавить шаблоны определений## Добавить шаблоны лемм## Поправить tex, где его нет## Корректно оформить ссылки## Поподробней рассказать про ЭП-дерево## Использование лемм оформить ссылками## Структуру поменять, переставить пункты местами, чтобы не было ссылок в тексте на то, что ещё не рассказывалось## "Конец" в доказательстве выглядит некрасиво. Как и "Доказательство". Опять же, всё сделать шаблонами## Псевдокод добавить, если из описания будет не совсем понятно, как это реализовать (данный пункт допускает возможность поправить идейное описание алгоритма вместо добавление псевдокода)## Возможно, ещё какие-то правки по мелочи## Картинки приветствуются. Если их добавить (или убедить меня, что и так норм, или сделать что-то другое), а всё остальное будет очень няшно сделано, то всё может рассматриваться как целый коспект в баллах.# [[Timsort]]## Последнюю картинку можно сделать более красочной == 9. Сортирующие сети ==# [[Сортирующие сети]]## Занести оставшиеся определения в [[Шаблон: Определение]]## Англоязычные термины Тикеты ко всем## Ссылки на вики через интервики# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип2ому терму]]## Ссылки через интервики## Поменять знаки неравенст в tex на более красивые# [[Сортировочные сети с особыми свойствами]]# [[Сортирующие сети для квадратичных сортировок]]# [[Сеть Бетчера]] == 10. Алгоритмы поиска ==# '''взяли''' [[Целочисленный двоичный поиск]]## Заменить тире на [[Шаблон:---]]## Англоязычные термины## Переменные взять в tex## Отформатировать псевдокод## Добавить категории## <= заменить в tex на \leqslant## Добавить эвристику с запоминанием последнего узла при последовательных запросах и её оценку## Добавить ссылок## Пару слов о том, чем плохо условие на остановку, если вдруг попали в нужный элемент (или чем хорошо)# '''взяли''' [[Вещественный двоичный поиск]]## Плюсы и минусы cпособов оформить по-красивому## Отформатировать псевдокод## Добавить категории## Добавить оценку на число итераций## Больше ссылок# '''взяли''' [[Троичный поиск]]## Добавить категории## Добавить ссылок## Отформатировать псевдокод## Сделать так, чтобы картинка не залезала на псевдокод## Англоязычные термины## Увеличить дроби## См. также красиво оформить# [[Поиск с помощью золотого сечения]]## Отформатировать псевдокод## Дроби увеличить## Добавить категории# '''!!!''' [[Интерполяционный поиск]]## Расположения картинки и псевдокода относительно друг друга не очень удачные## Нормальную картинку сделать## Ссылки нормально оформить## Расписать асимптотику нормально## Отформатировать псевдокод## Примеры данных, на которых поиск работает хорошо
