Участник:Shersh/Тикеты к 4ому терму — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(4. Суффиксный массив)
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 4ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показано 135 промежуточных версий этого же участника)
Строка 6: Строка 6:
 
# [[Основные определения, связанные со строками]]
 
# [[Основные определения, связанные со строками]]
 
# [[Период и бордер, их связь]]
 
# [[Период и бордер, их связь]]
# '''взяли''' [[Слово Фибоначчи]] (''7'')  
+
# ''fixed'' [[Слово Фибоначчи]] (''2'')  
 
## Убрать лишние пункты
 
## Убрать лишние пункты
 
## Англоязычные термины
 
## Англоязычные термины
Строка 14: Строка 14:
 
## Написать, почему строка Фибоначчи будет (2, 4) исключением
 
## Написать, почему строка Фибоначчи будет (2, 4) исключением
 
## Можно написать про исключения отдельный конспект даже, если там много информации наберётся
 
## Можно написать про исключения отдельный конспект даже, если там много информации наберётся
# '''взяли''' [[Слово Туэ-Морса]] (''7'')
+
# '''fixed''' [[Слово Туэ-Морса]] (''5'')
## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
 
 
## Англоязычные термины
 
## Англоязычные термины
 
## Правильно оформить См. также и Источники информации
 
## Правильно оформить См. также и Источники информации
## Доказать разные прикольные факты про строку Туэ-Морса (''+3'' за факт)
+
## Доказать какой-нибудь нетривиальный факт про строку Туэ-Морса
 
# [[Декомпозиция Линдона]]
 
# [[Декомпозиция Линдона]]
 
# [[Алгоритм Ландау-Шмидта]]
 
# [[Алгоритм Ландау-Шмидта]]
# '''!!!''' [[Алгоритм Крочемора]] (''5'')
+
# '''взяли''' [[Алгоритм Крочемора]] (''5'')
 
## Пояснить наивную реализацию в начале
 
## Пояснить наивную реализацию в начале
 
## Доказать первую лемму
 
## Доказать первую лемму
 
## Удалить Лоренца из источников
 
## Удалить Лоренца из источников
 
## Пояснить подробней псевдокод
 
## Пояснить подробней псевдокод
 +
## Взять кортежи в тех и оформить красиво
 +
# [[Алгоритм Мейна-Лоренца]]
  
 
== 2. Поиск подстроки в строке ==
 
== 2. Поиск подстроки в строке ==
: 0. ''взяли'' [[Поиск подстроки в строке]] (''1'')
+
: 0. [[Поиск подстроки в строке]]
:# Взять обозначения перед псевдокодом в \mathtt
+
=== Точный поиск ===
:# Придумать более удачный способ нумерации списка
+
# [[Наивный алгоритм поиска подстроки в строке]]
# ''взяли'' [[Наивный алгоритм поиска подстроки в строке]] (''0.5'')
+
# [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
## Задачу взять в [[Шаблон:Задача]]
+
# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
## Заменить литературу на источники информации
+
# [[Префикс-функция]]
## Сделать подпункты уровнем меньше
 
## Убрать среднее O во времени работы
 
# '''взяли''' [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]] (''5'')
 
## Добавить подробное объяснение примера строки, на которой плохо работает такое хеширование
 
## Отформатировать псевдокод
 
## Добавить См. также
 
## Оформить правильно Источники информации
 
## Взять хэш в \mathrm
 
# ''взяли'' [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]] (''0.5'')
 
## Задачу взять в шаблон
 
## Переменные взять в Tex
 
## Отформатировать псевдокод
 
## Оформить правильно См. также и Источники информации
 
# ''взяли'' [[Префикс-функция]] (''1'')
 
## Какой-то нехороший человек вычел 1 из индексации префикс-функции, хотя в начале сказано, что строки нумеруются с 1. Исправить надо.
 
 
# [[Алгоритм Кнута-Морриса-Пратта]]
 
# [[Алгоритм Кнута-Морриса-Пратта]]
# ''взяли'' [[Алгоритм Бойера-Мура]] (''4'')
+
# [[Автомат Кнута-Морриса-Пратта]]
## Добавить '''понятную''' табличку примера с пояснением каждого шага
+
# [[Z-функция]]
## and в Tex заменить на знак конъюнкции
+
# '''fixed''' [[Бор]] (''8'')
## Добавить пояснений в формальные определения
 
## Ссылки заменить на источники информации
 
# [[Алгоритм Колусси]]
 
# [[Алгоритм Shift-And]]
 
# ''взяли'' [[Z-функция]] (''1'')
 
## Пункт определение не нужен, заменить на шаблон и дать формальное определение
 
## Оформить красиво доказательство эффективного алгоритма
 
## Добавить См. также
 
## Длинные обозначения после псевдокода взять в \mathtt
 
# '''!!!''' [[Автомат для поиска образца в тексте]] (''10'')
 
## Дописать до нормальной статьи о суффиксном автомате (если это оно и есть), см. список предлагаемых тем
 
# '''взяли''' [[Бор]] (''8'')
 
 
## Больше ссылок
 
## Больше ссылок
 
## Кое-где надо подправить tex
 
## Кое-где надо подправить tex
Строка 73: Строка 47:
 
## Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах
 
## Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах
 
## Добавить см. также, оформить правильно источники информации
 
## Добавить см. также, оформить правильно источники информации
# '''!!!''' [[Алгоритм Ахо-Корасик]] (''8'')
+
## Категория
 +
# '''fixed''' [[Алгоритм Ахо-Корасик]] (''8'')
 +
## Задачу в шаблон
 
## Написать асимптотику нормально
 
## Написать асимптотику нормально
 
## Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше уточнить у куратора
 
## Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше уточнить у куратора
Строка 80: Строка 56:
 
## Источники заменить на источники информации
 
## Источники заменить на источники информации
 
## Отформатировать раздел с масками
 
## Отформатировать раздел с масками
# [[Алгоритм Ландау-Вишкина (k несовпадений)]]
+
## Категория
 +
# ''fixed'' [[Алгоритм Бойера-Мура]] (''4'')
 +
## Добавить '''понятную''' табличку примера с пояснением каждого шага
 +
## and в Tex заменить на знак конъюнкции
 +
## Добавить пояснений в формальные определения
 +
## Ссылки заменить на источники информации
 +
## Категория
 +
## Отформатировать псевдокод
 +
# [[Алгоритм Колусси]]
 +
# [[Алгоритм Shift-And]]
 +
# ''fixed'' [[Двусторонний алгоритм]] (0.5)
 +
## Список с большой буквы начать
 +
## Неправильный порядок разделов в конце конспекта
 +
## Стрелки в псевдокоде заменить на =
 +
 
 +
=== Нечёткий поиск ===
 +
<ol>
 +
<li value=15> [[Алгоритм Ландау-Вишкина (k несовпадений)]] </li>
 +
<li> [[Алгоритм Ландау-Вишкина (k различий)]] </li>
 +
</ol>
  
 
== 3. Суффиксное дерево ==
 
== 3. Суффиксное дерево ==
# ''взяли'' [[Суффиксный бор]] (''2'')
+
# [[Суффиксный бор]]
## Изменить знаки неравенства
+
# ''fixed'' [[Сжатое суффиксное дерево]] (''2'')
## Отформатировать псевдокод
 
## Оформить правильно источники инфрмации
 
## Добавить пример строки, на которой будет O(n^2) памяти достигаться
 
## Заменить многоточия на \dots
 
# [[Сжатое суффиксное дерево]] (''2'')
 
 
## Немного пояснить про эквивалентность определений сжатого суффиксного бора и сжатого дерева, а то путаница какая-то сейчас
 
## Немного пояснить про эквивалентность определений сжатого суффиксного бора и сжатого дерева, а то путаница какая-то сейчас
 
## Англоязычные термины
 
## Англоязычные термины
Строка 96: Строка 86:
 
## Свойства написать с маленькой буквы и перечислить через запятую
 
## Свойства написать с маленькой буквы и перечислить через запятую
 
## Добавить псевдокод структуры Vertex перед построением
 
## Добавить псевдокод структуры Vertex перед построением
# '''взяли''' [[Алгоритм Укконена]] (''8'') ''напишите уже кто-нибудь (желательно адекватный человек, а то третий год непонятный конспект в разработке)''
+
# [[Алгоритм Укконена]]
## Псевдокод оформить как нормальный псевдокод
+
# [[Алгоритм МакКрейта]]
## Убрать подпункты леммы, их название занести в Шаблон
+
# ''fixed'' [[Алгоритм Фарача]] (''2'')
## Англоязычные термины
 
## Подстроку обозначать как <tex> s[i..j] </tex>
 
## В начале пункта Алгоритм форматирование не ок
 
## Изменить знаки неравенств
 
## Оформить правильно Источники информации
 
## См. также переместить перед Источниками информации
 
## Добавить картинок по ходу дела (на емаксе есть ссылка на pdf, откуда можно взять картинки, только описание с той пдфки не копипастить)
 
## Пояснить, чем хорош этот алгоритм построения суффиксного дерева, но почему его в реальной жизни мало используют
 
# ''взяли'' [[Алгоритм МакКрейта]] (''0.5'')
 
## Англоязычные термины
 
## Ссылки оформить примечаниями
 
# ''взяли'' [[Алгоритм Фарача]] (''2'')
 
 
## В конспекте полно опечаток - исправить
 
## В конспекте полно опечаток - исправить
 
## Интервики на поразрядную сортировку
 
## Интервики на поразрядную сортировку
Строка 117: Строка 95:
  
 
== 4. Суффиксный массив ==
 
== 4. Суффиксный массив ==
# ''взяли'' [[Суффиксный массив]] (''1'')
+
# [[Суффиксный массив]]
## Англоязычные термины
+
# [[Построение суффиксного массива с помощью стандартных методов сортировки]]
## Пример оформить красивей и понятней
+
# [[Алгоритм цифровой сортировки суффиксов циклической строки]]
## Добавить применений
+
# ''fixed'' [[Алгоритм Касаи и др.]] (''3'')
## Оформить правильно Источники информации и см. также, покидать всяких ссылок в источники
+
## Кажется, что LCP вычисляет не длину общих префиксов циклических сдвигов; или надо что-то ещё добавить
# ''взяли'' [[Построение суффиксного массива с помощью стандартных методов сортировки]] (''2'')
+
## "будем использовать промежуточный массив " — лучше написать "вспомогательный"
## Отформатировать псевдокоды
+
## Добавить фразу и картинку про то, что массив LCP удобно представлять в виде ступенек/столбиков разной высоты
## Оформить правильно источники информации
+
## Кстати, не очень понятно, зачем нужен Height, если по сути он выполняет роль LCP
## Зачем второй сложный алгоритм за O(n log n), если уже есть алгоритм с хешами?
+
## Надо сказать, в каком порядке мы фиксируем соседа: lcp[i] содержит префикс i и i-1 или i и i+1
## Добавить См. также на алгоритм построения массива с помощью цифровой сортировки
+
## Думаю, что к утверждению 2 нужные пояснения, а то происходят нетривиальные переходы из словесной формулировки в утверждение; ещё надо добавить, что не изменится относительный порядок именно этих двух суффиксов, а не всех
# '''взяли''' [[Алгоритм цифровой сортировки суффиксов циклической строки]] (''7'')
+
# [[Алгоритм Карккайнена-Сандерса]]
## Добавить ссылку на цифровую сортировку куда-нибудь в конспект
+
# '''fixed''' [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]] (''7'')
## Заменить картинку таблицы на теховскую таблицу
 
## Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать
 
## Возможно придётся чуточку переписать описание алгоритма
 
## Оформить правильно источники информации
 
## Добавить см. также на другие алгоритмы построения
 
# ''взяли'' [[Алгоритм Касаи и др.]] (''0.5'')
 
## Оформить правильно англоязычные термины
 
## Двойное неравенство написать под минимумом
 
## Добавить См. также
 
## Длинные названия взять в \mathrm
 
# '''взяли''' [[Алгоритм Карккайнена-Сандерса]] (''5'')
 
## Заменить знаки неравенств
 
## Отформатировать псевдокоды
 
## Отформатировать обозначения в шагах
 
## Оформить примеры таблицами
 
## Увеличить дроби
 
## Добавить См. также
 
## Оформить правильно примечания и Источники информации
 
# '''взяли''' [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]] (''7'')
 
 
## Отформатировать псевдокоды
 
## Отформатировать псевдокоды
 
## Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
 
## Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
Строка 154: Строка 113:
  
 
== 5. Задача о наименьшем общем предке ==
 
== 5. Задача о наименьшем общем предке ==
# ''взяли'' [[Сведение задачи LCA к задаче RMQ]] (''3'')
+
# [[Сведение задачи LCA к задаче RMQ]]
## Оформить правильно англоязычные термины
+
# [[Сведение задачи RMQ к задаче LCA]]
## Убрать пункт "Постановка задачи", добавить Шаблон:Задача
+
# [[Метод двоичного подъема]]
## Имена функций взять в \mathrm, имена массивов взять в \mathtt
+
# [[Решение RMQ с помощью разреженной таблицы]]
## Нарисовать векторную нормальную картинку
+
# ''fixed'' [[Алгоритм Фарака-Колтона и Бендера]] (''2'')
## Заменить знаки неравенств
+
## Отформатировать псевдокод
## Оформить правильно источники информации
 
# ''взяли'' [[Сведение задачи RMQ к задаче LCA]] (''2'')
 
## Задачу взять в Шаблон
 
## Кинуть интервики на дерево по неявному
 
## Чуть подробней написать алгоритм, более плавное введение сделать
 
## Пункт "Доказательство" тоже немного не к месту выглядит, заменить его на что-нибудь получше
 
## В сложности тоже сказать больше подробностей
 
# ''взяли'' [[Метод двоичного подъема]] (''0.5'')
 
## Англоязычные термины
 
## Интервики на динамическое программирование
 
## Заменить знаки неравенств
 
## min заменить на \min
 
## Добавить См. также
 
# ''взяли'' [[Решение RMQ с помощью разреженной таблицы]] (''1'')
 
## Что значит online static?
 
## Постановку задачи в Шаблон
 
## Заменить знаки неравенств
 
## fl лучше как функцию оформить
 
## Увеличить дроби
 
## Заменить вертикальную черту на \mid
 
## Многоточния заменить на \ldots
 
## Заменить источники на Источники информации
 
## ''(+1 в карму за перерисовку картинки на красивую)''
 
# '''!!!''' [[Алгоритм Фарака-Колтона и Бендера]] (''8'')
 
## Задачу взять в Шаблон
 
## Переменные и константы в Tex
 
## Добавить оптимизацию по памяти
 
## Написать псевдокод
 
## RMQ взять в Tex
 
## Увеличить картинку
 
 
## Увеличить дроби
 
## Увеличить дроби
## Источники заменить на источники информации
+
# '''!!!''' [[Heavy-light декомпозиция]] (''6'')
# [[Алгоритм Шибера-Вишкина]] (''2'')
+
## "решается с помощью heavy-light декомпозиции" — может быть решена
 +
## "Пусть A, B - ко" — дефисы нужно заменить на тире
 +
## В начале у тебя идут вершины a,b и A,B, а потом u,v и a,b. Надо сделать единообразно, чтобы начало конспекта и его конец согласовывались. Например, сделать корни путей большими буквами — норм. Тогда можно либо a,b и A,B, либо u,v и U,V.
 +
## "В данном случае корень одного из путей является вершиной другого." — а почему пути не могут пересекаться крест-на-крест?
 +
## Слишком много повтором «Пусть» в доказательстве леммы.
 +
## "Но LCA должен принадлежать двум путям. Но" — дублирование «Но»
 +
## "Предположим, что LCA не равны" — криво написано, нужно формально исходя из формулировки
 +
## Ну и вообще, как будто слов пожадничал на лемму и кое-как написал
 +
## "Построим декомпозицию." — декомпозицию чего и для чего? Очень плохо оставлять открытый контекст, особенно в начале пункта. Лучше чуть более подробно описать, чтобы было понятно
 +
## "Корень пути, на котором лежит текущая вершина.
 +
Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева." — вообще непонятно, как связано то, что мы хотим сохранить с тем, что написано потом. Нет предложения-связки
 +
## "Пусть требуется" — опять пуст
 +
## "Пусть на данной итерации" — как будто других слов нет
 +
## "LCA будет та" — это не по-русски
 +
## Возьми LCA в тексте везде в \mathrm
 +
## "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?
 +
# ''fixed'' [[Алгоритм Шибера-Вишкина]] (''3'')
 
## Англоязычные термины
 
## Англоязычные термины
 
## Интервики на LCA
 
## Интервики на LCA
Строка 203: Строка 148:
 
## Правильно оформить источники информации
 
## Правильно оформить источники информации
 
# [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
 
# [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
# [[Link-Cut Tree]]
+
# '''fixed''' [[Link-Cut Tree]] (5)
 +
## Отформатировать псевдокоды
 +
## Написать более понятное введение и пояснить подробней остальные смутные операции
 +
## Список оформлен некрасиво в начале
 +
## Категории
 +
## Оформить правильно См. также и Источники информации
  
 
== 6. Матроиды ==
 
== 6. Матроиды ==
 
=== Основные факты теории матроидов ===
 
=== Основные факты теории матроидов ===
 
# [[Определение матроида]]
 
# [[Определение матроида]]
# [[Примеры матроидов]] (''1'')
+
# [[Примеры матроидов]]
## Красивые списки в доказательствах
 
## Добавить категорию
 
## Заменить | на \mid
 
 
# [[Прямая сумма матроидов]]
 
# [[Прямая сумма матроидов]]
 
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
# '''!!!''' [[Теорема о базах]] (''5'')
+
# [[Теорема о базах]]
## Англоязычные термины
+
# [[Аксиоматизация матроида базами]]
## Добавить ссылок, см. также
 
## Поправить tex
 
## Обернуть семейство в \mathcal
 
## Добавить сильную теорему баз (base exchange) {{---}} см. Chandra Chekuri
 
# [[Аксиоматизация матроида базами]] (''0.5'')
 
## Оформить правильно источники информации
 
## Больше ссылок
 
## Добавить категорию
 
 
# [[Теорема о циклах]]
 
# [[Теорема о циклах]]
 
# [[Аксиоматизация матроида циклами]]
 
# [[Аксиоматизация матроида циклами]]
# [[Ранговая функция, полумодулярность]] (''1'')
+
# [[Ранговая функция, полумодулярность]]
## tex
 
## Ссылки
 
## Англоязычные термины
 
## Заменить знаки неравенств
 
## Добавить источники информации
 
## Добавить категорию
 
 
# [[Двойственный матроид]]
 
# [[Двойственный матроид]]
 
# [[Оператор замыкания для матроидов]]
 
# [[Оператор замыкания для матроидов]]
# '''!!!''' [[Покрытия, закрытые множества]] (''8'')
+
# [[Покрытия, закрытые множества]]
## Доказать две теоремы
 
 
# [[Матроид Вамоса]]
 
# [[Матроид Вамоса]]
  
 
=== Пересечение матроидов ===  
 
=== Пересечение матроидов ===  
 
<ol>
 
<ol>
<li value="14"> '''!!!''' [[Пересечение матроидов, определение, примеры]] (''7'') </li>
+
<li value="14"> [[Пересечение матроидов, определение, примеры]] </li>
# Ссылки
+
<li> '''взяли''' [[Лемма о паросочетании в графе замен]] (''5'') </li>
# tex
 
# Ещё примеров
 
# Больше общих описаний
 
# Пример, когда пересечение матроидов не является матроидом
 
# Доказательство матроидности уже приведённых примеров
 
# Добавить категорию
 
<li> '''!!!''' [[Лемма о паросочетании в графе замен]] (''5'') </li>
 
 
# Док-во по индукции оформить красиво
 
# Док-во по индукции оформить красиво
 
# Исправить док-во: неверный переход
 
# Исправить док-во: неверный переход
 
# Заменить xor на треугольник
 
# Заменить xor на треугольник
 
# Добавить категорию
 
# Добавить категорию
<li> [[Лемма о единственном паросочетании в графе замен]] (''0.3'') </li>
+
<li> ''fixed'' [[Лемма о единственном паросочетании в графе замен]] (''0.5'') </li>
 
# Оформить правильно источники информации
 
# Оформить правильно источники информации
 
# Добавить категорию
 
# Добавить категорию
<li> '''!!!''' [[Граф замен для двух матроидов]] (''5'') </li>
+
# Категория
 +
# Оформить красиво док-во по индукции
 +
<li> ''fixed'' [[Граф замен для двух матроидов]] (''3'') </li>
 
# Нарисовать нормальную картинку
 
# Нарисовать нормальную картинку
 
# Добавить информацию про граф замен для одного матроида
 
# Добавить информацию про граф замен для одного матроида
Строка 264: Строка 191:
 
# Оформиь правильно источники информации
 
# Оформиь правильно источники информации
 
# Добавить категорию
 
# Добавить категорию
<li> [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]] (''1'') </li>
+
<li> [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]] </li>
# Картинки плывут {{---}} разместить нормально
+
<li> [[Алгоритм построения базы в пересечении матроидов]] </li>
# Заменить обозначение графа замен на принятое
 
# Сделать интервики на другие конспекты (паросочетание, кратчайший путь, граф замен)
 
<li> '''!!!''' [[Алгоритм построения базы в пересечении матроидов]] (''8'') </li>
 
# Матроиды записать через угловые скобки
 
# Заменить тире на шаблон
 
# Добавить категории
 
# Отформатировать псевдокод
 
# Мелкие правки в tex
 
# Перерисовать картинку
 
# Помёрджить со следующим конспектом
 
<li> [[Теорема Эдмондса-Лоулера]] </li>
 
# Добавить категории
 
# Заменить знак симметрической разности, а так же другие мелкие правки в tex
 
# Картинки кривовато расположены {{---}} поправить
 
# Исправить ошибки в док-ве
 
 
</ol>
 
</ol>
  
 
=== Объединение матроидов ===
 
=== Объединение матроидов ===
 
<ol>
 
<ol>
<li value="21"> '''!!!''' [[Объединение матроидов, проверка множества на независимость]] (''8'') </li>
+
<li value="21"> '''fixed''' [[Объединение матроидов, проверка множества на независимость]] (''8'') </li>
 
# Добавить формальное определение
 
# Добавить формальное определение
 
# Структурировать конспект, а не оставлять просто набором тезисов
 
# Структурировать конспект, а не оставлять просто набором тезисов
Строка 293: Строка 205:
 
# Добавить содержательный примеры
 
# Добавить содержательный примеры
 
# Заменить тире на [[Шаблон:---]]
 
# Заменить тире на [[Шаблон:---]]
# Помёрджить со следующим конспектом
+
<li> ''взяли'' [[Объединение матроидов, доказательство того, что объединение является матроидом]] (1) </li>
<li> [[Объединение матроидов, доказательство того, что объединение является матроидом]] </li>
 
 
# Добавить категории
 
# Добавить категории
 
# Добавить интервики
 
# Добавить интервики
<li> '''!!!''' [[Алгоритм построения базы в объединении матроидов]] (''7'') </li>
+
# Отформатировать по правилам
 +
# Помёрджить с предыдущим конспектом
 +
<li> '''взяли''' [[Алгоритм построения базы в объединении матроидов]] (''7'') </li>
 
# В определение само определение выделить жирным
 
# В определение само определение выделить жирным
 
# Тире заменить на [[Шаблон:---]]
 
# Тире заменить на [[Шаблон:---]]
Строка 306: Строка 219:
  
 
== 7. Теория расписаний ==
 
== 7. Теория расписаний ==
* Тут неплохо было бы разбить на разделы все задачи, добавить примеров, оформить всё последовательно
+
=== Общая теория ===
# [[Классификация задач]] (''1'')
+
# [[Классификация задач]]
## Тех в нотацию Грэхема
+
# '''fixed''' [[Методы решения задач теории расписаний]] (''5'')
## Оформить правильно англоязычные термины
 
## Добавить источники информации, см. также, категории
 
# '''!!!''' [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]] (''8'')
 
## Начать с простейших примеров, когда только d_i, потом усложнять
 
## Отформатировать псевдокод
 
## Оформить правильно источники информации
 
## Добавить категории
 
# [[Методы решения задач теории расписаний]] (''3'')
 
 
## Как-нибудь структурировать конспект, а то много всего рандомного написано
 
## Как-нибудь структурировать конспект, а то много всего рандомного написано
 
## Ссылки оформить как интервики
 
## Ссылки оформить как интервики
## Оставить только совсем мелки доказательства, на наборы задач кинуть ссылки или создать новые конспекты
+
## Оставить только совсем мелкие доказательства, на наборы задач кинуть ссылки или создать новые конспекты
 
## Добавить источники информации
 
## Добавить источники информации
# [[Правило Лаулера]] (''3'')
+
## Разнести на отдельные конспекты с доказательством, если такой задачи нет, или оформить как основную статью с ссылкой на оригинал, приведя обзорное решение
## Задачу в шаблон
+
# [[Правило Лаулера]]
## Отформатировать псевдокод
+
 
## Заменить дефисы на тире
+
=== Задачи с одним станком ===
## Заменить знаки неравенств
+
<ol>
## Добавить "информации" в источники
+
<li value=4> ''взяли'' [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]] (''1.5'') </li>
# [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]] (''1.5'')
+
# Переименовать конспект и оставить перенаправление
## Задачу в шаблон
+
# Задачу в шаблон
## Отформатировать псевдокод
+
# Отформатировать псевдокод
## Добавить категории
+
# Добавить категории
## Заменить литературу на источники информации
+
# Заменить литературу на источники информации
# '''!!!''' [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]] (''8'')
+
<li> [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]</li>
## Задачу в шаблон
+
<li> '''fixed''' [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]] (''8'') </li>
## Рассмотреть более простые варианты задачи для начала
+
# Начать с простейших примеров, когда только d_i, потом усложнять
## Отформатировать псевдокод
+
# Отформатировать псевдокод
## Добавить источники
+
# Оформить правильно источники информации
# [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
+
# Добавить категории
# [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]] (''3'')
+
<li> [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]</li>
## Более простой аналог задачи рассмотреть (только с U_i)
+
<li> [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]</li>
## Отформатировать псевдокод
+
<li> ''fixed'' [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]] (''3'') </li>
## Заменить литературу на источники информации
+
# Более простой аналог задачи рассмотреть (только с U_i)
# [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] (''7'')
+
# Отформатировать псевдокод
## Задачу в шаблон
+
# Заменить литературу на источники информации
## Отформатировать псевдокоды
+
<li> '''fixed''' [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] (''7'') </li>
## Более подробное и понятное описание, чтобы было понятно, как закодить
+
# Задачу в шаблон
## Увеличить дроби
+
# Отформатировать псевдокоды
# [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]] (''1'')
+
# Более подробное и понятное описание, чтобы было понятно, как закодить
## Задачу в шаблон
+
# Увеличить дроби
## Заменить знаки неравенств
+
<li> [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]</li>
## Добавить источники информации
+
</ol>
# [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]] (''0.5'')
+
 
## Увеличить дроби
+
=== Специальные случаи задач для двух станков ===
## Оформить правильно источники информации
+
<ol>
## Добавить категории
+
<li value=12> ''fixed'' [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]] (''2'') </li>
## Заменить знаки неравенств
+
# Увеличить дроби
# [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]] (''0.5'')
+
# Оформить правильно источники информации
## Заменить знаки неравенств
+
# Добавить категории
## Добавить категории
+
# Заменить знаки неравенств
# [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]] (''2'')
+
# Взять задачу в шаблон, пункт описание не нужен
## Задачу в шаблон
+
# Добавить нотацию задачи в начало
## Отформатировать псевдокоды
+
<li>'''fixed''' [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]] (''5'') </li>
## Заменить знаки неравенств
+
# Допилить
## Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней
+
# Доказать корректность
# [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]] (''0.5'')
+
# Задачу в шаблон
## Задачу в шаблон
+
# Отформатировать псевдокод
## Заменить знаки неравенств
+
# Добавить категории
## Добавить информации в источники
+
<li> ''fixed'' [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] (''3'') </li>
# [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]] (''1'')
+
# Задачу в шаблон
## Там получаются очень большие списки, если рассматривать их все для каждого станка, нужно написать, как лучше всего организовать очередь приоритетов
+
# Заменить знаки неравенств
## Увеличить дроби
+
# Отформатировать псевдокод
## Задачу в шаблон
+
# Красивые картинки
## Оформить правильно Источники инфорации
+
<li> ''fixed'' [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]] (''1'') </li>
# '''!!!''' [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]] (''5'')
+
# Заменить знаки неравенств
## Допилить
+
# Категории
## Доказать корректность
+
# задачу в шаблон
## Задачу в шаблон
+
# Отформатировать псевдокод
## Отформатировать псевдокод
+
<li> ''fixed'' [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]] (''1'') </li>
## Добавить категории
+
# Задачу в шаблон
# [[Flow shop]] (''2'')
+
# Знаки неравенств
## Таблички оформить как викитаблички, а не как код
+
# Источники информации
## Битое примечание
+
# Дефисы на тире
## Отформатировать псевдокоды
+
# Исправить теховское обозначение задачи
## Добавить категории
+
<li> '''fixed''' [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]] (10) </li>
# [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] (''3'')
+
# Доделать
## Задачу в шаблон
+
</ol>
## Заменить знаки неравенств
+
 
## Отформатировать псевдокод
+
=== Задачи для произвольного числа станков ===
## Красивые картинки
+
<ol>
# [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]] (''2'')
+
<li value=18> ''fixed'' [[Flow shop]] (''2'') </li>
## Ранее было доказано, что эта задача сводится к 1|p_ij=1|sumwiUi, поэтому надо просто выпилить отсюда значимую часть и перенести примером в Flow shop
+
# Таблички оформить как викитаблички, а не как код
# [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]] (''1'')
+
# Битое примечание
## Заменить знаки неравенств
+
# Отформатировать псевдокоды
## Категории
+
# Добавить категории
## задачу в шаблон
+
<li> [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]] </li>
## Отформатировать псевдокод
+
<li> [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]] </li>
# [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]] (''0.5'')
+
<li> ''fixed'' [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]] (''3'')</li>
## Категории
+
# Задачу в шаблон
## Шаблон
+
# Отформатировать псевдокоды
## Знаки неравенств
+
# Заменить знаки неравенств
# [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]] (''1'')
+
# Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней
## Задачу в шаблон
+
<li> ''fixed'' [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]] (''0.5'') </li>
## Знаки неравенств
+
# Задачу в шаблон
## Источники информации
+
# Заменить знаки неравенств
## Дефисы на тире
+
# Добавить информации в источники
# '''!!!''' [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]] (10)
+
<li> [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]] </li>
## Доделать
+
<li> ''fixed'' [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]] (''0.5'') </li>
 +
# Категории
 +
# Шаблон
 +
# Знаки неравенств
 +
</ol>

Текущая версия на 19:15, 23 февраля 2017

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

Помним про добавление англоязычных терминов в конспекты.

1. Основные определения. Простые комбинаторные свойства слов

  1. Основные определения, связанные со строками
  2. Период и бордер, их связь
  3. fixed Слово Фибоначчи (2)
    1. Убрать лишние пункты
    2. Англоязычные термины
    3. Все переменные в Tex
    4. Исправить знаки неравенств
    5. Правильно оформить См. также и Источники информации
    6. Написать, почему строка Фибоначчи будет (2, 4) исключением
    7. Можно написать про исключения отдельный конспект даже, если там много информации наберётся
  4. fixed Слово Туэ-Морса (5)
    1. Англоязычные термины
    2. Правильно оформить См. также и Источники информации
    3. Доказать какой-нибудь нетривиальный факт про строку Туэ-Морса
  5. Декомпозиция Линдона
  6. Алгоритм Ландау-Шмидта
  7. взяли Алгоритм Крочемора (5)
    1. Пояснить наивную реализацию в начале
    2. Доказать первую лемму
    3. Удалить Лоренца из источников
    4. Пояснить подробней псевдокод
    5. Взять кортежи в тех и оформить красиво
  8. Алгоритм Мейна-Лоренца

2. Поиск подстроки в строке

0. Поиск подстроки в строке

Точный поиск

  1. Наивный алгоритм поиска подстроки в строке
  2. Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
  3. Поиск наибольшей общей подстроки двух строк с использованием хеширования
  4. Префикс-функция
  5. Алгоритм Кнута-Морриса-Пратта
  6. Автомат Кнута-Морриса-Пратта
  7. Z-функция
  8. fixed Бор (8)
    1. Больше ссылок
    2. Кое-где надо подправить tex
    3. Нарисовать нормальные картинки
    4. Построение оформить эстетично по шагам
    5. Добавить ссылки на суффиксный бор, провести связь с суффиксным деревом
    6. Добавить информацию про использование дерева для хранения переходов
    7. Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах
    8. Добавить см. также, оформить правильно источники информации
    9. Категория
  9. fixed Алгоритм Ахо-Корасик (8)
    1. Задачу в шаблон
    2. Написать асимптотику нормально
    3. Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше уточнить у куратора
    4. Красивые картинки
    5. Отформатировать псевдокод
    6. Источники заменить на источники информации
    7. Отформатировать раздел с масками
    8. Категория
  10. fixed Алгоритм Бойера-Мура (4)
    1. Добавить понятную табличку примера с пояснением каждого шага
    2. and в Tex заменить на знак конъюнкции
    3. Добавить пояснений в формальные определения
    4. Ссылки заменить на источники информации
    5. Категория
    6. Отформатировать псевдокод
  11. Алгоритм Колусси
  12. Алгоритм Shift-And
  13. fixed Двусторонний алгоритм (0.5)
    1. Список с большой буквы начать
    2. Неправильный порядок разделов в конце конспекта
    3. Стрелки в псевдокоде заменить на =

Нечёткий поиск

  1. Алгоритм Ландау-Вишкина (k несовпадений)
  2. Алгоритм Ландау-Вишкина (k различий)

3. Суффиксное дерево

  1. Суффиксный бор
  2. fixed Сжатое суффиксное дерево (2)
    1. Немного пояснить про эквивалентность определений сжатого суффиксного бора и сжатого дерева, а то путаница какая-то сейчас
    2. Англоязычные термины
    3. Сделать список нормальный в доказательстве
    4. Отформатировать псевдокод в построении
    5. Свойства написать с маленькой буквы и перечислить через запятую
    6. Добавить псевдокод структуры Vertex перед построением
  3. Алгоритм Укконена
  4. Алгоритм МакКрейта
  5. fixed Алгоритм Фарача (2)
    1. В конспекте полно опечаток - исправить
    2. Интервики на поразрядную сортировку
    3. Рисунки подписать в thumb
    4. Добавить недостатки и преимущества

4. Суффиксный массив

  1. Суффиксный массив
  2. Построение суффиксного массива с помощью стандартных методов сортировки
  3. Алгоритм цифровой сортировки суффиксов циклической строки
  4. fixed Алгоритм Касаи и др. (3)
    1. Кажется, что LCP вычисляет не длину общих префиксов циклических сдвигов; или надо что-то ещё добавить
    2. "будем использовать промежуточный массив " — лучше написать "вспомогательный"
    3. Добавить фразу и картинку про то, что массив LCP удобно представлять в виде ступенек/столбиков разной высоты
    4. Кстати, не очень понятно, зачем нужен Height, если по сути он выполняет роль LCP
    5. Надо сказать, в каком порядке мы фиксируем соседа: lcp[i] содержит префикс i и i-1 или i и i+1
    6. Думаю, что к утверждению 2 нужные пояснения, а то происходят нетривиальные переходы из словесной формулировки в утверждение; ещё надо добавить, что не изменится относительный порядок именно этих двух суффиксов, а не всех
  5. Алгоритм Карккайнена-Сандерса
  6. fixed Алгоритм поиска подстроки в строке с помощью суффиксного массива (7)
    1. Отформатировать псевдокоды
    2. Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
    3. Исправить баги в Tex
    4. Оформить правильно источники информации

5. Задача о наименьшем общем предке

  1. Сведение задачи LCA к задаче RMQ
  2. Сведение задачи RMQ к задаче LCA
  3. Метод двоичного подъема
  4. Решение RMQ с помощью разреженной таблицы
  5. fixed Алгоритм Фарака-Колтона и Бендера (2)
    1. Отформатировать псевдокод
    2. Увеличить дроби
  6. !!! Heavy-light декомпозиция (6)
    1. "решается с помощью heavy-light декомпозиции" — может быть решена
    2. "Пусть A, B - ко" — дефисы нужно заменить на тире
    3. В начале у тебя идут вершины a,b и A,B, а потом u,v и a,b. Надо сделать единообразно, чтобы начало конспекта и его конец согласовывались. Например, сделать корни путей большими буквами — норм. Тогда можно либо a,b и A,B, либо u,v и U,V.
    4. "В данном случае корень одного из путей является вершиной другого." — а почему пути не могут пересекаться крест-на-крест?
    5. Слишком много повтором «Пусть» в доказательстве леммы.
    6. "Но LCA должен принадлежать двум путям. Но" — дублирование «Но»
    7. "Предположим, что LCA не равны" — криво написано, нужно формально исходя из формулировки
    8. Ну и вообще, как будто слов пожадничал на лемму и кое-как написал
    9. "Построим декомпозицию." — декомпозицию чего и для чего? Очень плохо оставлять открытый контекст, особенно в начале пункта. Лучше чуть более подробно описать, чтобы было понятно
    10. "Корень пути, на котором лежит текущая вершина.

Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева." — вообще непонятно, как связано то, что мы хотим сохранить с тем, что написано потом. Нет предложения-связки

    1. "Пусть требуется" — опять пуст
    2. "Пусть на данной итерации" — как будто других слов нет
    3. "LCA будет та" — это не по-русски
    4. Возьми LCA в тексте везде в \mathrm
    5. "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?
  1. fixed Алгоритм Шибера-Вишкина (3)
    1. Англоязычные термины
    2. Интервики на LCA
    3. Чё ещё за подготовка?
    4. Почему-то в определении находится не определение, надо бы нормально переписать
    5. Лучше дать нормальное название обхода: pre-order, in-order или post-, если что-то из этого оно и есть
    6. Увеличить дроби
    7. Добавить См. также
    8. Добавить Категории
    9. Правильно оформить источники информации
  2. Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
  3. fixed Link-Cut Tree (5)
    1. Отформатировать псевдокоды
    2. Написать более понятное введение и пояснить подробней остальные смутные операции
    3. Список оформлен некрасиво в начале
    4. Категории
    5. Оформить правильно См. также и Источники информации

6. Матроиды

Основные факты теории матроидов

  1. Определение матроида
  2. Примеры матроидов
  3. Прямая сумма матроидов
  4. Теорема Радо-Эдмондса (жадный алгоритм)
  5. Теорема о базах
  6. Аксиоматизация матроида базами
  7. Теорема о циклах
  8. Аксиоматизация матроида циклами
  9. Ранговая функция, полумодулярность
  10. Двойственный матроид
  11. Оператор замыкания для матроидов
  12. Покрытия, закрытые множества
  13. Матроид Вамоса

Пересечение матроидов

  1. Пересечение матроидов, определение, примеры
  2. взяли Лемма о паросочетании в графе замен (5)
    1. Док-во по индукции оформить красиво
    2. Исправить док-во: неверный переход
    3. Заменить xor на треугольник
    4. Добавить категорию
  3. fixed Лемма о единственном паросочетании в графе замен (0.5)
    1. Оформить правильно источники информации
    2. Добавить категорию
    3. Категория
    4. Оформить красиво док-во по индукции
  4. fixed Граф замен для двух матроидов (3)
    1. Нарисовать нормальную картинку
    2. Добавить информацию про граф замен для одного матроида
    3. Исправить ссылки в соответствующих конспектах
    4. Создать новый конспект, в него сделать перенаправление из текущего
    5. Оформиь правильно источники информации
    6. Добавить категорию
  5. Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
  6. Алгоритм построения базы в пересечении матроидов

Объединение матроидов

  1. fixed Объединение матроидов, проверка множества на независимость (8)
    1. Добавить формальное определение
    2. Структурировать конспект, а не оставлять просто набором тезисов
    3. Добавить категории
    4. Добавить ссылок
    5. Избавиться от сокращений
    6. Добавить содержательный примеры
    7. Заменить тире на Шаблон:---
  2. взяли Объединение матроидов, доказательство того, что объединение является матроидом (1)
    1. Добавить категории
    2. Добавить интервики
    3. Отформатировать по правилам
    4. Помёрджить с предыдущим конспектом
  3. взяли Алгоритм построения базы в объединении матроидов (7)
    1. В определение само определение выделить жирным
    2. Тире заменить на Шаблон:---
    3. Добавить категории
    4. Добавить псевдокод
    5. Написать более подробное описание алгоритма поиска базы в объединении

7. Теория расписаний

Общая теория

  1. Классификация задач
  2. fixed Методы решения задач теории расписаний (5)
    1. Как-нибудь структурировать конспект, а то много всего рандомного написано
    2. Ссылки оформить как интервики
    3. Оставить только совсем мелкие доказательства, на наборы задач кинуть ссылки или создать новые конспекты
    4. Добавить источники информации
    5. Разнести на отдельные конспекты с доказательством, если такой задачи нет, или оформить как основную статью с ссылкой на оригинал, приведя обзорное решение
  3. Правило Лаулера

Задачи с одним станком

  1. взяли [math]1 \mid \mid \sum U_{i}[/math] (1.5)
    1. Переименовать конспект и оставить перенаправление
    2. Задачу в шаблон
    3. Отформатировать псевдокод
    4. Добавить категории
    5. Заменить литературу на источники информации
  2. [math]1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}[/math]
  3. fixed [math]1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -[/math] (8)
    1. Начать с простейших примеров, когда только d_i, потом усложнять
    2. Отформатировать псевдокод
    3. Оформить правильно источники информации
    4. Добавить категории
  4. [math] 1 \mid r_i,p_i=p \mid \sum w_i U_i[/math]
  5. [math]1 \mid outtree \mid \sum w_i C_i[/math]
  6. fixed [math]1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}[/math] (3)
    1. Более простой аналог задачи рассмотреть (только с U_i)
    2. Отформатировать псевдокод
    3. Заменить литературу на источники информации
  7. fixed [math]1 \mid prec, pmtn, r_i \mid f_{\max}[/math] (7)
    1. Задачу в шаблон
    2. Отформатировать псевдокоды
    3. Более подробное и понятное описание, чтобы было понятно, как закодить
    4. Увеличить дроби
  8. [math]1 \mid prec; r_i; p_i = 1 \mid L_{max}[/math]

Специальные случаи задач для двух станков

  1. fixed [math]P2 \mid prec, p_i = 1 \mid L_{\max}[/math] (2)
    1. Увеличить дроби
    2. Оформить правильно источники информации
    3. Добавить категории
    4. Заменить знаки неравенств
    5. Взять задачу в шаблон, пункт описание не нужен
    6. Добавить нотацию задачи в начало
  2. fixed [math]R2 \mid \mid C_{max}[/math] (5)
    1. Допилить
    2. Доказать корректность
    3. Задачу в шаблон
    4. Отформатировать псевдокод
    5. Добавить категории
  3. fixed [math]F2 \mid \mid C_{max}[/math] (3)
    1. Задачу в шаблон
    2. Заменить знаки неравенств
    3. Отформатировать псевдокод
    4. Красивые картинки
  4. fixed [math]O2 \mid \mid C_{max}[/math] (1)
    1. Заменить знаки неравенств
    2. Категории
    3. задачу в шаблон
    4. Отформатировать псевдокод
  5. fixed [math]J2 \mid n_{i} \le 2 \mid C_{max}[/math] (1)
    1. Задачу в шаблон
    2. Знаки неравенств
    3. Источники информации
    4. Дефисы на тире
    5. Исправить теховское обозначение задачи
  6. fixed [math]J2\mid p_{ij} = 1\mid L_{max}[/math] (10)
    1. Доделать

Задачи для произвольного числа станков

  1. fixed Flow shop (2)
    1. Таблички оформить как викитаблички, а не как код
    2. Битое примечание
    3. Отформатировать псевдокоды
    4. Добавить категории
  2. [math]F \mid p_{ij} = 1 \mid \sum w_i U_i[/math]
  3. [math]P \mid pmtn, r_i \mid L_{max}[/math]
  4. fixed [math]Q \mid pmtn \mid C_{max}[/math] (3)
    1. Задачу в шаблон
    2. Отформатировать псевдокоды
    3. Заменить знаки неравенств
    4. Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней
  5. fixed [math]Q \mid pmtn, r_{i} \mid L_{max}[/math] (0.5)
    1. Задачу в шаблон
    2. Заменить знаки неравенств
    3. Добавить информации в источники
  6. [math]Q\mid\mid\sum{C_i}[/math]
  7. fixed [math]O \mid p_{ij} = 1 \mid \sum U_i[/math] (0.5)
    1. Категории
    2. Шаблон
    3. Знаки неравенств