748
правок
Изменения
Новая страница: «Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. ==...»
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
== 1. Амортизационный анализ ==
# [[Амортизационный анализ]]
# [[Динамический массив]] (''6'')
## Сравнение со списком
## Англоязычные термины
## Потенциальный анализ для произвольных A, B, C
# [[Hashed Array Tree]] (''5'')
## Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
## Добавить про ''буферизованный'' список
## Редактирование по мелочи
# [[Список]]
# [[Стек]]
# [[Очередь]]
# [[Дек]]
# [[Мажорирующий элемент]]
# [[Счетчик Кнута]] (''5'')
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
# [[Мастер-теорема]]
# [[List order maintenance]]
== 2. Персистентные структуры данных ==
# [[Персистентные структуры данных]]
# [[Персистентный стек]]
# [[Персистентная очередь]]
# [[Персистентный дек]]
# [[Персистентная приоритетная очередь]] (10)
## Отрефакторить псевдокод
## Добавить красивые картинки
## Оформить всё правильно
## Добавить наивное решение на дереве
## Подробней описать решение
== 3. Приоритетные очереди ==
: 0. [[Приоритетные очереди]]
# [[Двоичная куча]]
# [[Биномиальная куча]]
# [[Фибоначчиева куча]] (5-10)
## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
# [[Левосторонняя куча]]
# [[Тонкая куча]]
# [[Толстая куча на избыточном счетчике]]
# [[Куча Бродала-Окасаки]] (''4'')
## Ссылки заменить на источники информации, сделать маркированным списком
## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
## Написать подробней операции
## Форматнуть чутка псевдокод
## Заменить Смотри также на См. также
== 4. Система непересекающихся множеств ==
# [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'')
## Сделать структуру в списке типа Generic
## Написать про возможную частую ошибку в реализации массивом
## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] (''0.5'')
## Оформить правильно источники информации
## Интервики на амортизационный анализ
## Добавить пробелы в Других реализациях перед (
## Англоязычные термины правильно оформить
# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
# '''!!!''' [[СНМ с операцией удаления за О(1)]] (''6'')
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
## Кое-где не хватает точек в конце предложений
## Вообще кажется, что можно проще
## Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
== 5. Поисковые структуры данных==
:0. [[Поисковые структуры данных]]
# [[Упорядоченное множество]]
# [[Дерево поиска, наивная реализация]]
# [[АВЛ-дерево]]
# [[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?
## Увеличить дроби
## Добавить категорию
# [[Сортировка вставками]]
=== Сортировки на сравнениях ===
<ol>
<li value="4"> [[Сортировка Шелла]] </li>
<li> [[Сортировка кучей]] </li>
<li> [[Быстрая сортировка]] (''2'') </li>
<li> [[Сортировка слиянием]] </li>
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
# Оформить правильно Источники информации
# Добавить категорию
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
<li> [[Терпеливая сортировка]] (0.5) </li>
# Имена массивов взять в \mathtt
# Отформатировать псевдокоды
# Добавить категорию
<li> [[Timsort]] </li>
<li> [[Smoothsort]] </li>
<li> [[Теорема о нижней оценке для сортировки сравнениями]] </li>
# Заменить знаки неравенств
# Добавить "информации" в источники
# Добавить пару следствий из теоремы
# Добавить категорию
</ol>
=== Многопоточные сортировки ===
<ol>
<li value="12"> [[Многопоточная сортировка слиянием]] </li>
<li> [[PSRS-сортировка]] </li>
</ol>
=== Другие сортировки ===
<ol>
<li value="14"> [[Поиск k-ой порядковой статистики]] (''2'') </li>
# Англоязычные термины
# Переменные в Tex
# Отформатировать псевдокод
# Заменить знаки неравенств
# Увеличить дроби
# Оформить правильно Источники информации
# Добавить категории, См. также
# Добавить про модификацию partition с разбиением на 3 части
# Кажется, что не работает, так как partition возвращает абсолютное смещение
<li> [[Поиск k-ой порядковой статистики за линейное время]] </li>
<li> [[Поиск k-ой порядковой статистики в двух массивах]]
<li> ''fixed'' [[Сортировка подсчетом]] (''1'') </li>
# Англоязычные термины
# Отформартировать псевдокод
# Добавить, что хоть алгоритм и работает за линейное время, но является псевдополиномиальным
# (+2 за более сочные картинки)
# Добавить "информации" в Источники
# Добавить категорию
<li> [[Цифровая сортировка]] </li>
<li> [[Карманная сортировка]] </li>
<li> [[Сортировка Хана]] </li>
# '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
<li> [[Задача флага Нидерландов]] </li>
</ol>
== 10. Сортирующие сети ==
# [[Сортирующие сети]]
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
# [[Сортирующие сети для квадратичных сортировок]]
# [[Сортировочные сети с особыми свойствами]]
# ''fixed'' [[Сеть Бетчера]] (''0.5'')
## Оформить правильно англ. термины
## Внутренние ссылки оформить примечаниями
## Заменить знаки неравенств
## Увеличить дроби
## Заменить многоточия на \dots
## Оформить правильно Источники информации
## Добавить См. также
== 11. Алгоритмы поиска ==
# [[Целочисленный двоичный поиск]]
# [[Поиск в матрице]]
# [[Вещественный двоичный поиск]]
# [[Троичный поиск]] (''2'')
## Про == нужно сказать другое
## Добавить про унимодальность функции в начале
## Сказать, почему плохо, когда функция не строго монотонна
## Добавить сюда метод дихотомии
# [[Поиск с помощью золотого сечения]]
# [[Интерполяционный поиск]] (2)
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
== 1. Амортизационный анализ ==
# [[Амортизационный анализ]]
# [[Динамический массив]] (''6'')
## Сравнение со списком
## Англоязычные термины
## Потенциальный анализ для произвольных A, B, C
# [[Hashed Array Tree]] (''5'')
## Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
## Добавить про ''буферизованный'' список
## Редактирование по мелочи
# [[Список]]
# [[Стек]]
# [[Очередь]]
# [[Дек]]
# [[Мажорирующий элемент]]
# [[Счетчик Кнута]] (''5'')
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
# [[Мастер-теорема]]
# [[List order maintenance]]
== 2. Персистентные структуры данных ==
# [[Персистентные структуры данных]]
# [[Персистентный стек]]
# [[Персистентная очередь]]
# [[Персистентный дек]]
# [[Персистентная приоритетная очередь]] (10)
## Отрефакторить псевдокод
## Добавить красивые картинки
## Оформить всё правильно
## Добавить наивное решение на дереве
## Подробней описать решение
== 3. Приоритетные очереди ==
: 0. [[Приоритетные очереди]]
# [[Двоичная куча]]
# [[Биномиальная куча]]
# [[Фибоначчиева куча]] (5-10)
## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
# [[Левосторонняя куча]]
# [[Тонкая куча]]
# [[Толстая куча на избыточном счетчике]]
# [[Куча Бродала-Окасаки]] (''4'')
## Ссылки заменить на источники информации, сделать маркированным списком
## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
## Написать подробней операции
## Форматнуть чутка псевдокод
## Заменить Смотри также на См. также
== 4. Система непересекающихся множеств ==
# [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'')
## Сделать структуру в списке типа Generic
## Написать про возможную частую ошибку в реализации массивом
## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] (''0.5'')
## Оформить правильно источники информации
## Интервики на амортизационный анализ
## Добавить пробелы в Других реализациях перед (
## Англоязычные термины правильно оформить
# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
# '''!!!''' [[СНМ с операцией удаления за О(1)]] (''6'')
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
## Кое-где не хватает точек в конце предложений
## Вообще кажется, что можно проще
## Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
== 5. Поисковые структуры данных==
:0. [[Поисковые структуры данных]]
# [[Упорядоченное множество]]
# [[Дерево поиска, наивная реализация]]
# [[АВЛ-дерево]]
# [[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?
## Увеличить дроби
## Добавить категорию
# [[Сортировка вставками]]
=== Сортировки на сравнениях ===
<ol>
<li value="4"> [[Сортировка Шелла]] </li>
<li> [[Сортировка кучей]] </li>
<li> [[Быстрая сортировка]] (''2'') </li>
<li> [[Сортировка слиянием]] </li>
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
# Оформить правильно Источники информации
# Добавить категорию
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
<li> [[Терпеливая сортировка]] (0.5) </li>
# Имена массивов взять в \mathtt
# Отформатировать псевдокоды
# Добавить категорию
<li> [[Timsort]] </li>
<li> [[Smoothsort]] </li>
<li> [[Теорема о нижней оценке для сортировки сравнениями]] </li>
# Заменить знаки неравенств
# Добавить "информации" в источники
# Добавить пару следствий из теоремы
# Добавить категорию
</ol>
=== Многопоточные сортировки ===
<ol>
<li value="12"> [[Многопоточная сортировка слиянием]] </li>
<li> [[PSRS-сортировка]] </li>
</ol>
=== Другие сортировки ===
<ol>
<li value="14"> [[Поиск k-ой порядковой статистики]] (''2'') </li>
# Англоязычные термины
# Переменные в Tex
# Отформатировать псевдокод
# Заменить знаки неравенств
# Увеличить дроби
# Оформить правильно Источники информации
# Добавить категории, См. также
# Добавить про модификацию partition с разбиением на 3 части
# Кажется, что не работает, так как partition возвращает абсолютное смещение
<li> [[Поиск k-ой порядковой статистики за линейное время]] </li>
<li> [[Поиск k-ой порядковой статистики в двух массивах]]
<li> ''fixed'' [[Сортировка подсчетом]] (''1'') </li>
# Англоязычные термины
# Отформартировать псевдокод
# Добавить, что хоть алгоритм и работает за линейное время, но является псевдополиномиальным
# (+2 за более сочные картинки)
# Добавить "информации" в Источники
# Добавить категорию
<li> [[Цифровая сортировка]] </li>
<li> [[Карманная сортировка]] </li>
<li> [[Сортировка Хана]] </li>
# '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
<li> [[Задача флага Нидерландов]] </li>
</ol>
== 10. Сортирующие сети ==
# [[Сортирующие сети]]
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
# [[Сортирующие сети для квадратичных сортировок]]
# [[Сортировочные сети с особыми свойствами]]
# ''fixed'' [[Сеть Бетчера]] (''0.5'')
## Оформить правильно англ. термины
## Внутренние ссылки оформить примечаниями
## Заменить знаки неравенств
## Увеличить дроби
## Заменить многоточия на \dots
## Оформить правильно Источники информации
## Добавить См. также
== 11. Алгоритмы поиска ==
# [[Целочисленный двоичный поиск]]
# [[Поиск в матрице]]
# [[Вещественный двоичный поиск]]
# [[Троичный поиск]] (''2'')
## Про == нужно сказать другое
## Добавить про унимодальность функции в начале
## Сказать, почему плохо, когда функция не строго монотонна
## Добавить сюда метод дихотомии
# [[Поиск с помощью золотого сечения]]
# [[Интерполяционный поиск]] (2)
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
