Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. == 1. Амортизационный анализ ==# '''fixed''' перенаправление [[Амортизационный анализ]]## Увеличить маленькие дроби## Добавить ссылок## Добавить интервики## Список в стеке с multipop поправить {{---}} он очень некрасиво смотрится## Исправить tex, а ещё некоторые речевые ошибки в конспекте## Функции взять в \mathrm## Добавить парочку примеров на методы.# [[Саморасширяющийся массив]]# '''fixed''' [[Массив с увеличением/уменьшением размера]]## Объединить с предыдущим## Поправить texУчастник: неравенства поменять, дроби увеличить## Добавить информацию о том, какие структуры данных в современных языках программирования используют саморасширяющийся массив# '''взяли''' [[Список]]## Заменить тире на шаблон## Отформатировать псевдокод## Поправить ссылки в См. также, сделать маркированным списком## Объединить Ссылки и Литературу## Добавить категории## Добавить примеры интересных задач на списки (обычно их спрашивают на собеседованиях)# ''взяли'' [[Стек]]## Отрефакторить псевдокод## Поправить ссылки## Имена функций в тексте обернуть в \mathrm## Оформить имена функций в lowerCamelCase## Добавить интервики на список## Заменить тире на {{---}}# ''взяли'' [[Очередь]]## То же самое, что и в предыдущем## Плюсы и Минусы оформить единообразно маркированным списком## Заменить ссылки в источника на интервики# '''взяли''' [[Персистентный стек]]# '''взяли''' [[Персистентная очередь]]# '''взяли''' [[Персистентный дек]]## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)# [[Мажорирующий элемент]]## Поправить псевдокод## Заменить тире на шаблон, а кое-где {{---}} наоборот, на дефис## != в тексте заменить на \ne## Убрать скобки из диапазона массива## Заменить size в доказательстве про K на ||# '''взяли''' [[Счетчик Кнута]]## Добавить картинки с более понятным пояснением## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)## Может быть можно обобщить как-то на случай <tex>d<Shersh/tex>-ичной системы счисления? (используется в толстых кучах)## Будет полезно добавить источники, если про это где-то можно почитать## Полностью переписать конспект, он очень невнятный == 2. Приоритетные очереди == # [[Двоичная куча]]## Ссылки на википедию сделать через интервики## Отформатировать псевдокод## Названия функций сделать в lowerCamelCase, например, siftDown## Функции в тексте обернуть в \mathrm# [[Биномиальная куча]]## Увеличить размер сочетаний## Отрефакторить псевдокод## Круглые скобки в логарифме можно убрать## Названия функций в тексте обернуть в \mathrm# '''fixed''' [[Фибоначчиева куча]]## Ссылки заменить на интервики## Функции в тексте обернуть в \mathrm## Скобки в логарифме можно убрать## Все переменные и константы взять в tex## Исправить уровни заголовков## Местами текст смешивается с tex, непонятны переходы становятся# [[Левосторонняя куча]]# [[Тонкая куча]]## То же самое, что в фибоначчиевых кучах# [[Толстая куча на избыточном счетчике]]## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.## Ссылка в интервики с большой буквы {{---}} заменить на маленькую## Отформатировать псевдокод## Всё оформлено в UpperCamelCase, наверное, надо что-то с этим сделать## Названия функций обернуть в \mathrm## Поправить ошибку в Источниках## Все переменные и константы взять в tex## "Основные операции оформить аккуратней## В одном месте лишнее выделение текста псевдокодным прямоугольником, в другом месте комментарий вылез за псевдокод# '''!!!''' [[Куча Бродала-Окасаки]]## Ссылки заменить на источники информации, сделать маркированным списком## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge## Написать подробней операции == 3. Система непересекающихся множеств ==# ''fixed'' [[СНМ (наивные реализации) | Наивные реализации]]## Добавить формальное определение## Переменные и константы взять в tex## Функции взять в \mathrm## Отформатировать псевдокод## Картинку можно убрать из thumb## Источники объединить с ссылками# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]## Имена функций в тексте обернуть в \mathrm## Отформатировать псевдокод## Объединить источники и ссылки# '''!!!''' [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]## Интервики## Функции в тексте взять в \mathrm## Заменить \ge на \geqslant## Добавить определение итерированного логарифма, а то из текста непонятно, что это такое## Переменные и константы взять в tex## Пояснить переходы в оценке ранговой эвристики: про интервал, про оценку на <tex> R(v_1 </tex>## Добавить другие эвристики и оценить их == 4. Поисковые структуры данных == # [[Упорядоченное множество]]## Названия функций в тексте обернуть в \mathrm## Имена функций оформить в lowerCamelCase## Расширить определение до элементов, на которых задан порядок## Добавить несколько слов о наивной реализации на массиве## Добавить ссылок# '''!!!''' [[Дерево поиска, наивная реализация]]## Тире заменить на шаблон## Отформатировать псевдокод## Добавить про персистентное двоичное дерево и псевдокод операций вставки и удаления: показать как там всё просто## Функции в тексте обернуть в \mathrm## Ссылки объединить с литературой, добавить больше ссылок, оформить красиво# [[АВЛ-дерево]]## Исправить знаки неравенств в tex## Заменить тире на шаблон## Константы обернуть в tex## Литературу заменить на источники информации, добавить ссылок## '''!!!''' Рассмотреть реализацию с меньшим количеством памяти в узлах# [[2-3 дерево]]## Ссылки оформить красиво## Случаи сделать списком# [[B-дерево]]## Увеличить дроби## Отформатировать псевдокод# '''!!!''' [[Красно-черное дерево]]## Дефис в определении заменить на тире## Тире в тексте {{---}} на шаблон## Константы взять в tex## Оформить красиво источники информации## Определение выделить жирным## В Кормене чуть другое определение красно-чёрного дерева: рассмотреть эквивалентность## Добавить операцию [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf split]# [[Декартово дерево]]## Тире заменить на шаблон## Имена функций оформить в lowerCamelCase## Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев## Отформатировать псевдокод# [[Декартово дерево по неявному ключу]]## Добавить псевдокод## Тире заменить на шаблон## Сделать интервики на Rope## Добавить ссылок ## Функции в тексте обернуть в \mathrm и оформить их в lowerCamelCase# '''!!!''' [[Splay-дерево]]## Исправить знаки неравенств в tex## Увеличить дроби## Тире заменить на шаблон## Показать, что лемма верна для любого фиксированного веса узла## Функции оформить в lowerCamelCase# [[Рандомизированное бинарное дерево поиска]]## Отформатировать псевдокод## Функции в тексте взять в \mathrm## Умножение сделать везде единообразным, например, через \cdot## Переменные и константы в тексте взять в tex# [[Дерево ван Эмде Боаса]]## Имена функций взять в \mathrm## Отформатировать псевдокод# '''!!!''' [[Список с пропусками]]## \theta cделать большой буквой## Определение в начале мутное## Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?## Увеличить дроби## Отформатировать псевдокод## log заменить на \log## Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит# [[Fusion tree]]## Тире заменить на шаблон## sketch cделать везде с маленькой буквы, а кое-где исправить snetch на sketch## XOR заменить на \oplus## succ cделать с маленькой буквы# [[Сверхбыстрый цифровой бор]] == 5. Дерево отрезков == # [[Статистики на отрезках. Корневая эвристика]]## Отформатировать псевдокод## Заменить тире на шаблон# '''fixed''' [[Дерево отрезков. Построение]]## Добавить псевдокод персистентного дерева отрезков## Заменить в псевдокоде f на бинарную операцию <tex> \circ </tex>## Поправить ссылки в источниках## Поправить tex: знаки неравенств, дроби и т. п.## Отрефакторить псевдокод## Исправить несогласованность текста и псевдокода: в тексте полуинтервал, а в псевдоде {{---}} отрезок## Исправить ошибку в картинке персистентного дерева# ''взяли'' [[Реализация запроса в дереве отрезков сверху]]## Отформатировать псевдокод## Тире заменить на шаблон## Заменить "Ссылки" на источники информации и оформить их маркированным списком## Добавить см. также на реализацию запросов cнизу# ''взяли'' [[Реализация запроса в дереве отрезков снизу]]## Отформатировать псевдокод## Имена переменных оформить в lowerCamelCase## Переменные в тексте взять в tex## Источники информации оформить маркированным списком## Добавить см. также на реализацию запросов сверху# [[Несогласованные поддеревья. Реализация массового обновления]]## Константы взять в tex## Отформатировать псевдокод## Добавить примеры массовых операций# [[Многомерное дерево отрезков]]## Константы взять в tex## Отформатировать псевдокод# [[Сжатое многомерное дерево отрезков]]## Отформатировать псевдокод## Литературу заменить на Источники информации == 6. Дерево Фенвика ==# '''!!!''' [[Дерево Фенвика]]## Тире заменить на шаблон## Исправить багу в доказательстве (см. обсуждения)## Битовые операции окружить пробелами## Знаки неравенств заменить на \leqslant и \geqslant## Расписать эквивалентность формул с числом единиц и побитовые операции## Заменить i = \overline{0, n - 1} на i = 0 .. n - 1## Добавить описание побитовых операций в самое начало, чтобы не использовать их перед их определением## Отформатировать псевдокод## Оформить красиво ссылки## Добавить категории## Имена функций взять в \mathrm## Добавить преимущества и недостатки дерева Фенвика# [[Встречное дерево Фенвика]]## Добавить категории## Добавить ссылок## "отрезок длины 1..2^n" {{---}} странное обозначение длины## Умножение матриц не является коммутативной операцией, добавить другой пример# [[Дерево Фенвика для некоммутативных операций]]## Добавить категории## Доказательство оформить в виде шаблона теоремы или заменить на "Корректность"## Скобки вокруг n в log(n) можно убрать# '''!!!''' [[Многомерное дерево Фенвика]]## Тире заменить на шаблон## Отформатировать псевдокод## Разместить картинку так, чтобы не залезала на псевдокод## Имена функций обернуть в \mathrm## Псевдокод сделать отдельным подпунктом## Оформить красиво ссылки## Добавить категории## Перерисовать картинку (см. обсуждения) == 7. Хеширование ==# [[Хеш-таблица]]## Смотрите обсуждения## Константы взять в tex## Понятия в тексте взять в шаблон определения## Многоточия в tex заменить на \dots# [[Разрешение коллизий]]## Отформатировать псевдокод## Разрешение коллизий из предыдущего конспекта перенести в этот, а в том сделать интервики на данный конспект## Имена функций взять в \mathrm## \mod заменить на \bmod## Поправить ссылки## '''!!!''' Добавить оценку на длину кластеров# [[Хеширование кукушки]]## Взять в tex знаки = и константы## Добавить интервики## Объединить ссылки с источниками# [[Идеальное хеширование]]## Заменить тире на шаблон## Ссылку на неравенство Маркова оформить как интервики на соответствующий конспект# [[Перехеширование. Амортизационный анализ]]## Оформить функции в lowerCamelCase и обернуть их в тексте в \mathrm## Изменить знаки неравенств## Добавить ссылок# [[Фильтр Блума]]# [[Универсальное семейство хеш-функций]]## Добавить ссылок == 8. [[Сортировка]] ==# [[Сортировка выбором]]## Ссылку через интервики# '''взяли''' [[Сортировка пузырьком]]## Добавить ещё оптимизаций этой сортировки (шейкерная сортировка, расчёской, odd-even и прочие {{---}} полный список есть на [[ wikipedia:en:Bubble_sort | википедии ]]) {{---}} полностью расписывать не надо, только ссылки и краткое описание. Об уменьшии константы в асимптотике можно пару слов сказать, если только она и уменьшается.## Дать точные оценки на число сравнений в худшем случае## Отформатировать псевдокод## Ссылка на вики# '''fixed''' [[Сортировка вставками]]## То же самое, что и в предыдущем тикете## Увеличить дроби## Внести переменные и константы в tex# [[Сортировка Шелла]]# '''взяли''' [[Сортировка кучей]]## Можно добавить всякие модификации сортировки кучей, например, JSort.# ''fixed'' [[Быстрая сортировка]]## Тут вообще ссылки ужасные## Отформатиовать псевдокод# '''fixed''' [[Сортировка слиянием]]## Эта сортировка хорошо параллелится. Но вдруг можно придумать, как манипулировать потоками, чтобы достичь наибольшей эффективности, особенно если одновременно может работать ограниченное число потоков.## Написать псевдокод многопоточной сортировки# [[Cортировка слиянием с использованием O(1) дополнительной памяти]]# [[Теорема о нижней оценке для сортировки сравнениями]]# [[Сортировка подсчетом]]# [[Сортировка подсчетом сложных объектов]]# '''fixed''' [[Цифровая сортировка]]## Добавить модификацию для сортировки цифр в порядке от старших к младшим## Убрать ; из псевдокода# [[Карманная сортировка]]# [[Поиск k-ой порядковой статистики]]# [[Поиск k-ой порядковой статистики за линейное время]]# '''fixed''' [[Сортировка Хана]]## Привести конспект в порядок! ## Добавить шаблоны определений## Добавить шаблоны лемм## Поправить tex, где его нет## Корректно оформить ссылки## Поподробней рассказать про ЭП-дерево## Использование лемм оформить ссылками## Структуру поменять, переставить пункты местами, чтобы не было ссылок в тексте на то, что ещё не рассказывалось## "Конец" в доказательстве выглядит некрасиво. Как и "Доказательство". Опять же, всё сделать шаблонами## Псевдокод добавить, если из описания будет не совсем понятно, как это реализовать (данный пункт допускает возможность поправить идейное описание алгоритма вместо добавление псевдокода)## Возможно, ещё какие-то правки по мелочи## Картинки приветствуются. Если их добавить (или убедить меня, что и так норм, или сделать что-то другое), а всё остальное будет очень няшно сделано, то всё может рассматриваться как целый коспект в баллах.# [[Timsort]]## Последнюю картинку можно сделать более красочной == 9. Сортирующие сети ==# ''fixed'' [[Сортирующие сети]]## Занести оставшиеся определения в [[Шаблон: Определение]]## Англоязычные термины Тикеты ко всем## Ссылки на вики через интервики# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]## Ссылки через интервики## Поменять знаки неравенст в tex на более красивые# [[Сортировочные сети с особыми свойствами]]# [[Сортирующие сети для квадратичных сортировок]]# [[Сеть Бетчера]] == 10. Алгоритмы поиска ==# '''взяли''' [[Целочисленный двоичный поиск]]## Заменить тире на [[Шаблон:---]]## Англоязычные термины## Переменные взять в tex## Отформатировать псевдокод## Добавить категории## <= заменить в tex на \leqslant## Добавить эвристику с запоминанием последнего узла при последовательных запросах и её оценку## Добавить ссылок## Пару слов о том, чем плохо условие на остановку, если вдруг попали в нужный элемент (или чем хорошо)# '''fixed''' [[Вещественный двоичный поиск]]## Плюсы и минусы cпособов оформить по-красивому## Отформатировать псевдокод## Добавить категории## Добавить оценку на число итераций## Больше ссылок# '''взяли''' [[Троичный поиск2ому терму]]## Добавить категории## Добавить ссылок## Отформатировать псевдокод## Сделать так, чтобы картинка не залезала на псевдокод## Англоязычные термины## Увеличить дроби## См. также красиво оформить# '''взяли''' [[Поиск с помощью золотого сечения]]## Отформатировать псевдокод## Дроби увеличить## Добавить категории## Добавить аналогичный, но другое поиск фибоначчи## Небольшой рефакторинг структуры конспекта# '''взяли''' [[Интерполяционный поиск]]## Расположения картинки и псевдокода относительно друг друга не очень удачные## Нормальную картинку сделать## Ссылки нормально оформить## Расписать асимптотику нормально## Отформатировать псевдокод## Примеры данных, на которых поиск работает хорошо
