3622
правки
Изменения
м
# Англоязычные термины
# Описание алгоритма сделать покрасивей
# Заменить многоточия на \ldots
# Увеличить дроби
# Пояснить про разбиение массива на три части и чем это помогает
# Добавить ещё модификаций
# Добавить См. также
# Добавить категорию
# Исправить баг с partition
Изменён уровень защиты страницы «Участник:Shersh/Тикеты ко 2ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
== 01. Амортизационный анализ ==# ''fixed'' [[Амортизационный анализ]] (0.5)
## Англоязычные термины
## Нормальный нумерованный список
# [[Стек]]
# [[Очередь]]
# ''fixed'' [[Дек]]# [[Мажорирующий элемент]] (''1.5'')## Поправить псевдокод## Заменить тире на шаблон, а кое-где {{---}} наоборот, на дефис## != в тексте заменить на \ne## Убрать скобки из диапазона массива## Заменить size в доказательстве про K на ||## Длинные обозначения взять в \mathtt## Заменить источники на источники информации
# '''!!!''' [[Счетчик Кнута]] (''5'')
## Добавить рассуждения про декремент (и вычитание 1 из произвольного разряда)
# [[Мастер-теорема]]
# [[List order maintenance]]
== 12. Персистентные структуры данных ==
# [[Персистентные структуры данных]]
# [[Персистентный стек]]
# [[Персистентная очередь]]
# [[Персистентный дек]]
# '''!!!fixed''' [[Персистентная приоритетная очередь]] (10)
## Отрефакторить псевдокод
## Добавить красивые картинки
## Подробней описать решение
== 23. Приоритетные очереди ==
: 0. [[Приоритетные очереди]]
# [[Двоичная куча]]
# [[Биномиальная куча]]
# '''!!!''' [[Фибоначчиева куча]](5-10)## В конспекте лаже, уже первое определение неверное. Надо переписать нормально.
# [[Левосторонняя куча]]
# [[Тонкая куча]]
# '''!!!''' [[Толстая куча на избыточном счетчике]] (''7'')## Англоязычные термины## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.## Ссылка в интервики с большой буквы {{---}} заменить на маленькую## Отформатировать псевдокод## Всё оформлено в UpperCamelCase, наверное, надо что-то с этим сделать## Названия функций обернуть в \mathrm## Поправить ошибку в Источниках## Все переменные и константы взять в tex## "Основные операции оформить аккуратней## В одном месте лишнее выделение текста псевдокодным прямоугольником, в другом месте комментарий вылез за псевдокод## Заголовки сделать на уровень меньше## Структуру оформить псевдокодом с комментариями## Подпункты с большой буквы назвать## Возможно, надо будет исправить что-то ещё, слишком много трэша# ''взяли'' [[Куча Бродала-Окасаки]] (''4'')
## Ссылки заменить на источники информации, сделать маркированным списком
## Непонятно, почему merge работает за О(1), если он вызывает insert ниже, который вызывает merge
## Заменить Смотри также на См. также
== 34. Система непересекающихся множеств ==
# [[СНМ (наивные реализации) | Наивные реализации]] (''0.5'')
## Сделать структуру в списке типа Generic
## Добавить пробелы в Других реализациях перед (
## Англоязычные термины правильно оформить
# '''fixed''' [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] (''5'')## Написать внятное доказательство
# '''!!!''' [[СНМ с операцией удаления за О(1)]] (''6'')
## "Мы работаем в предположении, что очистка списка не подразумевает удаления каждого элемента вручную" - пояснить, почему можем так предполагать
## Если проще нельзя, то пояснить про трудности с обычной эвристикой во время get (find)
== 45. Поисковые структуры данных==
:0. [[Поисковые структуры данных]]
# [[Упорядоченное множество]]
# [[2-3 дерево]]
# [[B-дерево]]
# '''взяли''' [[Красно-черное дерево]] (''5'')## Добавить про связь с 2-3 и 2-4 деревом# '''взяли''' [[Декартово дерево]] (''6'')## Тире заменить на шаблон## Имена функций оформить в lowerCamelCase## Сделать псевдокод менее похожим на код С++ (без ссылок): пусть split возвращает пару деревьев## Разобраться с приоритетами (см. обсуждение)## Какое-то палево в удалении с k.x - eps## Оформить правильно источники информации## Заменить знаки неравенств## Может быть можно избавиться от проверок на null?
# [[Декартово дерево по неявному ключу]] (1)
## В псевдокоде нет проверок на ''null''
# '''fixed''' [[Splay-дерево]] (''8'')## Оформить правильно англоязычные термины## Исправить знаки неравенств в tex## Увеличить дроби## Дефисы заменить на шаблон тире## Показать, что лемма верна для любого фиксированного веса узла## Функции оформить в lowerCamelCase## Пример, когда move to root занимает <tex>\Omega(n)</tex> времени, и заменить O на омегу## Знаки умножения заменить на \cdot## Заменить многоточия на \ldots
# '''!!!''' [[Tango-дерево]] (''8'')
## Доказательство теоремы Уилбера
# [[Rope]]
== 56. Дерево отрезков==
# [[Статистики на отрезках. Корневая эвристика]]
# [[Дерево отрезков. Построение]]
## Добавить см. также
# [[Многомерное дерево отрезков]]
# ''fixed'' [[Сжатое многомерное дерево отрезков]] (''1'')
## Отформатировать псевдокод
## Англоязычные термины
## Добавить категории
== 67. Дерево Фенвика ==* # [[Дерево Фенвика]]* # [[Встречное дерево Фенвика]]* # [[Дерево Фенвика для некоммутативных операций]]* # [[Многомерное дерево Фенвика]]
== 78. Хеширование ==
# [[Хеш-таблица]]
# [[Разрешение коллизий]]
# [[Перехеширование. Амортизационный анализ]] (''1'')
## Пояснить, почему будет O(1) на добавление при перехешировании
# ''fixed'' [[Фильтр Блума]] (1.5)## Оформить правильно Источники информации## Англоязычные термины## Константы, AND, OR в Tex## А зачем нужна такая структура данных?## Вынести определения, чтобы в следующем конспекте не дублировалось
# [[Quotient filter]] (3)
## Сделать нормальное описание алгоритма, а то ничего не понятно
## Понятное описание
== 89. Сортировка ==:0. ''fixed'' [[Сортировка]]
=== Квадратичные сортировки ===
# ''fixed'' [[Сортировка выбором]] (''1'')## Ссылку через интервики## Оформить правильно англоязычные термины## Отформатировать псевдокоды## Сказать, в чём разница между двумя вариантами и оформить сами варианты красивей## Оформить правильно источники информации## Добавить См. также## Добавить категорию
# [[Сортировка пузырьком]] (''2'')
## Сделать единообразные псевдокоды с равным количеством отступов
## Увеличить дроби
## Добавить категорию
# [[Сортировка вставками]] (''0.5'')
=== Сортировки на сравнениях ===
<ol>
<li value="4"> ''fixed'' [[Сортировка Шелла]] (''0.5'') </li># Заменить дефисы на тире# Заменить многоточия на \ldots# Написать правильно ln# Пофиксить категории# Оформить правильно Источники информации и См. также<li> [[Сортировка кучей]] (''5'') </li>
<li> [[Быстрая сортировка]] (''2'') </li>
<li> [[Сортировка слиянием]] </li>
<li> [[Cортировка слиянием с использованием O(1) дополнительной памяти]] (0.5) </li>
<li> [[Timsort]] </li>
<li> [[Smoothsort]] </li>
<li> [[Теорема о нижней оценке для сортировки сравнениями]] (''1'') </li>
# Заменить знаки неравенств
# Добавить "информации" в источники
<li> [[Поиск k-ой порядковой статистики за линейное время]] </li>
<li> [[Поиск k-ой порядковой статистики в двух массивах]]
<li> ''fixed'' [[Сортировка подсчетом]] (''1'') </li>
# Англоязычные термины
# Отформартировать псевдокод
<li> [[Цифровая сортировка]] </li>
<li> [[Карманная сортировка]] </li>
<li> '''!!!''' [[Сортировка Хана]] </li>## '''(10)''' В отдельный конспект про ЭП-дерево и что это такое (за отдельные баллы, разумеется)
<li> [[Задача флага Нидерландов]] </li>
</ol>
== 910. Сортирующие сети ==
# [[Сортирующие сети]]
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
# [[Сортирующие сети для квадратичных сортировок]]
# [[Сортировочные сети с особыми свойствами]]
# ''fixed'' [[Сеть Бетчера]] (''0.5'')
## Оформить правильно англ. термины
## Внутренние ссылки оформить примечаниями
## Добавить См. также
== 1011. Алгоритмы поиска ==# '''fixed''' [[Целочисленный двоичный поиск]] (5)## Исправить часть про различные алгоритмы[[Поиск в матрице]]
# [[Вещественный двоичный поиск]]
# [[Троичный поиск]] (''2'')
## Сказать, почему плохо, когда функция не строго монотонна
## Добавить сюда метод дихотомии
# [[Поиск с помощью золотого сечения]] (''4'')
# [[Интерполяционный поиск]] (2)
## Хотелось бы увидеть пример Интерполяционного поиска на арифметической прогрессии, как говорится в начале, в сравнении с бинпоиском
## Можно что-нибудь сказать про интерполяционный поиск на геом. прогрессии или в других предположениях
