|
|
| (не показано 69 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
| + | #перенаправление [[Участник:Shersh/Тикеты ко 2ому терму]] |
| − | | |
| − | == 1. Амортизационный анализ ==
| |
| − | # '''fixed''' [[Амортизационный анализ]]
| |
| − | ## Увеличить маленькие дроби
| |
| − | ## Добавить ссылок
| |
| − | ## Добавить интервики
| |
| − | ## Список в стеке с multipop поправить {{---}} он очень некрасиво смотрится
| |
| − | ## Исправить tex, а ещё некоторые речевые ошибки в конспекте
| |
| − | ## Функции взять в \mathrm
| |
| − | ## Добавить парочку примеров на методы.
| |
| − | # [[Саморасширяющийся массив]] | |
| − | # '''!!!''' [[Массив с увеличением/уменьшением размера]]
| |
| − | ## Объединить с предыдущим
| |
| − | ## Поправить tex: неравенства поменять, дроби увеличить
| |
| − | ## Добавить информацию о том, какие структуры данных в современных языках программирования используют саморасширяющийся массив
| |
| − | # [[Список]]
| |
| − | # [[Стек]]
| |
| − | # [[Очередь]]
| |
| − | ## Заменить ссылки в источника на интервики
| |
| − | # '''взяли''' [[Персистентный стек]]
| |
| − | # '''взяли''' [[Персистентная очередь]]
| |
| − | # '''взяли''' [[Персистентный дек]]
| |
| − | ## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)
| |
| − | # [[Мажорирующий элемент]]
| |
| − | # '''взяли''' [[Счетчик Кнута]]
| |
| − | ## Добавить картинки с более понятным пояснением
| |
| − | ## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)
| |
| − | ## Может быть можно обобщить как-то на случай <tex>d</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) дополнительной памяти]]
| |
| − | # [[Теорема о нижней оценке для сортировки сравнениями]]
| |
| − | # [[Сортировка подсчетом]]
| |
| − | # [[Сортировка подсчетом сложных объектов]]
| |
| − | # '''!!!''' [[Цифровая сортировка]]
| |
| − | ## Добавить модификацию для сортировки цифр в порядке от старших к младшим
| |
| − | ## Убрать ; из псевдокода
| |
| − | # [[Карманная сортировка]]
| |
| − | # [[Поиск k-ой порядковой статистики]]
| |
| − | # [[Поиск k-ой порядковой статистики за линейное время]]
| |
| − | # '''!!!''' [[Сортировка Хана]]
| |
| − | ## Привести конспект в порядок!
| |
| − | ## Добавить шаблоны определений
| |
| − | ## Добавить шаблоны лемм
| |
| − | ## Поправить tex, где его нет
| |
| − | ## Корректно оформить ссылки
| |
| − | ## Поподробней рассказать про ЭП-дерево
| |
| − | ## Использование лемм оформить ссылками
| |
| − | ## Структуру поменять, переставить пункты местами, чтобы не было ссылок в тексте на то, что ещё не рассказывалось
| |
| − | ## "Конец" в доказательстве выглядит некрасиво. Как и "Доказательство". Опять же, всё сделать шаблонами
| |
| − | ## Псевдокод добавить, если из описания будет не совсем понятно, как это реализовать (данный пункт допускает возможность поправить идейное описание алгоритма вместо добавление псевдокода)
| |
| − | ## Возможно, ещё какие-то правки по мелочи
| |
| − | ## Картинки приветствуются. Если их добавить (или убедить меня, что и так норм, или сделать что-то другое), а всё остальное будет очень няшно сделано, то всё может рассматриваться как целый коспект в баллах.
| |
| − | # [[Timsort]]
| |
| − | | |
| − | == 9. Сортирующие сети ==
| |
| − | # [[Сортирующие сети]]
| |
| − | # [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
| |
| − | # [[Сортировочные сети с особыми свойствами]]
| |
| − | # [[Сортирующие сети для квадратичных сортировок]]
| |
| − | # [[Сеть Бетчера]]
| |
| − | | |
| − | == 10. Алгоритмы поиска ==
| |
| − | # [[Целочисленный двоичный поиск]]
| |
| − | # [[Вещественный двоичный поиск]]
| |
| − | # [[Троичный поиск]]
| |
| − | # [[Поиск с помощью золотого сечения]]
| |
| − | # [[Интерполяционный поиск]]
| |
