Участник:Shersh/Тикеты ко 2ому терму — различия между версиями
Shersh (обсуждение | вклад) м (→4. Поисковые структуры данных) |
Shersh (обсуждение | вклад) м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты ко 2ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))) |
||
| (не показано 89 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. | Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. | ||
| − | == | + | == 1. Амортизационный анализ == |
| − | # '' | + | # ''fixed'' [[Амортизационный анализ]] (0.5) |
## Англоязычные термины | ## Англоязычные термины | ||
## Нормальный нумерованный список | ## Нормальный нумерованный список | ||
| − | + | # '''!!!''' [[Динамический массив]] (''6'') | |
| − | # ''' | ||
## Сравнение со списком | ## Сравнение со списком | ||
## Англоязычные термины | ## Англоязычные термины | ||
| Строка 15: | Строка 14: | ||
## Редактирование по мелочи | ## Редактирование по мелочи | ||
# [[Список]] | # [[Список]] | ||
| − | # | + | # [[Стек]] |
| − | + | # [[Очередь]] | |
| − | + | # [[Дек]] | |
| − | # | + | # [[Мажорирующий элемент]] |
| − | |||
| − | |||
| − | # | ||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# '''!!!''' [[Счетчик Кнута]] (''5'') | # '''!!!''' [[Счетчик Кнута]] (''5'') | ||
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда) | ## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда) | ||
| + | # [[Мастер-теорема]] | ||
| + | # [[List order maintenance]] | ||
| − | == | + | == 2. Персистентные структуры данных == |
| − | # | + | # [[Персистентные структуры данных]] |
| − | + | # [[Персистентный стек]] | |
| − | + | # [[Персистентная очередь]] | |
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Персистентный дек]] | # [[Персистентный дек]] | ||
| + | # '''fixed''' [[Персистентная приоритетная очередь]] (10) | ||
| + | ## Отрефакторить псевдокод | ||
| + | ## Добавить красивые картинки | ||
| + | ## Оформить всё правильно | ||
| + | ## Добавить наивное решение на дереве | ||
| + | ## Подробней описать решение | ||
| − | == | + | == 3. Приоритетные очереди == |
| − | : 0. | + | : 0. [[Приоритетные очереди]] |
| − | + | # [[Двоичная куча]] | |
| − | + | # [[Биномиальная куча]] | |
| − | + | # '''!!!''' [[Фибоначчиева куча]] (5-10) | |
| − | + | ## В конспекте лаже, уже первое определение неверное. Надо переписать нормально. | |
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | ## | ||
| − | |||
| − | |||
# [[Левосторонняя куча]] | # [[Левосторонняя куча]] | ||
| − | # | + | # [[Тонкая куча]] |
| − | # | + | # [[Толстая куча на избыточном счетчике]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Куча Бродала-Окасаки]] (''4'') | # [[Куча Бродала-Окасаки]] (''4'') | ||
## Ссылки заменить на источники информации, сделать маркированным списком | ## Ссылки заменить на источники информации, сделать маркированным списком | ||
| Строка 93: | Строка 51: | ||
## Заменить Смотри также на См. также | ## Заменить Смотри также на См. также | ||
| − | == | + | == 4. Система непересекающихся множеств == |
| − | # | + | # [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'') |
## Сделать структуру в списке типа Generic | ## Сделать структуру в списке типа Generic | ||
## Написать про возможную частую ошибку в реализации массивом | ## Написать про возможную частую ошибку в реализации массивом | ||
## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt | ## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt | ||
| − | # | + | # [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] (''0.5'') |
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
## Интервики на амортизационный анализ | ## Интервики на амортизационный анализ | ||
## Добавить пробелы в Других реализациях перед ( | ## Добавить пробелы в Других реализациях перед ( | ||
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
| − | # | + | # [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] |
| − | + | # '''!!!''' [[СНМ с операцией удаления за О(1)]] (''6'') | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # ''' | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать | ## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать | ||
| − | |||
## Кое-где не хватает точек в конце предложений | ## Кое-где не хватает точек в конце предложений | ||
| + | ## Вообще кажется, что можно проще | ||
## Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё. | ## Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё. | ||
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find) | ## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find) | ||
| − | == | + | == 5. Поисковые структуры данных== |
| − | :0. | + | :0. [[Поисковые структуры данных]] |
| − | + | # [[Упорядоченное множество]] | |
| − | + | # [[Дерево поиска, наивная реализация]] | |
| − | + | # [[АВЛ-дерево]] | |
| − | + | # [[2-3 дерево]] | |
| − | + | # [[B-дерево]] | |
| − | + | # [[Красно-черное дерево]] | |
| − | # | + | # [[Декартово дерево]] |
| − | + | # [[Декартово дерево по неявному ключу]] (1) | |
| − | + | ## В псевдокоде нет проверок на ''null'' | |
| − | + | # [[Splay-дерево]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | ## | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# '''!!!''' [[Tango-дерево]] (''8'') | # '''!!!''' [[Tango-дерево]] (''8'') | ||
## Доказательство теоремы Уилбера | ## Доказательство теоремы Уилбера | ||
## А причём тут вообще она? | ## А причём тут вообще она? | ||
| − | # | + | # [[Рандомизированное бинарное дерево поиска]] |
| − | + | # [[Дерево ван Эмде Боаса]] | |
| − | + | # '''!!!''' [[Список с пропусками]] (''7'') | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # ''' | ||
## \theta cделать большой буквой | ## \theta cделать большой буквой | ||
## Определение в начале мутное | ## Определение в начале мутное | ||
| Строка 237: | Строка 99: | ||
## Добавить См. также | ## Добавить См. также | ||
## Написать, почему все так любят скиплист, особенно в вычислительной геометрии | ## Написать, почему все так любят скиплист, особенно в вычислительной геометрии | ||
| − | # | + | # [[Fusion tree]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Сверхбыстрый цифровой бор]] (''2'') | # [[Сверхбыстрый цифровой бор]] (''2'') | ||
## Отформатировать псевдокоды | ## Отформатировать псевдокоды | ||
| Строка 251: | Строка 105: | ||
## Добавить См. также | ## Добавить См. также | ||
## Многоточия заменить на \ldots | ## Многоточия заменить на \ldots | ||
| − | # [[Rope]] | + | # [[Rope]] |
| − | |||
| − | |||
| − | == | + | == 6. Дерево отрезков== |
| − | # | + | # [[Статистики на отрезках. Корневая эвристика]] |
| − | + | # [[Дерево отрезков. Построение]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Реализация запроса в дереве отрезков сверху]] (''0.5'') | # [[Реализация запроса в дереве отрезков сверху]] (''0.5'') | ||
## Много пробелов в коде, отформатировать | ## Много пробелов в коде, отформатировать | ||
| Строка 286: | Строка 124: | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
## Добавить см. также | ## Добавить см. также | ||
| − | # | + | # [[Многомерное дерево отрезков]] |
| − | + | # ''fixed'' [[Сжатое многомерное дерево отрезков]] (''1'') | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
## Англоязычные термины | ## Англоязычные термины | ||
| Строка 300: | Строка 133: | ||
## Добавить категории | ## Добавить категории | ||
| − | == | + | == 7. Дерево Фенвика == |
| − | # | + | # [[Дерево Фенвика]] |
| − | + | # [[Встречное дерево Фенвика]] | |
| − | + | # [[Дерево Фенвика для некоммутативных операций]] | |
| − | + | # [[Многомерное дерево Фенвика]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == | + | == 8. Хеширование == |
| − | # | + | # [[Хеш-таблица]] |
| − | + | # [[Разрешение коллизий]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Хеширование кукушки]] (''2'') | # [[Хеширование кукушки]] (''2'') | ||
## Англоязычные термины | ## Англоязычные термины | ||
| Строка 368: | Строка 149: | ||
## А что делать в случае зацикливания? | ## А что делать в случае зацикливания? | ||
## Плюсы-минусы метода | ## Плюсы-минусы метода | ||
| − | # | + | # [[Идеальное хеширование]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Перехеширование. Амортизационный анализ]] (''1'') | # [[Перехеширование. Амортизационный анализ]] (''1'') | ||
## Пояснить, почему будет O(1) на добавление при перехешировании | ## Пояснить, почему будет O(1) на добавление при перехешировании | ||
| − | # [[Фильтр Блума]] ( | + | # [[Фильтр Блума]] (1.5) |
| − | # | + | # [[Quotient filter]] (3) |
| − | + | ## Сделать нормальное описание алгоритма, а то ничего не понятно | |
| − | ## | + | # [[Универсальное семейство хеш-функций]] (''0.5'') |
| − | # | ||
## Добавить ссылок | ## Добавить ссылок | ||
## Англоязычные термины | ## Англоязычные термины | ||
| Строка 388: | Строка 163: | ||
## Заменить знаки неравенств | ## Заменить знаки неравенств | ||
## Добавить "информации" в источники | ## Добавить "информации" в источники | ||
| + | # '''!!!''' [[Расширяемое хеширование]] (5) | ||
| + | ## Красивые картинки | ||
| + | ## Понятное описание | ||
| − | == | + | == 9. Сортировка == |
| − | :0. | + | :0. [[Сортировка]] |
| − | |||
| − | |||
| − | |||
| − | |||
=== Квадратичные сортировки === | === Квадратичные сортировки === | ||
| − | # | + | # [[Сортировка выбором]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Сортировка пузырьком]] (''2'') | # [[Сортировка пузырьком]] (''2'') | ||
## Сделать единообразные псевдокоды с равным количеством отступов | ## Сделать единообразные псевдокоды с равным количеством отступов | ||
| Строка 410: | Строка 177: | ||
## Увеличить дроби | ## Увеличить дроби | ||
## Добавить категорию | ## Добавить категорию | ||
| − | # | + | # [[Сортировка вставками]] |
| − | |||
| − | |||
| − | |||
| − | |||
=== Сортировки на сравнениях === | === Сортировки на сравнениях === | ||
<ol> | <ol> | ||
| − | <li value="4"> [[Сортировка Шелла]] | + | <li value="4"> [[Сортировка Шелла]] </li> |
| − | + | <li> [[Сортировка кучей]] </li> | |
| − | + | <li> [[Быстрая сортировка]] (''2'') </li> | |
| − | + | <li> [[Сортировка слиянием]] </li> | |
| − | + | <li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li> | |
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> [[Быстрая сортировка]] ('' | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
# Оформить правильно Источники информации | # Оформить правильно Источники информации | ||
# Добавить категорию | # Добавить категорию | ||
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни | # Написать в начале, зачем оно надо и насколько эффективно в реальной жизни | ||
| − | <li> [[Терпеливая сортировка]] (0. | + | <li> [[Терпеливая сортировка]] (0.5) </li> |
# Имена массивов взять в \mathtt | # Имена массивов взять в \mathtt | ||
# Отформатировать псевдокоды | # Отформатировать псевдокоды | ||
# Добавить категорию | # Добавить категорию | ||
| − | <li> | + | <li> [[Timsort]] </li> |
| − | + | <li> [[Smoothsort]] </li> | |
| − | + | <li> [[Теорема о нижней оценке для сортировки сравнениями]] </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
# Заменить знаки неравенств | # Заменить знаки неравенств | ||
# Добавить "информации" в источники | # Добавить "информации" в источники | ||
| Строка 481: | Строка 204: | ||
=== Многопоточные сортировки === | === Многопоточные сортировки === | ||
<ol> | <ol> | ||
| − | <li value="12"> | + | <li value="12"> [[Многопоточная сортировка слиянием]] </li> |
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[PSRS-сортировка]] </li> | <li> [[PSRS-сортировка]] </li> | ||
</ol> | </ol> | ||
| Строка 491: | Строка 210: | ||
=== Другие сортировки === | === Другие сортировки === | ||
<ol> | <ol> | ||
| − | <li value="14"> [[Поиск k-ой порядковой статистики]] ('' | + | <li value="14"> [[Поиск k-ой порядковой статистики]] (''2'') </li> |
# Англоязычные термины | # Англоязычные термины | ||
# Переменные в Tex | # Переменные в Tex | ||
| Строка 500: | Строка 219: | ||
# Добавить категории, См. также | # Добавить категории, См. также | ||
# Добавить про модификацию partition с разбиением на 3 части | # Добавить про модификацию partition с разбиением на 3 части | ||
| − | <li> | + | # Кажется, что не работает, так как partition возвращает абсолютное смещение |
| − | + | <li> [[Поиск k-ой порядковой статистики за линейное время]] </li> | |
| − | + | <li> [[Поиск k-ой порядковой статистики в двух массивах]] | |
| − | + | <li> ''fixed'' [[Сортировка подсчетом]] (''1'') </li> | |
| − | |||
| − | |||
| − | |||
| − | <li> '' | ||
# Англоязычные термины | # Англоязычные термины | ||
# Отформартировать псевдокод | # Отформартировать псевдокод | ||
| Строка 515: | Строка 230: | ||
# Добавить категорию | # Добавить категорию | ||
<li> [[Цифровая сортировка]] </li> | <li> [[Цифровая сортировка]] </li> | ||
| − | <li> | + | <li> [[Карманная сортировка]] </li> |
| − | + | <li> [[Сортировка Хана]] </li> | |
| − | + | # '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется) | |
| − | + | <li> [[Задача флага Нидерландов]] </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ol> | </ol> | ||
| − | == | + | == 10. Сортирующие сети == |
| − | # | + | # [[Сортирующие сети]] |
| − | + | # [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] | |
| − | + | # [[Сортирующие сети для квадратичных сортировок]] | |
| − | # | + | # [[Сортировочные сети с особыми свойствами]] |
| − | + | # ''fixed'' [[Сеть Бетчера]] (''0.5'') | |
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
## Оформить правильно англ. термины | ## Оформить правильно англ. термины | ||
## Внутренние ссылки оформить примечаниями | ## Внутренние ссылки оформить примечаниями | ||
| Строка 566: | Строка 250: | ||
## Добавить См. также | ## Добавить См. также | ||
| − | == | + | == 11. Алгоритмы поиска == |
| − | # | + | # [[Целочисленный двоичный поиск]] |
| − | # | + | # [[Поиск в матрице]] |
| − | |||
| − | |||
| − | |||
| − | |||
# [[Вещественный двоичный поиск]] | # [[Вещественный двоичный поиск]] | ||
# [[Троичный поиск]] (''2'') | # [[Троичный поиск]] (''2'') | ||
| Строка 579: | Строка 259: | ||
## Сказать, почему плохо, когда функция не строго монотонна | ## Сказать, почему плохо, когда функция не строго монотонна | ||
## Добавить сюда метод дихотомии | ## Добавить сюда метод дихотомии | ||
| − | # | + | # [[Поиск с помощью золотого сечения]] |
| − | + | # [[Интерполяционный поиск]] (2) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Интерполяционный поиск]] ( | ||
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском | ## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском | ||
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях | ## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях | ||
Текущая версия на 19:15, 23 февраля 2017
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
Содержание
1. Амортизационный анализ
- fixed Амортизационный анализ (0.5)
- Англоязычные термины
- Нормальный нумерованный список
- !!! Динамический массив (6)
- Сравнение со списком
- Англоязычные термины
- Потенциальный анализ для произвольных A, B, C
- !!! Hashed Array Tree (5)
- Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
- Добавить про буферизованный список
- Редактирование по мелочи
- Список
- Стек
- Очередь
- Дек
- Мажорирующий элемент
- !!! Счетчик Кнута (5)
- Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
- Мастер-теорема
- List order maintenance
2. Персистентные структуры данных
- Персистентные структуры данных
- Персистентный стек
- Персистентная очередь
- Персистентный дек
- fixed Персистентная приоритетная очередь (10)
- Отрефакторить псевдокод
- Добавить красивые картинки
- Оформить всё правильно
- Добавить наивное решение на дереве
- Подробней описать решение
3. Приоритетные очереди
- Двоичная куча
- Биномиальная куча
- !!! Фибоначчиева куча (5-10)
- В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
- Левосторонняя куча
- Тонкая куча
- Толстая куча на избыточном счетчике
- Куча Бродала-Окасаки (4)
- Ссылки заменить на источники информации, сделать маркированным списком
- Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
- Написать подробней операции
- Форматнуть чутка псевдокод
- Заменить Смотри также на См. также
4. Система непересекающихся множеств
- Наивные реализации (0.5)
- Сделать структуру в списке типа Generic
- Написать про возможную частую ошибку в реализации массивом
- Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
- Списки с весовой эвристикой (0.5)
- Оформить правильно источники информации
- Интервики на амортизационный анализ
- Добавить пробелы в Других реализациях перед (
- Англоязычные термины правильно оформить
- Реализация с помощью леса корневых деревьев
- !!! СНМ с операцией удаления за О(1) (6)
- "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
- Кое-где не хватает точек в конце предложений
- Вообще кажется, что можно проще
- Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
- Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
5. Поисковые структуры данных
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево
- Красно-черное дерево
- Декартово дерево
- Декартово дерево по неявному ключу (1)
- В псевдокоде нет проверок на null
- Splay-дерево
- !!! Tango-дерево (8)
- Доказательство теоремы Уилбера
- А причём тут вообще она?
- Рандомизированное бинарное дерево поиска
- Дерево ван Эмде Боаса
- !!! Список с пропусками (7)
- \theta cделать большой буквой
- Определение в начале мутное
- Оформить правильно англоязычные термины
- Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
- Увеличить дроби
- Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
- Отформатировать псевдокод
- log заменить на \log
- Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
- Оформить правильно источники информации
- Добавить См. также
- Написать, почему все так любят скиплист, особенно в вычислительной геометрии
- Fusion tree
- Сверхбыстрый цифровой бор (2)
- Отформатировать псевдокоды
- Сказать, почему префиксы в хеше не буду есть много памяти
- Добавить См. также
- Многоточия заменить на \ldots
- Rope
6. Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху (0.5)
- Много пробелов в коде, отформатировать
- Заменить neutral на varepsilon, введя сначала моноид
- Добавить построение в См. также
- В примере случаи разной глубины красиво оформить
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления (3)
- Добавить примеры массовых операций в начало
- В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
- Константы взять в tex
- Отформатировать псевдокод
- Обозначения перед псевдокодов взять в \mathtt или в \mathrm
- Оформить правильно источники информации
- Добавить см. также
- Многомерное дерево отрезков
- fixed Сжатое многомерное дерево отрезков (1)
- Отформатировать псевдокод
- Англоязычные термины
- Литературу заменить на Источники информации
- Первую картинку заменить на Tex'овскую красивую фигурную скобку
- Добавить См. также
- Добавить категории
7. Дерево Фенвика
- Дерево Фенвика
- Встречное дерево Фенвика
- Дерево Фенвика для некоммутативных операций
- Многомерное дерево Фенвика
8. Хеширование
- Хеш-таблица
- Разрешение коллизий
- Хеширование кукушки (2)
- Англоязычные термины
- Взять в tex знаки = и константы
- Добавить интервики
- Оформить правильно источники информации
- А что делать в случае зацикливания?
- Плюсы-минусы метода
- Идеальное хеширование
- Перехеширование. Амортизационный анализ (1)
- Пояснить, почему будет O(1) на добавление при перехешировании
- Фильтр Блума (1.5)
- Quotient filter (3)
- Сделать нормальное описание алгоритма, а то ничего не понятно
- Универсальное семейство хеш-функций (0.5)
- Добавить ссылок
- Англоязычные термины
- Смотри обсуждения
- Заменить многоточия на \dots
- Заменить \mod на \bmod
- Заменить знаки неравенств
- Добавить "информации" в источники
- !!! Расширяемое хеширование (5)
- Красивые картинки
- Понятное описание
9. Сортировка
- 0. Сортировка
Квадратичные сортировки
- Сортировка выбором
- Сортировка пузырьком (2)
- Сделать единообразные псевдокоды с равным количеством отступов
- Пояснить преимущества каждой модификации сортировки
- Подробней расписать comb sort, и почему там n log n?
- Увеличить дроби
- Добавить категорию
- Сортировка вставками
Сортировки на сравнениях
- Сортировка Шелла
- Сортировка кучей
- Быстрая сортировка (2)
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти (0.5)
- Оформить правильно Источники информации
- Добавить категорию
- Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
- Терпеливая сортировка (0.5)
- Имена массивов взять в \mathtt
- Отформатировать псевдокоды
- Добавить категорию
- Timsort
- Smoothsort
- Теорема о нижней оценке для сортировки сравнениями
- Заменить знаки неравенств
- Добавить "информации" в источники
- Добавить пару следствий из теоремы
- Добавить категорию
Многопоточные сортировки
Другие сортировки
- Поиск k-ой порядковой статистики (2)
- Англоязычные термины
- Переменные в Tex
- Отформатировать псевдокод
- Заменить знаки неравенств
- Увеличить дроби
- Оформить правильно Источники информации
- Добавить категории, См. также
- Добавить про модификацию partition с разбиением на 3 части
- Кажется, что не работает, так как partition возвращает абсолютное смещение
- Поиск k-ой порядковой статистики за линейное время
- Поиск k-ой порядковой статистики в двух массивах
- fixed Сортировка подсчетом (1)
- Англоязычные термины
- Отформартировать псевдокод
- Добавить, что хоть алгоритм и работает за линейное время, но является псевдополиномиальным
- (+2 за более сочные картинки)
- Добавить "информации" в Источники
- Добавить категорию
- Цифровая сортировка
- Карманная сортировка
- Сортировка Хана
- (10) В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
- Задача флага Нидерландов
10. Сортирующие сети
- Сортирующие сети
- Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
- Сортирующие сети для квадратичных сортировок
- Сортировочные сети с особыми свойствами
- fixed Сеть Бетчера (0.5)
- Оформить правильно англ. термины
- Внутренние ссылки оформить примечаниями
- Заменить знаки неравенств
- Увеличить дроби
- Заменить многоточия на \dots
- Оформить правильно Источники информации
- Добавить См. также
11. Алгоритмы поиска
- Целочисленный двоичный поиск
- Поиск в матрице
- Вещественный двоичный поиск
- Троичный поиск (2)
- Про == нужно сказать другое
- Добавить про унимодальность функции в начале
- Сказать, почему плохо, когда функция не строго монотонна
- Добавить сюда метод дихотомии
- Поиск с помощью золотого сечения
- Интерполяционный поиск (2)
- Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
- Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
