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