Алгоритмы и структуры данных:Тикеты

Материал из Викиконспекты
Версия от 22:25, 12 ноября 2018; Lapenok.aleksej (обсуждение | вклад) (→‎Сортировки на сравнениях)
Перейти к: навигация, поиск

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

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

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

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

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

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

0. Приоритетные очереди
  1. Двоичная куча
  2. Биномиальная куча
  3. Фибоначчиева куча
  4. Левосторонняя куча 0,25
    1. См. также
  5. Тонкая куча 0,25
    1. См. также
  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. Сортировка пузырьком 2
    1. Сделать единообразные псевдокоды с равным количеством отступов
    2. Пояснить преимущества каждой модификации сортировки
    3. Подробней расписать comb sort, и почему там n log n?
    4. Увеличить дроби
    5. Добавить категорию
  3. Сортировка вставками

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

  1. Сортировка Шелла
  2. Сортировка кучей
  3. Быстрая сортировка
  4. Сортировка слиянием
  5. Cортировка слиянием с использованием O(1) дополнительной памяти (5)
    1. Оформить правильно Источники информации
    2. Добавить категорию
    3. Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
    4. Написать подробнее про ассимптотику
    5. Добавить всевдокод
    6. Привести конспект в порядок
  6. Терпеливая сортировка (0.5)
    1. Имена массивов взять в \mathtt
    2. Отформатировать псевдокоды
    3. Добавить категорию
  7. Timsort
  8. Smoothsort
  9. взяли Теорема о нижней оценке для сортировки сравнениями
    10. (4)
    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. Сортировка подсчетом
  5. Цифровая сортировка
  6. Карманная сортировка
  7. Сортировка Хана
    1. (10) В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
  8. Задача флага Нидерландов
  9. Блинная сортировка

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

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

  1. Целочисленный двоичный поиск
  2. Поиск в матрице
  3. Вещественный двоичный поиск
  4. Троичный поиск 2
    1. Про == нужно сказать другое
    2. Добавить про унимодальность функции в начале
    3. Сказать, почему плохо, когда функция не строго монотонна
    4. Добавить сюда метод дихотомии
  5. Поиск с помощью золотого сечения
  6. Интерполяционный поиск 2
    1. Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
    2. Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
  7. Метод Фибоначчи 2?
    1. Пример работы алгоритма
    2. Что-то еще может быть, написать куратору

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

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

11. Связь между структурами данных

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_и_структуры_данных:Тикеты&oldid=66746»