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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (4. Поисковые структуры данных)
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты ко 2ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показано 89 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
 
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
  
== 0. Амортизационный анализ ==
+
== 1. Амортизационный анализ ==
# '''!!!''' [[Амортизационный анализ]] (до ''10'')
+
# ''fixed'' [[Амортизационный анализ]] (0.5)
 
## Англоязычные термины
 
## Англоязычные термины
 
## Нормальный нумерованный список
 
## Нормальный нумерованный список
## Добавить интересных примеров (по ''3'' за пример)
+
# '''!!!''' [[Динамический массив]] (''6'')
# '''взяли''' [[Динамический массив]] (''5'')
 
 
## Сравнение со списком
 
## Сравнение со списком
 
## Англоязычные термины
 
## Англоязычные термины
Строка 15: Строка 14:
 
## Редактирование по мелочи
 
## Редактирование по мелочи
 
# [[Список]]
 
# [[Список]]
## Интересные задачи на список (по ''3'' за каждую)
+
# [[Стек]]
# ''fixed'' [[Стек]] (0.5)
+
# [[Очередь]]
## Обозначения перед псевдокодом в \mathtt
+
# [[Дек]]
## Ссылки на источники информации
+
# [[Мажорирующий элемент]]
## Многоточия на \dots
 
# ''fixed'' [[Очередь]] (''0.5'')
 
## То же самое, что и в предыдущем
 
# ''взяли'' [[Мажорирующий элемент]] (''1.5'')
 
## Поправить псевдокод
 
## Заменить тире на шаблон, а кое-где {{---}} наоборот, на дефис
 
## != в тексте заменить на \ne
 
## Убрать скобки из диапазона массива
 
## Заменить size в доказательстве про K на ||
 
## Длинные обозначения взять в \mathtt
 
## Заменить источники на источники информации
 
 
# '''!!!''' [[Счетчик Кнута]] (''5'')
 
# '''!!!''' [[Счетчик Кнута]] (''5'')
 
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
 
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
 +
# [[Мастер-теорема]]
 +
# [[List order maintenance]]
  
== 1. Персистентные структуры данных ==
+
== 2. Персистентные структуры данных ==
# ''fixed'' [[Персистентный стек]] (''3'')
+
# [[Персистентные структуры данных]]
## Пример задачи
+
# [[Персистентный стек]]
## Более подробный псевдокод
+
# [[Персистентная очередь]]
## Оформить нормально источники информации
 
# ''fixed'' [[Персистентная очередь]] (''1'')
 
## Убрать заголовки первого уровня
 
## Оформить правильно источники информации
 
## Оформить правильно кортеж, длинные обозначения в tex взять в \mathtt
 
## Отформатировать псевдокоды
 
 
# [[Персистентный дек]]
 
# [[Персистентный дек]]
 +
# '''fixed''' [[Персистентная приоритетная очередь]] (10)
 +
## Отрефакторить псевдокод
 +
## Добавить красивые картинки
 +
## Оформить всё правильно
 +
## Добавить наивное решение на дереве
 +
## Подробней описать решение
  
== 2. Приоритетные очереди ==
+
== 3. Приоритетные очереди ==
: 0. '''взяли''' [[Приоритетные очереди]] (''10'')
+
: 0. [[Приоритетные очереди]]
:# Добавить табличку с кучами и асимптотиками операций, как в [[Сортировка | сортировке]]
+
# [[Двоичная куча]]
:# Надо пояснить, какой интерфейс должны реализовывать приоритетные очереди, как они реализованы в современных языках программирования
+
# [[Биномиальная куча]]
:# Добавить даже про те кучи, которых нет на вики-конспектах (возможно, потом добавятся)
+
# '''!!!''' [[Фибоначчиева куча]] (5-10)
:# Добавить всякой общей информации (где применяются, зачем нужны, почему не бывает "быстрых" куч)
+
## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
# '''fixed''' [[Двоичная куча]] (''5'')
 
## Англоязычные термины
 
## Добавить про merge
 
## Добавить про поиск k-того элемента в как будто отсортированном массиве (''+1'' за красивую картинку)
 
## Красивая картинка расположения элементов двоичной кучи в массиве (с линиями от элементов массива к сыновьям)
 
# ''fixed'' [[Биномиальная куча]] (''3'')
 
## Англоязычные термины
 
## Табличку сделать красивой
 
## Добавить про конфлюэнтную персистентность биномиальных куч
 
# ''fixed'' [[Фибоначчиева куча]] (''2'')
 
## Англоязычные термины
 
## Оформить структуру узла (то есть только первый пункт структуры) псевдокдом с комментариями
 
## Табличку оформить красиво
 
 
# [[Левосторонняя куча]]
 
# [[Левосторонняя куча]]
# ''взяли'' [[Тонкая куча]] (''4'')
+
# [[Тонкая куча]]
## Оформить правильно англоязычные термины
+
# [[Толстая куча на избыточном счетчике]]
## Взять длинные обозначение в \mathrm
 
## Табличку сделать красивой
 
## Отформатировать псевдокоды
 
## Оформить структуру узла и кучи псевдокодом с комментариями
 
# '''!!!''' [[Толстая куча на избыточном счетчике]] (''7'')
 
## Англоязычные термины
 
## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
 
## Ссылка в интервики с большой буквы {{---}} заменить на маленькую
 
## Отформатировать псевдокод
 
## Всё оформлено в UpperCamelCase, наверное, надо что-то с этим сделать
 
## Названия функций обернуть в \mathrm
 
## Поправить ошибку в Источниках
 
## Все переменные и константы взять в tex
 
## "Основные операции оформить аккуратней
 
## В одном месте лишнее выделение текста псевдокодным прямоугольником, в другом месте комментарий вылез за псевдокод
 
## Заголовки сделать на уровень меньше
 
## Структуру оформить псевдокодом с комментариями
 
## Подпункты с большой буквы назвать
 
## Возможно, надо будет исправить что-то ещё, слишком много трэша
 
 
# [[Куча Бродала-Окасаки]] (''4'')
 
# [[Куча Бродала-Окасаки]] (''4'')
 
## Ссылки заменить на источники информации, сделать маркированным списком
 
## Ссылки заменить на источники информации, сделать маркированным списком
Строка 93: Строка 51:
 
## Заменить Смотри также на См. также
 
## Заменить Смотри также на См. также
  
== 3. Система непересекающихся множеств ==
+
== 4. Система непересекающихся множеств ==
# ''взяли'' [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'')
+
# [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'')
 
## Сделать структуру в списке типа Generic
 
## Сделать структуру в списке типа Generic
 
## Написать про возможную частую ошибку в реализации массивом
 
## Написать про возможную частую ошибку в реализации массивом
 
## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
 
## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
# ''взяли'' [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] (''0.5'')
+
# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] (''0.5'')
 
## Оформить правильно источники информации
 
## Оформить правильно источники информации
 
## Интервики на амортизационный анализ
 
## Интервики на амортизационный анализ
 
## Добавить пробелы в Других реализациях перед (
 
## Добавить пробелы в Других реализациях перед (
 
## Англоязычные термины правильно оформить
 
## Англоязычные термины правильно оформить
# '''fixed''' [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] (''8'')
+
# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
## Интервики
+
# '''!!!''' [[СНМ с операцией удаления за О(1)]] (''6'')
## Функции в тексте взять в \mathrm
 
## Заменить \ge на \geqslant
 
## Добавить определение итерированного логарифма, а то из текста непонятно, что это такое
 
## Переменные и константы взять в tex
 
## Пояснить переходы в оценке ранговой эвристики: про интервал, про оценку на <tex> R(v_1) </tex>, и вообще, сделать доказательство более понятным
 
## Отформатировать псевдокоды
 
## Убрать запятые в определении функции аккермана
 
## Оформить правильно источники информации
 
## Добавить См. также
 
# '''взяли''' [[СНМ с операцией удаления за О(1)]] (''8'')
 
## "Наша структура данных должна" - убрать наша
 
## Заменить введение на описание
 
## Все переменные взять в Tex
 
## Добавить, что корень {{---}} это представитель
 
## max заменить на \max
 
## Провести аналогию со списками в модификации первого соображения
 
## Пояснить неподписанные шаги в некоторых функциях
 
## Операцию присваивания нормально написать (через стрелочку или просто через равно)
 
## N_list и DFS_list по-разному в конспекте называются, надо одинаково сделать
 
 
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
 
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
## Постараться обезличить текст
 
 
## Кое-где не хватает точек в конце предложений
 
## Кое-где не хватает точек в конце предложений
 +
## Вообще кажется, что можно проще
 
## Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
 
## Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
 
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
 
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
  
== 4. Поисковые структуры данных==
+
== 5. Поисковые структуры данных==
:0. '''added''' [[Поисковые структуры данных]] (''10'')
+
:0. [[Поисковые структуры данных]]
:# Табличка поисковых структур как в Сортировке
+
# [[Упорядоченное множество]]
:# Здесь хочется видеть какую-нибудь классификацию, время работы разных процедур (худшее, среднее), занимаемую память и особенности
+
# [[Дерево поиска, наивная реализация]]
:# Неплохо бы также сказать о различных деревьях, которых нет на викиконспектах
+
# [[АВЛ-дерево]]
# '''взяли''' [[Упорядоченное множество]] (''5'')
+
# [[2-3 дерево]]
## Расширить определение до элементов, на которых задан порядок
+
# [[B-дерево]]
## Пункт определение не нужен
+
# [[Красно-черное дерево]]
## Названия функций в тексте обернуть в \mathrm
+
# [[Декартово дерево]]
## Имена функций оформить в lowerCamelCase
+
# [[Декартово дерево по неявному ключу]] (1)
## Добавить наивную реализацию на массиве
+
## В псевдокоде нет проверок на ''null''
## Добавить ссылок
+
# [[Splay-дерево]]
## Сказать примечание, что если нам не нужна упорядоченность, то с этой задачей неплохо ещё хеши справляются
 
# '''fixed''' [[Дерево поиска, наивная реализация]] (''7'')
 
## Правильно оформить англоязычные термины
 
## Тире заменить на шаблон
 
## Отформатировать псевдокод
 
## Функции в тексте обернуть в \mathrm
 
## Ссылки объединить с литературой, добавить больше ссылок, оформить красиво
 
## Заменить названия обходов на preorder и postorder
 
## Добавить простые рекурсивные варианты всех (или почти всех операций), когда нам не нужно хранить родителей, в удалении есть два способа реализации, пояснить разницу
 
## Кажется, что удаление можно написать проще, даже в таком варианте
 
# '''fixed''' [[АВЛ-дерево]] (''7'')
 
## Исправить знаки неравенств в tex
 
## Заменить тире на шаблон
 
## Константы обернуть в tex
 
## Литературу заменить на источники информации, добавить ссылок
 
## Англоязычные термины
 
## Псевдокоды поворотов (с родителями и без)
 
## Картинки, поясняющие расстановку балансов после поворотов (большого и малого), то есть со шкалой высот рядом
 
# ''fixed'' [[2-3 дерево]] (''1.5'')
 
## Как-то структура криво оформлена; неплохо бы ещё сказать, как это на практике хранится/удобно реализовывается.
 
## Источники информаии оформить правильно
 
## Случаи сделать списком
 
## Пояснить во вставке про изменения ключей в родителях
 
## ''+4'' за красивую картинку вставки с расщеплением нескольких узлов
 
# ''взяли'' [[B-дерево]] (''1.5'')
 
## Опять бы структуру красивей оформить
 
## Увеличить дроби
 
## Отформатировать псевдокод
 
## Оформить правильно См. также и Источники информации
 
# '''fixed''' [[Красно-черное дерево]] (''6'')
 
## Ангоязычные термины
 
## Тире в тексте {{---}} на шаблон
 
## Константы взять в tex
 
## Оформить красиво источники информации
 
## Добавить См. также
 
## Определение выделить жирным
 
## В Кормене чуть другое определение красно-чёрного дерева: рассмотреть эквивалентность
 
## А что будет, если сделать корень дерева красным?
 
## Чем же 1 бит - это преимущество? Во всех современных ЯП самый маленький тип имеет размер 1 байт.
 
# '''взяли''' [[Декартово дерево]] (''6'')
 
## Тире заменить на шаблон
 
## Имена функций оформить в lowerCamelCase
 
## Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев
 
## Разобраться с приоритетами (см. обсуждение)
 
## Какое-то палево в удалении с k.x - eps
 
## Оформить правильно источники информации
 
## Заменить знаки неравенств
 
# ''fixed'' [[Декартово дерево по неявному ключу]] (''4'')
 
## Добавить псевдокод
 
## Тире заменить на шаблон
 
## Сделать интервики на Rope
 
## Добавить ссылок
 
## Функции в тексте обернуть в \mathrm и оформить их в lowerCamelCase
 
# '''!!!''' [[Splay-дерево]] (''8'')
 
## Оформить правильно англоязычные термины
 
## Исправить знаки неравенств в tex
 
## Увеличить дроби
 
## Дефисы заменить на шаблон тире
 
## Показать, что лемма верна для любого фиксированного веса узла
 
## Функции оформить в lowerCamelCase
 
## Пример, когда move to root занимает <tex>\Omega(n)</tex> времени, и заменить O на омегу
 
## Знаки умножения заменить на \cdot
 
## Заменить многоточия на \ldots
 
 
# '''!!!''' [[Tango-дерево]] (''8'')
 
# '''!!!''' [[Tango-дерево]] (''8'')
 
## Доказательство теоремы Уилбера
 
## Доказательство теоремы Уилбера
 
## А причём тут вообще она?
 
## А причём тут вообще она?
# ''fixed'' [[Рандомизированное бинарное дерево поиска]] (''4'')
+
# [[Рандомизированное бинарное дерево поиска]]
## Отформатировать псевдокод
+
# [[Дерево ван Эмде Боаса]]
## Функции в тексте взять в \mathrm
+
# '''!!!''' [[Список с пропусками]] (''7'')
## Умножение сделать везде единообразным, например, через \cdot
 
## Переменные и константы в тексте взять в tex
 
## Увеличить дроби
 
## Первое определение выделить жирным
 
## Вертикальную черту в tex заменить на \mid
 
## Оформить правильно источники информации
 
## Убрать скобки вокруг похожих идей
 
# ''fixed'' [[Дерево ван Эмде Боаса]] (''1'')
 
## Имена функций взять в \mathrm
 
## Отформатировать псевдокод
 
## Англоязычные термины
 
## Оформить правильно источники информации
 
## Добавить См. также
 
# '''взяли''' [[Список с пропусками]] (''7'')
 
 
## \theta cделать большой буквой
 
## \theta cделать большой буквой
 
## Определение в начале мутное
 
## Определение в начале мутное
Строка 237: Строка 99:
 
## Добавить См. также
 
## Добавить См. также
 
## Написать, почему все так любят скиплист, особенно в вычислительной геометрии
 
## Написать, почему все так любят скиплист, особенно в вычислительной геометрии
# '''fixed''' [[Fusion tree]] (''5'')
+
# [[Fusion tree]]
## Тире заменить на шаблон
 
## sketch cделать везде с маленькой буквы, а кое-где исправить snetch на sketch
 
## XOR заменить на \oplus
 
## AND тоже заменить на что-то хорошее
 
## succ cделать с маленькой буквы
 
## Добавить про цикл Де Брюина и сказать, где он применяется (см. лекции Станкевича)
 
## Оформить правильно источники информации
 
## Сделать в утверждении список через #, убрать ";"
 
 
# [[Сверхбыстрый цифровой бор]] (''2'')
 
# [[Сверхбыстрый цифровой бор]] (''2'')
 
## Отформатировать псевдокоды
 
## Отформатировать псевдокоды
Строка 251: Строка 105:
 
## Добавить См. также
 
## Добавить См. также
 
## Многоточия заменить на \ldots
 
## Многоточия заменить на \ldots
# [[Rope]] (''+2 в карму'')
+
# [[Rope]]
## Почему бы не хранить просто вектор указателей на строки, а подстроки брать slice'ами?
 
## И что ещё можно делать с Rope?
 
  
== 5. Дерево отрезков==
+
== 6. Дерево отрезков==
# ''fixed'' [[Статистики на отрезках. Корневая эвристика]] (''1.5'')
+
# [[Статистики на отрезках. Корневая эвристика]]
## Отформатировать псевдокод
+
# [[Дерево отрезков. Построение]]
## Заменить тире на шаблон
 
## Увеличить дроби
 
## Заменить Источники на источники информации
 
## Пример, когда нужна необходимость
 
## Исправить определение
 
## Преимущества sqrt-декомпозиции
 
# ''fixed'' [[Дерево отрезков. Построение]] (''1.5'')
 
## Присвоение элементам ДО одного значения {{---}} не ассоциативная операция, значит, про моноид надо поправить
 
## Пояснить подробней про моноиды (например, что минимум {{---}} это моноид) (''+1 ещё за каждый интересный пример задачи'')
 
## Заменить знаки неравенства
 
## Увеличить дроби
 
## Отформартировать псевдокод
 
## Оформить правильно См. также и ссылки
 
## Перенести про персистентность в конспект про персистентные СД
 
 
# [[Реализация запроса в дереве отрезков сверху]] (''0.5'')
 
# [[Реализация запроса в дереве отрезков сверху]] (''0.5'')
 
## Много пробелов в коде, отформатировать
 
## Много пробелов в коде, отформатировать
Строка 286: Строка 124:
 
## Оформить правильно источники информации
 
## Оформить правильно источники информации
 
## Добавить см. также
 
## Добавить см. также
# ''fixed'' [[Многомерное дерево отрезков]] (''2'')
+
# [[Многомерное дерево отрезков]]  
## Взять задачу в Шаблон:Задача
+
# ''fixed'' [[Сжатое многомерное дерево отрезков]] (''1'')
## Константы взять в tex
 
## Отформатировать псевдокод
 
## Многоточие заменить на \ldots
 
## Оформить правильно Источники информации и См. также
 
# [[Сжатое многомерное дерево отрезков]] (''1'')
 
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 
## Англоязычные термины
 
## Англоязычные термины
Строка 300: Строка 133:
 
## Добавить категории
 
## Добавить категории
  
== 6. Дерево Фенвика ==
+
== 7. Дерево Фенвика ==
# '''fixed''' [[Дерево Фенвика]] (''8'')
+
# [[Дерево Фенвика]]
## Англоязычные термины
+
# [[Встречное дерево Фенвика]]
## Тире заменить на шаблон
+
# [[Дерево Фенвика для некоммутативных операций]]
## Исправить багу в доказательстве (см. обсуждения)
+
# [[Многомерное дерево Фенвика]]
## Битовые операции окружить пробелами
 
## Знаки неравенств заменить на \leqslant и \geqslant
 
## Расписать эквивалентность формул с числом единиц и побитовые операции
 
## Заменить i = \overline{0, n - 1} на i = 0 .. n - 1
 
## Добавить описание побитовых операций в самое начало, чтобы не использовать их перед их определением
 
## Отформатировать псевдокод
 
## Оформить красиво ссылки
 
## Добавить категории
 
## Имена функций взять в \mathrm
 
## Добавить преимущества и недостатки дерева Фенвика
 
## Сделать красивые таблички
 
# ''fixed'' [[Встречное дерево Фенвика]] (''3'')
 
## Англоязычные термины
 
## Добавить категории
 
## Добавить ссылок
 
## Добавить См. также
 
## Оформить правильно источники информации
 
## "отрезок длины 1..2^n" {{---}} странное обозначение длины
 
## Умножение матриц не является коммутативной операцией, добавить другой пример
 
## Свойства и картинки нормально оформить
 
# ''fixed'' [[Дерево Фенвика для некоммутативных операций]] (''0.5'')
 
## Добавить категории
 
## Доказательство оформить в виде шаблона теоремы или заменить на "Корректность"
 
## Скобки вокруг n в log(n) можно убрать
 
## Добавить См. также, Источники информации по возможности
 
# '''взяли''' [[Многомерное дерево Фенвика]] (''7'')
 
## Тире заменить на шаблон
 
## Отформатировать псевдокод
 
## Разместить картинку так, чтобы не залезала на псевдокод
 
## Имена функций обернуть в \mathrm
 
## Псевдокод сделать отдельным подпунктом
 
## Оформить красиво ссылки
 
## Добавить категории
 
## Добавить См. также
 
## Перерисовать картинку (см. обсуждения)
 
## Англоязычные термины
 
  
== 7. Хеширование ==
+
== 8. Хеширование ==
# ''fixed'' [[Хеш-таблица]] (''3'')
+
# [[Хеш-таблица]]
## Смотрите обсуждения
+
# [[Разрешение коллизий]]  
## Англоязычные термины
 
## Сказать, какой интерфейс реализует (ассоциативный массив) и провести аналогию с деревьями поиска
 
## Какие классы в современных языках реализуют хеширование
 
## Константы взять в tex
 
## Понятия в тексте взять в шаблон определения
 
## Многоточия в tex заменить на \dots
 
## Оформить правильно Источники информации
 
# ''fixed'' [[Разрешение коллизий]] (''4'')
 
## Определение убрать, оно уже есть в другом конспекте, на него просто интервики надо сделать
 
## Добавить про способ борьбы с коллизиями в Java 8 (''+2 в карму за картинку такого способа'')
 
## Отформатировать псевдокод
 
## Разрешение коллизий из предыдущего конспекта перенести в этот, а в том сделать интервики на данный конспект
 
## Имена функций взять в \mathrm
 
## \mod заменить на \bmod
 
## Англоязычные термины
 
## Оформить правильно Источники информации
 
 
# [[Хеширование кукушки]] (''2'')
 
# [[Хеширование кукушки]] (''2'')
 
## Англоязычные термины
 
## Англоязычные термины
Строка 368: Строка 149:
 
## А что делать в случае зацикливания?
 
## А что делать в случае зацикливания?
 
## Плюсы-минусы метода
 
## Плюсы-минусы метода
# ''fixed'' [[Идеальное хеширование]] (''0.5'')
+
# [[Идеальное хеширование]]
## Англоязычные термины
 
## Задачу взять в Шаблон
 
## Заменить тире на шаблон
 
## Ссылку на неравенство Маркова оформить как интервики на соответствующий конспект
 
## Оформить правильно Источники информации
 
 
# [[Перехеширование. Амортизационный анализ]] (''1'')
 
# [[Перехеширование. Амортизационный анализ]] (''1'')
 
## Пояснить, почему будет O(1) на добавление при перехешировании
 
## Пояснить, почему будет O(1) на добавление при перехешировании
# [[Фильтр Блума]] (0.3)
+
# [[Фильтр Блума]] (1.5)
## Оформить правильно Источники информации
+
# [[Quotient filter]] (3)
## Англоязычные термины
+
## Сделать нормальное описание алгоритма, а то ничего не понятно
## Константы, AND, OR в Tex
+
# [[Универсальное семейство хеш-функций]] (''0.5'')
# ''взяли'' [[Универсальное семейство хеш-функций]] (''0.5'')
 
 
## Добавить ссылок
 
## Добавить ссылок
 
## Англоязычные термины
 
## Англоязычные термины
Строка 388: Строка 163:
 
## Заменить знаки неравенств
 
## Заменить знаки неравенств
 
## Добавить "информации" в источники
 
## Добавить "информации" в источники
 +
# '''!!!''' [[Расширяемое хеширование]] (5)
 +
## Красивые картинки
 +
## Понятное описание
  
== 8. Сортировка ==
+
== 9. Сортировка ==
:0. ''fixed'' [[Сортировка]] (''1'')
+
:0. [[Сортировка]]
:# Англоязычные термины
 
:# Сказать ещё про мнопоточные алгоритмы
 
:# Оформить правильно Источники информации
 
:# Добавить недостающие сортировки с конспектов
 
 
=== Квадратичные сортировки ===
 
=== Квадратичные сортировки ===
# ''взяли'' [[Сортировка выбором]] (''0.5'')
+
# [[Сортировка выбором]]
## Ссылку через интервики
 
## Оформить правильно англоязычные термины
 
## Отформатировать псевдокоды
 
## Сказать, в чём разница между двумя вариантами и оформить сами варианты красивей
 
## Оформить правильно источники информации
 
## Добавить См. также
 
## Добавить категорию
 
 
# [[Сортировка пузырьком]] (''2'')
 
# [[Сортировка пузырьком]] (''2'')
 
## Сделать единообразные псевдокоды с равным количеством отступов
 
## Сделать единообразные псевдокоды с равным количеством отступов
Строка 410: Строка 177:
 
## Увеличить дроби
 
## Увеличить дроби
 
## Добавить категорию
 
## Добавить категорию
# ''fixed''  [[Сортировка вставками]] (''0.5'')
+
# [[Сортировка вставками]]
## Англоязычные термины
 
## Убрать жирное выделение BinSearch в модификации вставками и написать с маленькой буквы
 
## Оформить правильно Источники информации
 
## Добавить категорию
 
  
 
=== Сортировки на сравнениях ===
 
=== Сортировки на сравнениях ===
 
<ol>
 
<ol>
<li value="4"> [[Сортировка Шелла]] (''0.3'') </li>
+
<li value="4"> [[Сортировка Шелла]] </li>
# Заменить дефисы на тире
+
<li> [[Сортировка кучей]] </li>
# Заменить многоточия на \ldots
+
<li> [[Быстрая сортировка]] (''2'') </li>
# Написать правильно ln
+
<li> [[Сортировка слиянием]] </li>
# Пофиксить категории
+
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
# Оформить правильно Источники информации и См. также
 
<li> '''fixed''' [[Сортировка кучей]] (''5'') </li>
 
# Оформить правильно англоязычные термины
 
# Обернуть имена функций в \mathrm
 
# Отформатировать псевдокоды
 
# Добавить См. также
 
# Оформить правильно Источники информации
 
# Добавить категорию
 
# Объяснить, почему модификация JSort даёт вообще какой-то выигрыш, добавить картинки JSort
 
<li> [[Быстрая сортировка]] (''1.5'') </li>
 
# Англоязычные термины
 
# Описание алгоритма сделать покрасивей
 
# Заменить многоточия на \ldots
 
# Увеличить дроби
 
# Пояснить про разбиение массива на три части и чем это помогает
 
# Добавить ещё модификаций
 
# Добавить См. также
 
# Добавить категорию
 
<li> ''fixed'' [[Сортировка слиянием]] (''4'') </li>
 
# Анимированную работу алгоритма сделать ссылкой-примечанием
 
# Можно убрать скобки в логарифме
 
# Отформатировать псевдокод
 
# Картинка залезает на псевдокод
 
# А лучше вообще перерисовать картинку слияния, создать красивую, а то существующая убогая
 
# Полуинтервалы в тексте взять в tex
 
# Добавить См. также
 
# Добавить псевдокод итеративной сортировки слиянием
 
# Оформить правильно Источники информации
 
# Добавить категорию
 
# Многоточия заменить на \dots
 
<li> ''взяли'' [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
 
 
# Оформить правильно Источники информации
 
# Оформить правильно Источники информации
 
# Добавить категорию
 
# Добавить категорию
 
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
 
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
<li> [[Терпеливая сортировка]] (0.2) </li>
+
<li> [[Терпеливая сортировка]] (0.5) </li>
 
# Имена массивов взять в \mathtt
 
# Имена массивов взять в \mathtt
 
# Отформатировать псевдокоды
 
# Отформатировать псевдокоды
 
# Добавить категорию
 
# Добавить категорию
<li> ''fixed'' [[Timsort]] (''4'') </li>
+
<li> [[Timsort]] </li>
# Последнюю картинку можно сделать более красочной, поэтому надо её перерисовать
+
<li> [[Smoothsort]] </li>
# Отформатировать псевдокоды
+
<li> [[Теорема о нижней оценке для сортировки сравнениями]] </li>
# Заменить знаки неравенств
 
# Обозначения переменных в тексте взять в \mathtt
 
# and заменить на знак конъюнкции
 
# min заменить на \min
 
# Заменить Источники на источники информации
 
# Добавить категорию
 
# Многоточия заменить на \dots
 
# Рассмотреть баг, недавно обнаруженный в реализациях Java, Android, etc
 
<li> ''взяли'' [[Теорема о нижней оценке для сортировки сравнениями]] (''1'') </li>
 
 
# Заменить знаки неравенств
 
# Заменить знаки неравенств
 
# Добавить "информации" в источники
 
# Добавить "информации" в источники
Строка 481: Строка 204:
 
=== Многопоточные сортировки ===
 
=== Многопоточные сортировки ===
 
<ol>
 
<ol>
<li value="12"> ''fixed'' [[Многопоточная сортировка слиянием]] (''0.5'') </li>
+
<li value="12"> [[Многопоточная сортировка слиянием]] </li>
# Комментарии в зелёный
 
# Пофиксить категории
 
# Добавить См. также
 
# Заменить дефисы на тире
 
 
<li> [[PSRS-сортировка]] </li>
 
<li> [[PSRS-сортировка]] </li>
 
</ol>
 
</ol>
Строка 491: Строка 210:
 
=== Другие сортировки ===
 
=== Другие сортировки ===
 
<ol>
 
<ol>
<li value="14"> [[Поиск k-ой порядковой статистики]] (''1.5'') </li>
+
<li value="14"> [[Поиск k-ой порядковой статистики]] (''2'') </li>
 
# Англоязычные термины
 
# Англоязычные термины
 
# Переменные в Tex
 
# Переменные в Tex
Строка 500: Строка 219:
 
# Добавить категории, См. также
 
# Добавить категории, См. также
 
# Добавить про модификацию partition с разбиением на 3 части
 
# Добавить про модификацию partition с разбиением на 3 части
<li> ''fixed'' [[Поиск k-ой порядковой статистики за линейное время]] (''0.5'') </li>
+
# Кажется, что не работает, так как partition возвращает абсолютное смещение
# Дублируется определение
+
<li> [[Поиск k-ой порядковой статистики за линейное время]] </li>
# Убрать пункт "Историческая справка"
+
<li> [[Поиск k-ой порядковой статистики в двух массивах]]
# Увеличить дроби
+
<li> ''fixed'' [[Сортировка подсчетом]] (''1'') </li>
# Заменить знаки неравенств
 
# Оформить правильно источники информации
 
# Добавить категорию
 
<li> ''взяли'' [[Сортировка подсчетом]] (''1'') </li>
 
 
# Англоязычные термины
 
# Англоязычные термины
 
# Отформартировать псевдокод
 
# Отформартировать псевдокод
Строка 515: Строка 230:
 
# Добавить категорию
 
# Добавить категорию
 
<li> [[Цифровая сортировка]] </li>
 
<li> [[Цифровая сортировка]] </li>
<li> ''fixed'' [[Карманная сортировка]] (''0.5'') </li>
+
<li> [[Карманная сортировка]] </li>
# Оформить правильно англ. термины
+
<li> [[Сортировка Хана]] </li>
# Отформатировать псевдокод
+
# '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
# Тету сделать большой
+
<li> [[Задача флага Нидерландов]] </li>
# Оформить правильно источники информации
 
# Добавить См. также
 
# Добавить категорию
 
# Принцип работы красиво оформить
 
# Картинка залезает на код
 
<li> '''взяли''' [[Сортировка Хана]] (''7'') </li>
 
# Дефисы заменить на тире
 
# Оформить правильно англоязычные термины
 
# Определения {{---}} жирным
 
# Возможно про ЭП-дерево стоит отдельный конспект написать, обсудить с куратором при желании взяться за это
 
# Увеличить дроби
 
# Добавить картинок
 
# == в тексте не используется
 
# "Algorithm Sort(k \log\log n, level, a_{0}, a_{1}, \ldots, a_{t})" {{---}} непонятные обозначения, пояснить, что всё это значит, и оформить красиво
 
# Все константы и переменные взять в Tex
 
# Добавить категорию
 
 
</ol>
 
</ol>
  
== 9. Сортирующие сети ==
+
== 10. Сортирующие сети ==
# ''взяли'' [[Сортирующие сети]] (''0.3'')
+
# [[Сортирующие сети]]
## Оформить правильно англоязычные термины
+
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
## Заменить min и max на \min и \max
+
# [[Сортирующие сети для квадратичных сортировок]]
## Добавить "информации" в источники
+
# [[Сортировочные сети с особыми свойствами]]  
# ''взяли'' [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] (''0.5'')
+
# ''fixed'' [[Сеть Бетчера]] (''0.5'')
## "Обычно можно оценить" - немного странно здесь выглядит обычно
 
## Заменить знаки неравенств
 
## Англоязычные термины
 
## Написать, что определение обозначения [i:j] для компаратора
 
## Оформить правильно Источники информации
 
## Добавить См. также
 
# '''fixed''' [[Сортирующие сети для квадратичных сортировок]] (''5'')
 
## Добавить доказательства размеров слоёв в сетях
 
## Оформить правильно Источники информации
 
## Добавить См. также на особые свойства
 
# ''взяли'' [[Сортировочные сети с особыми свойствами]] (''0.2'')
 
## Переименовать конспект в "Сортирующие сети..."
 
## Оформить правильно англ. термины
 
## Оформить правильно источники информации
 
# [[Сеть Бетчера]] (''0.5'')
 
 
## Оформить правильно англ. термины
 
## Оформить правильно англ. термины
 
## Внутренние ссылки оформить примечаниями
 
## Внутренние ссылки оформить примечаниями
Строка 566: Строка 250:
 
## Добавить См. также
 
## Добавить См. также
  
== 10. Алгоритмы поиска ==
+
== 11. Алгоритмы поиска ==
# ''взяли'' [[Целочисленный двоичный поиск]] (''1'')
+
# [[Целочисленный двоичный поиск]]
## Задачу в Шаблон
+
# [[Поиск в матрице]]
## В псевдокоде надо l = -1, а к len(a) можно не добавлять 1
 
## Добавить про вариант без переполнения в псевдокод
 
## Заменить дефис на тире
 
## Сделать псевдокод более generic-like
 
 
# [[Вещественный двоичный поиск]]
 
# [[Вещественный двоичный поиск]]
 
# [[Троичный поиск]] (''2'')
 
# [[Троичный поиск]] (''2'')
Строка 579: Строка 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. Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях