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