Изменения

# '''!!!'fixed'' [[Амортизационный анализ]] (до ''10''0.5)

## Добавить интересных примеров (по ''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[[Персистентный стек]]## Отформатировать псевдокоды[[Персистентная очередь]]

# '''fixed''' [[Мажорирующий элементПерсистентная приоритетная очередь]] (''1.5''10)## Поправить Отрефакторить псевдокод## Заменить тире на шаблон, а кое-где {{---}} наоборот, на дефисДобавить красивые картинки## != в тексте заменить на \neОформить всё правильно## Убрать скобки из диапазона массива## Заменить size в доказательстве про K на ||## Длинные обозначения взять в \mathtt## Заменить источники Добавить наивное решение на источники информации# '''!!!''' [[Счетчик Кнута]] (10)дереве## Добавить прибавление к произвольному разряду за O(1)Подробней описать решение

== 23. Приоритетные очереди (проверяются) ==: 0. [[Приоритетные очереди]]# ''fixed'' [[Двоичная куча]]## Ссылки на википедию сделать через интервики## Отформатировать псевдокод## Названия функций сделать в lowerCamelCase, например, siftDown## Функции в тексте обернуть в \mathrm# ''fixed'' [[Биномиальная куча]]## Увеличить размер сочетаний## Отрефакторить псевдокод## Круглые скобки в логарифме можно убрать## Названия функций в тексте обернуть в \mathrm# '''fixed!!!''' [[Фибоначчиева куча]](5-10)## Ссылки заменить на интервики## Функции в тексте обернуть в \mathrm## Скобки в логарифме можно убрать## Все переменные и константы взять в tex## Исправить уровни заголовков## Местами текст смешивается с texВ конспекте лаже, непонятны переходы становятсяуже первое определение неверное. Надо переписать нормально.

## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.## Ссылка в интервики с большой буквы {{---}} заменить на маленькую## Отформатировать псевдокод## Всё оформлено в 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)==

## Названия функций в тексте обернуть в \mathrm## Имена функций оформить в lowerCamelCase## Расширить определение до элементов, на которых задан порядок## Добавить несколько слов о наивной реализации на массиве## Добавить ссылок# '''!!!''' [[Дерево поиска, наивная реализация]]## Тире заменить на шаблон## Отформатировать псевдокод## Добавить про персистентное двоичное дерево и псевдокод операций вставки и удаления: показать как там всё просто## Функции в тексте обернуть в \mathrm## Ссылки объединить с литературой, добавить больше ссылок, оформить красиво

## Увеличить дроби## Отформатировать псевдокод# '''!!!''' [[Красно-черное дерево]]## Дефис в определении заменить на тире## Тире в тексте {{---}} на шаблон## Константы взять в tex## Оформить красиво источники информации## Определение выделить жирным## В Кормене чуть другое определение красно-чёрного дерева: рассмотреть эквивалентность## Добавить операцию [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&rep=rep1&type=pdf split]

## Тире заменить на шаблон## Имена функций оформить в lowerCamelCase## Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев## Отформатировать псевдокод# [[Декартово дерево по неявному ключу]](1)## Добавить псевдокод## Тире заменить В псевдокоде нет проверок на шаблон''null''## Сделать интервики на Rope## Добавить ссылок ## Функции в тексте обернуть в \mathrm и оформить их в lowerCamelCase[[Splay-дерево]]# '''!!!''' [[SplayTango-дерево]](''8'')## Исправить знаки неравенств в tex## Увеличить дроби## Тире заменить на шаблон## Показать, что лемма верна для любого фиксированного веса узлаДоказательство теоремы Уилбера## Функции оформить в lowerCamelCaseА причём тут вообще она?

## Имена функций взять в \mathrm## Отформатировать псевдокод# '''!!!''' [[Список с пропусками]](''7'')

# [[Сверхбыстрый цифровой бор]] (''2'')## Тире заменить на шаблонОтформатировать псевдокоды## sketch cделать везде с маленькой буквыСказать, а кое-где исправить snetch на sketchпочему префиксы в хеше не буду есть много памяти## Добавить См. также## XOR Многоточия заменить на \oplus## succ cделать с маленькой буквыldots# [[Сверхбыстрый цифровой борRope]] == 5. Дерево отрезков (проверяется)==

## Отформатировать псевдокод## Заменить тире на шаблон# '''fixed''' [[Дерево отрезков. Построение]]## Добавить псевдокод персистентного дерева отрезков## Заменить в псевдокоде f на бинарную операцию <tex> \circ </tex>## Поправить ссылки в источниках## Поправить tex: знаки неравенств, дроби и т. п.## Отрефакторить псевдокод## Исправить несогласованность текста и псевдокода: в тексте полуинтервал, а в псевдоде {{---}} отрезок## Исправить ошибку в картинке персистентного дерева# ''fixed'' [[Реализация запроса в дереве отрезков сверху]](''0.5'')## Отформатировать псевдокод## Тире заменить на шаблонМного пробелов в коде, отформатировать## Заменить "Ссылки" neutral на источники информации и оформить их маркированным спискомvarepsilon, введя сначала моноид## Добавить смпостроение в См. также на реализацию запросов cнизу# ''fixed'' # В примере случаи разной глубины красиво оформить# [[Реализация запроса в дереве отрезков снизу]]## Отформатировать псевдокод[[Несогласованные поддеревья. Реализация массового обновления]] (''3'')## Имена переменных оформить Добавить примеры массовых операций в lowerCamelCaseначало## Переменные в тексте взять в tex## Источники информации оформить маркированным списком## Добавить смВ начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. также Надо бы это пояснить и кинуть интервики на реализацию запросов сверху# [[Несогласованные поддеревьякольцо (см. Реализация массового обновления]]замечания в обсуждениях)

## Обозначения перед псевдокодов взять в \mathtt или в \mathrm## Оформить правильно источники информации## Добавить примеры массовых операцийсм. также# [[Многомерное дерево отрезков]]## Константы взять в tex## Отформатировать псевдокод# ''fixed'' [[Сжатое многомерное дерево отрезков]](''1'')

== 67. Дерево Фенвика (проверяется)==# '''!!!''' [[Дерево Фенвика]]## Тире заменить на шаблон## Исправить багу в доказательстве (см. обсуждения)## Битовые операции окружить пробелами## Знаки неравенств заменить на \leqslant и \geqslant## Расписать эквивалентность формул с числом единиц и побитовые операции## Заменить i = \overline{0, n - 1} на i = 0 .. n - 1## Добавить описание побитовых операций в самое начало, чтобы не использовать их перед их определением## Отформатировать псевдокод## Оформить красиво ссылки## Добавить категории## Имена функций взять в \mathrm## Добавить преимущества и недостатки дерева Фенвика

## Добавить категории## Доказательство оформить в виде шаблона теоремы или заменить на "Корректность"## Скобки вокруг n в log(n) можно убрать# '''!!!''' [[Многомерное дерево Фенвика]]## Тире заменить на шаблон## Отформатировать псевдокод## Разместить картинку так, чтобы не залезала на псевдокод## Имена функций обернуть в \mathrm## Псевдокод сделать отдельным подпунктом## Оформить красиво ссылки## Добавить категории## Перерисовать картинку (см. обсуждения)

== 78. Хеширование (проверяется) ==

## Смотрите обсуждения## Константы взять в tex## Понятия в тексте взять в шаблон определения## Многоточия в tex заменить на \dots# [[Разрешение коллизий]]## Отформатировать псевдокод## Разрешение коллизий из предыдущего конспекта перенести в этот, а в том сделать интервики на данный конспект## Имена функций взять в \mathrm## \mod заменить на \bmod## Поправить ссылки## ''[[Хеширование кукушки]] ('!!!'2'' Добавить оценку на длину кластеров)# [[Хеширование кукушки]]# Англоязычные термины

## Объединить ссылки с источникамиОформить правильно источники информации## А что делать в случае зацикливания?## Плюсы-минусы метода

## Заменить тире на шаблон## Ссылку на неравенство Маркова оформить как интервики на соответствующий конспект# [[Перехеширование. Амортизационный анализ]](''1'')## Оформить функции в lowerCamelCase и обернуть их в тексте в \mathrmПояснить, почему будет O(1) на добавление при перехешировании## Изменить знаки неравенств## Добавить ссылок[[Фильтр Блума]] (1.5)# [[Фильтр БлумаQuotient filter]](3)## Сделать нормальное описание алгоритма, а то ничего не понятно# [[Универсальное семейство хеш-функций]](''0.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'' [[Сортирующие сети]]## Занести оставшиеся определения в [[Шаблон: Определение]]## Англоязычные термины ко всем## Ссылки на вики через интервики

# [[Сортировочные сети с особыми свойствами]] # ''fixed'' [[Сеть Бетчера]](''0.5'')## Оформить правильно англ. термины## Внутренние ссылки оформить примечаниями## Заменить знаки неравенств## Увеличить дроби## Заменить многоточия на \dots## Оформить правильно Источники информации## Добавить См. также

== 1011. Алгоритмы поиска (проверяются) ==# '''взяли''' [[Целочисленный двоичный поиск]]## Заменить тире на [[Шаблон:---Поиск в матрице]]## Англоязычные термины## Переменные взять в tex## Отформатировать псевдокод## Добавить категории## <= заменить в tex на \leqslant## Добавить эвристику с запоминанием последнего узла при последовательных запросах и её оценку## Добавить ссылок## Пару слов о том, чем плохо условие на остановку, если вдруг попали в нужный элемент (или чем хорошо)# '''fixed''' [[Вещественный двоичный поиск]]## Плюсы и минусы cпособов оформить по-красивому## Отформатировать псевдокод## Добавить категории## Добавить оценку на число итераций## Больше ссылок# '''fixed''' [[Троичный поиск]](''2'')## Добавить категорииПро == нужно сказать другое## Добавить ссылокпро унимодальность функции в начале## Отформатировать псевдокод## Сделать такСказать, почему плохо, чтобы картинка когда функция не залезала на псевдокодстрого монотонна## Англоязычные терминыДобавить сюда метод дихотомии## Увеличить дроби## См. также красиво оформить# '''взяли''' [[Поиск с помощью золотого сечения]]## Отформатировать псевдокод## Дроби увеличить## Добавить категории## Добавить аналогичный, но другое поиск фибоначчи## Небольшой рефакторинг структуры конспекта# '''fixed''' [[Интерполяционный поиск]](2)## Расположения картинки и псевдокода относительно друг друга не очень удачныеХотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском## Нормальную картинку сделать## Ссылки нормально оформить## Расписать асимптотику нормально## Отформатировать псевдокод## Примеры данных, Можно что-нибудь сказать про интерполяционный поиск на которых поиск работает хорошогеом. прогрессии или в других предположениях