Изменения

Перейти к: навигация, поиск

Алгоритмы и структуры данных:Тикеты

5220 байт убрано, 22:25, 12 ноября 2018
→‎Сортировки на сравнениях
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела(например, конспект стек из раздела Амортизационный анализ имеет тикет 1-5).
== 1. Амортизационный анализ ==
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
== 5. Поисковые структуры данных==
:0. [[Поисковые структуры данных]]
# [[Упорядоченное множество]]
# [[Дерево поиска, наивная реализация]]
# [[АВЛ-дерево]]
# [[2-3 дерево]]
# [[B-дерево]]
# взяли [[Красно-черное дерево]] 10
## добавить псевдокод для операций
## расписать доказательства теорем и утверждений подробнее
# [[Декартово дерево]]
# [[Декартово дерево по неявному ключу]] 1
## В псевдокоде нет проверок на ''null''
# [[Splay-дерево]] 0,25
## См. также
# взяли [[Взвешенное дерево]] 8
## Категории
## Написать реализацию дерева и операции над ним
## Нарисовать картинки с примерами операций над этим деревом
# [[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]]
# [[Метод двоичного подъема]] 3
## добавить пример работы алгоритма
# [[Решение RMQ с помощью разреженной таблицы]]
# [[Двумерная разреженная таблица]]
# [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
# [[Алгоритм Хьюи]]
# [[Heavy-light декомпозиция]] 6
## "решается с помощью heavy-light декомпозиции" — может быть решена
## "Пусть A, B - ко" — дефисы нужно заменить на тире
## В начале у тебя идут вершины a,b и A,B, а потом u,v и a,b. Надо сделать единообразно, чтобы начало конспекта и его конец согласовывались. Например, сделать корни путей большими буквами — норм. Тогда можно либо a,b и A,B, либо u,v и U,V.
## "В данном случае корень одного из путей является вершиной другого." — а почему пути не могут пересекаться крест-на-крест?
## Слишком много повтором «Пусть» в доказательстве леммы.
## "Но LCA должен принадлежать двум путям. Но" — дублирование «Но»
## "Предположим, что LCA не равны" — криво написано, нужно формально исходя из формулировки
## Ну и вообще, как будто слов пожадничал на лемму и кое-как написал
## "Построим декомпозицию." — декомпозицию чего и для чего? Очень плохо оставлять открытый контекст, особенно в начале пункта. Лучше чуть более подробно описать, чтобы было понятно
## "Корень пути, на котором лежит текущая вершина.
## Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева." — вообще непонятно, как связано то, что мы хотим сохранить с тем, что написано потом. Нет предложения-связки
## "Пусть требуется" — опять пуст
## "Пусть на данной итерации" — как будто других слов нет
## "LCA будет та" — это не по-русски
## Возьми LCA в тексте везде в \mathrm
## "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?
# [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
# [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex> 0,25
## См. также
# [[Link-Cut Tree]]<tex>^\star</tex>
# [[Rake-Compress деревья]]<tex>^\star</tex> 0,25
## Английские термины
== 9. Хеширование ==# [[Хеш-таблица]] 0,25## См. также# [[Разрешение коллизий]] # взяли [[Хеширование кукушки]] 2## Англоязычные термины## Взять в tex знаки = и константы## Добавить интервики## Оформить правильно источники информации## А что делать в случае зацикливания?## Плюсы-минусы метода# [[Идеальное хеширование]]# [[Перехеширование. Амортизационный анализ]] 1## Пояснить, почему будет O(1) на добавление при перехешировании# [[Фильтр Блума]] 0,25## См. также# [[Quotient filter]] 3## Сделать нормальное описание алгоритма, а то ничего не понятно# [[Универсальное семейство хеш-функций]] 0.5## Добавить ссылок## Англоязычные термины## Смотри обсуждения## Заменить многоточия на \dots## Заменить \mod на \bmod## Заменить знаки неравенств## Добавить "информации" в источники# [[Расширяемое хеширование]] 5## Красивые картинки## Понятное описание == 10. Сортировка ==
:0. [[Сортировка]]
=== Квадратичные сортировки ===
<li> [[Быстрая сортировка]] </li>
<li> [[Сортировка слиянием]] </li>
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
# Оформить правильно Источники информации
# Добавить категорию
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
# Написать подробнее про ассимптотику
# Добавить всевдокод
# Привести конспект в порядок
<li> [[Терпеливая сортировка]] (0.5) </li>
# Имена массивов взять в \mathtt
<li> [[Timsort]] </li>
<li> [[Smoothsort]] </li>
<li> взяли [[Теорема о нижней оценке для сортировки сравнениями]] </li> (4)
# Заменить знаки неравенств
# Добавить "информации" в источники
</ol>
== 116. Сортирующие сети ==
# [[Сортирующие сети]]
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
# [[Сеть Бетчера]]
== 127. Алгоритмы поиска ==
# [[Целочисленный двоичный поиск]]
# [[Поиск в матрице]]
## Что-то еще может быть, написать куратору
== 138. Хеширование ==# [[Хеш-таблица]]# [[Разрешение коллизий]] # [[Хеширование кукушки]]# [[Идеальное хеширование]]# [[Перехеширование. Амортизационный анализ]] # [[Фильтр Блума]] # [[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. Связь между структурами данных ==
* [[Связь между структурами данных]]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/61894...66746»

Навигация