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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Защищена страница «Участник:Shersh/Тикеты ко 2ому терму» ([edit=sysop] (бессрочно) [move=sysop] (бессрочно)))
(→‎1. Амортизационный анализ)
Строка 2: Строка 2:
  
 
== 1. Амортизационный анализ ==
 
== 1. Амортизационный анализ ==
−
# '''fixed''' [[Амортизационный анализ]]
+
# '''!!!''' [[Амортизационный анализ]] (до ''10'')
−
## Увеличить маленькие дроби
+
## Англоязычные термины
−
## Добавить ссылок
+
## Нормальный нумерованный список
−
## Добавить интервики
+
## Добавить интересных примеров (по ''3'' за пример)
−
## Список в стеке с multipop поправить {{---}} он очень некрасиво смотрится
+
# '''!!!''' [[Динамический массив]] (''10'')
−
## Исправить tex, а ещё некоторые речевые ошибки в конспекте
+
## Оптимизации реализаций в реальной жизни https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md (кеши, всё такое)
−
## Функции взять в \mathrm
+
## Сравнение со списком
−
## Добавить парочку примеров на методы.
+
## Англоязычные термины
−
# [[Саморасширяющийся массив]]
+
## Потенциальный анализ для произвольных A, B, C
−
# '''fixed''' [[Массив с увеличением/уменьшением размера]]
+
# '''!!!''' [[Hashed Array Tree]] (''5'')
−
## Объединить с предыдущим
+
## Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
−
## Поправить tex: неравенства поменять, дроби увеличить
+
## Добавить про ''буферизованный'' список
−
## Добавить информацию о том, какие структуры данных в современных языках программирования используют саморасширяющийся массив
+
## Редактирование по мелочи
−
# '''fixed''' [[Список]]
+
# [[Список]]
−
## Заменить тире на шаблон
+
## Интересные задачи на список (по ''3'' за каждую)
−
## Отформатировать псевдокод
+
# [[Стек]] (0.5)
−
## Поправить ссылки в См. также, сделать маркированным списком
+
## Обозначения перед псевдокодом в \mathtt
−
## Объединить Ссылки и Литературу
+
## Ссылки на источники информации
−
## Добавить категории
+
## Многоточия на \dots
−
## Добавить примеры интересных задач на списки (обычно их спрашивают на собеседованиях)
+
# [[Очередь]] (0.5)
−
# ''fixed'' [[Стек]]
 
−
## Отрефакторить псевдокод
 
−
## Поправить ссылки
 
−
## Имена функций в тексте обернуть в \mathrm
 
−
## Оформить имена функций в lowerCamelCase
 
−
## Добавить интервики на список
 
−
## Заменить тире на {{---}}
 
−
# ''fixed'' [[Очередь]]
 
 
## То же самое, что и в предыдущем
 
## То же самое, что и в предыдущем
−
## Плюсы и Минусы оформить единообразно маркированным списком
+
# [[Персистентный стек]] (''3'')
−
## Заменить ссылки в источника на интервики
+
## Пример задачи
−
# '''!!!''' [[Персистентный стек]]
+
## Более подробный псевдокод
−
# '''!!!''' [[Персистентная очередь]]
+
## Оформить нормально источники информации
−
# '''!!!''' [[Персистентный дек]]
+
# [[Персистентная очередь]] (''1'')
−
## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)
+
## Убрать заголовки первого уровня
−
# [[Мажорирующий элемент]]
+
## Оформить правильно источники информации
 +
## Оформить правильно кортеж, длинные обозначения в tex взять в \mathtt
 +
## Отформатировать псевдокоды
 +
# [[Персистентный дек]]
 +
# [[Мажорирующий элемент]] (''1.5'')
 
## Поправить псевдокод
 
## Поправить псевдокод
 
## Заменить тире на шаблон, а кое-где {{---}} наоборот, на дефис
 
## Заменить тире на шаблон, а кое-где {{---}} наоборот, на дефис
Строка 43: Строка 39:
 
## Убрать скобки из диапазона массива
 
## Убрать скобки из диапазона массива
 
## Заменить size в доказательстве про K на ||
 
## Заменить size в доказательстве про K на ||
−
# '''fixed''' [[Счетчик Кнута]]
+
## Длинные обозначения взять в \mathtt
−
## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)
+
## Заменить источники на источники информации
−
## Может быть можно обобщить как-то на случай <tex>d</tex>-ичной системы счисления? (используется в толстых кучах)
+
# '''!!!''' [[Счетчик Кнута]] (10)
−
## Будет полезно добавить источники, если про это где-то можно почитать
+
## Добавить прибавление к произвольному разряду за O(1)
−
## Полностью переписать конспект, он очень невнятный
 
  
 
== 2. Приоритетные очереди ==
 
== 2. Приоритетные очереди ==

Версия 00:15, 20 января 2015

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

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

  1. !!! Амортизационный анализ (до 10)
    1. Англоязычные термины
    2. Нормальный нумерованный список
    3. Добавить интересных примеров (по 3 за пример)
  2. !!! Динамический массив (10)
    1. Оптимизации реализаций в реальной жизни https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md (кеши, всё такое)
    2. Сравнение со списком
    3. Англоязычные термины
    4. Потенциальный анализ для произвольных A, B, C
  3. !!! Hashed Array Tree (5)
    1. Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
    2. Добавить про буферизованный список
    3. Редактирование по мелочи
  4. Список
    1. Интересные задачи на список (по 3 за каждую)
  5. Стек (0.5)
    1. Обозначения перед псевдокодом в \mathtt
    2. Ссылки на источники информации
    3. Многоточия на \dots
  6. Очередь (0.5)
    1. То же самое, что и в предыдущем
  7. Персистентный стек (3)
    1. Пример задачи
    2. Более подробный псевдокод
    3. Оформить нормально источники информации
  8. Персистентная очередь (1)
    1. Убрать заголовки первого уровня
    2. Оформить правильно источники информации
    3. Оформить правильно кортеж, длинные обозначения в tex взять в \mathtt
    4. Отформатировать псевдокоды
  9. Персистентный дек
  10. Мажорирующий элемент (1.5)
    1. Поправить псевдокод
    2. Заменить тире на шаблон, а кое-где — наоборот, на дефис
    3.  != в тексте заменить на \ne
    4. Убрать скобки из диапазона массива
    5. Заменить size в доказательстве про K на ||
    6. Длинные обозначения взять в \mathtt
    7. Заменить источники на источники информации
  11. !!! Счетчик Кнута (10)
    1. Добавить прибавление к произвольному разряду за O(1)

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

  1. fixed Двоичная куча
    1. Ссылки на википедию сделать через интервики
    2. Отформатировать псевдокод
    3. Названия функций сделать в lowerCamelCase, например, siftDown
    4. Функции в тексте обернуть в \mathrm
  2. fixed Биномиальная куча
    1. Увеличить размер сочетаний
    2. Отрефакторить псевдокод
    3. Круглые скобки в логарифме можно убрать
    4. Названия функций в тексте обернуть в \mathrm
  3. fixed Фибоначчиева куча
    1. Ссылки заменить на интервики
    2. Функции в тексте обернуть в \mathrm
    3. Скобки в логарифме можно убрать
    4. Все переменные и константы взять в tex
    5. Исправить уровни заголовков
    6. Местами текст смешивается с tex, непонятны переходы становятся
  4. Левосторонняя куча
  5. Тонкая куча
    1. То же самое, что в фибоначчиевых кучах
  6. Толстая куча на избыточном счетчике
    1. Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
    2. Ссылка в интервики с большой буквы — заменить на маленькую
    3. Отформатировать псевдокод
    4. Всё оформлено в UpperCamelCase, наверное, надо что-то с этим сделать
    5. Названия функций обернуть в \mathrm
    6. Поправить ошибку в Источниках
    7. Все переменные и константы взять в tex
    8. "Основные операции оформить аккуратней
    9. В одном месте лишнее выделение текста псевдокодным прямоугольником, в другом месте комментарий вылез за псевдокод
  7. !!! Куча Бродала-Окасаки
    1. Ссылки заменить на источники информации, сделать маркированным списком
    2. Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
    3. Написать подробней операции

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

  1. fixed Наивные реализации
    1. Добавить формальное определение
    2. Переменные и константы взять в tex
    3. Функции взять в \mathrm
    4. Отформатировать псевдокод
    5. Картинку можно убрать из thumb
    6. Источники объединить с ссылками
  2. Списки с весовой эвристикой
    1. Имена функций в тексте обернуть в \mathrm
    2. Отформатировать псевдокод
    3. Объединить источники и ссылки
  3. !!! Реализация с помощью леса корневых деревьев
    1. Интервики
    2. Функции в тексте взять в \mathrm
    3. Заменить \ge на \geqslant
    4. Добавить определение итерированного логарифма, а то из текста непонятно, что это такое
    5. Переменные и константы взять в tex
    6. Пояснить переходы в оценке ранговой эвристики: про интервал, про оценку на [math] R(v_1 [/math]
    7. Добавить другие эвристики и оценить их

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

  1. Упорядоченное множество
    1. Названия функций в тексте обернуть в \mathrm
    2. Имена функций оформить в lowerCamelCase
    3. Расширить определение до элементов, на которых задан порядок
    4. Добавить несколько слов о наивной реализации на массиве
    5. Добавить ссылок
  2. !!! Дерево поиска, наивная реализация
    1. Тире заменить на шаблон
    2. Отформатировать псевдокод
    3. Добавить про персистентное двоичное дерево и псевдокод операций вставки и удаления: показать как там всё просто
    4. Функции в тексте обернуть в \mathrm
    5. Ссылки объединить с литературой, добавить больше ссылок, оформить красиво
  3. АВЛ-дерево
    1. Исправить знаки неравенств в tex
    2. Заменить тире на шаблон
    3. Константы обернуть в tex
    4. Литературу заменить на источники информации, добавить ссылок
    5. !!! Рассмотреть реализацию с меньшим количеством памяти в узлах
  4. 2-3 дерево
    1. Ссылки оформить красиво
    2. Случаи сделать списком
  5. B-дерево
    1. Увеличить дроби
    2. Отформатировать псевдокод
  6. !!! Красно-черное дерево
    1. Дефис в определении заменить на тире
    2. Тире в тексте — на шаблон
    3. Константы взять в tex
    4. Оформить красиво источники информации
    5. Определение выделить жирным
    6. В Кормене чуть другое определение красно-чёрного дерева: рассмотреть эквивалентность
    7. Добавить операцию split
  7. Декартово дерево
    1. Тире заменить на шаблон
    2. Имена функций оформить в lowerCamelCase
    3. Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев
    4. Отформатировать псевдокод
  8. Декартово дерево по неявному ключу
    1. Добавить псевдокод
    2. Тире заменить на шаблон
    3. Сделать интервики на Rope
    4. Добавить ссылок
    5. Функции в тексте обернуть в \mathrm и оформить их в lowerCamelCase
  9. !!! Splay-дерево
    1. Исправить знаки неравенств в tex
    2. Увеличить дроби
    3. Тире заменить на шаблон
    4. Показать, что лемма верна для любого фиксированного веса узла
    5. Функции оформить в lowerCamelCase
  10. Рандомизированное бинарное дерево поиска
    1. Отформатировать псевдокод
    2. Функции в тексте взять в \mathrm
    3. Умножение сделать везде единообразным, например, через \cdot
    4. Переменные и константы в тексте взять в tex
  11. Дерево ван Эмде Боаса
    1. Имена функций взять в \mathrm
    2. Отформатировать псевдокод
  12. !!! Список с пропусками
    1. \theta cделать большой буквой
    2. Определение в начале мутное
    3. Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
    4. Увеличить дроби
    5. Отформатировать псевдокод
    6. log заменить на \log
    7. Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
  13. Fusion tree
    1. Тире заменить на шаблон
    2. sketch cделать везде с маленькой буквы, а кое-где исправить snetch на sketch
    3. XOR заменить на \oplus
    4. succ cделать с маленькой буквы
  14. Сверхбыстрый цифровой бор

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

  1. Статистики на отрезках. Корневая эвристика
    1. Отформатировать псевдокод
    2. Заменить тире на шаблон
  2. fixed Дерево отрезков. Построение
    1. Добавить псевдокод персистентного дерева отрезков
    2. Заменить в псевдокоде f на бинарную операцию [math] \circ [/math]
    3. Поправить ссылки в источниках
    4. Поправить tex: знаки неравенств, дроби и т. п.
    5. Отрефакторить псевдокод
    6. Исправить несогласованность текста и псевдокода: в тексте полуинтервал, а в псевдоде — отрезок
    7. Исправить ошибку в картинке персистентного дерева
  3. fixed Реализация запроса в дереве отрезков сверху
    1. Отформатировать псевдокод
    2. Тире заменить на шаблон
    3. Заменить "Ссылки" на источники информации и оформить их маркированным списком
    4. Добавить см. также на реализацию запросов cнизу
  4. fixed Реализация запроса в дереве отрезков снизу
    1. Отформатировать псевдокод
    2. Имена переменных оформить в lowerCamelCase
    3. Переменные в тексте взять в tex
    4. Источники информации оформить маркированным списком
    5. Добавить см. также на реализацию запросов сверху
  5. Несогласованные поддеревья. Реализация массового обновления
    1. Константы взять в tex
    2. Отформатировать псевдокод
    3. Добавить примеры массовых операций
  6. Многомерное дерево отрезков
    1. Константы взять в tex
    2. Отформатировать псевдокод
  7. Сжатое многомерное дерево отрезков
    1. Отформатировать псевдокод
    2. Литературу заменить на Источники информации

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

  1. !!! Дерево Фенвика
    1. Тире заменить на шаблон
    2. Исправить багу в доказательстве (см. обсуждения)
    3. Битовые операции окружить пробелами
    4. Знаки неравенств заменить на \leqslant и \geqslant
    5. Расписать эквивалентность формул с числом единиц и побитовые операции
    6. Заменить i = \overline{0, n - 1} на i = 0 .. n - 1
    7. Добавить описание побитовых операций в самое начало, чтобы не использовать их перед их определением
    8. Отформатировать псевдокод
    9. Оформить красиво ссылки
    10. Добавить категории
    11. Имена функций взять в \mathrm
    12. Добавить преимущества и недостатки дерева Фенвика
  2. Встречное дерево Фенвика
    1. Добавить категории
    2. Добавить ссылок
    3. "отрезок длины 1..2^n" — странное обозначение длины
    4. Умножение матриц не является коммутативной операцией, добавить другой пример
  3. Дерево Фенвика для некоммутативных операций
    1. Добавить категории
    2. Доказательство оформить в виде шаблона теоремы или заменить на "Корректность"
    3. Скобки вокруг n в log(n) можно убрать
  4. !!! Многомерное дерево Фенвика
    1. Тире заменить на шаблон
    2. Отформатировать псевдокод
    3. Разместить картинку так, чтобы не залезала на псевдокод
    4. Имена функций обернуть в \mathrm
    5. Псевдокод сделать отдельным подпунктом
    6. Оформить красиво ссылки
    7. Добавить категории
    8. Перерисовать картинку (см. обсуждения)

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

  1. Хеш-таблица
    1. Смотрите обсуждения
    2. Константы взять в tex
    3. Понятия в тексте взять в шаблон определения
    4. Многоточия в tex заменить на \dots
  2. Разрешение коллизий
    1. Отформатировать псевдокод
    2. Разрешение коллизий из предыдущего конспекта перенести в этот, а в том сделать интервики на данный конспект
    3. Имена функций взять в \mathrm
    4. \mod заменить на \bmod
    5. Поправить ссылки
    6. !!! Добавить оценку на длину кластеров
  3. Хеширование кукушки
    1. Взять в tex знаки = и константы
    2. Добавить интервики
    3. Объединить ссылки с источниками
  4. Идеальное хеширование
    1. Заменить тире на шаблон
    2. Ссылку на неравенство Маркова оформить как интервики на соответствующий конспект
  5. Перехеширование. Амортизационный анализ
    1. Оформить функции в lowerCamelCase и обернуть их в тексте в \mathrm
    2. Изменить знаки неравенств
    3. Добавить ссылок
  6. Фильтр Блума
  7. Универсальное семейство хеш-функций
    1. Добавить ссылок

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

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

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

  1. fixed Сортирующие сети
    1. Занести оставшиеся определения в Шаблон: Определение
    2. Англоязычные термины ко всем
    3. Ссылки на вики через интервики
  2. Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
    1. Ссылки через интервики
    2. Поменять знаки неравенст в tex на более красивые
  3. Сортировочные сети с особыми свойствами
  4. Сортирующие сети для квадратичных сортировок
  5. Сеть Бетчера

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

  1. взяли Целочисленный двоичный поиск
    1. Заменить тире на Шаблон:---
    2. Англоязычные термины
    3. Переменные взять в tex
    4. Отформатировать псевдокод
    5. Добавить категории
    6. <= заменить в tex на \leqslant
    7. Добавить эвристику с запоминанием последнего узла при последовательных запросах и её оценку
    8. Добавить ссылок
    9. Пару слов о том, чем плохо условие на остановку, если вдруг попали в нужный элемент (или чем хорошо)
  2. fixed Вещественный двоичный поиск
    1. Плюсы и минусы cпособов оформить по-красивому
    2. Отформатировать псевдокод
    3. Добавить категории
    4. Добавить оценку на число итераций
    5. Больше ссылок
  3. fixed Троичный поиск
    1. Добавить категории
    2. Добавить ссылок
    3. Отформатировать псевдокод
    4. Сделать так, чтобы картинка не залезала на псевдокод
    5. Англоязычные термины
    6. Увеличить дроби
    7. См. также красиво оформить
  4. взяли Поиск с помощью золотого сечения
    1. Отформатировать псевдокод
    2. Дроби увеличить
    3. Добавить категории
    4. Добавить аналогичный, но другое поиск фибоначчи
    5. Небольшой рефакторинг структуры конспекта
  5. fixed Интерполяционный поиск
    1. Расположения картинки и псевдокода относительно друг друга не очень удачные
    2. Нормальную картинку сделать
    3. Ссылки нормально оформить
    4. Расписать асимптотику нормально
    5. Отформатировать псевдокод
    6. Примеры данных, на которых поиск работает хорошо
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_ко_2ому_терму&oldid=44721»