Участник:Shersh/Тикеты ко 2ому терму — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎2. Приоритетные очереди)
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты ко 2ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показано 46 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
 
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
  
−
== 0. Амортизационный анализ ==
+
== 1. Амортизационный анализ ==
−
# [[Амортизационный анализ]] (0.5)
+
# ''fixed'' [[Амортизационный анализ]] (0.5)
 
## Англоязычные термины
 
## Англоязычные термины
 
## Нормальный нумерованный список
 
## Нормальный нумерованный список
Строка 16: Строка 16:
 
# [[Стек]]
 
# [[Стек]]
 
# [[Очередь]]
 
# [[Очередь]]
−
# ''fixed'' [[Мажорирующий элемент]] (''1.5'')
+
# [[Дек]]
−
## Поправить псевдокод
+
# [[Мажорирующий элемент]]
−
## Заменить тире на шаблон, а кое-где {{---}} наоборот, на дефис
 
−
## != в тексте заменить на \ne
 
−
## Убрать скобки из диапазона массива
 
−
## Заменить size в доказательстве про K на ||
 
−
## Длинные обозначения взять в \mathtt
 
−
## Заменить источники на источники информации
 
 
# '''!!!''' [[Счетчик Кнута]] (''5'')
 
# '''!!!''' [[Счетчик Кнута]] (''5'')
 
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
 
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
 
# [[Мастер-теорема]]
 
# [[Мастер-теорема]]
 +
# [[List order maintenance]]
  
−
== 1. Персистентные структуры данных ==
+
== 2. Персистентные структуры данных ==
 
# [[Персистентные структуры данных]]
 
# [[Персистентные структуры данных]]
 
# [[Персистентный стек]]
 
# [[Персистентный стек]]
 
# [[Персистентная очередь]]
 
# [[Персистентная очередь]]
 
# [[Персистентный дек]]
 
# [[Персистентный дек]]
−
# '''!!!''' [[Персистентная приоритетная очередь]] (10)
+
# '''fixed''' [[Персистентная приоритетная очередь]] (10)
 
## Отрефакторить псевдокод
 
## Отрефакторить псевдокод
 
## Добавить красивые картинки
 
## Добавить красивые картинки
Строка 40: Строка 35:
 
## Подробней описать решение
 
## Подробней описать решение
  
−
== 2. Приоритетные очереди ==
+
== 3. Приоритетные очереди ==
 
: 0. [[Приоритетные очереди]]
 
: 0. [[Приоритетные очереди]]
 
# [[Двоичная куча]]
 
# [[Двоичная куча]]
 
# [[Биномиальная куча]]
 
# [[Биномиальная куча]]
−
# [[Фибоначчиева куча]]
+
# '''!!!''' [[Фибоначчиева куча]] (5-10)
 +
## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
 
# [[Левосторонняя куча]]
 
# [[Левосторонняя куча]]
 
# [[Тонкая куча]]
 
# [[Тонкая куча]]
−
# '''!!!''' [[Толстая куча на избыточном счетчике]] (''7'')
+
# [[Толстая куча на избыточном счетчике]]
−
## Англоязычные термины
+
# [[Куча Бродала-Окасаки]] (''4'')
−
## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
 
−
## Ссылка в интервики с большой буквы {{---}} заменить на маленькую
 
−
## Отформатировать псевдокод
 
−
## Всё оформлено в UpperCamelCase, наверное, надо что-то с этим сделать
 
−
## Названия функций обернуть в \mathrm
 
−
## Поправить ошибку в Источниках
 
−
## Все переменные и константы взять в tex
 
−
## "Основные операции оформить аккуратней
 
−
## В одном месте лишнее выделение текста псевдокодным прямоугольником, в другом месте комментарий вылез за псевдокод
 
−
## Заголовки сделать на уровень меньше
 
−
## Структуру оформить псевдокодом с комментариями
 
−
## Подпункты с большой буквы назвать
 
−
## Возможно, надо будет исправить что-то ещё, слишком много трэша
 
−
# ''взяли'' [[Куча Бродала-Окасаки]] (''4'')
 
 
## Ссылки заменить на источники информации, сделать маркированным списком
 
## Ссылки заменить на источники информации, сделать маркированным списком
 
## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
 
## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
Строка 69: Строка 51:
 
## Заменить Смотри также на См. также
 
## Заменить Смотри также на См. также
  
−
== 3. Система непересекающихся множеств ==
+
== 4. Система непересекающихся множеств ==
 
# [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'')
 
# [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'')
 
## Сделать структуру в списке типа Generic
 
## Сделать структуру в списке типа Generic
Строка 79: Строка 61:
 
## Добавить пробелы в Других реализациях перед (
 
## Добавить пробелы в Других реализациях перед (
 
## Англоязычные термины правильно оформить
 
## Англоязычные термины правильно оформить
−
# '''fixed''' [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] (''5'')
+
# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
−
## Написать внятное доказательство
 
 
# '''!!!''' [[СНМ с операцией удаления за О(1)]] (''6'')
 
# '''!!!''' [[СНМ с операцией удаления за О(1)]] (''6'')
 
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
 
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
Строка 88: Строка 69:
 
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
 
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
  
−
== 4. Поисковые структуры данных==
+
== 5. Поисковые структуры данных==
 
:0. [[Поисковые структуры данных]]
 
:0. [[Поисковые структуры данных]]
 
# [[Упорядоченное множество]]
 
# [[Упорядоченное множество]]
Строка 95: Строка 76:
 
# [[2-3 дерево]]
 
# [[2-3 дерево]]
 
# [[B-дерево]]
 
# [[B-дерево]]
−
# '''взяли''' [[Красно-черное дерево]] (''5'')
+
# [[Красно-черное дерево]]
−
## Добавить про связь с 2-3 и 2-4 деревом
+
# [[Декартово дерево]]
−
# '''взяли''' [[Декартово дерево]] (''6'')
 
−
## Тире заменить на шаблон
 
−
## Имена функций оформить в lowerCamelCase
 
−
## Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев
 
−
## Разобраться с приоритетами (см. обсуждение)
 
−
## Какое-то палево в удалении с k.x - eps
 
−
## Оформить правильно источники информации
 
−
## Заменить знаки неравенств
 
−
## Может быть можно избавиться от проверок на null?
 
 
# [[Декартово дерево по неявному ключу]] (1)
 
# [[Декартово дерево по неявному ключу]] (1)
 
## В псевдокоде нет проверок на ''null''
 
## В псевдокоде нет проверок на ''null''
−
# '''fixed''' [[Splay-дерево]] (''8'')
+
# [[Splay-дерево]]
−
## Оформить правильно англоязычные термины
 
−
## Исправить знаки неравенств в tex
 
−
## Увеличить дроби
 
−
## Дефисы заменить на шаблон тире
 
−
## Показать, что лемма верна для любого фиксированного веса узла
 
−
## Функции оформить в lowerCamelCase
 
−
## Пример, когда move to root занимает <tex>\Omega(n)</tex> времени, и заменить O на омегу
 
−
## Знаки умножения заменить на \cdot
 
−
## Заменить многоточия на \ldots
 
 
# '''!!!''' [[Tango-дерево]] (''8'')
 
# '''!!!''' [[Tango-дерево]] (''8'')
 
## Доказательство теоремы Уилбера
 
## Доказательство теоремы Уилбера
Строка 144: Строка 107:
 
# [[Rope]]
 
# [[Rope]]
  
−
== 5. Дерево отрезков==
+
== 6. Дерево отрезков==
 
# [[Статистики на отрезках. Корневая эвристика]]
 
# [[Статистики на отрезках. Корневая эвристика]]
 
# [[Дерево отрезков. Построение]]
 
# [[Дерево отрезков. Построение]]
Строка 162: Строка 125:
 
## Добавить см. также
 
## Добавить см. также
 
# [[Многомерное дерево отрезков]]  
 
# [[Многомерное дерево отрезков]]  
−
# [[Сжатое многомерное дерево отрезков]] (''1'')
+
# ''fixed'' [[Сжатое многомерное дерево отрезков]] (''1'')
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 
## Англоязычные термины
 
## Англоязычные термины
Строка 170: Строка 133:
 
## Добавить категории
 
## Добавить категории
  
−
== 6. Дерево Фенвика ==
+
== 7. Дерево Фенвика ==
−
* [[Дерево Фенвика]]
+
# [[Дерево Фенвика]]
−
* [[Встречное дерево Фенвика]]
+
# [[Встречное дерево Фенвика]]
−
* [[Дерево Фенвика для некоммутативных операций]]
+
# [[Дерево Фенвика для некоммутативных операций]]
−
* [[Многомерное дерево Фенвика]]
+
# [[Многомерное дерево Фенвика]]
  
−
== 7. Хеширование ==
+
== 8. Хеширование ==
 
# [[Хеш-таблица]]
 
# [[Хеш-таблица]]
 
# [[Разрешение коллизий]]  
 
# [[Разрешение коллизий]]  
Строка 189: Строка 152:
 
# [[Перехеширование. Амортизационный анализ]] (''1'')
 
# [[Перехеширование. Амортизационный анализ]] (''1'')
 
## Пояснить, почему будет O(1) на добавление при перехешировании
 
## Пояснить, почему будет O(1) на добавление при перехешировании
−
# ''взяли'' [[Фильтр Блума]] (1.5)
+
# [[Фильтр Блума]] (1.5)
−
## Оформить правильно Источники информации
 
−
## Англоязычные термины
 
−
## Константы, AND, OR в Tex
 
−
## А зачем нужна такая структура данных?
 
−
## Вынести определения, чтобы в следующем конспекте не дублировалось
 
 
# [[Quotient filter]] (3)
 
# [[Quotient filter]] (3)
 
## Сделать нормальное описание алгоритма, а то ничего не понятно
 
## Сделать нормальное описание алгоритма, а то ничего не понятно
Строка 209: Строка 167:
 
## Понятное описание
 
## Понятное описание
  
−
== 8. Сортировка ==
+
== 9. Сортировка ==
−
:0. ''fixed'' [[Сортировка]]
+
:0. [[Сортировка]]
 
=== Квадратичные сортировки ===
 
=== Квадратичные сортировки ===
−
# ''fixed'' [[Сортировка выбором]] (''1'')
+
# [[Сортировка выбором]]
−
## Ссылку через интервики
 
−
## Оформить правильно англоязычные термины
 
−
## Отформатировать псевдокоды
 
−
## Сказать, в чём разница между двумя вариантами и оформить сами варианты красивей
 
−
## Оформить правильно источники информации
 
−
## Добавить См. также
 
−
## Добавить категорию
 
 
# [[Сортировка пузырьком]] (''2'')
 
# [[Сортировка пузырьком]] (''2'')
 
## Сделать единообразные псевдокоды с равным количеством отступов
 
## Сделать единообразные псевдокоды с равным количеством отступов
Строка 226: Строка 177:
 
## Увеличить дроби
 
## Увеличить дроби
 
## Добавить категорию
 
## Добавить категорию
−
# [[Сортировка вставками]] (''0.5'')
+
# [[Сортировка вставками]]
  
 
=== Сортировки на сравнениях ===
 
=== Сортировки на сравнениях ===
 
<ol>
 
<ol>
−
<li value="4"> ''fixed'' [[Сортировка Шелла]] (''0.5'') </li>
+
<li value="4"> [[Сортировка Шелла]] </li>
−
# Заменить дефисы на тире
+
<li> [[Сортировка кучей]] </li>
−
# Заменить многоточия на \ldots
 
−
# Написать правильно ln
 
−
# Пофиксить категории
 
−
# Оформить правильно Источники информации и См. также
 
−
<li> [[Сортировка кучей]] (''5'') </li>
 
 
<li> [[Быстрая сортировка]] (''2'') </li>
 
<li> [[Быстрая сортировка]] (''2'') </li>
−
# Англоязычные термины
 
−
# Описание алгоритма сделать покрасивей
 
−
# Заменить многоточия на \ldots
 
−
# Увеличить дроби
 
−
# Пояснить про разбиение массива на три части и чем это помогает
 
−
# Добавить ещё модификаций
 
−
# Добавить См. также
 
−
# Добавить категорию
 
−
# Исправить баг с partition
 
 
<li> [[Сортировка слиянием]] </li>
 
<li> [[Сортировка слиянием]] </li>
 
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
 
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
Строка 258: Строка 195:
 
<li> [[Timsort]] </li>
 
<li> [[Timsort]] </li>
 
<li> [[Smoothsort]] </li>
 
<li> [[Smoothsort]] </li>
−
<li> [[Теорема о нижней оценке для сортировки сравнениями]] (''1'') </li>
+
<li> [[Теорема о нижней оценке для сортировки сравнениями]] </li>
 
# Заменить знаки неравенств
 
# Заменить знаки неравенств
 
# Добавить "информации" в источники
 
# Добавить "информации" в источники
Строка 285: Строка 222:
 
<li> [[Поиск k-ой порядковой статистики за линейное время]] </li>
 
<li> [[Поиск k-ой порядковой статистики за линейное время]] </li>
 
<li> [[Поиск k-ой порядковой статистики в двух массивах]]
 
<li> [[Поиск k-ой порядковой статистики в двух массивах]]
−
<li> [[Сортировка подсчетом]] (''1'') </li>
+
<li> ''fixed'' [[Сортировка подсчетом]] (''1'') </li>
 
# Англоязычные термины
 
# Англоязычные термины
 
# Отформартировать псевдокод
 
# Отформартировать псевдокод
Строка 294: Строка 231:
 
<li> [[Цифровая сортировка]] </li>
 
<li> [[Цифровая сортировка]] </li>
 
<li> [[Карманная сортировка]] </li>
 
<li> [[Карманная сортировка]] </li>
−
<li> '''!!!''' [[Сортировка Хана]] </li>
+
<li> [[Сортировка Хана]] </li>
−
## В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
+
# '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
 
<li> [[Задача флага Нидерландов]] </li>
 
<li> [[Задача флага Нидерландов]] </li>
 
</ol>
 
</ol>
  
−
== 9. Сортирующие сети ==
+
== 10. Сортирующие сети ==
 
# [[Сортирующие сети]]
 
# [[Сортирующие сети]]
 
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
# [[Сортирующие сети для квадратичных сортировок]]
 
# [[Сортирующие сети для квадратичных сортировок]]
 
# [[Сортировочные сети с особыми свойствами]]  
 
# [[Сортировочные сети с особыми свойствами]]  
−
# [[Сеть Бетчера]] (''0.5'')
+
# ''fixed'' [[Сеть Бетчера]] (''0.5'')
 
## Оформить правильно англ. термины
 
## Оформить правильно англ. термины
 
## Внутренние ссылки оформить примечаниями
 
## Внутренние ссылки оформить примечаниями
Строка 313: Строка 250:
 
## Добавить См. также
 
## Добавить См. также
  
−
== 10. Алгоритмы поиска ==
+
== 11. Алгоритмы поиска ==
−
# '''fixed''' [[Целочисленный двоичный поиск]] (5)
+
# [[Целочисленный двоичный поиск]]
−
## Исправить часть про различные алгоритмы
+
# [[Поиск в матрице]]
 
# [[Вещественный двоичный поиск]]
 
# [[Вещественный двоичный поиск]]
 
# [[Троичный поиск]] (''2'')
 
# [[Троичный поиск]] (''2'')
Строка 322: Строка 259:
 
## Сказать, почему плохо, когда функция не строго монотонна
 
## Сказать, почему плохо, когда функция не строго монотонна
 
## Добавить сюда метод дихотомии
 
## Добавить сюда метод дихотомии
−
# [[Поиск с помощью золотого сечения]] (''4'')
+
# [[Поиск с помощью золотого сечения]]
 
# [[Интерполяционный поиск]] (2)
 
# [[Интерполяционный поиск]] (2)
 
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
 
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
 
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
 
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях

Текущая версия на 19:15, 23 февраля 2017

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.

1. Амортизационный анализ

  1. fixed Амортизационный анализ (0.5)
    1. Англоязычные термины
    2. Нормальный нумерованный список
  2. !!! Динамический массив (6)
    1. Сравнение со списком
    2. Англоязычные термины
    3. Потенциальный анализ для произвольных A, B, C
  3. !!! Hashed Array Tree (5)
    1. Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
    2. Добавить про буферизованный список
    3. Редактирование по мелочи
  4. Список
  5. Стек
  6. Очередь
  7. Дек
  8. Мажорирующий элемент
  9. !!! Счетчик Кнута (5)
    1. Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
  10. Мастер-теорема
  11. List order maintenance

2. Персистентные структуры данных

  1. Персистентные структуры данных
  2. Персистентный стек
  3. Персистентная очередь
  4. Персистентный дек
  5. fixed Персистентная приоритетная очередь (10)
    1. Отрефакторить псевдокод
    2. Добавить красивые картинки
    3. Оформить всё правильно
    4. Добавить наивное решение на дереве
    5. Подробней описать решение

3. Приоритетные очереди

0. Приоритетные очереди
  1. Двоичная куча
  2. Биномиальная куча
  3. !!! Фибоначчиева куча (5-10)
    1. В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
  4. Левосторонняя куча
  5. Тонкая куча
  6. Толстая куча на избыточном счетчике
  7. Куча Бродала-Окасаки (4)
    1. Ссылки заменить на источники информации, сделать маркированным списком
    2. Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
    3. Написать подробней операции
    4. Форматнуть чутка псевдокод
    5. Заменить Смотри также на См. также

4. Система непересекающихся множеств

  1. Наивные реализации (0.5)
    1. Сделать структуру в списке типа Generic
    2. Написать про возможную частую ошибку в реализации массивом
    3. Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
  2. Списки с весовой эвристикой (0.5)
    1. Оформить правильно источники информации
    2. Интервики на амортизационный анализ
    3. Добавить пробелы в Других реализациях перед (
    4. Англоязычные термины правильно оформить
  3. Реализация с помощью леса корневых деревьев
  4. !!! СНМ с операцией удаления за О(1) (6)
    1. "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
    2. Кое-где не хватает точек в конце предложений
    3. Вообще кажется, что можно проще
    4. Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
    5. Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)

5. Поисковые структуры данных

0. Поисковые структуры данных
  1. Упорядоченное множество
  2. Дерево поиска, наивная реализация
  3. АВЛ-дерево
  4. 2-3 дерево
  5. B-дерево
  6. Красно-черное дерево
  7. Декартово дерево
  8. Декартово дерево по неявному ключу (1)
    1. В псевдокоде нет проверок на null
  9. Splay-дерево
  10. !!! Tango-дерево (8)
    1. Доказательство теоремы Уилбера
    2. А причём тут вообще она?
  11. Рандомизированное бинарное дерево поиска
  12. Дерево ван Эмде Боаса
  13. !!! Список с пропусками (7)
    1. \theta cделать большой буквой
    2. Определение в начале мутное
    3. Оформить правильно англоязычные термины
    4. Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
    5. Увеличить дроби
    6. Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
    7. Отформатировать псевдокод
    8. log заменить на \log
    9. Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
    10. Оформить правильно источники информации
    11. Добавить См. также
    12. Написать, почему все так любят скиплист, особенно в вычислительной геометрии
  14. Fusion tree
  15. Сверхбыстрый цифровой бор (2)
    1. Отформатировать псевдокоды
    2. Сказать, почему префиксы в хеше не буду есть много памяти
    3. Добавить См. также
    4. Многоточия заменить на \ldots
  16. Rope

6. Дерево отрезков

  1. Статистики на отрезках. Корневая эвристика
  2. Дерево отрезков. Построение
  3. Реализация запроса в дереве отрезков сверху (0.5)
    1. Много пробелов в коде, отформатировать
    2. Заменить neutral на varepsilon, введя сначала моноид
    3. Добавить построение в См. также
    4. В примере случаи разной глубины красиво оформить
  4. Реализация запроса в дереве отрезков снизу
  5. Несогласованные поддеревья. Реализация массового обновления (3)
    1. Добавить примеры массовых операций в начало
    2. В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
    3. Константы взять в tex
    4. Отформатировать псевдокод
    5. Обозначения перед псевдокодов взять в \mathtt или в \mathrm
    6. Оформить правильно источники информации
    7. Добавить см. также
  6. Многомерное дерево отрезков
  7. fixed Сжатое многомерное дерево отрезков (1)
    1. Отформатировать псевдокод
    2. Англоязычные термины
    3. Литературу заменить на Источники информации
    4. Первую картинку заменить на Tex'овскую красивую фигурную скобку
    5. Добавить См. также
    6. Добавить категории

7. Дерево Фенвика

  1. Дерево Фенвика
  2. Встречное дерево Фенвика
  3. Дерево Фенвика для некоммутативных операций
  4. Многомерное дерево Фенвика

8. Хеширование

  1. Хеш-таблица
  2. Разрешение коллизий
  3. Хеширование кукушки (2)
    1. Англоязычные термины
    2. Взять в tex знаки = и константы
    3. Добавить интервики
    4. Оформить правильно источники информации
    5. А что делать в случае зацикливания?
    6. Плюсы-минусы метода
  4. Идеальное хеширование
  5. Перехеширование. Амортизационный анализ (1)
    1. Пояснить, почему будет O(1) на добавление при перехешировании
  6. Фильтр Блума (1.5)
  7. Quotient filter (3)
    1. Сделать нормальное описание алгоритма, а то ничего не понятно
  8. Универсальное семейство хеш-функций (0.5)
    1. Добавить ссылок
    2. Англоязычные термины
    3. Смотри обсуждения
    4. Заменить многоточия на \dots
    5. Заменить \mod на \bmod
    6. Заменить знаки неравенств
    7. Добавить "информации" в источники
  9. !!! Расширяемое хеширование (5)
    1. Красивые картинки
    2. Понятное описание

9. Сортировка

0. Сортировка

Квадратичные сортировки

  1. Сортировка выбором
  2. Сортировка пузырьком (2)
    1. Сделать единообразные псевдокоды с равным количеством отступов
    2. Пояснить преимущества каждой модификации сортировки
    3. Подробней расписать comb sort, и почему там n log n?
    4. Увеличить дроби
    5. Добавить категорию
  3. Сортировка вставками

Сортировки на сравнениях

  1. Сортировка Шелла
  2. Сортировка кучей
  3. Быстрая сортировка (2)
  4. Сортировка слиянием
  5. Cортировка слиянием с использованием O(1) дополнительной памяти (0.5)
    1. Оформить правильно Источники информации
    2. Добавить категорию
    3. Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
  6. Терпеливая сортировка (0.5)
    1. Имена массивов взять в \mathtt
    2. Отформатировать псевдокоды
    3. Добавить категорию
  7. Timsort
  8. Smoothsort
  9. Теорема о нижней оценке для сортировки сравнениями
    1. Заменить знаки неравенств
    2. Добавить "информации" в источники
    3. Добавить пару следствий из теоремы
    4. Добавить категорию

Многопоточные сортировки

  1. Многопоточная сортировка слиянием
  2. PSRS-сортировка

Другие сортировки

  1. Поиск k-ой порядковой статистики (2)
    1. Англоязычные термины
    2. Переменные в Tex
    3. Отформатировать псевдокод
    4. Заменить знаки неравенств
    5. Увеличить дроби
    6. Оформить правильно Источники информации
    7. Добавить категории, См. также
    8. Добавить про модификацию partition с разбиением на 3 части
    9. Кажется, что не работает, так как partition возвращает абсолютное смещение
  2. Поиск k-ой порядковой статистики за линейное время
  3. Поиск k-ой порядковой статистики в двух массивах
  4. fixed Сортировка подсчетом (1)
    1. Англоязычные термины
    2. Отформартировать псевдокод
    3. Добавить, что хоть алгоритм и работает за линейное время, но является псевдополиномиальным
    4. (+2 за более сочные картинки)
    5. Добавить "информации" в Источники
    6. Добавить категорию
  5. Цифровая сортировка
  6. Карманная сортировка
  7. Сортировка Хана
    1. (10) В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
  8. Задача флага Нидерландов

10. Сортирующие сети

  1. Сортирующие сети
  2. Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
  3. Сортирующие сети для квадратичных сортировок
  4. Сортировочные сети с особыми свойствами
  5. fixed Сеть Бетчера (0.5)
    1. Оформить правильно англ. термины
    2. Внутренние ссылки оформить примечаниями
    3. Заменить знаки неравенств
    4. Увеличить дроби
    5. Заменить многоточия на \dots
    6. Оформить правильно Источники информации
    7. Добавить См. также

11. Алгоритмы поиска

  1. Целочисленный двоичный поиск
  2. Поиск в матрице
  3. Вещественный двоичный поиск
  4. Троичный поиск (2)
    1. Про == нужно сказать другое
    2. Добавить про унимодальность функции в начале
    3. Сказать, почему плохо, когда функция не строго монотонна
    4. Добавить сюда метод дихотомии
  5. Поиск с помощью золотого сечения
  6. Интерполяционный поиск (2)
    1. Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
    2. Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_ко_2ому_терму&oldid=60457»