Участник:Shersh/Тикеты ко 2ому терму

Материал из Викиконспекты
< Участник:Shersh
Версия от 16:41, 12 февраля 2015; Shersh (обсуждение | вклад) (→‎4. Поисковые структуры данных (проверяются))
Перейти к: навигация, поиск

Тикеты индексируются как "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. Приоритетные очереди

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

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

  1. Наивные реализации (0.5)
    1. Сделать структуру в списке типа Generic
    2. Написать про возможную частую ошибку в реализации массивом
    3. Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
  2. Списки с весовой эвристикой (0.5)
    1. Оформить правильно источники информации
    2. Интервики на амортизационный анализ
    3. Добавить пробелы в Других реализациях перед (
    4. Англоязычные термины правильно оформить
  3. !!! Реализация с помощью леса корневых деревьев (8)
    1. Интервики
    2. Функции в тексте взять в \mathrm
    3. Заменить \ge на \geqslant
    4. Добавить определение итерированного логарифма, а то из текста непонятно, что это такое
    5. Переменные и константы взять в tex
    6. Пояснить переходы в оценке ранговой эвристики: про интервал, про оценку на [math] R(v_1) [/math], и вообще, сделать доказательство более понятным
    7. Отформатировать псевдокоды
    8. Убрать запятые в определении функции аккермана
    9. Оформить правильно источники информации
    10. Добавить См. также
  4. !!! СНМ с операцией удаления за О(1) (8)
    1. "Наша структура данных должна" - убрать наша
    2. Заменить введение на описание
    3. Все переменные взять в Tex
    4. Добавить, что корень — это представитель
    5. max заменить на \max
    6. Провести аналогию со списками в модификации первого соображения
    7. Пояснить неподписанные шаги в некоторых функциях
    8. Операцию присваивания нормально написать (через стрелочку или просто через равно)
    9. N_list и DFS_list по-разному в конспекте называются, надо одинаково сделать
    10. "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
    11. Постараться обезличить текст
    12. Кое-где не хватает точек в конце предложений
    13. Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
    14. Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)

4. Поисковые структуры данных (проверяются)

0. Поисковые структуры данных (10)
  1. Табличка поисковых структур как в Сортировке
  2. Здесь хочется видеть какую-нибудь классификацию, время работы разных процедур (худшее, среднее), занимаемую память и особенности
  3. Неплохо бы также сказать о различных деревьях, которых нет на викиконспектах
  1. Упорядоченное множество (4)
    1. Расширить определение до элементов, на которых задан порядок
    2. Пункт определение не нужен
    3. Названия функций в тексте обернуть в \mathrm
    4. Имена функций оформить в lowerCamelCase
    5. Добавить наивную реализацию на массиве
    6. Добавить ссылок
    7. Сказать примечание, что если нам не нужна упорядоченность, то с этой задачей неплохо ещё хеши справляются
  2. !!! Дерево поиска, наивная реализация (7)
    1. Правильно оформить англоиязычные термины
    2. Тире заменить на шаблон
    3. Отформатировать псевдокод
    4. Функции в тексте обернуть в \mathrm
    5. Ссылки объединить с литературой, добавить больше ссылок, оформить красиво
    6. Заменить названия обходов на preorder и postorder
    7. Добавить простые рекурсивные варианты всех (или почти всех операций), когда нам не нужно хранить родителей, в удалении есть два способа реализации, пояснить разницу
    8. Кажется, что удаление можно написать проще, даже в таком варианте
  3. !!! АВЛ-дерево (7)
    1. Исправить знаки неравенств в tex
    2. Заменить тире на шаблон
    3. Константы обернуть в tex
    4. Литературу заменить на источники информации, добавить ссылок
    5. Англоязычные термины
    6. Псевдокоды поворотов (с родителями и без)
    7. Картинки, поясняющие расстановку балансов после поворотов (большого и малого), то есть со шкалой высот рядом
    8. !!! Рассмотреть реализацию с меньшим количеством памяти в узлах
  4. 2-3 дерево (1.5)
    1. Как-то структура криво оформлена; неплохо бы ещё сказать, как это на практике хранится/удобно реализовывается.
    2. Источники информаии оформить правильно
    3. Случаи сделать списком
    4. Пояснить во вставке про изменения ключей в родителях
    5. +4 за красивую картинку вставки с расщеплением нескольких узлов
  5. B-дерево (1.5)
    1. Опять бы структуру красивей оформить
    2. Увеличить дроби
    3. Отформатировать псевдокод
    4. Оформить правильно См. также и Источники информации
  6. !!! Красно-черное дерево (6)
    1. Ангоязычные термины
    2. Тире в тексте — на шаблон
    3. Константы взять в tex
    4. Оформить красиво источники информации
    5. Добавить См. также
    6. Определение выделить жирным
    7. В Кормене чуть другое определение красно-чёрного дерева: рассмотреть эквивалентность
    8. А что будет, если сделать корень дерева красным?
    9. Чем же 1 бит - это преимущество? Во всех современных ЯП самый маленький тип имеет размер 1 байт.
  7. !!! Декартово дерево (6)
    1. Тире заменить на шаблон
    2. Имена функций оформить в lowerCamelCase
    3. Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев
    4. Разобраться с приоритетами (см. обсуждение)
    5. Какое-то палево в удалении с k.x - eps
    6. Оформить правильно источники информации
    7. Заменить знаки неравенств
  8. Декартово дерево по неявному ключу (4)
    1. Добавить псевдокод
    2. Тире заменить на шаблон
    3. Сделать интервики на Rope
    4. Добавить ссылок
    5. Функции в тексте обернуть в \mathrm и оформить их в lowerCamelCase
  9. !!! Splay-дерево (8)
    1. Оформить правильно англоязычные термины
    2. Исправить знаки неравенств в tex
    3. Увеличить дроби
    4. Дефисы заменить на шаблон тире
    5. Показать, что лемма верна для любого фиксированного веса узла
    6. Функции оформить в lowerCamelCase
    7. Пример, когда move to root занимает [math]\Omega(n)[/math] времени, и заменить O на омегу
    8. Знаки умножения заменить на \cdot
    9. Заменить многоточия на \ldots
  10. !!! Tango-дерево (8)
    1. Доказательство теоремы Уилбера
    2. А причём тут вообще она?
  11. Рандомизированное бинарное дерево поиска (4)
    1. Отформатировать псевдокод
    2. Функции в тексте взять в \mathrm
    3. Умножение сделать везде единообразным, например, через \cdot
    4. Переменные и константы в тексте взять в tex
    5. Увеличить дроби
    6. Первое определение выделить жирным
    7. Вертикальную черту в tex заменить на \mid
    8. Оформить правильно источники информации
    9. Убрать скобки вокруг похожих идей
  12. Дерево ван Эмде Боаса (1)
    1. Имена функций взять в \mathrm
    2. Отформатировать псевдокод
    3. Англоязычные термины
    4. Оформить правильно источники информации
    5. Добавить См. также
  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 (5)
    1. Тире заменить на шаблон
    2. sketch cделать везде с маленькой буквы, а кое-где исправить snetch на sketch
    3. XOR заменить на \oplus
    4. AND тоже заменить на что-то хорошее
    5. succ cделать с маленькой буквы
    6. Добавить про цикл Де Брюина и сказать, где он применяется (см. лекции Станкевича)
    7. Оформить правильно источники информации
    8. Сделать в утверждении список через #, убрать ";"
    9. +1 в карму за нахождение непонятно объяснённого момента
  15. Сверхбыстрый цифровой бор (2)
    1. Отформатировать псевдокоды
    2. Сказать, почему префиксы в хеше не буду есть много памяти
    3. Добавить См. также
    4. Многоточия заменить на \ldots
  16. Rope (+2 в карму)
    1. Почему бы не хранить просто вектор указателей на строки, а подстроки брать slice'ами?
    2. И что ещё можно делать с Rope?

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

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

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=44849»