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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Защищена страница «Участник:Shersh/Тикеты к 4ому терму» ([edit=sysop] (бессрочно) [move=sysop] (бессрочно)))
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 4ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показаны 173 промежуточные версии этого же участника)
Строка 4: Строка 4:
  
 
== 1. Основные определения. Простые комбинаторные свойства слов ==
 
== 1. Основные определения. Простые комбинаторные свойства слов ==
# '''fixed''' [[Основные определения, связанные со строками]]
+
# [[Основные определения, связанные со строками]]
 +
# [[Период и бордер, их связь]]
 +
# ''fixed'' [[Слово Фибоначчи]] (''2'')
 +
## Убрать лишние пункты
 
## Англоязычные термины
 
## Англоязычные термины
## Исправить tex <tex> \leq </tex>
+
## Все переменные в Tex
## Убрать определения бордера и периода из следующего конспекта и перенести их в этот, а там сделать ссылками
+
## Исправить знаки неравенств
## Добавить определение периода, как возможность представить строку в виде конкатенации каких-то строк
+
## Правильно оформить См. также и Источники информации
## Помёржить с похожим конспектом теории формальных языков
 
# '''fixed''' [[Период и бордер, их связь]]
 
## Избавиться от br и подобных тегов. Всё сделать через tex
 
## Добавить больше ссылок
 
## Поправить доказательства местами
 
## Нормальное доказтельство про НОД
 
# '''!!!''' [[Слово Фибоначчи]]
 
 
## Написать, почему строка Фибоначчи будет (2, 4) исключением
 
## Написать, почему строка Фибоначчи будет (2, 4) исключением
 
## Можно написать про исключения отдельный конспект даже, если там много информации наберётся
 
## Можно написать про исключения отдельный конспект даже, если там много информации наберётся
# '''!!!''' [[Слово Туэ-Морса]]
+
# '''fixed''' [[Слово Туэ-Морса]] (''5'')
## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
+
## Англоязычные термины
## А ещё сделать ссылки на Википедию через интервики
+
## Правильно оформить См. также и Источники информации
 +
## Доказать какой-нибудь нетривиальный факт про строку Туэ-Морса
 +
# [[Декомпозиция Линдона]]
 +
# [[Алгоритм Ландау-Шмидта]]
 +
# '''взяли''' [[Алгоритм Крочемора]] (''5'')
 +
## Пояснить наивную реализацию в начале
 +
## Доказать первую лемму
 +
## Удалить Лоренца из источников
 +
## Пояснить подробней псевдокод
 +
## Взять кортежи в тех и оформить красиво
 +
# [[Алгоритм Мейна-Лоренца]]
  
 
== 2. Поиск подстроки в строке ==
 
== 2. Поиск подстроки в строке ==
: 0. '''added''' добавить в "Поиск подстроки в строке" табличку с алгоритмами поиска и оценкой асимптотик, как [[ Сортировка | здесь]]
+
: 0. [[Поиск подстроки в строке]]
# '''fixed''' [[Наивный алгоритм поиска подстроки в строке]]
+
=== Точный поиск ===
## Добавить категории
+
# [[Наивный алгоритм поиска подстроки в строке]]
## Преимущества алгоритма (да, даже у наивного они есть)
+
# [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
## Поправить tex в конспекте и псевдокод
 
# ''fixed'' [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 
## Добавить категории
 
## Пример плохой строки, на которой хеширование не работает
 
 
# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
 
# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
# '''fixed''' [[Префикс-функция]]
+
# [[Префикс-функция]]
## Добавить неформальное определение
+
# [[Алгоритм Кнута-Морриса-Пратта]]
## Отформатировать псевдокод {{---}} сейчас не совсем по-человечески выглядит
+
# [[Автомат Кнута-Морриса-Пратта]]
## Поменять заголовки "Алгоритм" и "Оптимизация" на "Наивный алгоритм" и "Эффективный алгоритм"
+
# [[Z-функция]]
## Ужасная картинка! Перерисовать
+
# '''fixed''' [[Бор]] (''8'')
## Сделать описание эффективного алгоритма более понятным и адекватным
 
## Категории!
 
## Англоязычные термины
 
# '''fixed''' [[Алгоритм Кнута-Морриса-Пратта]]
 
## И тут категории
 
## Оформить нормально источники
 
## Поправить tex в описании, сделать описание более понятным. Например, сказать, что значение префикс функции в данной позиции равно длине бордера строки, а в данном случае это и будет ответом
 
## Англоязычные термины
 
## Индекс <tex> i </tex> в картинке слишком маленький относительно букв {{---}} поправить
 
# ''fixed'' [[Z-функция]]
 
## Категории
 
## Ссылки на википедию оформить как интервики
 
## Поправить ужасный псевдокод
 
# '''взяли'' [[Автомат для поиска образца в тексте]]
 
## Дописать до нормальной статьи о суффиксном автомате (если это оно и есть)
 
# '''!!!''' [[Бор]]
 
 
## Больше ссылок
 
## Больше ссылок
 
## Кое-где надо подправить tex
 
## Кое-где надо подправить tex
Строка 60: Строка 46:
 
## Добавить информацию про использование дерева для хранения переходов
 
## Добавить информацию про использование дерева для хранения переходов
 
## Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах
 
## Расказать немного про использование бора в качестве Map и дать оценку на оптимальность при известных запросах
# '''!!!''' [[Алгоритм Ахо-Корасик]]
+
## Добавить см. также, оформить правильно источники информации
 +
## Категория
 +
# '''fixed''' [[Алгоритм Ахо-Корасик]] (''8'')
 +
## Задачу в шаблон
 
## Написать асимптотику нормально
 
## Написать асимптотику нормально
## Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше написать по поводу того, что хотите сделать
+
## Другие способы ускорения алгоритма или оптимизаций по памяти. Лучше уточнить у куратора
 +
## Красивые картинки
 +
## Отформатировать псевдокод
 +
## Источники заменить на источники информации
 +
## Отформатировать раздел с масками
 +
## Категория
 +
# ''fixed'' [[Алгоритм Бойера-Мура]] (''4'')
 +
## Добавить '''понятную''' табличку примера с пояснением каждого шага
 +
## and в Tex заменить на знак конъюнкции
 +
## Добавить пояснений в формальные определения
 +
## Ссылки заменить на источники информации
 +
## Категория
 +
## Отформатировать псевдокод
 +
# [[Алгоритм Колусси]]
 +
# [[Алгоритм Shift-And]]
 +
# ''fixed'' [[Двусторонний алгоритм]] (0.5)
 +
## Список с большой буквы начать
 +
## Неправильный порядок разделов в конце конспекта
 +
## Стрелки в псевдокоде заменить на =
 +
 
 +
=== Нечёткий поиск ===
 +
<ol>
 +
<li value=15> [[Алгоритм Ландау-Вишкина (k несовпадений)]] </li>
 +
<li> [[Алгоритм Ландау-Вишкина (k различий)]] </li>
 +
</ol>
  
 
== 3. Суффиксное дерево ==
 
== 3. Суффиксное дерево ==
 
# [[Суффиксный бор]]
 
# [[Суффиксный бор]]
# [[Сжатое суффиксное дерево]]
+
# ''fixed'' [[Сжатое суффиксное дерево]] (''2'')
# '''взяли''' [[Алгоритм Укконена]]
+
## Немного пояснить про эквивалентность определений сжатого суффиксного бора и сжатого дерева, а то путаница какая-то сейчас
## Дописать нормальный псевдокод
+
## Англоязычные термины
## Сделать понятное и нормальное описание
+
## Сделать список нормальный в доказательстве
## Подстроку переписать как <tex> s[i..j] </tex>
+
## Отформатировать псевдокод в построении
## Константы и переменные взять в tex
+
## Свойства написать с маленькой буквы и перечислить через запятую
## Пробелы перед скобками в тексте
+
## Добавить псевдокод структуры Vertex перед построением
## Интервики на леммы
+
# [[Алгоритм Укконена]]
## В Cм. также добавить два других алгоритма построения суффиксных деревьев
+
# [[Алгоритм МакКрейта]]
## Добавить ссылок в источники, оформить нормально
+
# ''fixed'' [[Алгоритм Фарача]] (''2'')
 +
## В конспекте полно опечаток - исправить
 +
## Интервики на поразрядную сортировку
 +
## Рисунки подписать в thumb
 +
## Добавить недостатки и преимущества
  
 
== 4. Суффиксный массив ==
 
== 4. Суффиксный массив ==
 
# [[Суффиксный массив]]
 
# [[Суффиксный массив]]
 
# [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
# [[Построение суффиксного массива с помощью стандартных методов сортировки]]
# '''!!!''' [[Алгоритм цифровой сортировки суффиксов циклической строки]]
+
# [[Алгоритм цифровой сортировки суффиксов циклической строки]]
## Добавить ссылку на цифровую сортировку куда-нибудь в конспект
+
# ''fixed'' [[Алгоритм Касаи и др.]] (''3'')
## Заменить картинку таблицы на теховскую таблицу
+
## Кажется, что LCP вычисляет не длину общих префиксов циклических сдвигов; или надо что-то ещё добавить
## Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать
+
## "будем использовать промежуточный массив " — лучше написать "вспомогательный"
## Возможно придётся чуточку переписать описание алгоритма
+
## Добавить фразу и картинку про то, что массив LCP удобно представлять в виде ступенек/столбиков разной высоты
# ''взяли'' [[Алгоритм Касаи и др.]]
+
## Кстати, не очень понятно, зачем нужен Height, если по сути он выполняет роль LCP
## Добавить псевдокод
+
## Надо сказать, в каком порядке мы фиксируем соседа: lcp[i] содержит префикс i и i-1 или i и i+1
## Заменить Источники на Источники информации
+
## Думаю, что к утверждению 2 нужные пояснения, а то происходят нетривиальные переходы из словесной формулировки в утверждение; ещё надо добавить, что не изменится относительный порядок именно этих двух суффиксов, а не всех
## Исправить знаки неравенств
 
## Переход в последней теореме оформить на отдельной строке, чтобы пояснение не путалось в формуле
 
 
# [[Алгоритм Карккайнена-Сандерса]]
 
# [[Алгоритм Карккайнена-Сандерса]]
# '''!!!''' [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
+
# '''fixed''' [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]] (''7'')
 
## Отформатировать псевдокоды
 
## Отформатировать псевдокоды
 
## Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
 
## Разобраться в алгоритмах и написать нормальное описание: там встречаются баги
 +
## Исправить баги в Tex
 +
## Оформить правильно источники информации
  
 
== 5. Задача о наименьшем общем предке ==
 
== 5. Задача о наименьшем общем предке ==
# ''fixed'' [[Метод двоичного подъема]]
 
## Поправить ужасный псевдокод
 
 
# [[Сведение задачи LCA к задаче RMQ]]
 
# [[Сведение задачи LCA к задаче RMQ]]
 +
# [[Сведение задачи RMQ к задаче LCA]]
 +
# [[Метод двоичного подъема]]
 
# [[Решение RMQ с помощью разреженной таблицы]]
 
# [[Решение RMQ с помощью разреженной таблицы]]
# '''!!!''' [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
+
# ''fixed'' [[Алгоритм Фарака-Колтона и Бендера]] (''2'')
## Добавить оптимизацию по памяти
+
## Отформатировать псевдокод
## Написать псевдокод
+
## Увеличить дроби
## Добавить сведение задачи RMQ к задаче +/-1 RMQ
+
# '''!!!''' [[Heavy-light декомпозиция]] (''6'')
# [[Алгоритм Шибера-Вишкина]]
+
## "решается с помощью heavy-light декомпозиции" — может быть решена
# [[Сведение задачи RMQ к задаче LCA]]
+
## "Пусть 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
 +
## Чё ещё за подготовка?
 +
## Почему-то в определении находится не определение, надо бы нормально переписать
 +
## Лучше дать нормальное название обхода: pre-order, in-order или post-, если что-то из этого оно и есть
 +
## Увеличить дроби
 +
## Добавить См. также
 +
## Добавить Категории
 +
## Правильно оформить источники информации
 +
# [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
 +
# '''fixed''' [[Link-Cut Tree]] (5)
 +
## Отформатировать псевдокоды
 +
## Написать более понятное введение и пояснить подробней остальные смутные операции
 +
## Список оформлен некрасиво в начале
 +
## Категории
 +
## Оформить правильно См. также и Источники информации
  
 
== 6. Матроиды ==
 
== 6. Матроиды ==
# ''fixed'' [[Определение матроида]]
+
=== Основные факты теории матроидов ===
## Англоязычные термины
+
# [[Определение матроида]]
## Поправить источники информации
+
# [[Примеры матроидов]]
## Заменить тире на [[Шаблон:---]]
+
# [[Прямая сумма матроидов]]
# '''fixed''' [[Примеры матроидов]]
+
# [[Теорема Радо-Эдмондса (жадный алгоритм)]]
## Англоязычные термины
+
# [[Теорема о базах]]
## Добавить ссылок, см. также
 
## Отформатировать tex (тире, знаки неравенств, dots, mid и т. п.)
 
## Длинные слова взять в \mathrm
 
## Добавить интервики
 
## Добавить примеры матроидов из дз как определения
 
## Добавить примеры матроидов [http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf отсюда] (ещё про бинарные) с доказательствами (может набраться на <tex> 10 </tex> баллов в итоге, если всё сделать очень хорошо)
 
# '''fixed''' [[Прямая сумма матроидов]]
 
## Добавить в определение слова "прямая сумма"
 
## Добавить ссылки, см. также, интервики
 
## Пример разложения в прямую сумму (можно из дз)
 
# '''fixed''' [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
## Объединить со следующим конспектом
 
## Различные задачи на жадные алгоритмы, лучше те, где жадность неочевидна
 
## Ссылки, tex
 
# ''взяли'' [[Жадный алгоритм поиска базы минимального веса]]
 
## Добавить разных ссылок
 
## Мутное описание алгоритма
 
## Криво написана асимптотика
 
## Больше интервики
 
# '''!!!''' [[Теорема о базах]]
 
## Англоязычные термины
 
## Добавить ссылок, см. также
 
## Поправить tex
 
## Обернуть семейство в \mathcal
 
## Добавить сильную теорему баз (base exchange) {{---}} см. Chandra Chekuri
 
 
# [[Аксиоматизация матроида базами]]
 
# [[Аксиоматизация матроида базами]]
## Больше ссылок
+
# [[Теорема о циклах]]
# ''fixed'' [[Теорема о циклах]]
 
## Поправить tex
 
## Заменить Ccl на \mathfrak{C}
 
## Добавить ссылок
 
## Англоязычные термины
 
 
# [[Аксиоматизация матроида циклами]]
 
# [[Аксиоматизация матроида циклами]]
 
# [[Ранговая функция, полумодулярность]]
 
# [[Ранговая функция, полумодулярность]]
## tex
+
# [[Двойственный матроид]]
## Ссылки
+
# [[Оператор замыкания для матроидов]]
## Англоязычные термины
+
# [[Покрытия, закрытые множества]]
# ''fixed'' [[Двойственный матроид]]
+
# [[Матроид Вамоса]]
## Множество через фигурные скобки написать в определении
 
## Англоязычные термины к определениям
 
## Маркированный и нумерованный списки смотрятся ужасно вместе
 
## Тире заменить на шаблон
 
## Добавить ссылок и интервики
 
## Расписать неочевидный переход про единственность цикла в расширенной базе
 
# ''fixed'' [[Оператор замыкания для матроидов]]
 
## Тире
 
## Больше ссылок
 
  
== 7.Пересечение матроидов ==
+
=== Пересечение матроидов ===
# '''!!!''' [[Пересечение матроидов, определение, примеры]]
+
<ol>
## Ссылки
+
<li value="14"> [[Пересечение матроидов, определение, примеры]] </li>
## tex
+
<li> '''взяли''' [[Лемма о паросочетании в графе замен]] (''5'') </li>
## Ещё примеров
+
# Док-во по индукции оформить красиво
## Больше общих описаний
+
# Исправить док-во: неверный переход
## Пример, когда пересечение матроидов не является матроидом
+
# Заменить xor на треугольник
## Доказательство матроидности уже приведённых примеров
+
# Добавить категорию
# '''!!!''' [[Лемма о паросочетании в графе замен]]
+
<li> ''fixed'' [[Лемма о единственном паросочетании в графе замен]] (''0.5'') </li>
## Док-во по индукции оформить красиво
+
# Оформить правильно источники информации
## Исправить док-во: неверный переход
+
# Добавить категорию
## Заменить xor на треугольник
+
# Категория
# ''fixed'' [[Лемма о единственном паросочетании в графе замен]]
+
# Оформить красиво док-во по индукции
## Константы в tex
+
<li> ''fixed'' [[Граф замен для двух матроидов]] (''3'') </li>
## Убрать сокращения
+
# Нарисовать нормальную картинку
## Добавить интервики
+
# Добавить информацию про граф замен для одного матроида
# '''!!!''' [[Граф замен для двух матроидов]]
+
# Исправить ссылки в соответствующих конспектах
## Нарисовать нормальную картинку
+
# Создать новый конспект, в него сделать перенаправление из текущего
## Добавить информацию про граф замен для одного матроида
+
# Оформиь правильно источники информации
## Исправить ссылки в соответствующих конспектах
+
# Добавить категорию
## Создать новый конспект, в него сделать перенаправление из текущего
+
<li> [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]] </li>
# [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
+
<li> [[Алгоритм построения базы в пересечении матроидов]] </li>
## Картинки плывут {{---}} разместить нормально
+
</ol>
## Заменить обозначение графа замен на принятое
 
## Сделать интервики на другие конспекты (паросочетание, кратчайший путь, граф замен)
 
# '''!!!''' [[Алгоритм построения базы в пересечении матроидов]]
 
## Матроиды записать через угловые скобки
 
## Заменить тире на шаблон
 
## Добавить категории
 
## Отформатировать псевдокод
 
## Мелкие правки в tex
 
## Перерисовать картинку
 
## Помёрджить со следующим конспектом
 
# [[Теорема Эдмондса-Лоулера]]
 
## Добавить категории
 
## Заменить знак симметрической разности, а так же другие мелкие правки в tex
 
## Картинки кривовато расположены {{---}} поправить
 
## Исправить ошибки в док-ве
 
  
== 8. Объединение матроидов ==
+
=== Объединение матроидов ===
# '''!!!''' [[Объединение матроидов, проверка множества на независимость]]
+
<ol>
## Добавить формальное определение
+
<li value="21"> '''fixed''' [[Объединение матроидов, проверка множества на независимость]] (''8'') </li>
## Структурировать конспект, а не оставлять просто набором тезисов
+
# Добавить формальное определение
## Добавить категории
+
# Структурировать конспект, а не оставлять просто набором тезисов
## Добавить ссылок
+
# Добавить категории
## Избавиться от сокращений
+
# Добавить ссылок
## Добавить содержательный примеры
+
# Избавиться от сокращений
## Заменить тире на [[Шаблон:---]]
+
# Добавить содержательный примеры
## Помёрджить со следующим конспектом
+
# Заменить тире на [[Шаблон:---]]
# [[Объединение матроидов, доказательство того, что объединение является матроидом]]
+
<li> ''взяли'' [[Объединение матроидов, доказательство того, что объединение является матроидом]] (1) </li>
## Добавить категории
+
# Добавить категории
## Добавить интервики
+
# Добавить интервики
# '''!!!''' [[Алгоритм построения базы в объединении матроидов]]
+
# Отформатировать по правилам
## В определение само определение выделить жирным
+
# Помёрджить с предыдущим конспектом
## Тире заменить на [[Шаблон:---]]
+
<li> '''взяли''' [[Алгоритм построения базы в объединении матроидов]] (''7'') </li>
## Добавить категории
+
# В определение само определение выделить жирным
## Добавить псевдокод
+
# Тире заменить на [[Шаблон:---]]
## Написать более подробное описание алгоритма поиска базы в объединении
+
# Добавить категории
 +
# Добавить псевдокод
 +
# Написать более подробное описание алгоритма поиска базы в объединении
 +
</ol>
  
== 9. Теория расписаний ==
+
== 7. Теория расписаний ==
 +
=== Общая теория ===
 
# [[Классификация задач]]
 
# [[Классификация задач]]
# [[Методы решения задач теории расписаний]]
+
# '''fixed''' [[Методы решения задач теории расписаний]] (''5'')
 +
## Как-нибудь структурировать конспект, а то много всего рандомного написано
 +
## Ссылки оформить как интервики
 +
## Оставить только совсем мелкие доказательства, на наборы задач кинуть ссылки или создать новые конспекты
 +
## Добавить источники информации
 +
## Разнести на отдельные конспекты с доказательством, если такой задачи нет, или оформить как основную статью с ссылкой на оригинал, приведя обзорное решение
 
# [[Правило Лаулера]]
 
# [[Правило Лаулера]]
# [[Flow shop]]
+
 
# [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
+
=== Задачи с одним станком ===
# [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
+
<ol>
# [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
+
<li value=4> ''взяли'' [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]] (''1.5'') </li>
# [[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>]]
+
# Задачу в шаблон
# [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
+
# Отформатировать псевдокод
# [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
+
# Добавить категории
# [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
+
# Заменить литературу на источники информации
# [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
+
<li> [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]</li>
# [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
+
<li> '''fixed''' [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]] (''8'') </li>
# [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
+
# Начать с простейших примеров, когда только d_i, потом усложнять
# [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
+
# Отформатировать псевдокод
# [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
+
# Оформить правильно источники информации
# [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
+
# Добавить категории
# [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
+
<li> [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]</li>
# [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
+
<li> [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]</li>
# [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
+
<li> ''fixed'' [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]] (''3'') </li>
# [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]
+
# Более простой аналог задачи рассмотреть (только с U_i)
# [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]
+
# Отформатировать псевдокод
 +
# Заменить литературу на источники информации
 +
<li> '''fixed''' [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] (''7'') </li>
 +
# Задачу в шаблон
 +
# Отформатировать псевдокоды
 +
# Более подробное и понятное описание, чтобы было понятно, как закодить
 +
# Увеличить дроби
 +
<li> [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]</li>
 +
</ol>
 +
 
 +
=== Специальные случаи задач для двух станков ===
 +
<ol>
 +
<li value=12> ''fixed'' [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]] (''2'') </li>
 +
# Увеличить дроби
 +
# Оформить правильно источники информации
 +
# Добавить категории
 +
# Заменить знаки неравенств
 +
# Взять задачу в шаблон, пункт описание не нужен
 +
# Добавить нотацию задачи в начало
 +
<li>'''fixed''' [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]] (''5'') </li>
 +
# Допилить
 +
# Доказать корректность
 +
# Задачу в шаблон
 +
# Отформатировать псевдокод
 +
# Добавить категории
 +
<li> ''fixed'' [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] (''3'') </li>
 +
# Задачу в шаблон
 +
# Заменить знаки неравенств
 +
# Отформатировать псевдокод
 +
# Красивые картинки
 +
<li> ''fixed'' [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]] (''1'') </li>
 +
# Заменить знаки неравенств
 +
# Категории
 +
# задачу в шаблон
 +
# Отформатировать псевдокод
 +
<li> ''fixed'' [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]] (''1'') </li>
 +
# Задачу в шаблон
 +
# Знаки неравенств
 +
# Источники информации
 +
# Дефисы на тире
 +
# Исправить теховское обозначение задачи
 +
<li> '''fixed''' [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]] (10) </li>
 +
# Доделать
 +
</ol>
 +
 
 +
=== Задачи для произвольного числа станков ===
 +
<ol>
 +
<li value=18> ''fixed'' [[Flow shop]] (''2'') </li>
 +
# Таблички оформить как викитаблички, а не как код
 +
# Битое примечание
 +
# Отформатировать псевдокоды
 +
# Добавить категории
 +
<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>
 +
<li> ''fixed'' [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]] (''3'')</li>
 +
# Задачу в шаблон
 +
# Отформатировать псевдокоды
 +
# Заменить знаки неравенств
 +
# Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней
 +
<li> ''fixed'' [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]] (''0.5'') </li>
 +
# Задачу в шаблон
 +
# Заменить знаки неравенств
 +
# Добавить информации в источники
 +
<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. Знаки неравенств