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