748
правок
Изменения
→Сортировки на сравнениях
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела(например, конспект стек из раздела Амортизационный анализ имеет тикет 1-5).
== 1. Амортизационный анализ ==
# [[Двоичная куча]]
# [[Биномиальная куча]]
# взяли [[Фибоначчиева куча]] 5-10## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
# [[Левосторонняя куча]] 0,25
## См. также
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
== 9. Хеширование ==# [[Хеш-таблица]] 0,25## См. также# [[Разрешение коллизий]] # взяли [[Хеширование кукушки]] 2## Англоязычные термины## Взять в tex знаки = и константы## Добавить интервики## Оформить правильно источники информации## А что делать в случае зацикливания?## Плюсы-минусы метода# [[Идеальное хеширование]]# [[Перехеширование. Амортизационный анализ]] 1## Пояснить, почему будет O(1) на добавление при перехешировании# [[Фильтр Блума]] 0,25## См. также# [[Quotient filter]] 3## Сделать нормальное описание алгоритма, а то ничего не понятно# [[Универсальное семейство хеш-функций]] 0.5## Добавить ссылок## Англоязычные термины## Смотри обсуждения## Заменить многоточия на \dots## Заменить \mod на \bmod## Заменить знаки неравенств## Добавить "информации" в источники# [[Расширяемое хеширование]] 5## Красивые картинки## Понятное описание == 10. Сортировка ==
:0. [[Сортировка]]
=== Квадратичные сортировки ===
<li> [[Быстрая сортировка]] </li>
<li> [[Сортировка слиянием]] </li>
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
# Оформить правильно Источники информации
# Добавить категорию
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
# Написать подробнее про ассимптотику
# Добавить всевдокод
# Привести конспект в порядок
<li> [[Терпеливая сортировка]] (0.5) </li>
# Имена массивов взять в \mathtt
<li> [[Timsort]] </li>
<li> [[Smoothsort]] </li>
<li> взяли [[Теорема о нижней оценке для сортировки сравнениями]] </li> (4)
# Заменить знаки неравенств
# Добавить "информации" в источники
</ol>
== 116. Сортирующие сети ==
# [[Сортирующие сети]]
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
# [[Сеть Бетчера]]
== 127. Алгоритмы поиска ==
# [[Целочисленный двоичный поиск]]
# [[Поиск в матрице]]
## Что-то еще может быть, написать куратору
== 138. Хеширование ==# [[Хеш-таблица]]# [[Разрешение коллизий]] # [[Хеширование кукушки]]# [[Идеальное хеширование]]# [[Перехеширование. Амортизационный анализ]] # [[Фильтр Блума]] # [[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. Связь между структурами данных ==
* [[Связь между структурами данных]]