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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
−
#перенаправление [[Участник:Shersh/Тикеты ко 2ому терму]]
+
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
 +
 
 +
== 1. Амортизационный анализ ==
 +
# '''fixed''' [[Амортизационный анализ]]
 +
## Увеличить маленькие дроби
 +
## Добавить ссылок
 +
## Добавить интервики
 +
## Список в стеке с multipop поправить {{---}} он очень некрасиво смотрится
 +
## Исправить tex, а ещё некоторые речевые ошибки в конспекте
 +
## Функции взять в \mathrm
 +
## Добавить парочку примеров на методы.
 +
# [[Саморасширяющийся массив]]
 +
# '''fixed''' [[Массив с увеличением/уменьшением размера]]
 +
## Объединить с предыдущим
 +
## Поправить tex: неравенства поменять, дроби увеличить
 +
## Добавить информацию о том, какие структуры данных в современных языках программирования используют саморасширяющийся массив
 +
# [[Список]]
 +
# [[Стек]]
 +
# [[Очередь]]
 +
## Заменить ссылки в источника на интервики
 +
# '''взяли''' [[Персистентный стек]]
 +
# '''взяли''' [[Персистентная очередь]]
 +
# '''взяли''' [[Персистентный дек]]
 +
## Добавить по примеру задачи в каждый из трёх конспектов выше, где может пригодиться такая структура (все три задачи будут рассматриваться как один конспект; можно разделить, если примеры будут очень сложными)
 +
# [[Мажорирующий элемент]]
 +
# '''взяли''' [[Счетчик Кнута]]
 +
## Добавить картинки с более понятным пояснением
 +
## Написать красиво и аккуратно (тут требуется человек с чувством прекрасного)
 +
## Может быть можно обобщить как-то на случай <tex>d</tex>-ичной системы счисления? (используется в толстых кучах)
 +
## Будет полезно добавить источники, если про это где-то можно почитать
 +
## Полностью переписать конспект, он очень невнятный
 +
 
 +
== 2. Приоритетные очереди ==
 +
 
 +
# ''взяли'' [[Двоичная куча]]
 +
## Ссылки на википедию сделать через интервики
 +
# [[Биномиальная куча]]
 +
## интервики
 +
# [[Фибоначчиева куча]]
 +
## Ссылки заменить на интервики
 +
# [[Левосторонняя куча]]
 +
# [[Тонкая куча]]
 +
# [[Толстая куча на избыточном счетчике]]
 +
## Расписать подробно операцию "декремент". Можно как-то связать со счётчиком Кнута.
 +
# [[Куча Бродала-Окасаки]]
 +
 
 +
== 3. Система непересекающихся множеств ==
 +
# [[СНМ (наивные реализации) | Наивные реализации]]
 +
# [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 +
# [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 +
## Интервики
 +
 
 +
== 4. Поисковые структуры данных ==
 +
 
 +
# [[Упорядоченное множество]]
 +
# [[Дерево поиска, наивная реализация]]
 +
# [[АВЛ-дерево]]
 +
# [[2-3 дерево]]
 +
# [[B-дерево]]
 +
# [[Красно-черное дерево]]
 +
# [[Декартово дерево]]
 +
# [[Декартово дерево по неявному ключу]]
 +
# [[Splay-дерево]]
 +
# [[Рандомизированное бинарное дерево поиска]]
 +
# [[Дерево ван Эмде Боаса]]
 +
# [[Список с пропусками]]
 +
# [[Fusion tree]]
 +
# [[Сверхбыстрый цифровой бор]]
 +
* В каждом конспекте сделать ссылки на википедию через интервики
 +
 
 +
== 5. Дерево отрезков ==
 +
 
 +
# [[Статистики на отрезках. Корневая эвристика]]
 +
# '''fixed''' [[Дерево отрезков. Построение]]
 +
## Добавить псевдокод персистентного дерева отрезков
 +
## Заменить в псевдокоде f на бинарную операцию <tex> \circ </tex>
 +
## Поправить ссылки в источниках
 +
## Поправить tex: знаки неравенств, дроби и т. п.
 +
## Отрефакторить псевдокод
 +
## Исправить несогласованность текста и псевдокода: в тексте полуинтервал, а в псевдоде {{---}} отрезок
 +
## Исправить ошибку в картинке персистентного дерева
 +
# [[Реализация запроса в дереве отрезков сверху]]
 +
# [[Реализация запроса в дереве отрезков снизу]]
 +
# [[Несогласованные поддеревья. Реализация массового обновления]]
 +
# [[Многомерное дерево отрезков]]
 +
# [[Сжатое многомерное дерево отрезков]]
 +
 
 +
== 6. Дерево Фенвика ==
 +
# [[Дерево Фенвика]]
 +
# [[Встречное дерево Фенвика]]
 +
# [[Дерево Фенвика для некоммутативных операций]]
 +
# [[Многомерное дерево Фенвика]]
 +
 
 +
== 7. Хеширование ==
 +
# [[Хеш-таблица]]
 +
# '''!!!''' [[Разрешение коллизий]]
 +
## Добавить примеры каких-нибудь интересных и популярных хешей, поизучать их свойства
 +
# [[Хеширование кукушки]]
 +
# [[Идеальное хеширование]]
 +
# [[Перехеширование. Амортизационный анализ]]
 +
# [[Фильтр Блума]]
 +
# [[Универсальное семейство хеш-функций]]
 +
 
 +
== 8. [[Сортировка]] ==
 +
# [[Сортировка выбором]]
 +
## Ссылку через интервики
 +
# '''взяли''' [[Сортировка пузырьком]]
 +
## Добавить ещё оптимизаций этой сортировки (шейкерная сортировка, расчёской, odd-even и прочие {{---}} полный список есть на [[ wikipedia:en:Bubble_sort | википедии ]]) {{---}} полностью расписывать не надо, только ссылки и краткое описание. Об уменьшии константы в асимптотике можно пару слов сказать, если только она и уменьшается.
 +
## Дать точные оценки на число сравнений в худшем случае
 +
## Отформатировать псевдокод
 +
## Ссылка на вики
 +
# '''fixed''' [[Сортировка вставками]]
 +
## То же самое, что и в предыдущем тикете
 +
## Увеличить дроби
 +
## Внести переменные и константы в tex
 +
# [[Сортировка Шелла]]
 +
# '''взяли''' [[Сортировка кучей]]
 +
## Можно добавить всякие модификации сортировки кучей, например, JSort.
 +
# [[Быстрая сортировка]]
 +
## Тут вообще ссылки ужасные
 +
# '''взяли''' [[Сортировка слиянием]]
 +
## Эта сортировка хорошо параллелится. Но вдруг можно придумать, как манипулировать потоками, чтобы достичь наибольшей эффективности, особенно если одновременно может работать ограниченное число потоков.
 +
## Написать псевдокод многопоточной сортировки
 +
# [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 +
# [[Теорема о нижней оценке для сортировки сравнениями]]
 +
# [[Сортировка подсчетом]]
 +
# [[Сортировка подсчетом сложных объектов]]
 +
# '''fixed''' [[Цифровая сортировка]]
 +
## Добавить модификацию для сортировки цифр в порядке от старших к младшим
 +
## Убрать ; из псевдокода
 +
# [[Карманная сортировка]]
 +
# [[Поиск k-ой порядковой статистики]]
 +
# [[Поиск k-ой порядковой статистики за линейное время]]
 +
# '''взяли''' [[Сортировка Хана]]
 +
## Привести конспект в порядок!
 +
## Добавить шаблоны определений
 +
## Добавить шаблоны лемм
 +
## Поправить tex, где его нет
 +
## Корректно оформить ссылки
 +
## Поподробней рассказать про ЭП-дерево
 +
## Использование лемм оформить ссылками
 +
## Структуру поменять, переставить пункты местами, чтобы не было ссылок в тексте на то, что ещё не рассказывалось
 +
## "Конец" в доказательстве выглядит некрасиво. Как и "Доказательство". Опять же, всё сделать шаблонами
 +
## Псевдокод добавить, если из описания будет не совсем понятно, как это реализовать (данный пункт допускает возможность поправить идейное описание алгоритма вместо добавление псевдокода)
 +
## Возможно, ещё какие-то правки по мелочи
 +
## Картинки приветствуются. Если их добавить (или убедить меня, что и так норм, или сделать что-то другое), а всё остальное будет очень няшно сделано, то всё может рассматриваться как целый коспект в баллах.
 +
# [[Timsort]]
 +
## Последнюю картинку можно сделать более красочной
 +
 
 +
== 9. Сортирующие сети ==
 +
# ''fixed'' [[Сортирующие сети]]
 +
## Занести оставшиеся определения в [[Шаблон: Определение]]
 +
## Англоязычные термины ко всем
 +
## Ссылки на вики через интервики
 +
# [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 +
## Ссылки через интервики
 +
## Поменять знаки неравенст в tex на более красивые
 +
# [[Сортировочные сети с особыми свойствами]]
 +
# [[Сортирующие сети для квадратичных сортировок]]
 +
# [[Сеть Бетчера]]
 +
 
 +
== 10. Алгоритмы поиска ==
 +
# '''взяли''' [[Целочисленный двоичный поиск]]
 +
## Заменить тире на [[Шаблон:---]]
 +
## Англоязычные термины
 +
## Переменные взять в tex
 +
## Отформатировать псевдокод
 +
## Добавить категории
 +
## <= заменить в tex на \leqslant
 +
## Добавить эвристику с запоминанием последнего узла при последовательных запросах и её оценку
 +
## Добавить ссылок
 +
## Пару слов о том, чем плохо условие на остановку, если вдруг попали в нужный элемент (или чем хорошо)
 +
# '''взяли''' [[Вещественный двоичный поиск]]
 +
## Плюсы и минусы cпособов оформить по-красивому
 +
## Отформатировать псевдокод
 +
## Добавить категории
 +
## Добавить оценку на число итераций
 +
## Больше ссылок
 +
# '''взяли''' [[Троичный поиск]]
 +
## Добавить категории
 +
## Добавить ссылок
 +
## Отформатировать псевдокод
 +
## Сделать так, чтобы картинка не залезала на псевдокод
 +
## Англоязычные термины
 +
## Увеличить дроби
 +
## См. также красиво оформить
 +
# '''взяли''' [[Поиск с помощью золотого сечения]]
 +
## Отформатировать псевдокод
 +
## Дроби увеличить
 +
## Добавить категории
 +
## Добавить аналогичный, но другое поиск фибоначчи
 +
## Небольшой рефакторинг структуры конспекта
 +
# '''взяли''' [[Интерполяционный поиск]]
 +
## Расположения картинки и псевдокода относительно друг друга не очень удачные
 +
## Нормальную картинку сделать
 +
## Ссылки нормально оформить
 +
## Расписать асимптотику нормально
 +
## Отформатировать псевдокод
 +
## Примеры данных, на которых поиск работает хорошо

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_по_конспектам_year2013»