Алгоритмы и структуры данных:Тикеты — различия между версиями
(→2. Персистентные структуры данных) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 49 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
| − | Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. | + | Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект стек из раздела Амортизационный анализ имеет тикет 1-5). |
== 1. Амортизационный анализ == | == 1. Амортизационный анализ == | ||
| Строка 8: | Строка 8: | ||
## Англоязычные термины | ## Англоязычные термины | ||
## Потенциальный анализ для произвольных A, B, C | ## Потенциальный анализ для произвольных A, B, C | ||
| + | ## См. также | ||
# [[Hashed Array Tree]] 5 | # [[Hashed Array Tree]] 5 | ||
## Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать? | ## Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать? | ||
## Добавить про ''буферизованный'' список | ## Добавить про ''буферизованный'' список | ||
## Редактирование по мелочи | ## Редактирование по мелочи | ||
| + | ## См. также | ||
# [[Список]] | # [[Список]] | ||
| − | # [[Стек]] | + | # [[Стек]] |
# [[Очередь]] | # [[Очередь]] | ||
# [[Дек]] | # [[Дек]] | ||
| Строка 39: | Строка 41: | ||
# [[Двоичная куча]] | # [[Двоичная куча]] | ||
# [[Биномиальная куча]] | # [[Биномиальная куча]] | ||
| − | # [[Фибоначчиева куча]] | + | # [[Фибоначчиева куча]] |
| − | + | # [[Левосторонняя куча]] 0,25 | |
| − | # [[Левосторонняя куча]] | + | ## См. также |
| − | # [[Тонкая куча]] | + | # [[Тонкая куча]] 0,25 |
| + | ## См. также | ||
# [[Толстая куча на избыточном счетчике]] | # [[Толстая куча на избыточном счетчике]] | ||
| − | # [[Куча Бродала-Окасаки]] | + | # [[Куча Бродала-Окасаки]] 4 |
## Ссылки заменить на источники информации, сделать маркированным списком | ## Ссылки заменить на источники информации, сделать маркированным списком | ||
## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge | ## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge | ||
| Строка 52: | Строка 55: | ||
== 4. Система непересекающихся множеств == | == 4. Система непересекающихся множеств == | ||
| − | # [[СНМ (наивные реализации) | Наивные реализации]] | + | # [[СНМ (наивные реализации) | Наивные реализации]] 0.5 |
## Сделать структуру в списке типа Generic | ## Сделать структуру в списке типа Generic | ||
## Написать про возможную частую ошибку в реализации массивом | ## Написать про возможную частую ошибку в реализации массивом | ||
## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt | ## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt | ||
| − | # [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] | + | # [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] 0.5 |
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
## Интервики на амортизационный анализ | ## Интервики на амортизационный анализ | ||
| Строка 62: | Строка 65: | ||
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] | # [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] | ||
| − | # | + | # [[СНМ с операцией удаления за О(1)]] 6 |
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать | ## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать | ||
## Кое-где не хватает точек в конце предложений | ## Кое-где не хватает точек в конце предложений | ||
| Строка 69: | Строка 72: | ||
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find) | ## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find) | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == | + | == 5. Сортировка == |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
:0. [[Сортировка]] | :0. [[Сортировка]] | ||
=== Квадратичные сортировки === | === Квадратичные сортировки === | ||
# [[Сортировка выбором]] | # [[Сортировка выбором]] | ||
| − | # [[Сортировка пузырьком]] | + | # [[Сортировка пузырьком]] 2 |
## Сделать единообразные псевдокоды с равным количеством отступов | ## Сделать единообразные псевдокоды с равным количеством отступов | ||
## Пояснить преимущества каждой модификации сортировки | ## Пояснить преимущества каждой модификации сортировки | ||
| Строка 183: | Строка 90: | ||
<li value="4"> [[Сортировка Шелла]] </li> | <li value="4"> [[Сортировка Шелла]] </li> | ||
<li> [[Сортировка кучей]] </li> | <li> [[Сортировка кучей]] </li> | ||
| − | <li> [[Быстрая сортировка]] | + | <li> [[Быстрая сортировка]] </li> |
<li> [[Сортировка слиянием]] </li> | <li> [[Сортировка слиянием]] </li> | ||
| − | <li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] ( | + | <li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (5) </li> |
# Оформить правильно Источники информации | # Оформить правильно Источники информации | ||
# Добавить категорию | # Добавить категорию | ||
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни | # Написать в начале, зачем оно надо и насколько эффективно в реальной жизни | ||
| + | # Написать подробнее про ассимптотику | ||
| + | # Добавить всевдокод | ||
| + | # Привести конспект в порядок | ||
<li> [[Терпеливая сортировка]] (0.5) </li> | <li> [[Терпеливая сортировка]] (0.5) </li> | ||
# Имена массивов взять в \mathtt | # Имена массивов взять в \mathtt | ||
| Строка 195: | Строка 105: | ||
<li> [[Timsort]] </li> | <li> [[Timsort]] </li> | ||
<li> [[Smoothsort]] </li> | <li> [[Smoothsort]] </li> | ||
| − | <li> [[Теорема о нижней оценке для сортировки сравнениями]] </li> | + | <li> взяли [[Теорема о нижней оценке для сортировки сравнениями]] </li> (4) |
# Заменить знаки неравенств | # Заменить знаки неравенств | ||
# Добавить "информации" в источники | # Добавить "информации" в источники | ||
| Строка 210: | Строка 120: | ||
=== Другие сортировки === | === Другие сортировки === | ||
<ol> | <ol> | ||
| − | <li value="14"> [[Поиск k-ой порядковой статистики]] | + | <li value="14"> [[Поиск k-ой порядковой статистики]] 2 </li> |
# Англоязычные термины | # Англоязычные термины | ||
# Переменные в Tex | # Переменные в Tex | ||
| Строка 222: | Строка 132: | ||
<li> [[Поиск k-ой порядковой статистики за линейное время]] </li> | <li> [[Поиск k-ой порядковой статистики за линейное время]] </li> | ||
<li> [[Поиск k-ой порядковой статистики в двух массивах]] | <li> [[Поиск k-ой порядковой статистики в двух массивах]] | ||
| − | <li> | + | <li> [[Сортировка подсчетом]] </li> |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Цифровая сортировка]] </li> | <li> [[Цифровая сортировка]] </li> | ||
<li> [[Карманная сортировка]] </li> | <li> [[Карманная сортировка]] </li> | ||
| Строка 234: | Строка 138: | ||
# '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется) | # '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется) | ||
<li> [[Задача флага Нидерландов]] </li> | <li> [[Задача флага Нидерландов]] </li> | ||
| + | <li> [[Блинная сортировка]]</li> | ||
</ol> | </ol> | ||
| − | == | + | == 6. Сортирующие сети == |
# [[Сортирующие сети]] | # [[Сортирующие сети]] | ||
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] | # [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] | ||
# [[Сортирующие сети для квадратичных сортировок]] | # [[Сортирующие сети для квадратичных сортировок]] | ||
# [[Сортировочные сети с особыми свойствами]] | # [[Сортировочные сети с особыми свойствами]] | ||
| − | # | + | # [[Сеть Бетчера]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == | + | == 7. Алгоритмы поиска == |
# [[Целочисленный двоичный поиск]] | # [[Целочисленный двоичный поиск]] | ||
# [[Поиск в матрице]] | # [[Поиск в матрице]] | ||
# [[Вещественный двоичный поиск]] | # [[Вещественный двоичный поиск]] | ||
| − | # [[Троичный поиск]] | + | # [[Троичный поиск]] 2 |
## Про == нужно сказать другое | ## Про == нужно сказать другое | ||
## Добавить про унимодальность функции в начале | ## Добавить про унимодальность функции в начале | ||
| Строка 260: | Строка 158: | ||
## Добавить сюда метод дихотомии | ## Добавить сюда метод дихотомии | ||
# [[Поиск с помощью золотого сечения]] | # [[Поиск с помощью золотого сечения]] | ||
| − | # [[Интерполяционный поиск]] | + | # [[Интерполяционный поиск]] 2 |
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском | ## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском | ||
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях | ## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях | ||
| + | # [[Метод Фибоначчи]] 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. Связь между структурами данных == | ||
| + | * [[Связь между структурами данных]] | ||
Текущая версия на 19:27, 4 сентября 2022
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект стек из раздела Амортизационный анализ имеет тикет 1-5).
Содержание
1. Амортизационный анализ
- Амортизационный анализ 0,25
- См. также
- Динамический массив 6
- Сравнение со списком
- Англоязычные термины
- Потенциальный анализ для произвольных A, B, C
- См. также
- Hashed Array Tree 5
- Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
- Добавить про буферизованный список
- Редактирование по мелочи
- См. также
- Список
- Стек
- Очередь
- Дек
- Мажорирующий элемент 0,25
- См. также
- Счетчик Кнута 5
- Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
- Мастер-теорема
- List order maintenance
2. Персистентные структуры данных
- Персистентные структуры данных
- Персистентный стек
- Персистентная очередь
- Персистентный дек
- Персистентная приоритетная очередь 10
- Отрефакторить псевдокод
- Добавить красивые картинки
- Оформить всё правильно
- Добавить наивное решение на дереве
- Подробней описать решение
3. Приоритетные очереди
- Двоичная куча
- Биномиальная куча
- Фибоначчиева куча
- Левосторонняя куча 0,25
- См. также
- Тонкая куча 0,25
- См. также
- Толстая куча на избыточном счетчике
- Куча Бродала-Окасаки 4
- Ссылки заменить на источники информации, сделать маркированным списком
- Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
- Написать подробней операции
- Форматнуть чутка псевдокод
- Заменить Смотри также на См. также
4. Система непересекающихся множеств
- Наивные реализации 0.5
- Сделать структуру в списке типа Generic
- Написать про возможную частую ошибку в реализации массивом
- Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
- Списки с весовой эвристикой 0.5
- Оформить правильно источники информации
- Интервики на амортизационный анализ
- Добавить пробелы в Других реализациях перед (
- Англоязычные термины правильно оформить
- Реализация с помощью леса корневых деревьев
- СНМ с операцией удаления за О(1) 6
- "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
- Кое-где не хватает точек в конце предложений
- Вообще кажется, что можно проще
- Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
- Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
5. Сортировка
- 0. Сортировка
Квадратичные сортировки
- Сортировка выбором
- Сортировка пузырьком 2
- Сделать единообразные псевдокоды с равным количеством отступов
- Пояснить преимущества каждой модификации сортировки
- Подробней расписать comb sort, и почему там n log n?
- Увеличить дроби
- Добавить категорию
- Сортировка вставками
Сортировки на сравнениях
- Сортировка Шелла
- Сортировка кучей
- Быстрая сортировка
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти (5)
- Оформить правильно Источники информации
- Добавить категорию
- Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
- Написать подробнее про ассимптотику
- Добавить всевдокод
- Привести конспект в порядок
- Терпеливая сортировка (0.5)
- Имена массивов взять в \mathtt
- Отформатировать псевдокоды
- Добавить категорию
- Timsort
- Smoothsort
- взяли Теорема о нижней оценке для сортировки сравнениями (4)
- Заменить знаки неравенств
- Добавить "информации" в источники
- Добавить пару следствий из теоремы
- Добавить категорию
Многопоточные сортировки
Другие сортировки
- Поиск k-ой порядковой статистики 2
- Англоязычные термины
- Переменные в Tex
- Отформатировать псевдокод
- Заменить знаки неравенств
- Увеличить дроби
- Оформить правильно Источники информации
- Добавить категории, См. также
- Добавить про модификацию partition с разбиением на 3 части
- Кажется, что не работает, так как partition возвращает абсолютное смещение
- Поиск k-ой порядковой статистики за линейное время
- Поиск k-ой порядковой статистики в двух массивах
- Сортировка подсчетом
- Цифровая сортировка
- Карманная сортировка
- Сортировка Хана
- (10) В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
- Задача флага Нидерландов
- Блинная сортировка
6. Сортирующие сети
- Сортирующие сети
- Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
- Сортирующие сети для квадратичных сортировок
- Сортировочные сети с особыми свойствами
- Сеть Бетчера
7. Алгоритмы поиска
- Целочисленный двоичный поиск
- Поиск в матрице
- Вещественный двоичный поиск
- Троичный поиск 2
- Про == нужно сказать другое
- Добавить про унимодальность функции в начале
- Сказать, почему плохо, когда функция не строго монотонна
- Добавить сюда метод дихотомии
- Поиск с помощью золотого сечения
- Интерполяционный поиск 2
- Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
- Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
- Метод Фибоначчи 2?
- Пример работы алгоритма
- Что-то еще может быть, написать куратору
8. Хеширование
- Хеш-таблица
- Разрешение коллизий
- Хеширование кукушки
- Идеальное хеширование
- Перехеширование. Амортизационный анализ
- Фильтр Блума
- Quotient filter
- Универсальное семейство хеш-функций 0.5
- Добавить ссылок
- Англоязычные термины
- Смотри обсуждения
- Увеличить дроби
- Заменить многоточия на \dots
- Заменить \mod на \bmod
- Заменить знаки неравенств
- Добавить см также
- Расширяемое хеширование (5)
- Красивые картинки
- Понятное описание
