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