Участник:Shersh/Тикеты по конспектам year2013

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.

1. Амортизационный анализ

1. fixed Амортизационный анализ
   1. Увеличить маленькие дроби
   2. Добавить ссылок
   3. Добавить интервики
   4. Список в стеке с multipop поправить — он очень некрасиво смотрится
   5. Исправить tex, а ещё некоторые речевые ошибки в конспекте
   6. Функции взять в \mathrm
   7. Добавить парочку примеров на методы.
2. Саморасширяющийся массив
3. fixed Массив с увеличением/уменьшением размера
   1. Объединить с предыдущим
   2. Поправить tex: неравенства поменять, дроби увеличить
   3. Добавить информацию о том, какие структуры данных в современных языках программирования используют саморасширяющийся массив
4. взяли Список
   1. Заменить тире на шаблон
   2. Отформатировать псевдокод
   3. Поправить ссылки в См. также, сделать маркированным списком
   4. Объединить Ссылки и Литературу
   5. Добавить категории
   6. Добавить примеры интересных задач на списки (обычно их спрашивают на собеседованиях)
5. взяли Стек
   1. Отрефакторить псевдокод
   2. Поправить ссылки
   3. Имена функций в тексте обернуть в \mathrm
   4. Оформить имена функций в lowerCamelCase
6. взяли Очередь
   1. То же самое, что и в предыдущем
   2. Плюсы и Минусы оформить единообразно маркированным списком
   3. Заменить ссылки в источника на интервики
7. взяли Персистентный стек
8. взяли Персистентная очередь
9. взяли Персистентный дек
   1. Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)
10. Мажорирующий элемент
    1. Поправить псевдокод
    2. Заменить тире на шаблон, а кое-где — наоборот, на дефис
    3.  != в тексте заменить на \ne
    4. Убрать скобки из диапазона массива
    5. Заменить size в доказательстве про K на ||
11. взяли Счетчик Кнута
    1. Добавить картинки с более понятным пояснением
    2. Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)
    3. Может быть можно обобщить как-то на случай [math]d[/math]-ичной системы счисления? (используется в толстых кучах)
    4. Будет полезно добавить источники, если про это где-то можно почитать
    5. Полностью переписать конспект, он очень невнятный

2. Приоритетные очереди

1. взяли Двоичная куча
   1. Ссылки на википедию сделать через интервики
   2. Отформатировать псевдокод
   3. Названия функций сделать в lowerCamelCase, например, siftDown
   4. Функции в тексте обернуть в \mathrm
2. Биномиальная куча
   1. Увеличить размер сочетаний
   2. Отрефакторить псевдокод
   3. Круглые скобки в логарифме можно убрать
   4. Названия функций в тексте обернуть в \mathrm
3. Фибоначчиева куча
   1. Ссылки заменить на интервики
   2. Функции в тексте обернуть в \mathrm
   3. Скобки в логарифме можно убрать
   4. Все переменные и константы взять в tex
4. Левосторонняя куча
5. Тонкая куча
   1. То же самое, что в фибоначчиевых кучах
6. Толстая куча на избыточном счетчике
   1. Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
   2. Ссылка в интервики с большой буквы — заменить на маленькую
   3. Отформатировать псевдокод
   4. Всё оформлено в UpperCamelCase, наверное, надо что-то с этим сделать
   5. Названия функций обернуть в \mathrm
   6. Поправить ошибку в Источниках
   7. Все переменные и константы взять в tex
   8. "Основные операции оформить аккуратней
   9. В одном месте лишнее выделение текста псевдокодным прямоугольником, в другом месте комментарий вылез за псевдокод
7. взяли Куча Бродала-Окасаки
   1. Определение выделить жирным
   2. Заменить log на \log
   3. Функции в тексте взять в \mathrm
   4. Заменить тире на шаблон
   5. Отформатировать псевдокод
   6. Ссылки заменить на источники информации, сделать маркированным списком

3. Система непересекающихся множеств

1. взяли Наивные реализации
   1. Добавить формальное определение
   2. Переменные и константы взять в tex
   3. Функции взять в \mathrm
   4. Отформатировать псевдокод
   5. Картинку можно убрать из thumb
   6. Источники объединить с ссылками
2. взяли Списки с весовой эвристикой
   1. Имена функций в тексте обернуть в \mathrm
   2. Отформатировать псевдокод
   3. Объединить источники и ссылки
3. !!! Реализация с помощью леса корневых деревьев
   1. Интервики
   2. Функции в тексте взять в \mathrm
   3. Заменить \ge на \geqslant
   4. Добавить определение итерированного логарифма, а то из текста непонятно, что это такое
   5. Переменные и константы взять в tex
   6. Пояснить переходы в оценке ранговой эвристики: про интервал, про оценку на [math] R(v_1 [/math]
   7. Добавить другие эвристики и оценить их

4. Поисковые структуры данных

1. Упорядоченное множество
   1. Названия функций в тексте обернуть в \mathrm
   2. Имена функций оформить в lowerCamelCase
   3. Расширить определение до элементов, на которых задан порядок
   4. Добавить несколько слов о наивной реализации на массиве
   5. Добавить ссылок
2. Дерево поиска, наивная реализация
3. АВЛ-дерево
4. 2-3 дерево
5. B-дерево
6. Красно-черное дерево
7. Декартово дерево
8. Декартово дерево по неявному ключу
9. Splay-дерево
10. Рандомизированное бинарное дерево поиска
11. Дерево ван Эмде Боаса
12. Список с пропусками
13. Fusion tree
14. Сверхбыстрый цифровой бор

5. Дерево отрезков

1. Статистики на отрезках. Корневая эвристика
2. fixed Дерево отрезков. Построение
   1. Добавить псевдокод персистентного дерева отрезков
   2. Заменить в псевдокоде f на бинарную операцию [math] \circ [/math]
   3. Поправить ссылки в источниках
   4. Поправить tex: знаки неравенств, дроби и т. п.
   5. Отрефакторить псевдокод
   6. Исправить несогласованность текста и псевдокода: в тексте полуинтервал, а в псевдоде — отрезок
   7. Исправить ошибку в картинке персистентного дерева
3. Реализация запроса в дереве отрезков сверху
4. Реализация запроса в дереве отрезков снизу
5. Несогласованные поддеревья. Реализация массового обновления
6. Многомерное дерево отрезков
7. Сжатое многомерное дерево отрезков

6. Дерево Фенвика

1. Дерево Фенвика
2. Встречное дерево Фенвика
3. Дерево Фенвика для некоммутативных операций
4. Многомерное дерево Фенвика

7. Хеширование

1. Хеш-таблица
2. !!! Разрешение коллизий
   1. Добавить примеры каких-нибудь интересных и популярных хешей, поизучать их свойства
3. Хеширование кукушки
4. Идеальное хеширование
5. Перехеширование. Амортизационный анализ
6. Фильтр Блума
7. Универсальное семейство хеш-функций

8. Сортировка

1. Сортировка выбором
   1. Ссылку через интервики
2. взяли Сортировка пузырьком
   1. Добавить ещё оптимизаций этой сортировки (шейкерная сортировка, расчёской, odd-even и прочие — полный список есть на википедии ) — полностью расписывать не надо, только ссылки и краткое описание. Об уменьшии константы в асимптотике можно пару слов сказать, если только она и уменьшается.
   2. Дать точные оценки на число сравнений в худшем случае
   3. Отформатировать псевдокод
   4. Ссылка на вики
3. fixed Сортировка вставками
   1. То же самое, что и в предыдущем тикете
   2. Увеличить дроби
   3. Внести переменные и константы в tex
4. Сортировка Шелла
5. взяли Сортировка кучей
   1. Можно добавить всякие модификации сортировки кучей, например, JSort.
6. fixed Быстрая сортировка
   1. Тут вообще ссылки ужасные
   2. Отформатиовать псевдокод
7. fixed Сортировка слиянием
   1. Эта сортировка хорошо параллелится. Но вдруг можно придумать, как манипулировать потоками, чтобы достичь наибольшей эффективности, особенно если одновременно может работать ограниченное число потоков.
   2. Написать псевдокод многопоточной сортировки
8. Cортировка слиянием с использованием O(1) дополнительной памяти
9. Теорема о нижней оценке для сортировки сравнениями
10. Сортировка подсчетом
11. Сортировка подсчетом сложных объектов
12. fixed Цифровая сортировка
    1. Добавить модификацию для сортировки цифр в порядке от старших к младшим
    2. Убрать ; из псевдокода
13. Карманная сортировка
14. Поиск k-ой порядковой статистики
15. Поиск k-ой порядковой статистики за линейное время
16. fixed Сортировка Хана
    1. Привести конспект в порядок!
    2. Добавить шаблоны определений
    3. Добавить шаблоны лемм
    4. Поправить tex, где его нет
    5. Корректно оформить ссылки
    6. Поподробней рассказать про ЭП-дерево
    7. Использование лемм оформить ссылками
    8. Структуру поменять, переставить пункты местами, чтобы не было ссылок в тексте на то, что ещё не рассказывалось
    9. "Конец" в доказательстве выглядит некрасиво. Как и "Доказательство". Опять же, всё сделать шаблонами
    10. Псевдокод добавить, если из описания будет не совсем понятно, как это реализовать (данный пункт допускает возможность поправить идейное описание алгоритма вместо добавление псевдокода)
    11. Возможно, ещё какие-то правки по мелочи
    12. Картинки приветствуются. Если их добавить (или убедить меня, что и так норм, или сделать что-то другое), а всё остальное будет очень няшно сделано, то всё может рассматриваться как целый коспект в баллах.
17. Timsort
    1. Последнюю картинку можно сделать более красочной

9. Сортирующие сети

1. fixed Сортирующие сети
   1. Занести оставшиеся определения в Шаблон: Определение
   2. Англоязычные термины ко всем
   3. Ссылки на вики через интервики
2. Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
   1. Ссылки через интервики
   2. Поменять знаки неравенст в tex на более красивые
3. Сортировочные сети с особыми свойствами
4. Сортирующие сети для квадратичных сортировок
5. Сеть Бетчера

10. Алгоритмы поиска

1. взяли Целочисленный двоичный поиск
   1. Заменить тире на Шаблон:---
   2. Англоязычные термины
   3. Переменные взять в tex
   4. Отформатировать псевдокод
   5. Добавить категории
   6. <= заменить в tex на \leqslant
   7. Добавить эвристику с запоминанием последнего узла при последовательных запросах и её оценку
   8. Добавить ссылок
   9. Пару слов о том, чем плохо условие на остановку, если вдруг попали в нужный элемент (или чем хорошо)
2. взяли Вещественный двоичный поиск
   1. Плюсы и минусы cпособов оформить по-красивому
   2. Отформатировать псевдокод
   3. Добавить категории
   4. Добавить оценку на число итераций
   5. Больше ссылок
3. взяли Троичный поиск
   1. Добавить категории
   2. Добавить ссылок
   3. Отформатировать псевдокод
   4. Сделать так, чтобы картинка не залезала на псевдокод
   5. Англоязычные термины
   6. Увеличить дроби
   7. См. также красиво оформить
4. взяли Поиск с помощью золотого сечения
   1. Отформатировать псевдокод
   2. Дроби увеличить
   3. Добавить категории
   4. Добавить аналогичный, но другое поиск фибоначчи
   5. Небольшой рефакторинг структуры конспекта
5. взяли Интерполяционный поиск
   1. Расположения картинки и псевдокода относительно друг друга не очень удачные
   2. Нормальную картинку сделать
   3. Ссылки нормально оформить
   4. Расписать асимптотику нормально
   5. Отформатировать псевдокод
   6. Примеры данных, на которых поиск работает хорошо