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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎8. Сортировка)
(→‎8. Сортировка)
Строка 91: Строка 91:
 
== 8. [[Сортировка]] ==
 
== 8. [[Сортировка]] ==
 
# [[Сортировка выбором]]
 
# [[Сортировка выбором]]
−
# [[Сортировка пузырьком]]
+
## Ссылку через интервики
−
# [[Сортировка вставками]]
+
# '''!!!''' [[Сортировка пузырьком]]
 +
## Добавить ещё оптимизаций этой сортировки (шейкерная сортировка, расчёской, odd-even и прочие {{---}} полный список есть на [[ wikipedia:en:Bubble_sort | википедии ]])
 +
## Дать точные оценки на число сравнений в худшем случае
 +
## Отформатировать псевдокод
 +
## Ссылка на вики
 +
# '''!!!''' [[Сортировка вставками]]
 +
## То же самое, что и в предыдущем тикете
 
# [[Сортировка Шелла]]
 
# [[Сортировка Шелла]]
 
# '''!!!''' [[Сортировка кучей]]
 
# '''!!!''' [[Сортировка кучей]]
 
## Можно добавить всякие модификации сортировки кучей, например, JSort.
 
## Можно добавить всякие модификации сортировки кучей, например, JSort.
 
# [[Быстрая сортировка]]
 
# [[Быстрая сортировка]]
−
# [[Сортировка слиянием]]
+
## Тут вообще ссылки ужасные
 +
# '''!!!''' [[Сортировка слиянием]]
 +
## Эта сортировка хорошо параллелится. Но вдруг можно придумать, как манипулировать потоками, чтобы достичь наибольшей эффективности, особенно если одновременно может работать ограниченное число потоков.
 +
## Написать псевдокод многопоточной сортировки
 
# [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 
# [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 
# [[Теорема о нижней оценке для сортировки сравнениями]]
 
# [[Теорема о нижней оценке для сортировки сравнениями]]
 
# [[Сортировка подсчетом]]
 
# [[Сортировка подсчетом]]
 
# [[Сортировка подсчетом сложных объектов]]
 
# [[Сортировка подсчетом сложных объектов]]
−
# [[Цифровая сортировка]]
+
# '''!!!''' [[Цифровая сортировка]]
 +
## Добавить модификацию для сортировки цифр в порядке от старших к младшим
 
# [[Карманная сортировка]]
 
# [[Карманная сортировка]]
 
# [[Поиск k-ой порядковой статистики]]
 
# [[Поиск k-ой порядковой статистики]]
 
# [[Поиск k-ой порядковой статистики за линейное время]]
 
# [[Поиск k-ой порядковой статистики за линейное время]]
 
# [[Сортировка Хана]]
 
# [[Сортировка Хана]]
 +
## Привести конспект в порядок: добавить шаблоны определений, шаблоны лемм
 +
## При предложении дополнительных правок (например, картинок) может рассматриваться как полноценное дополнение
 
# [[Timsort]]
 
# [[Timsort]]
  

Версия 23:27, 1 мая 2014

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

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

  1. !!! Амортизационный анализ
    1. Можно добавить ещё по примеру на каждый метод.
  2. Саморасширяющийся массив
  3. Массив с увеличением/уменьшением размера
    1. Объединить с предыдущим, сделать всё красиво.
  4. Список
  5. Стек
  6. Очередь
    1. Заменить ссылки в источника на интервики
  7. взяли Персистентный стек
  8. взяли Персистентная очередь
  9. взяли Персистентный дек
    1. Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)
  10. Мажорирующий элемент
  11. !!! Счетчик Кнута
    1. Добавить картинки с более понятным пояснением
    2. Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)
    3. Может быть можно обобщить как-то на случай [math]d[/math]-ичной системы счисления? (используется в толстых кучах)
    4. Будет полезно добавить источники, если про это где-то можно почитать

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

  1. Двоичная куча
    1. Ссылки на википедию сделать через интервики
  2. Биномиальная куча
    1. интервики
  3. Фибоначчиева куча
    1. Ссылки заменить на интервики
  4. Левосторонняя куча
  5. Тонкая куча
  6. Толстая куча на избыточном счетчике
    1. Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
  7. Куча Бродала-Окасаки

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

  1. Наивные реализации
  2. Списки с весовой эвристикой
  3. Реализация с помощью леса корневых деревьев
    1. Интервики

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

  1. Упорядоченное множество
  2. Дерево поиска, наивная реализация
  3. АВЛ-дерево
  4. 2-3 дерево
  5. B-дерево
  6. Красно-черное дерево
  7. Декартово дерево
  8. Декартово дерево по неявному ключу
  9. Splay-дерево
  10. Рандомизированное бинарное дерево поиска
  11. Дерево ван Эмде Боаса
  12. Список с пропусками
  13. Fusion tree
  14. Сверхбыстрый цифровой бор
  • В каждом конспекте сделать ссылки на википедию через интервики

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

  1. Статистики на отрезках. Корневая эвристика
  2. !!! Дерево отрезков. Построение
    1. Добавить псевдокод персистентного дерева отрезков
    2. Заменить в псевдокоде f на бинарную операцию [math] \circ [/math]
    3. Поправить ссылки в источниках
  3. Реализация запроса в дереве отрезков сверху
  4. Реализация запроса в дереве отрезков снизу
  5. Несогласованные поддеревья. Реализация массового обновления
  6. Многомерное дерево отрезков
  7. Сжатое многомерное дерево отрезков

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

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

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

  1. Хеш-таблица
  2. !!! Разрешение коллизий
    1. Добавить примеры каких-нибудь интересных и популярных хешей, поизучать их свойства
  3. Хеширование кукушки
  4. Идеальное хеширование
  5. Перехеширование. Амортизационный анализ
  6. Фильтр Блума
  7. Универсальное семейство хеш-функций

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

  1. Сортировка выбором
    1. Ссылку через интервики
  2. !!! Сортировка пузырьком
    1. Добавить ещё оптимизаций этой сортировки (шейкерная сортировка, расчёской, odd-even и прочие — полный список есть на википедии )
    2. Дать точные оценки на число сравнений в худшем случае
    3. Отформатировать псевдокод
    4. Ссылка на вики
  3. !!! Сортировка вставками
    1. То же самое, что и в предыдущем тикете
  4. Сортировка Шелла
  5. !!! Сортировка кучей
    1. Можно добавить всякие модификации сортировки кучей, например, JSort.
  6. Быстрая сортировка
    1. Тут вообще ссылки ужасные
  7. !!! Сортировка слиянием
    1. Эта сортировка хорошо параллелится. Но вдруг можно придумать, как манипулировать потоками, чтобы достичь наибольшей эффективности, особенно если одновременно может работать ограниченное число потоков.
    2. Написать псевдокод многопоточной сортировки
  8. Cортировка слиянием с использованием O(1) дополнительной памяти
  9. Теорема о нижней оценке для сортировки сравнениями
  10. Сортировка подсчетом
  11. Сортировка подсчетом сложных объектов
  12. !!! Цифровая сортировка
    1. Добавить модификацию для сортировки цифр в порядке от старших к младшим
  13. Карманная сортировка
  14. Поиск k-ой порядковой статистики
  15. Поиск k-ой порядковой статистики за линейное время
  16. Сортировка Хана
    1. Привести конспект в порядок: добавить шаблоны определений, шаблоны лемм
    2. При предложении дополнительных правок (например, картинок) может рассматриваться как полноценное дополнение
  17. Timsort

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

  1. Сортирующие сети
  2. Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
  3. Сортировочные сети с особыми свойствами
  4. Сортирующие сети для квадратичных сортировок
  5. Сеть Бетчера

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

  1. Целочисленный двоичный поиск
  2. Вещественный двоичный поиск
  3. Троичный поиск
  4. Поиск с помощью золотого сечения
  5. Интерполяционный поиск
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_по_конспектам_year2013&oldid=36532»