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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎1. Амортизационный анализ)
м (rollbackEdits.php mass rollback)
 
(не показано 17 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
+
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект стек из раздела Амортизационный анализ имеет тикет 1-5).
  
 
== 1. Амортизационный анализ ==
 
== 1. Амортизационный анализ ==
Строка 41: Строка 41:
 
# [[Двоичная куча]]
 
# [[Двоичная куча]]
 
# [[Биномиальная куча]]
 
# [[Биномиальная куча]]
−
# взяли [[Фибоначчиева куча]] 5-10
+
# [[Фибоначчиева куча]]  
−
## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
 
 
# [[Левосторонняя куча]] 0,25
 
# [[Левосторонняя куча]] 0,25
 
## См. также
 
## См. также
Строка 73: Строка 72:
 
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
 
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время 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. Хеширование ==
+
== 5. Сортировка ==
−
# [[Хеш-таблица]] 0,25
 
−
## См. также
 
−
# [[Разрешение коллизий]]
 
−
# взяли [[Хеширование кукушки]] 2
 
−
## Англоязычные термины
 
−
## Взять в tex знаки = и константы
 
−
## Добавить интервики
 
−
## Оформить правильно источники информации
 
−
## А что делать в случае зацикливания?
 
−
## Плюсы-минусы метода
 
−
# [[Идеальное хеширование]]
 
−
# [[Перехеширование. Амортизационный анализ]] 1
 
−
## Пояснить, почему будет O(1) на добавление при перехешировании
 
−
# [[Фильтр Блума]] 0,25
 
−
## См. также
 
−
# [[Quotient filter]] 3
 
−
## Сделать нормальное описание алгоритма, а то ничего не понятно
 
−
# [[Универсальное семейство хеш-функций]] 0.5
 
−
## Добавить ссылок
 
−
## Англоязычные термины
 
−
## Смотри обсуждения
 
−
## Заменить многоточия на \dots
 
−
## Заменить \mod на \bmod
 
−
## Заменить знаки неравенств
 
−
## Добавить "информации" в источники
 
−
# [[Расширяемое хеширование]] 5
 
−
## Красивые картинки
 
−
## Понятное описание
 
−
 
 
−
== 10. Сортировка ==
 
 
:0. [[Сортировка]]
 
:0. [[Сортировка]]
 
=== Квадратичные сортировки ===
 
=== Квадратичные сортировки ===
Строка 230: Строка 92:
 
<li> [[Быстрая сортировка]] </li>
 
<li> [[Быстрая сортировка]] </li>
 
<li> [[Сортировка слиянием]] </li>
 
<li> [[Сортировка слиянием]] </li>
−
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
+
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (5) </li>
 
# Оформить правильно Источники информации
 
# Оформить правильно Источники информации
 
# Добавить категорию
 
# Добавить категорию
 
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
 
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
 +
# Написать подробнее про ассимптотику
 +
# Добавить всевдокод
 +
# Привести конспект в порядок
 
<li> [[Терпеливая сортировка]] (0.5) </li>
 
<li> [[Терпеливая сортировка]] (0.5) </li>
 
# Имена массивов взять в \mathtt
 
# Имена массивов взять в \mathtt
Строка 240: Строка 105:
 
<li> [[Timsort]] </li>
 
<li> [[Timsort]] </li>
 
<li> [[Smoothsort]] </li>
 
<li> [[Smoothsort]] </li>
−
<li> [[Теорема о нижней оценке для сортировки сравнениями]] </li> (4)
+
<li> взяли [[Теорема о нижней оценке для сортировки сравнениями]] </li> (4)
 
# Заменить знаки неравенств
 
# Заменить знаки неравенств
 
# Добавить "информации" в источники
 
# Добавить "информации" в источники
Строка 276: Строка 141:
 
</ol>
 
</ol>
  
−
== 11. Сортирующие сети ==
+
== 6. Сортирующие сети ==
 
# [[Сортирующие сети]]
 
# [[Сортирующие сети]]
 
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
Строка 283: Строка 148:
 
# [[Сеть Бетчера]]
 
# [[Сеть Бетчера]]
  
−
== 12. Алгоритмы поиска ==
+
== 7. Алгоритмы поиска ==
 
# [[Целочисленный двоичный поиск]]
 
# [[Целочисленный двоичный поиск]]
 
# [[Поиск в матрице]]
 
# [[Поиск в матрице]]
Строка 300: Строка 165:
 
## Что-то еще может быть, написать куратору
 
## Что-то еще может быть, написать куратору
  
−
== 13. Связь между структурами данных ==
+
== 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. Связь между структурами данных ==
 
* [[Связь между структурами данных]]
 
* [[Связь между структурами данных]]

Текущая версия на 19:27, 4 сентября 2022

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект стек из раздела Амортизационный анализ имеет тикет 1-5).

1. Амортизационный анализ

  1. Амортизационный анализ 0,25
    1. См. также
  2. Динамический массив 6
    1. Сравнение со списком
    2. Англоязычные термины
    3. Потенциальный анализ для произвольных A, B, C
    4. См. также
  3. Hashed Array Tree 5
    1. Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
    2. Добавить про буферизованный список
    3. Редактирование по мелочи
    4. См. также
  4. Список
  5. Стек
  6. Очередь
  7. Дек
  8. Мажорирующий элемент 0,25
    1. См. также
  9. Счетчик Кнута 5
    1. Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
  10. Мастер-теорема
  11. List order maintenance

2. Персистентные структуры данных

  1. Персистентные структуры данных
  2. Персистентный стек
  3. Персистентная очередь
  4. Персистентный дек
  5. Персистентная приоритетная очередь 10
    1. Отрефакторить псевдокод
    2. Добавить красивые картинки
    3. Оформить всё правильно
    4. Добавить наивное решение на дереве
    5. Подробней описать решение

3. Приоритетные очереди

0. Приоритетные очереди
  1. Двоичная куча
  2. Биномиальная куча
  3. Фибоначчиева куча
  4. Левосторонняя куча 0,25
    1. См. также
  5. Тонкая куча 0,25
    1. См. также
  6. Толстая куча на избыточном счетчике
  7. Куча Бродала-Окасаки 4
    1. Ссылки заменить на источники информации, сделать маркированным списком
    2. Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
    3. Написать подробней операции
    4. Форматнуть чутка псевдокод
    5. Заменить Смотри также на См. также

4. Система непересекающихся множеств

  1. Наивные реализации 0.5
    1. Сделать структуру в списке типа Generic
    2. Написать про возможную частую ошибку в реализации массивом
    3. Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
  2. Списки с весовой эвристикой 0.5
    1. Оформить правильно источники информации
    2. Интервики на амортизационный анализ
    3. Добавить пробелы в Других реализациях перед (
    4. Англоязычные термины правильно оформить
  3. Реализация с помощью леса корневых деревьев
  4. СНМ с операцией удаления за О(1) 6
    1. "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
    2. Кое-где не хватает точек в конце предложений
    3. Вообще кажется, что можно проще
    4. Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
    5. Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)


5. Сортировка

0. Сортировка

Квадратичные сортировки

  1. Сортировка выбором
  2. Сортировка пузырьком 2
    1. Сделать единообразные псевдокоды с равным количеством отступов
    2. Пояснить преимущества каждой модификации сортировки
    3. Подробней расписать comb sort, и почему там n log n?
    4. Увеличить дроби
    5. Добавить категорию
  3. Сортировка вставками

Сортировки на сравнениях

  1. Сортировка Шелла
  2. Сортировка кучей
  3. Быстрая сортировка
  4. Сортировка слиянием
  5. Cортировка слиянием с использованием O(1) дополнительной памяти (5)
    1. Оформить правильно Источники информации
    2. Добавить категорию
    3. Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
    4. Написать подробнее про ассимптотику
    5. Добавить всевдокод
    6. Привести конспект в порядок
  6. Терпеливая сортировка (0.5)
    1. Имена массивов взять в \mathtt
    2. Отформатировать псевдокоды
    3. Добавить категорию
  7. Timsort
  8. Smoothsort
  9. взяли Теорема о нижней оценке для сортировки сравнениями
    10. (4)
    1. Заменить знаки неравенств
    2. Добавить "информации" в источники
    3. Добавить пару следствий из теоремы
    4. Добавить категорию

Многопоточные сортировки

  1. Многопоточная сортировка слиянием
  2. PSRS-сортировка

Другие сортировки

  1. Поиск k-ой порядковой статистики 2
    1. Англоязычные термины
    2. Переменные в Tex
    3. Отформатировать псевдокод
    4. Заменить знаки неравенств
    5. Увеличить дроби
    6. Оформить правильно Источники информации
    7. Добавить категории, См. также
    8. Добавить про модификацию partition с разбиением на 3 части
    9. Кажется, что не работает, так как partition возвращает абсолютное смещение
  2. Поиск k-ой порядковой статистики за линейное время
  3. Поиск k-ой порядковой статистики в двух массивах
  4. Сортировка подсчетом
  5. Цифровая сортировка
  6. Карманная сортировка
  7. Сортировка Хана
    1. (10) В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
  8. Задача флага Нидерландов
  9. Блинная сортировка

6. Сортирующие сети

  1. Сортирующие сети
  2. Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
  3. Сортирующие сети для квадратичных сортировок
  4. Сортировочные сети с особыми свойствами
  5. Сеть Бетчера

7. Алгоритмы поиска

  1. Целочисленный двоичный поиск
  2. Поиск в матрице
  3. Вещественный двоичный поиск
  4. Троичный поиск 2
    1. Про == нужно сказать другое
    2. Добавить про унимодальность функции в начале
    3. Сказать, почему плохо, когда функция не строго монотонна
    4. Добавить сюда метод дихотомии
  5. Поиск с помощью золотого сечения
  6. Интерполяционный поиск 2
    1. Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
    2. Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
  7. Метод Фибоначчи 2?
    1. Пример работы алгоритма
    2. Что-то еще может быть, написать куратору

8. Хеширование

  1. Хеш-таблица
  2. Разрешение коллизий
  3. Хеширование кукушки
  4. Идеальное хеширование
  5. Перехеширование. Амортизационный анализ
  6. Фильтр Блума
  7. Quotient filter
  8. Универсальное семейство хеш-функций 0.5
    1. Добавить ссылок
    2. Англоязычные термины
    3. Смотри обсуждения
    4. Увеличить дроби
    5. Заменить многоточия на \dots
    6. Заменить \mod на \bmod
    7. Заменить знаки неравенств
    8. Добавить см также
  9. Расширяемое хеширование (5)
    1. Красивые картинки
    2. Понятное описание

11. Связь между структурами данных

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