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