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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. ==...»)
 
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты ко 2ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показаны 223 промежуточные версии этого же участника)
Строка 2: Строка 2:
  
 
== 1. Амортизационный анализ ==
 
== 1. Амортизационный анализ ==
−
# '''fixed''' [[Амортизационный анализ]]
+
# ''fixed'' [[Амортизационный анализ]] (0.5)
−
## Увеличить маленькие дроби
+
## Англоязычные термины
−
## Добавить ссылок
+
## Нормальный нумерованный список
−
## Добавить интервики
+
# '''!!!''' [[Динамический массив]] (''6'')
−
## Список в стеке с multipop поправить {{---}} он очень некрасиво смотрится
+
## Сравнение со списком
−
## Исправить tex, а ещё некоторые речевые ошибки в конспекте
+
## Англоязычные термины
−
## Функции взять в \mathrm
+
## Потенциальный анализ для произвольных A, B, C
−
## Добавить парочку примеров на методы.
+
# '''!!!''' [[Hashed Array Tree]] (''5'')
−
# [[Саморасширяющийся массив]]
+
## Сравнение с таким способом: храним указатели на массивы константного размера, размеры массивов не меняем, увеличиваем только массив указателей (чтобы не копировать). За сколько будет работать?
−
# '''fixed''' [[Массив с увеличением/уменьшением размера]]
+
## Добавить про ''буферизованный'' список
−
## Объединить с предыдущим
+
## Редактирование по мелочи
−
## Поправить tex: неравенства поменять, дроби увеличить
+
# [[Список]]
−
## Добавить информацию о том, какие структуры данных в современных языках программирования используют саморасширяющийся массив
+
# [[Стек]]
−
# '''fixed''' [[Список]]
+
# [[Очередь]]
−
## Заменить тире на шаблон
+
# [[Дек]]
−
## Отформатировать псевдокод
 
−
## Поправить ссылки в См. также, сделать маркированным списком
 
−
## Объединить Ссылки и Литературу
 
−
## Добавить категории
 
−
## Добавить примеры интересных задач на списки (обычно их спрашивают на собеседованиях)
 
−
# ''fixed'' [[Стек]]
 
−
## Отрефакторить псевдокод
 
−
## Поправить ссылки
 
−
## Имена функций в тексте обернуть в \mathrm
 
−
## Оформить имена функций в lowerCamelCase
 
−
## Добавить интервики на список
 
−
## Заменить тире на {{---}}
 
−
# ''fixed'' [[Очередь]]
 
−
## То же самое, что и в предыдущем
 
−
## Плюсы и Минусы оформить единообразно маркированным списком
 
−
## Заменить ссылки в источника на интервики
 
−
# '''!!!''' [[Персистентный стек]]
 
−
# '''!!!''' [[Персистентная очередь]]
 
−
# '''!!!''' [[Персистентный дек]]
 
−
## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)
 
 
# [[Мажорирующий элемент]]
 
# [[Мажорирующий элемент]]
−
## Поправить псевдокод
+
# '''!!!''' [[Счетчик Кнута]] (''5'')
−
## Заменить тире на шаблон, а кое-где {{---}} наоборот, на дефис
+
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
−
## != в тексте заменить на \ne
+
# [[Мастер-теорема]]
−
## Убрать скобки из диапазона массива
+
# [[List order maintenance]]
−
## Заменить size в доказательстве про K на ||
 
−
# '''fixed''' [[Счетчик Кнута]]
 
−
## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)
 
−
## Может быть можно обобщить как-то на случай <tex>d</tex>-ичной системы счисления? (используется в толстых кучах)
 
−
## Будет полезно добавить источники, если про это где-то можно почитать
 
−
## Полностью переписать конспект, он очень невнятный
 
  
−
== 2. Приоритетные очереди ==
+
== 2. Персистентные структуры данных ==
−
# ''fixed'' [[Двоичная куча]]
+
# [[Персистентные структуры данных]]
−
## Ссылки на википедию сделать через интервики
+
# [[Персистентный стек]]
−
## Отформатировать псевдокод
+
# [[Персистентная очередь]]
−
## Названия функций сделать в lowerCamelCase, например, siftDown
+
# [[Персистентный дек]]
−
## Функции в тексте обернуть в \mathrm
+
# '''fixed''' [[Персистентная приоритетная очередь]] (10)
−
# ''fixed'' [[Биномиальная куча]]
 
−
## Увеличить размер сочетаний
 
 
## Отрефакторить псевдокод
 
## Отрефакторить псевдокод
−
## Круглые скобки в логарифме можно убрать
+
## Добавить красивые картинки
−
## Названия функций в тексте обернуть в \mathrm
+
## Оформить всё правильно
−
# '''fixed''' [[Фибоначчиева куча]]
+
## Добавить наивное решение на дереве
−
## Ссылки заменить на интервики
+
## Подробней описать решение
−
## Функции в тексте обернуть в \mathrm
+
 
−
## Скобки в логарифме можно убрать
+
== 3. Приоритетные очереди ==
−
## Все переменные и константы взять в tex
+
: 0. [[Приоритетные очереди]]
−
## Исправить уровни заголовков
+
# [[Двоичная куча]]
−
## Местами текст смешивается с tex, непонятны переходы становятся
+
# [[Биномиальная куча]]
 +
# '''!!!''' [[Фибоначчиева куча]] (5-10)
 +
## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
 
# [[Левосторонняя куча]]
 
# [[Левосторонняя куча]]
 
# [[Тонкая куча]]
 
# [[Тонкая куча]]
−
## То же самое, что в фибоначчиевых кучах
 
 
# [[Толстая куча на избыточном счетчике]]
 
# [[Толстая куча на избыточном счетчике]]
−
## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
+
# [[Куча Бродала-Окасаки]] (''4'')
−
## Ссылка в интервики с большой буквы {{---}} заменить на маленькую
 
−
## Отформатировать псевдокод
 
−
## Всё оформлено в UpperCamelCase, наверное, надо что-то с этим сделать
 
−
## Названия функций обернуть в \mathrm
 
−
## Поправить ошибку в Источниках
 
−
## Все переменные и константы взять в tex
 
−
## "Основные операции оформить аккуратней
 
−
## В одном месте лишнее выделение текста псевдокодным прямоугольником, в другом месте комментарий вылез за псевдокод
 
−
# '''!!!''' [[Куча Бродала-Окасаки]]
 
 
## Ссылки заменить на источники информации, сделать маркированным списком
 
## Ссылки заменить на источники информации, сделать маркированным списком
 
## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
 
## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
 
## Написать подробней операции
 
## Написать подробней операции
 +
## Форматнуть чутка псевдокод
 +
## Заменить Смотри также на См. также
  
−
== 3. Система непересекающихся множеств ==
+
== 4. Система непересекающихся множеств ==
−
# ''fixed'' [[СНМ (наивные реализации) | Наивные реализации]]
+
# [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'')
−
## Добавить формальное определение
+
## Сделать структуру в списке типа Generic
−
## Переменные и константы взять в tex
+
## Написать про возможную частую ошибку в реализации массивом
−
## Функции взять в \mathrm
+
## Взять обозначения перед псевдокодом и внутри комментариев в \mathtt
−
## Отформатировать псевдокод
+
# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] (''0.5'')
−
## Картинку можно убрать из thumb
+
## Оформить правильно источники информации
−
## Источники объединить с ссылками
+
## Интервики на амортизационный анализ
−
# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
+
## Добавить пробелы в Других реализациях перед (
−
## Имена функций в тексте обернуть в \mathrm
+
## Англоязычные термины правильно оформить
−
## Отформатировать псевдокод
+
# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
−
## Объединить источники и ссылки
+
# '''!!!''' [[СНМ с операцией удаления за О(1)]] (''6'')
−
# '''!!!''' [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
+
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
−
## Интервики
+
## Кое-где не хватает точек в конце предложений
−
## Функции в тексте взять в \mathrm
+
## Вообще кажется, что можно проще
−
## Заменить \ge на \geqslant
+
## Пояснить соображения для второй модификации, начав с того, почему нельзя сделать намного проще: хранить в корне просто список листьев поддерева с этим корнем; во время union объединить два списка; во время get просто добавить все вершины пути к списку листьев корня (а то что-то развели в конспекте текста на дофига). Если внезапно окажется, что можно проще, то переписать всё.
−
## Добавить определение итерированного логарифма, а то из текста непонятно, что это такое
+
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
−
## Переменные и константы взять в tex
 
−
## Пояснить переходы в оценке ранговой эвристики: про интервал, про оценку на <tex> R(v_1 </tex>
 
−
## Добавить другие эвристики и оценить их
 
−
 
 
−
== 4. Поисковые структуры данных ==
 
  
 +
== 5. Поисковые структуры данных==
 +
:0. [[Поисковые структуры данных]]
 
# [[Упорядоченное множество]]
 
# [[Упорядоченное множество]]
−
## Названия функций в тексте обернуть в \mathrm
+
# [[Дерево поиска, наивная реализация]]
−
## Имена функций оформить в lowerCamelCase
 
−
## Расширить определение до элементов, на которых задан порядок
 
−
## Добавить несколько слов о наивной реализации на массиве
 
−
## Добавить ссылок
 
−
# '''!!!''' [[Дерево поиска, наивная реализация]]
 
−
## Тире заменить на шаблон
 
−
## Отформатировать псевдокод
 
−
## Добавить про персистентное двоичное дерево и псевдокод операций вставки и удаления: показать как там всё просто
 
−
## Функции в тексте обернуть в \mathrm
 
−
## Ссылки объединить с литературой, добавить больше ссылок, оформить красиво
 
 
# [[АВЛ-дерево]]
 
# [[АВЛ-дерево]]
−
## Исправить знаки неравенств в tex
 
−
## Заменить тире на шаблон
 
−
## Константы обернуть в tex
 
−
## Литературу заменить на источники информации, добавить ссылок
 
−
## '''!!!''' Рассмотреть реализацию с меньшим количеством памяти в узлах
 
 
# [[2-3 дерево]]
 
# [[2-3 дерево]]
−
## Ссылки оформить красиво
 
−
## Случаи сделать списком
 
 
# [[B-дерево]]
 
# [[B-дерево]]
−
## Увеличить дроби
+
# [[Красно-черное дерево]]
−
## Отформатировать псевдокод
 
−
# '''!!!''' [[Красно-черное дерево]]
 
−
## Дефис в определении заменить на тире
 
−
## Тире в тексте {{---}} на шаблон
 
−
## Константы взять в tex
 
−
## Оформить красиво источники информации
 
−
## Определение выделить жирным
 
−
## В Кормене чуть другое определение красно-чёрного дерева: рассмотреть эквивалентность
 
−
## Добавить операцию [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf split]
 
 
# [[Декартово дерево]]
 
# [[Декартово дерево]]
−
## Тире заменить на шаблон
+
# [[Декартово дерево по неявному ключу]] (1)
−
## Имена функций оформить в lowerCamelCase
+
## В псевдокоде нет проверок на ''null''
−
## Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев
+
# [[Splay-дерево]]
−
## Отформатировать псевдокод
+
# '''!!!''' [[Tango-дерево]] (''8'')
−
# [[Декартово дерево по неявному ключу]]
+
## Доказательство теоремы Уилбера
−
## Добавить псевдокод
+
## А причём тут вообще она?
−
## Тире заменить на шаблон
 
−
## Сделать интервики на Rope
 
−
## Добавить ссылок
 
−
## Функции в тексте обернуть в \mathrm и оформить их в lowerCamelCase
 
−
# '''!!!''' [[Splay-дерево]]
 
−
## Исправить знаки неравенств в tex
 
−
## Увеличить дроби
 
−
## Тире заменить на шаблон
 
−
## Показать, что лемма верна для любого фиксированного веса узла
 
−
## Функции оформить в lowerCamelCase
 
 
# [[Рандомизированное бинарное дерево поиска]]
 
# [[Рандомизированное бинарное дерево поиска]]
−
## Отформатировать псевдокод
 
−
## Функции в тексте взять в \mathrm
 
−
## Умножение сделать везде единообразным, например, через \cdot
 
−
## Переменные и константы в тексте взять в tex
 
 
# [[Дерево ван Эмде Боаса]]
 
# [[Дерево ван Эмде Боаса]]
−
## Имена функций взять в \mathrm
+
# '''!!!''' [[Список с пропусками]] (''7'')
−
## Отформатировать псевдокод
 
−
# '''!!!''' [[Список с пропусками]]
 
 
## \theta cделать большой буквой
 
## \theta cделать большой буквой
 
## Определение в начале мутное
 
## Определение в начале мутное
 +
## Оформить правильно англоязычные термины
 
## Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
 
## Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
 
## Увеличить дроби
 
## Увеличить дроби
 +
## Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 
## log заменить на \log
 
## log заменить на \log
 
## Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
 
## Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
 +
## Оформить правильно источники информации
 +
## Добавить См. также
 +
## Написать, почему все так любят скиплист, особенно в вычислительной геометрии
 
# [[Fusion tree]]
 
# [[Fusion tree]]
−
## Тире заменить на шаблон
+
# [[Сверхбыстрый цифровой бор]] (''2'')
−
## sketch cделать везде с маленькой буквы, а кое-где исправить snetch на sketch
+
## Отформатировать псевдокоды
−
## XOR заменить на \oplus
+
## Сказать, почему префиксы в хеше не буду есть много памяти
−
## succ cделать с маленькой буквы
+
## Добавить См. также
−
# [[Сверхбыстрый цифровой бор]]
+
## Многоточия заменить на \ldots
−
 
+
# [[Rope]]
−
== 5. Дерево отрезков ==
 
  
 +
== 6. Дерево отрезков==
 
# [[Статистики на отрезках. Корневая эвристика]]
 
# [[Статистики на отрезках. Корневая эвристика]]
−
## Отформатировать псевдокод
+
# [[Дерево отрезков. Построение]]
−
## Заменить тире на шаблон
+
# [[Реализация запроса в дереве отрезков сверху]] (''0.5'')
−
# '''fixed''' [[Дерево отрезков. Построение]]
+
## Много пробелов в коде, отформатировать
−
## Добавить псевдокод персистентного дерева отрезков
+
## Заменить neutral на varepsilon, введя сначала моноид
−
## Заменить в псевдокоде f на бинарную операцию <tex> \circ </tex>
+
## Добавить построение в См. также
−
## Поправить ссылки в источниках
+
## В примере случаи разной глубины красиво оформить
−
## Поправить tex: знаки неравенств, дроби и т. п.
+
# [[Реализация запроса в дереве отрезков снизу]]
−
## Отрефакторить псевдокод
+
# [[Несогласованные поддеревья. Реализация массового обновления]] (''3'')
−
## Исправить несогласованность текста и псевдокода: в тексте полуинтервал, а в псевдоде {{---}} отрезок
+
## Добавить примеры массовых операций в начало
−
## Исправить ошибку в картинке персистентного дерева
+
## В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
−
# ''fixed'' [[Реализация запроса в дереве отрезков сверху]]
 
−
## Отформатировать псевдокод
 
−
## Тире заменить на шаблон
 
−
## Заменить "Ссылки" на источники информации и оформить их маркированным списком
 
−
## Добавить см. также на реализацию запросов cнизу
 
−
# ''fixed'' [[Реализация запроса в дереве отрезков снизу]]
 
−
## Отформатировать псевдокод
 
−
## Имена переменных оформить в lowerCamelCase
 
−
## Переменные в тексте взять в tex
 
−
## Источники информации оформить маркированным списком
 
−
## Добавить см. также на реализацию запросов сверху
 
−
# [[Несогласованные поддеревья. Реализация массового обновления]]
 
−
## Константы взять в tex
 
−
## Отформатировать псевдокод
 
−
## Добавить примеры массовых операций
 
−
# [[Многомерное дерево отрезков]]
 
 
## Константы взять в tex
 
## Константы взять в tex
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
−
# [[Сжатое многомерное дерево отрезков]]
+
## Обозначения перед псевдокодов взять в \mathtt или в \mathrm
 +
## Оформить правильно источники информации
 +
## Добавить см. также
 +
# [[Многомерное дерево отрезков]]
 +
# ''fixed'' [[Сжатое многомерное дерево отрезков]] (''1'')
 
## Отформатировать псевдокод
 
## Отформатировать псевдокод
 +
## Англоязычные термины
 
## Литературу заменить на Источники информации
 
## Литературу заменить на Источники информации
 +
## Первую картинку заменить на Tex'овскую красивую фигурную скобку
 +
## Добавить См. также
 +
## Добавить категории
  
−
== 6. Дерево Фенвика ==
+
== 7. Дерево Фенвика ==
−
# '''!!!''' [[Дерево Фенвика]]
+
# [[Дерево Фенвика]]
−
## Тире заменить на шаблон
 
−
## Исправить багу в доказательстве (см. обсуждения)
 
−
## Битовые операции окружить пробелами
 
−
## Знаки неравенств заменить на \leqslant и \geqslant
 
−
## Расписать эквивалентность формул с числом единиц и побитовые операции
 
−
## Заменить i = \overline{0, n - 1} на i = 0 .. n - 1
 
−
## Добавить описание побитовых операций в самое начало, чтобы не использовать их перед их определением
 
−
## Отформатировать псевдокод
 
−
## Оформить красиво ссылки
 
−
## Добавить категории
 
−
## Имена функций взять в \mathrm
 
−
## Добавить преимущества и недостатки дерева Фенвика
 
 
# [[Встречное дерево Фенвика]]
 
# [[Встречное дерево Фенвика]]
−
## Добавить категории
 
−
## Добавить ссылок
 
−
## "отрезок длины 1..2^n" {{---}} странное обозначение длины
 
−
## Умножение матриц не является коммутативной операцией, добавить другой пример
 
 
# [[Дерево Фенвика для некоммутативных операций]]
 
# [[Дерево Фенвика для некоммутативных операций]]
−
## Добавить категории
+
# [[Многомерное дерево Фенвика]]
−
## Доказательство оформить в виде шаблона теоремы или заменить на "Корректность"
 
−
## Скобки вокруг n в log(n) можно убрать
 
−
# '''!!!''' [[Многомерное дерево Фенвика]]
 
−
## Тире заменить на шаблон
 
−
## Отформатировать псевдокод
 
−
## Разместить картинку так, чтобы не залезала на псевдокод
 
−
## Имена функций обернуть в \mathrm
 
−
## Псевдокод сделать отдельным подпунктом
 
−
## Оформить красиво ссылки
 
−
## Добавить категории
 
−
## Перерисовать картинку (см. обсуждения)
 
  
−
== 7. Хеширование ==
+
== 8. Хеширование ==
 
# [[Хеш-таблица]]
 
# [[Хеш-таблица]]
−
## Смотрите обсуждения
+
# [[Разрешение коллизий]]  
−
## Константы взять в tex
+
# [[Хеширование кукушки]] (''2'')
−
## Понятия в тексте взять в шаблон определения
+
## Англоязычные термины
−
## Многоточия в tex заменить на \dots
 
−
# [[Разрешение коллизий]]
 
−
## Отформатировать псевдокод
 
−
## Разрешение коллизий из предыдущего конспекта перенести в этот, а в том сделать интервики на данный конспект
 
−
## Имена функций взять в \mathrm
 
−
## \mod заменить на \bmod
 
−
## Поправить ссылки
 
−
## '''!!!''' Добавить оценку на длину кластеров
 
−
# [[Хеширование кукушки]]
 
 
## Взять в tex знаки = и константы
 
## Взять в tex знаки = и константы
 
## Добавить интервики
 
## Добавить интервики
−
## Объединить ссылки с источниками
+
## Оформить правильно источники информации
 +
## А что делать в случае зацикливания?
 +
## Плюсы-минусы метода
 
# [[Идеальное хеширование]]
 
# [[Идеальное хеширование]]
−
## Заменить тире на шаблон
+
# [[Перехеширование. Амортизационный анализ]] (''1'')
−
## Ссылку на неравенство Маркова оформить как интервики на соответствующий конспект
+
## Пояснить, почему будет O(1) на добавление при перехешировании
−
# [[Перехеширование. Амортизационный анализ]]
+
# [[Фильтр Блума]] (1.5)
−
## Оформить функции в lowerCamelCase и обернуть их в тексте в \mathrm
+
# [[Quotient filter]] (3)
−
## Изменить знаки неравенств
+
## Сделать нормальное описание алгоритма, а то ничего не понятно
−
## Добавить ссылок
+
# [[Универсальное семейство хеш-функций]] (''0.5'')
−
# [[Фильтр Блума]]
 
−
# [[Универсальное семейство хеш-функций]]
 
 
## Добавить ссылок
 
## Добавить ссылок
 +
## Англоязычные термины
 +
## Смотри обсуждения
 +
## Заменить многоточия на \dots
 +
## Заменить \mod на \bmod
 +
## Заменить знаки неравенств
 +
## Добавить "информации" в источники
 +
# '''!!!''' [[Расширяемое хеширование]] (5)
 +
## Красивые картинки
 +
## Понятное описание
  
−
== 8. [[Сортировка]] ==
+
== 9. Сортировка ==
 +
:0. [[Сортировка]]
 +
=== Квадратичные сортировки ===
 
# [[Сортировка выбором]]
 
# [[Сортировка выбором]]
−
## Ссылку через интервики
+
# [[Сортировка пузырьком]] (''2'')
−
# '''fixed''' [[Сортировка пузырьком]]
+
## Сделать единообразные псевдокоды с равным количеством отступов
−
## Добавить ещё оптимизаций этой сортировки (шейкерная сортировка, расчёской, odd-even и прочие {{---}} полный список есть на [[ wikipedia:en:Bubble_sort | википедии ]]) {{---}} полностью расписывать не надо, только ссылки и краткое описание. Об уменьшии константы в асимптотике можно пару слов сказать, если только она и уменьшается.
+
## Пояснить преимущества каждой модификации сортировки
−
## Дать точные оценки на число сравнений в худшем случае
+
## Подробней расписать comb sort, и почему там n log n?
−
## Отформатировать псевдокод
 
−
## Ссылка на вики
 
−
# '''fixed''' [[Сортировка вставками]]
 
−
## То же самое, что и в предыдущем тикете
 
 
## Увеличить дроби
 
## Увеличить дроби
−
## Внести переменные и константы в tex
+
## Добавить категорию
−
# [[Сортировка Шелла]]
+
# [[Сортировка вставками]]
−
# '''взяли''' [[Сортировка кучей]]
+
 
−
## Можно добавить всякие модификации сортировки кучей, например, JSort.
+
=== Сортировки на сравнениях ===
−
# ''fixed'' [[Быстрая сортировка]]
+
<ol>
−
## Тут вообще ссылки ужасные
+
<li value="4"> [[Сортировка Шелла]] </li>
−
## Отформатиовать псевдокод
+
<li> [[Сортировка кучей]] </li>
−
# [[Сортировка слиянием]]
+
<li> [[Быстрая сортировка]] (''2'') </li>
−
## Анимированную работу алгоритма сделать ссылкой-примечанием
+
<li> [[Сортировка слиянием]] </li>
−
## Можно убрать скобки в логарифме
+
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
−
## Отформатировать псевдокод
+
# Оформить правильно Источники информации
−
## Картинка залезает на псевдокод
+
# Добавить категорию
−
## Полуинтервалы в тексте взять в tex
+
# Написать в начале, зачем оно надо и насколько эффективно в реальной жизни
−
## Добавить См. также
+
<li> [[Терпеливая сортировка]] (0.5) </li>
−
# [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
+
# Имена массивов взять в \mathtt
−
# [[Теорема о нижней оценке для сортировки сравнениями]]
+
# Отформатировать псевдокоды
−
# [[Сортировка подсчетом]]
+
# Добавить категорию
−
# [[Сортировка подсчетом сложных объектов]]
+
<li> [[Timsort]] </li>
−
# '''fixed''' [[Цифровая сортировка]]
+
<li> [[Smoothsort]] </li>
−
## Добавить модификацию для сортировки цифр в порядке от старших к младшим
+
<li> [[Теорема о нижней оценке для сортировки сравнениями]] </li>
−
## Убрать ; из псевдокода
+
# Заменить знаки неравенств
−
# [[Карманная сортировка]]
+
# Добавить "информации" в источники
−
# [[Поиск k-ой порядковой статистики]]
+
# Добавить пару следствий из теоремы
−
# [[Поиск k-ой порядковой статистики за линейное время]]
+
# Добавить категорию
−
# '''fixed''' [[Сортировка Хана]]
+
</ol>
−
## Привести конспект в порядок!
+
 
−
## Добавить шаблоны определений
+
=== Многопоточные сортировки ===
−
## Добавить шаблоны лемм
+
<ol>
−
## Поправить tex, где его нет
+
<li value="12"> [[Многопоточная сортировка слиянием]] </li>
−
## Корректно оформить ссылки
+
<li> [[PSRS-сортировка]] </li>
−
## Поподробней рассказать про ЭП-дерево
+
</ol>
−
## Использование лемм оформить ссылками
+
 
−
## Структуру поменять, переставить пункты местами, чтобы не было ссылок в тексте на то, что ещё не рассказывалось
+
=== Другие сортировки ===
−
## "Конец" в доказательстве выглядит некрасиво. Как и "Доказательство". Опять же, всё сделать шаблонами
+
<ol>
−
## Псевдокод добавить, если из описания будет не совсем понятно, как это реализовать (данный пункт допускает возможность поправить идейное описание алгоритма вместо добавление псевдокода)
+
<li value="14"> [[Поиск k-ой порядковой статистики]] (''2'') </li>
−
## Возможно, ещё какие-то правки по мелочи
+
# Англоязычные термины
−
## Картинки приветствуются. Если их добавить (или убедить меня, что и так норм, или сделать что-то другое), а всё остальное будет очень няшно сделано, то всё может рассматриваться как целый коспект в баллах.
+
# Переменные в Tex
−
# [[Timsort]]
+
# Отформатировать псевдокод
−
## Последнюю картинку можно сделать более красочной
+
# Заменить знаки неравенств
 +
# Увеличить дроби
 +
# Оформить правильно Источники информации
 +
# Добавить категории, См. также
 +
# Добавить про модификацию partition с разбиением на 3 части
 +
# Кажется, что не работает, так как partition возвращает абсолютное смещение
 +
<li> [[Поиск k-ой порядковой статистики за линейное время]] </li>
 +
<li> [[Поиск k-ой порядковой статистики в двух массивах]]
 +
<li> ''fixed'' [[Сортировка подсчетом]] (''1'') </li>
 +
# Англоязычные термины
 +
# Отформартировать псевдокод
 +
# Добавить, что хоть алгоритм и работает за линейное время, но является псевдополиномиальным
 +
# (+2 за более сочные картинки)
 +
# Добавить "информации" в Источники
 +
# Добавить категорию
 +
<li> [[Цифровая сортировка]] </li>
 +
<li> [[Карманная сортировка]] </li>
 +
<li> [[Сортировка Хана]] </li>
 +
# '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
 +
<li> [[Задача флага Нидерландов]] </li>
 +
</ol>
  
−
== 9. Сортирующие сети ==
+
== 10. Сортирующие сети ==
−
# ''fixed'' [[Сортирующие сети]]
+
# [[Сортирующие сети]]
−
## Занести оставшиеся определения в [[Шаблон: Определение]]
 
−
## Англоязычные термины ко всем
 
−
## Ссылки на вики через интервики
 
 
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
−
## Ссылки через интервики
 
−
## Поменять знаки неравенст в tex на более красивые
 
−
# [[Сортировочные сети с особыми свойствами]]
 
 
# [[Сортирующие сети для квадратичных сортировок]]
 
# [[Сортирующие сети для квадратичных сортировок]]
−
# [[Сеть Бетчера]]
+
# [[Сортировочные сети с особыми свойствами]]
 +
# ''fixed'' [[Сеть Бетчера]] (''0.5'')
 +
## Оформить правильно англ. термины
 +
## Внутренние ссылки оформить примечаниями
 +
## Заменить знаки неравенств
 +
## Увеличить дроби
 +
## Заменить многоточия на \dots
 +
## Оформить правильно Источники информации
 +
## Добавить См. также
  
−
== 10. Алгоритмы поиска ==
+
== 11. Алгоритмы поиска ==
−
# '''взяли''' [[Целочисленный двоичный поиск]]
+
# [[Целочисленный двоичный поиск]]
−
## Заменить тире на [[Шаблон:---]]
+
# [[Поиск в матрице]]
−
## Англоязычные термины
+
# [[Вещественный двоичный поиск]]
−
## Переменные взять в tex
+
# [[Троичный поиск]] (''2'')
−
## Отформатировать псевдокод
+
## Про == нужно сказать другое
−
## Добавить категории
+
## Добавить про унимодальность функции в начале
−
## <= заменить в tex на \leqslant
+
## Сказать, почему плохо, когда функция не строго монотонна
−
## Добавить эвристику с запоминанием последнего узла при последовательных запросах и её оценку
+
## Добавить сюда метод дихотомии
−
## Добавить ссылок
+
# [[Поиск с помощью золотого сечения]]
−
## Пару слов о том, чем плохо условие на остановку, если вдруг попали в нужный элемент (или чем хорошо)
+
# [[Интерполяционный поиск]] (2)
−
# '''fixed''' [[Вещественный двоичный поиск]]
+
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
−
## Плюсы и минусы cпособов оформить по-красивому
+
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
−
## Отформатировать псевдокод
 
−
## Добавить категории
 
−
## Добавить оценку на число итераций
 
−
## Больше ссылок
 
−
# '''fixed''' [[Троичный поиск]]
 
−
## Добавить категории
 
−
## Добавить ссылок
 
−
## Отформатировать псевдокод
 
−
## Сделать так, чтобы картинка не залезала на псевдокод
 
−
## Англоязычные термины
 
−
## Увеличить дроби
 
−
## См. также красиво оформить
 
−
# '''взяли''' [[Поиск с помощью золотого сечения]]
 
−
## Отформатировать псевдокод
 
−
## Дроби увеличить
 
−
## Добавить категории
 
−
## Добавить аналогичный, но другое поиск фибоначчи
 
−
## Небольшой рефакторинг структуры конспекта
 
−
# '''fixed''' [[Интерполяционный поиск]]
 
−
## Расположения картинки и псевдокода относительно друг друга не очень удачные
 
−
## Нормальную картинку сделать
 
−
## Ссылки нормально оформить
 
−
## Расписать асимптотику нормально
 
−
## Отформатировать псевдокод
 
−
## Примеры данных, на которых поиск работает хорошо
 

Текущая версия на 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. Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_ко_2ому_терму&oldid=60457»