Просмотр исходного текста страницы Участник:Shersh/Тикеты к 4ому терму

Тикеты нумеруются как "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'') ''напишите уже кто-нибудь (желательно адекватный человек, а то третий год непонятный конспект в разработке)''
## Псевдокод оформить как нормальный псевдокод
## Убрать подпункты леммы, их название занести в Шаблон
## Англоязычные термины
## Подстроку обозначать как <tex> s[i..j] </tex>
## В начале пункта Алгоритм форматирование не ок
## Изменить знаки неравенств
## Оформить правильно Источники информации
## См. также переместить перед Источниками информации
## Добавить картинок по ходу дела (на емаксе есть ссылка на 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'')
## Доказать две теоремы
# [[Матроид Вамоса]]

=== Пересечение матроидов === 
<ol>
<li value="14"> '''взяли''' [[Пересечение матроидов, определение, примеры]] (''7'') </li>
# Ссылки
# tex
# Ещё примеров
# Больше общих описаний
# Пример, когда пересечение матроидов не является матроидом
# Доказательство матроидности уже приведённых примеров
# Добавить категорию
<li> '''!!!''' [[Лемма о паросочетании в графе замен]] (''5'') </li>
# Док-во по индукции оформить красиво
# Исправить док-во: неверный переход
# Заменить xor на треугольник
# Добавить категорию
<li> [[Лемма о единственном паросочетании в графе замен]] (''0.3'') </li>
# Оформить правильно источники информации
# Добавить категорию
<li> '''!!!''' [[Граф замен для двух матроидов]] (''5'') </li>
# Нарисовать нормальную картинку
# Добавить информацию про граф замен для одного матроида
# Исправить ссылки в соответствующих конспектах
# Создать новый конспект, в него сделать перенаправление из текущего
# Оформиь правильно источники информации
# Добавить категорию
<li> [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]] (''1'') </li>
# Картинки плывут {{---}} разместить нормально
# Заменить обозначение графа замен на принятое
# Сделать интервики на другие конспекты (паросочетание, кратчайший путь, граф замен)
<li> '''взяли''' [[Алгоритм построения базы в пересечении матроидов]] (''8'') </li>
# Матроиды записать через угловые скобки
# Заменить тире на шаблон
# Добавить категории
# Отформатировать псевдокод
# Мелкие правки в tex
# Перерисовать картинку
# Помёрджить со следующим конспектом
<li> [[Теорема Эдмондса-Лоулера]] </li>
# Добавить категории
# Заменить знак симметрической разности, а так же другие мелкие правки в tex
# Картинки кривовато расположены {{---}} поправить
# Исправить ошибки в док-ве
</ol>

=== Объединение матроидов ===
<ol>
<li value="21"> '''!!!''' [[Объединение матроидов, проверка множества на независимость]] (''8'') </li>
# Добавить формальное определение
# Структурировать конспект, а не оставлять просто набором тезисов
# Добавить категории
# Добавить ссылок
# Избавиться от сокращений
# Добавить содержательный примеры
# Заменить тире на [[Шаблон:---]]
# Помёрджить со следующим конспектом
<li> [[Объединение матроидов, доказательство того, что объединение является матроидом]] </li>
# Добавить категории
# Добавить интервики
<li> '''!!!''' [[Алгоритм построения базы в объединении матроидов]] (''7'') </li>
# В определение само определение выделить жирным
# Тире заменить на [[Шаблон:---]]
# Добавить категории
# Добавить псевдокод
# Написать более подробное описание алгоритма поиска базы в объединении
</ol>

== 7. Теория расписаний ==
* Тут неплохо было бы разбить на разделы все задачи, добавить примеров, оформить всё последовательно
# ''fixed'' [[Классификация задач]] (''1'')
## Тех в нотацию Грэхема
## Оформить правильно англоязычные термины
## Добавить источники информации, см. также, категории
# '''!!!''' [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]] (''8'')
## Начать с простейших примеров, когда только d_i, потом усложнять
## Отформатировать псевдокод
## Оформить правильно источники информации
## Добавить категории
# [[Методы решения задач теории расписаний]] (''3'')
## Как-нибудь структурировать конспект, а то много всего рандомного написано
## Ссылки оформить как интервики
## Оставить только совсем мелки доказательства, на наборы задач кинуть ссылки или создать новые конспекты
## Добавить источники информации
# ''fixed'' [[Правило Лаулера]] (''3'')
## Задачу в шаблон
## Отформатировать псевдокод
## Заменить дефисы на тире
## Заменить знаки неравенств
## Добавить "информации" в источники 
# [[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>]] (''4'')
## Задачу в шаблон
## Рассмотреть более простые варианты задачи для начала
## Отформатировать псевдокод
## Добавить источники
# [[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'')
## Более простой аналог задачи рассмотреть (только с U_i)
## Отформатировать псевдокод
## Заменить литературу на источники информации
# '''взяли''' [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] (''7'')
## Задачу в шаблон
## Отформатировать псевдокоды
## Более подробное и понятное описание, чтобы было понятно, как закодить
## Увеличить дроби
# ''взяли'' [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]] (''1'')
## Задачу в шаблон
## Заменить знаки неравенств
## Добавить источники информации
# [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]] (''0.5'')
## Увеличить дроби
## Оформить правильно источники информации
## Добавить категории
## Заменить знаки неравенств
# [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]] (''0.5'')
## Заменить знаки неравенств
## Добавить категории
# [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]] (''2'')
## Задачу в шаблон
## Отформатировать псевдокоды
## Заменить знаки неравенств
## Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней
# [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]] (''0.5'')
## Задачу в шаблон
## Заменить знаки неравенств
## Добавить информации в источники
# [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]] (''1'')
## Там получаются очень большие списки, если рассматривать их все для каждого станка, нужно написать, как лучше всего организовать очередь приоритетов
## Увеличить дроби
## Задачу в шаблон
## Оформить правильно Источники инфорации
# '''!!!''' [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]] (''5'')
## Допилить
## Доказать корректность
## Задачу в шаблон
## Отформатировать псевдокод
## Добавить категории
# [[Flow shop]] (''2'')
## Таблички оформить как викитаблички, а не как код
## Битое примечание
## Отформатировать псевдокоды
## Добавить категории
# [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] (''3'')
## Задачу в шаблон
## Заменить знаки неравенств
## Отформатировать псевдокод
## Красивые картинки
# ''взяли'' [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]] (''1'')
## Ранее было доказано, что эта задача сводится к 1|p_ij=1|sumwiUi, поэтому надо просто выпилить отсюда значимую часть и перенести примером в Flow shop
# [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]] (''1'')
## Заменить знаки неравенств
## Категории
## задачу в шаблон
## Отформатировать псевдокод
# [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]] (''0.5'')
## Категории
## Шаблон
## Знаки неравенств
# [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]] (''1'')
## Задачу в шаблон
## Знаки неравенств
## Источники информации
## Дефисы на тире
# '''!!!''' [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]] (10)
## Доделать