1632
правки
Изменения
м
# [[Hashed Array Tree]]<tex>^\star</tex> 0,25
== 5. Поисковые структуры данных==
:0. [[Поисковые структуры данных]]
# [[Упорядоченное множество]]
# [[Дерево поиска, наивная реализация]]
# [[АВЛ-дерево]]
# [[2-3 дерево]]
# [[B-дерево]]
# [[Красно-черное дерево]]
# [[Декартово дерево]]
# [[Декартово дерево по неявному ключу]] 1
## В псевдокоде нет проверок на ''null''
# [[Splay-дерево]] 0,25
## См. также
# [[Tango-дерево]] 8
## Доказательство теоремы Уилбера
## А причём тут вообще она?
# [[Рандомизированное бинарное дерево поиска]] 0,25
## См. также
# [[Дерево ван Эмде Боаса]]
# [[Список с пропусками]] 7
## \theta cделать большой буквой
## Определение в начале мутное
## Оформить правильно англоязычные термины
## Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
## Увеличить дроби
## Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
## Отформатировать псевдокод
## log заменить на \log
## Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
## Оформить правильно источники информации
## Добавить См. также
## Написать, почему все так любят скиплист, особенно в вычислительной геометрии
# [[Fusion tree]]
# [[Сверхбыстрый цифровой бор]] 2
## Отформатировать псевдокоды
## Сказать, почему префиксы в хеше не буду есть много памяти
## Добавить См. также
## Многоточия заменить на \ldots
# [[Rope]]
# [[AA-дерево]]
== 6. Дерево отрезков==
# [[Статистики на отрезках. Корневая эвристика]]
# [[Дерево отрезков. Построение]]
# [[Реализация запроса в дереве отрезков сверху]] 0.5
## Много пробелов в коде, отформатировать
## Заменить neutral на varepsilon, введя сначала моноид
## Добавить построение в См. также
## В примере случаи разной глубины красиво оформить
# [[Реализация запроса в дереве отрезков снизу]]
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
## Добавить примеры массовых операций в начало
## В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
## Константы взять в tex
## Отформатировать псевдокод
## Обозначения перед псевдокодов взять в \mathtt или в \mathrm
## Оформить правильно источники информации
## Добавить см. также
# [[Многомерное дерево отрезков]]
# [[Сжатое многомерное дерево отрезков]]
== 7. Дерево Фенвика ==
# [[Дерево Фенвика]]
# [[Встречное дерево Фенвика]]
# [[Дерево Фенвика для некоммутативных операций]] 0.25
## Источники информации
# [[Многомерное дерево Фенвика]] 0,25
## См. также
== 8 Задача о наименьшем общем предке ==
# [[Алгоритм Мо]]
# [[Сведение задачи LCA к задаче RMQ]]
# [[Сведение задачи RMQ к задаче LCA]]
# [[Метод двоичного подъема]]
# [[Решение RMQ с помощью разреженной таблицы]]
# [[Двумерная разреженная таблица]]
# [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
# [[Алгоритм Хьюи]]
# [[Heavy-light декомпозиция]]
# [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
# [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
# [[Link-Cut Tree]]<tex>^\star</tex>
# [[Rake-Compress деревья]]<tex>^\star</tex>
== 9. Хеширование ==
# [[Хеш-таблица]] 0,25
## См. также
# [[Разрешение коллизий]]
# [[Хеширование кукушки]] 2
## Англоязычные термины
## Взять в tex знаки = и константы
## Добавить интервики
## Оформить правильно источники информации
## А что делать в случае зацикливания?
## Плюсы-минусы метода
# [[Идеальное хеширование]]
# [[Перехеширование. Амортизационный анализ]] 1
## Пояснить, почему будет O(1) на добавление при перехешировании
# [[Фильтр Блума]] 0,25
## См. также
# [[Quotient filter]] 3
## Сделать нормальное описание алгоритма, а то ничего не понятно
# [[Универсальное семейство хеш-функций]] 0.5
## Добавить ссылок
## Англоязычные термины
## Смотри обсуждения
## Заменить многоточия на \dots
## Заменить \mod на \bmod
## Заменить знаки неравенств
## Добавить "информации" в источники
# [[Расширяемое хеширование]] 5
## Красивые картинки
## Понятное описание
rollbackEdits.php mass rollback
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела(например, конспект стек из раздела Амортизационный анализ имеет тикет 1-5).
== 1. Амортизационный анализ ==
## Англоязычные термины
## Потенциальный анализ для произвольных A, B, C
## См. также
# [[Hashed Array Tree]] 5
## Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
## Добавить про ''буферизованный'' список
## Редактирование по мелочи
## См. также
# [[Список]]
# [[Стек]]
# [[Очередь]]
# [[Дек]]
# [[Двоичная куча]]
# [[Биномиальная куча]]
# [[Фибоначчиева куча]] 5-10## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
# [[Левосторонняя куча]] 0,25
## См. также
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
== 105. Сортировка ==
:0. [[Сортировка]]
=== Квадратичные сортировки ===
<li value="4"> [[Сортировка Шелла]] </li>
<li> [[Сортировка кучей]] </li>
<li> [[Быстрая сортировка]] (''2'') </li>
<li> [[Сортировка слиянием]] </li>
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
# Оформить правильно Источники информации
# Добавить категорию
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
# Написать подробнее про ассимптотику
# Добавить всевдокод
# Привести конспект в порядок
<li> [[Терпеливая сортировка]] (0.5) </li>
# Имена массивов взять в \mathtt
<li> [[Timsort]] </li>
<li> [[Smoothsort]] </li>
<li> взяли [[Теорема о нижней оценке для сортировки сравнениями]] </li>(4)
# Заменить знаки неравенств
# Добавить "информации" в источники
# '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
<li> [[Задача флага Нидерландов]] </li>
<li> [[Блинная сортировка]]</li>
</ol>
== 116. Сортирующие сети ==
# [[Сортирующие сети]]
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
# [[Сеть Бетчера]]
== 117. Алгоритмы поиска ==
# [[Целочисленный двоичный поиск]]
# [[Поиск в матрице]]
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
# [[Метод Фибоначчи]] 2?
## Пример работы алгоритма
## Что-то еще может быть, написать куратору
== 8. Хеширование ==
# [[Хеш-таблица]]
# [[Разрешение коллизий]]
# [[Хеширование кукушки]]
# [[Идеальное хеширование]]
# [[Перехеширование. Амортизационный анализ]]
# [[Фильтр Блума]]
# [[Quotient filter]]
# [[Универсальное семейство хеш-функций]] ''0.5''
## Добавить ссылок
## Англоязычные термины
## Смотри обсуждения
## Увеличить дроби
## Заменить многоточия на \dots
## Заменить \mod на \bmod
## Заменить знаки неравенств
## Добавить см также
# [[Расширяемое хеширование]] (5)
## Красивые картинки
## Понятное описание
<!--
== Динамическое программирование ==
0 [[Динамическое программирование]]
=== 8 Классические задачи динамического программирования ===
# [[Кратчайший путь в ациклическом графе]]
# [[Задача о числе путей в ациклическом графе]]
# [[Задача о расстановке знаков в выражении]]
# [[Задача о порядке перемножения матриц]] (3)
## Взять переменные и константы в Tex
## Обернуть задачу в шаблон
## Интервики на конспект правильных скобочных последовательностей
## Написать, почему нас не устраивает число Каталана в асимптотике
## Отформатировать псевдокоды
## Оформить правильно источники информации
## Убрать про мемоизацию
# [[Задача о наибольшей общей подпоследовательности]]
# [[Задача о наибольшей возрастающей подпоследовательности]]
# [[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
# [[Задача коммивояжера, ДП по подмножествам]]
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
# [[Задача о рюкзаке]]
=== 9 Способы оптимизации методов динамического программирования ===
# [[Метод четырех русских для умножения матриц]]
# [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
# [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
# [[Meet-in-the-middle]]<tex>^\star</tex>
# [[Convex hull trick]]
=== 10 Другие задачи ===
# [[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
# [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
# [[Задача о наибольшей подпоследовательности-палиндроме]]
# [[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
# [[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
# [[Динамическое программирование по профилю]] (7)
## Англоязычные термины
## Заменить умножение на \cdot
## Заменить дефисы на тире
## Взять переменные и константы в Tex
## Отформатировать псевдокоды
## Добавить ещё примеров
## Оформить правильно источники информации
## Добавить нормальное объяснение происходящего (и почему это работает)
# [[Динамика по поддеревьям]]
-->
== 11. Связь между структурами данных ==
* [[Связь между структурами данных]]
