Участник:Shersh/Тикеты к 4ому терму — различия между версиями
Shersh (обсуждение | вклад) м (→7. Теория расписаний) |
Shersh (обсуждение | вклад) м (→7. Теория расписаний) |
||
Строка 350: | Строка 350: | ||
## Более подробное и понятное описание, чтобы было понятно, как закодить | ## Более подробное и понятное описание, чтобы было понятно, как закодить | ||
## Увеличить дроби | ## Увеличить дроби | ||
− | # '' | + | # ''fixed'' [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]] (''1'') |
## Задачу в шаблон | ## Задачу в шаблон | ||
## Заменить знаки неравенств | ## Заменить знаки неравенств |
Версия 10:15, 9 июня 2015
Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.
Помним про добавление англоязычных терминов в конспекты.
Содержание
1. Основные определения. Простые комбинаторные свойства слов
- Основные определения, связанные со строками
- Период и бордер, их связь
- взяли Слово Фибоначчи (7)
- Убрать лишние пункты
- Англоязычные термины
- Все переменные в Tex
- Исправить знаки неравенств
- Правильно оформить См. также и Источники информации
- Написать, почему строка Фибоначчи будет (2, 4) исключением
- Можно написать про исключения отдельный конспект даже, если там много информации наберётся
- взяли Слово Туэ-Морса (7)
- Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
- Англоязычные термины
- Правильно оформить См. также и Источники информации
- Доказать разные прикольные факты про строку Туэ-Морса (+3 за факт)
- Декомпозиция Линдона
- Алгоритм Ландау-Шмидта
- !!! Алгоритм Крочемора (5)
- Пояснить наивную реализацию в начале
- Доказать первую лемму
- Удалить Лоренца из источников
- Пояснить подробней псевдокод
2. Поиск подстроки в строке
- 0. взяли Поиск подстроки в строке (1)
- Взять обозначения перед псевдокодом в \mathtt
- Придумать более удачный способ нумерации списка
- взяли Наивный алгоритм поиска подстроки в строке (0.5)
- Задачу взять в Шаблон:Задача
- Заменить литературу на источники информации
- Сделать подпункты уровнем меньше
- Убрать среднее O во времени работы
- взяли Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа (5)
- Добавить подробное объяснение примера строки, на которой плохо работает такое хеширование
- Отформатировать псевдокод
- Добавить См. также
- Оформить правильно Источники информации
- Взять хэш в \mathrm
- взяли Поиск наибольшей общей подстроки двух строк с использованием хеширования (0.5)
- Задачу взять в шаблон
- Переменные взять в Tex
- Отформатировать псевдокод
- Оформить правильно См. также и Источники информации
- взяли Префикс-функция (1)
- Какой-то нехороший человек вычел 1 из индексации префикс-функции, хотя в начале сказано, что строки нумеруются с 1. Исправить надо.
- Алгоритм Кнута-Морриса-Пратта
- взяли Алгоритм Бойера-Мура (4)
- Добавить понятную табличку примера с пояснением каждого шага
- and в Tex заменить на знак конъюнкции
- Добавить пояснений в формальные определения
- Ссылки заменить на источники информации
- Алгоритм Колусси
- Алгоритм Shift-And
- взяли Z-функция (1)
- Пункт определение не нужен, заменить на шаблон и дать формальное определение
- Оформить красиво доказательство эффективного алгоритма
- Добавить См. также
- Длинные обозначения после псевдокода взять в \mathtt
- взяли Автомат для поиска образца в тексте (10)
- Дописать до нормальной статьи о суффиксном автомате (если это оно и есть), см. список предлагаемых тем
- взяли Бор (8)
- Больше ссылок
- Кое-где надо подправить tex
- Нарисовать нормальные картинки
- Построение оформить эстетично по шагам
- Добавить ссылки на суффиксный бор, провести связь с суффиксным деревом
- Добавить информацию про использование дерева для хранения переходов
- Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах
- Добавить см. также, оформить правильно источники информации
- взяли Алгоритм Ахо-Корасик (8)
- Задачу в шаблон
- Написать асимптотику нормально
- Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше уточнить у куратора
- Красивые картинки
- Отформатировать псевдокод
- Источники заменить на источники информации
- Отформатировать раздел с масками
- Алгоритм Ландау-Вишкина (k несовпадений)
3. Суффиксное дерево
- взяли Суффиксный бор (2)
- Изменить знаки неравенства
- Отформатировать псевдокод
- Оформить правильно источники инфрмации
- Добавить пример строки, на которой будет O(n^2) памяти достигаться
- Заменить многоточия на \dots
- Сжатое суффиксное дерево (2)
- Немного пояснить про эквивалентность определений сжатого суффиксного бора и сжатого дерева, а то путаница какая-то сейчас
- Англоязычные термины
- Сделать список нормальный в доказательстве
- Отформатировать псевдокод в построении
- Свойства написать с маленькой буквы и перечислить через запятую
- Добавить псевдокод структуры Vertex перед построением
- fixed Алгоритм Укконена (8.5) напишите уже кто-нибудь (желательно адекватный человек, а то третий год непонятный конспект в разработке)
- Псевдокод оформить как нормальный псевдокод
- Убрать подпункты леммы, их название занести в Шаблон
- Англоязычные термины
- Подстроку обозначать как
- В начале пункта Алгоритм форматирование не ок
- Изменить знаки неравенств
- Оформить правильно Источники информации
- См. также переместить перед Источниками информации
- Добавить картинок по ходу дела (на емаксе есть ссылка на pdf, откуда можно взять картинки, только описание с той пдфки не копипастить)
- Пояснить, чем хорош этот алгоритм построения суффиксного дерева, но почему его в реальной жизни мало используют
- fixed Алгоритм МакКрейта (0.5)
- Англоязычные термины
- Ссылки оформить примечаниями
- взяли Алгоритм Фарача (2)
- В конспекте полно опечаток - исправить
- Интервики на поразрядную сортировку
- Рисунки подписать в thumb
- Добавить недостатки и преимущества
4. Суффиксный массив
- fixed Суффиксный массив (1)
- Англоязычные термины
- Пример оформить красивей и понятней
- Добавить применений
- Оформить правильно Источники информации и см. также, покидать всяких ссылок в источники
- fixed Построение суффиксного массива с помощью стандартных методов сортировки (2)
- Отформатировать псевдокоды
- Оформить правильно источники информации
- Зачем второй сложный алгоритм за O(n log n), если уже есть алгоритм с хешами?
- Добавить См. также на алгоритм построения массива с помощью цифровой сортировки
- fixed Алгоритм цифровой сортировки суффиксов циклической строки (7)
- Добавить ссылку на цифровую сортировку куда-нибудь в конспект
- Заменить картинку таблицы на теховскую таблицу
- Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать
- Возможно придётся чуточку переписать описание алгоритма
- Оформить правильно источники информации
- Добавить см. также на другие алгоритмы построения
- взяли Алгоритм Касаи и др. (3)
- Кажется, что LCP вычисляет не длину общих префиксов циклических сдвигов; или надо что-то ещё добавить
- "будем использовать промежуточный массив " — лучше написать "вспомогательный"
- Добавить фразу и картинку про то, что массив LCP удобно представлять в виде ступенек/столбиков разной высоты
- Кстати, не очень понятно, зачем нужен Height, если по сути он выполняет роль LCP
- Надо сказать, в каком порядке мы фиксируем соседа: lcp[i] содержит префикс i и i-1 или i и i+1
- Думаю, что к утверждению 2 нужные пояснения, а то происходят нетривиальные переходы из словесной формулировки в утверждение; ещё надо добавить, что не изменится относительный порядок именно этих двух суффиксов, а не всех
- взяли Алгоритм Карккайнена-Сандерса (5)
- Заменить знаки неравенств
- Отформатировать псевдокоды
- Отформатировать обозначения в шагах
- Оформить примеры таблицами
- Увеличить дроби
- Добавить См. также
- Оформить правильно примечания и Источники информации
- взяли Алгоритм поиска подстроки в строке с помощью суффиксного массива (7)
- Отформатировать псевдокоды
- Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
- Исправить баги в Tex
- Оформить правильно источники информации
5. Задача о наименьшем общем предке
- взяли Сведение задачи LCA к задаче RMQ (3)
- Оформить правильно англоязычные термины
- Убрать пункт "Постановка задачи", добавить Шаблон:Задача
- Имена функций взять в \mathrm, имена массивов взять в \mathtt
- Нарисовать векторную нормальную картинку
- Заменить знаки неравенств
- Оформить правильно источники информации
- взяли Сведение задачи RMQ к задаче LCA (2)
- Задачу взять в Шаблон
- Кинуть интервики на дерево по неявному
- Чуть подробней написать алгоритм, более плавное введение сделать
- Пункт "Доказательство" тоже немного не к месту выглядит, заменить его на что-нибудь получше
- В сложности тоже сказать больше подробностей
- fixed Метод двоичного подъема (0.5)
- Англоязычные термины
- Интервики на динамическое программирование
- Заменить знаки неравенств
- min заменить на \min
- Добавить См. также
- взяли Решение RMQ с помощью разреженной таблицы (1)
- Что значит online static?
- Постановку задачи в Шаблон
- Заменить знаки неравенств
- fl лучше как функцию оформить
- Увеличить дроби
- Заменить вертикальную черту на \mid
- Многоточния заменить на \ldots
- Заменить источники на Источники информации
- (+1 в карму за перерисовку картинки на красивую)
- взяли Алгоритм Фарака-Колтона и Бендера (8)
- Задачу взять в Шаблон
- Переменные и константы в Tex
- Добавить оптимизацию по памяти
- Написать псевдокод
- RMQ взять в Tex
- Увеличить картинку
- Увеличить дроби
- Источники заменить на источники информации
- взяли Алгоритм Шибера-Вишкина (2)
- Англоязычные термины
- Интервики на LCA
- Чё ещё за подготовка?
- Почему-то в определении находится не определение, надо бы нормально переписать
- Лучше дать нормальное название обхода: pre-order, in-order или post-, если что-то из этого оно и есть
- Увеличить дроби
- Добавить См. также
- Добавить Категории
- Правильно оформить источники информации
- Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
- Link-Cut Tree
6. Матроиды
Основные факты теории матроидов
- Определение матроида
- Примеры матроидов (1)
- Красивые списки в доказательствах
- Добавить категорию
- Заменить | на \mid
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- взяли Теорема о базах (5)
- Англоязычные термины
- Добавить ссылок, см. также
- Поправить tex
- Обернуть семейство в \mathcal
- Добавить сильную теорему баз (base exchange) — см. Chandra Chekuri
- Аксиоматизация матроида базами (0.5)
- Оформить правильно источники информации
- Больше ссылок
- Добавить категорию
- Теорема о циклах
- Аксиоматизация матроида циклами
- fixed Ранговая функция, полумодулярность (1)
- tex
- Ссылки
- Англоязычные термины
- Заменить знаки неравенств
- Добавить источники информации
- Добавить категорию
- Двойственный матроид
- Оператор замыкания для матроидов
- взяли Покрытия, закрытые множества (8)
- Доказать две теоремы
- Матроид Вамоса
Пересечение матроидов
- взяли Пересечение матроидов, определение, примеры (7)
- Ссылки
- tex
- Ещё примеров
- Больше общих описаний
- Пример, когда пересечение матроидов не является матроидом
- Доказательство матроидности уже приведённых примеров
- Добавить категорию
- !!! Лемма о паросочетании в графе замен (5)
- Док-во по индукции оформить красиво
- Исправить док-во: неверный переход
- Заменить xor на треугольник
- Добавить категорию
- Лемма о единственном паросочетании в графе замен (0.3)
- Оформить правильно источники информации
- Добавить категорию
- !!! Граф замен для двух матроидов (5)
- Нарисовать нормальную картинку
- Добавить информацию про граф замен для одного матроида
- Исправить ссылки в соответствующих конспектах
- Создать новый конспект, в него сделать перенаправление из текущего
- Оформиь правильно источники информации
- Добавить категорию
- Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем (1)
- Картинки плывут — разместить нормально
- Заменить обозначение графа замен на принятое
- Сделать интервики на другие конспекты (паросочетание, кратчайший путь, граф замен)
- взяли Алгоритм построения базы в пересечении матроидов (8)
- Матроиды записать через угловые скобки
- Заменить тире на шаблон
- Добавить категории
- Отформатировать псевдокод
- Мелкие правки в tex
- Перерисовать картинку
- Помёрджить со следующим конспектом
- Теорема Эдмондса-Лоулера
- Добавить категории
- Заменить знак симметрической разности, а так же другие мелкие правки в tex
- Картинки кривовато расположены — поправить
- Исправить ошибки в док-ве
Объединение матроидов
- !!! Объединение матроидов, проверка множества на независимость (8)
- Добавить формальное определение
- Структурировать конспект, а не оставлять просто набором тезисов
- Добавить категории
- Добавить ссылок
- Избавиться от сокращений
- Добавить содержательный примеры
- Заменить тире на Шаблон:---
- Помёрджить со следующим конспектом
- Объединение матроидов, доказательство того, что объединение является матроидом
- Добавить категории
- Добавить интервики
- !!! Алгоритм построения базы в объединении матроидов (7)
- В определение само определение выделить жирным
- Тире заменить на Шаблон:---
- Добавить категории
- Добавить псевдокод
- Написать более подробное описание алгоритма поиска базы в объединении
7. Теория расписаний
- Тут неплохо было бы разбить на разделы все задачи, добавить примеров, оформить всё последовательно
- fixed Классификация задач (1)
- Тех в нотацию Грэхема
- Оформить правильно англоязычные термины
- Добавить источники информации, см. также, категории
- !!! (8)
- Начать с простейших примеров, когда только d_i, потом усложнять
- Отформатировать псевдокод
- Оформить правильно источники информации
- Добавить категории
- Методы решения задач теории расписаний (3)
- Как-нибудь структурировать конспект, а то много всего рандомного написано
- Ссылки оформить как интервики
- Оставить только совсем мелки доказательства, на наборы задач кинуть ссылки или создать новые конспекты
- Добавить источники информации
- fixed Правило Лаулера (3)
- Задачу в шаблон
- Отформатировать псевдокод
- Заменить дефисы на тире
- Заменить знаки неравенств
- Добавить "информации" в источники
- (1.5)
- Задачу в шаблон
- Отформатировать псевдокод
- Добавить категории
- Заменить литературу на источники информации
- взяли (4)
- Задачу в шаблон
- Рассмотреть более простые варианты задачи для начала
- Отформатировать псевдокод
- Добавить источники
- (3)
- Более простой аналог задачи рассмотреть (только с U_i)
- Отформатировать псевдокод
- Заменить литературу на источники информации
- взяли (7)
- Задачу в шаблон
- Отформатировать псевдокоды
- Более подробное и понятное описание, чтобы было понятно, как закодить
- Увеличить дроби
- fixed (1)
- Задачу в шаблон
- Заменить знаки неравенств
- Добавить источники информации
- (0.5)
- Увеличить дроби
- Оформить правильно источники информации
- Добавить категории
- Заменить знаки неравенств
- (0.5)
- Заменить знаки неравенств
- Добавить категории
- (2)
- Задачу в шаблон
- Отформатировать псевдокоды
- Заменить знаки неравенств
- Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней
- (0.5)
- Задачу в шаблон
- Заменить знаки неравенств
- Добавить информации в источники
- (1)
- Там получаются очень большие списки, если рассматривать их все для каждого станка, нужно написать, как лучше всего организовать очередь приоритетов
- Увеличить дроби
- Задачу в шаблон
- Оформить правильно Источники инфорации
- !!! (5)
- Допилить
- Доказать корректность
- Задачу в шаблон
- Отформатировать псевдокод
- Добавить категории
- Flow shop (2)
- Таблички оформить как викитаблички, а не как код
- Битое примечание
- Отформатировать псевдокоды
- Добавить категории
- (3)
- Задачу в шаблон
- Заменить знаки неравенств
- Отформатировать псевдокод
- Красивые картинки
- взяли (1)
- Ранее было доказано, что эта задача сводится к 1|p_ij=1|sumwiUi, поэтому надо просто выпилить отсюда значимую часть и перенести примером в Flow shop
- (1)
- Заменить знаки неравенств
- Категории
- задачу в шаблон
- Отформатировать псевдокод
- (0.5)
- Категории
- Шаблон
- Знаки неравенств
- (1)
- Задачу в шаблон
- Знаки неравенств
- Источники информации
- Дефисы на тире
- !!! (10)
- Доделать