Алгоритмы и структуры данных2:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎4 Задача о наименьшем общем предке)
(→‎1. Поисковые структуры данных)
 
(не показано 5 промежуточных версий этого же участника)
Строка 6: Строка 6:
 
# [[АВЛ-дерево]]
 
# [[АВЛ-дерево]]
 
# [[2-3 дерево]]
 
# [[2-3 дерево]]
−
# взяли [[B-дерево]] 0,5
+
# [[B-дерево]]  
−
## все цифры в тех
+
# взяли [[Красно-черное дерево]] 10
−
# [[Красно-черное дерево]] 10
 
 
## добавить псевдокод для операций
 
## добавить псевдокод для операций
 
## расписать доказательства теорем и утверждений подробнее
 
## расписать доказательства теорем и утверждений подробнее
 
# [[Декартово дерево]]
 
# [[Декартово дерево]]
−
# взяли [[Декартово дерево по неявному ключу]] 1
+
# [[Декартово дерево по неявному ключу]]
−
## В псевдокоде нет проверок на ''null''
+
# [[Splay-дерево]]  
−
# взяли [[Splay-дерево]] 0,25
 
−
## См. также
 
 
# [[Взвешенное дерево]]  
 
# [[Взвешенное дерево]]  
 
# [[Tango-дерево]] 8
 
# [[Tango-дерево]] 8
Строка 23: Строка 20:
 
## См. также
 
## См. также
 
# [[Дерево ван Эмде Боаса]]
 
# [[Дерево ван Эмде Боаса]]
−
# [[Список с пропусками]] 7
+
# взяли [[Список с пропусками]] 7
 
## \theta cделать большой буквой
 
## \theta cделать большой буквой
 
## Определение в начале мутное
 
## Определение в начале мутное
Строка 50: Строка 47:
 
== 2. Дерево отрезков==
 
== 2. Дерево отрезков==
 
# [[Статистики на отрезках. Корневая эвристика]]
 
# [[Статистики на отрезках. Корневая эвристика]]
−
# взяли [[Дерево отрезков. Построение]] 0.5
+
# [[Дерево отрезков. Построение]]
−
## Поправить тех
+
# [[Реализация запроса в дереве отрезков сверху]]  
−
## Поправить псевдокод
 
−
# взяли [[Реализация запроса в дереве отрезков сверху]] 0.5
 
−
## Много пробелов в коде, отформатировать
 
−
## Заменить neutral на varepsilon, введя сначала моноид
 
−
## Добавить построение в См. также
 
−
## В примере случаи разной глубины красиво оформить
 
−
## Поправить псевдокод
 
 
# [[Реализация запроса в дереве отрезков снизу]]
 
# [[Реализация запроса в дереве отрезков снизу]]
 
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
 
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
Строка 83: Строка 73:
 
# [[Сведение задачи LCA к задаче RMQ]]
 
# [[Сведение задачи LCA к задаче RMQ]]
 
# [[Сведение задачи RMQ к задаче LCA]]
 
# [[Сведение задачи RMQ к задаче LCA]]
−
# взяли [[Метод двоичного подъема]] 3
+
# [[Метод двоичного подъема]]
−
## добавить пример работы алгоритма
 
 
# [[Решение RMQ с помощью разреженной таблицы]]
 
# [[Решение RMQ с помощью разреженной таблицы]]
 
# [[Двумерная разреженная таблица]]
 
# [[Двумерная разреженная таблица]]
−
# [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
+
# [[Алгоритм Фарака-Колтона и Бендера]]  
 
# [[Алгоритм Хьюи]]
 
# [[Алгоритм Хьюи]]
−
# взяли [[Heavy-light декомпозиция]] 6
+
# [[Heavy-light декомпозиция]]  
−
## "решается с помощью 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>
 
# [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
−
# взяли [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex> 0,25
+
# [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>  
−
## См. также
 
 
# [[Link-Cut Tree]]<tex>^\star</tex>
 
# [[Link-Cut Tree]]<tex>^\star</tex>
−
# взяли [[Rake-Compress деревья]]<tex>^\star</tex> 0,25
+
# [[Rake-Compress деревья]]<tex>^\star</tex>  
−
## Английские термины
 
−
 
 
  
  

Текущая версия на 13:58, 18 мая 2019

1. Поисковые структуры данных

0. Поисковые структуры данных
  1. Упорядоченное множество
  2. Дерево поиска, наивная реализация
  3. АВЛ-дерево
  4. 2-3 дерево
  5. B-дерево
  6. взяли Красно-черное дерево 10
    1. добавить псевдокод для операций
    2. расписать доказательства теорем и утверждений подробнее
  7. Декартово дерево
  8. Декартово дерево по неявному ключу
  9. Splay-дерево
  10. Взвешенное дерево
  11. Tango-дерево 8
    1. Доказательство теоремы Уилбера
    2. А причём тут вообще она?
  12. взяли Рандомизированное бинарное дерево поиска 0,25
    1. См. также
  13. Дерево ван Эмде Боаса
  14. взяли Список с пропусками 7
    1. \theta cделать большой буквой
    2. Определение в начале мутное
    3. Оформить правильно англоязычные термины
    4. Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
    5. Увеличить дроби
    6. Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
    7. Отформатировать псевдокод
    8. log заменить на \log
    9. Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
    10. Оформить правильно источники информации
    11. Добавить См. также
    12. Написать, почему все так любят скиплист, особенно в вычислительной геометрии
  15. Fusion tree
  16. Сверхбыстрый цифровой бор 2
    1. Отформатировать псевдокоды
    2. Сказать, почему префиксы в хеше не буду есть много памяти
    3. Добавить См. также
    4. Многоточия заменить на \ldots
  17. Rope
  18. AA-дерево
  19. Техника частичного каскадирования
    1. Правильно оформить источники информации
  20. Centroid decomposition

2. Дерево отрезков

  1. Статистики на отрезках. Корневая эвристика
  2. Дерево отрезков. Построение
  3. Реализация запроса в дереве отрезков сверху
  4. Реализация запроса в дереве отрезков снизу
  5. Несогласованные поддеревья. Реализация массового обновления 3
    1. Добавить примеры массовых операций в начало
    2. В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
    3. Константы взять в tex
    4. Отформатировать псевдокод
    5. Обозначения перед псевдокодов взять в \mathtt или в \mathrm
    6. Оформить правильно источники информации
    7. Добавить см. также
  6. Многомерное дерево отрезков
  7. Сжатое многомерное дерево отрезков

3. Дерево Фенвика

  1. Дерево Фенвика
  2. Встречное дерево Фенвика
  3. взяли Дерево Фенвика для некоммутативных операций 0.25
    1. Источники информации
  4. взяли Многомерное дерево Фенвика 0,25
    1. См. также

4 Задача о наименьшем общем предке

  1. Алгоритм Мо
  2. Сведение задачи LCA к задаче RMQ
  3. Сведение задачи RMQ к задаче LCA
  4. Метод двоичного подъема
  5. Решение RMQ с помощью разреженной таблицы
  6. Двумерная разреженная таблица
  7. Алгоритм Фарака-Колтона и Бендера
  8. Алгоритм Хьюи
  9. Heavy-light декомпозиция
  10. Алгоритм Шибера-Вишкина[math]^\star[/math]
  11. Алгоритм Тарьяна поиска LCA за O(1) в оффлайн[math]^\star[/math]
  12. Link-Cut Tree[math]^\star[/math]
  13. Rake-Compress деревья[math]^\star[/math]


Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_и_структуры_данных2:Тикеты&oldid=71255»