Изменения

# '''!!!'fixed'' [[Слово Фибоначчи]] (''72'')

# '''!!!fixed''' [[Слово Туэ-Морса]] (''75'')## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.

## Доказать разные прикольные факты какой-нибудь нетривиальный факт про строку Туэ-Морса (''+3'' за факт)

# '''!!!взяли''' [[Алгоритм Крочемора]] (''5'')

: 0. [[Поиск подстроки в строке]] (''1''):# Взять обозначения перед псевдокодом в \mathtt:# Придумать более удачный способ нумерации списка=== Точный поиск ===# [[Наивный алгоритм поиска подстроки в строке]] (''0.5'')## Задачу взять в [[Шаблон:Задача]]## Заменить литературу на источники информации## Сделать подпункты уровнем меньше## Убрать среднее O во времени работы# '''!!!''' [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]] (''5'')## Добавить подробное объяснение примера строки, на которой плохо работает такое хеширование## Отформатировать псевдокод## Добавить См. также## Оформить правильно Источники информации## Взять хэш в \mathrm# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]] (''0.5'')## Задачу взять в шаблон## Переменные взять в Tex## Отформатировать псевдокод## Оформить правильно См. также и Источники информации# [[Префикс-функция]] (''1'')## Какой-то нехороший человек вычел 1 из индексации префикс-функции, хотя в начале сказано, что строки нумеруются с 1. Исправить надо.

# [[Алгоритм БойераАвтомат Кнута-Мура]] (''4'')## Добавить '''понятную''' табличку примера с пояснением каждого шага## and в Tex заменить на знак конъюнкции## Добавить пояснений в формальные определения## Ссылки заменить на источники информации# [[Алгоритм КолуссиМорриса-Пратта]]# [[Z-функция]] (''1'')## Пункт определение не нужен, заменить на шаблон и дать формальное определение## Оформить красиво доказательство эффективного алгоритма## Добавить См. также## Длинные обозначения после псевдокода взять в \mathtt # '''!!!''' [[Автомат для поиска образца в тексте]] (''10'')## Дописать до нормальной статьи о суффиксном автомате (если это оно и есть), см. список предлагаемых тем# '''!!!fixed''' [[Бор]] (''8'')

## Категория# '''!!!fixed''' [[Алгоритм Ахо-Корасик]] (''8'')## Задачу в шаблон

# # Категория# ''fixed'' [[Алгоритм Бойера-Мура]] (''4'')## Добавить '''понятную''' табличку примера с пояснением каждого шага## and в Tex заменить на знак конъюнкции## Добавить пояснений в формальные определения## Ссылки заменить на источники информации## Категория## Отформатировать псевдокод# [[Алгоритм Колусси]]# [[Алгоритм Shift-And]]# ''fixed'' [[Двусторонний алгоритм]] (0.5)## Список с большой буквы начать## Неправильный порядок разделов в конце конспекта## Стрелки в псевдокоде заменить на = === Нечёткий поиск ===<ol><li value=15> [[Алгоритм Ландау-Вишкина (k несовпадений)]]</li><li> [[Алгоритм Ландау-Вишкина (k различий)]] </li></ol>

# [[Суффиксный бор]] (# ''2fixed'')## Изменить знаки неравенства## Отформатировать псевдокод## Оформить правильно источники инфрмации## Добавить пример строки, на которой будет O(n^2) памяти достигаться## Заменить многоточия на \dots # [[Сжатое суффиксное дерево]] (''2'')

# '''!!!''' [[Алгоритм Укконена]] (''8'') ''напишите уже кто-нибудь (желательно адекватный человек, а то третий год непонятный конспект в разработке)''## Псевдокод оформить как нормальный псевдокод## Убрать подпункты леммы, их название занести в Шаблон## Англоязычные термины## Подстроку обозначать как <tex> s[i..j] </tex>## В начале пункта Алгоритм форматирование не ок## Изменить знаки неравенств## Оформить правильно Источники информации## См. также переместить перед Источниками информации## Добавить картинок по ходу дела (на емаксе есть ссылка на pdf, откуда можно взять картинки, только описание с той пдфки не копипастить)## Пояснить, чем хорош этот алгоритм построения суффиксного дерева, но почему его в реальной жизни мало используют# [[Алгоритм МакКрейта]] (# ''0.5fixed'')## Англоязычные термины## Ссылки оформить примечаниями# [[Алгоритм Фарача]] (''2'')

# [[Суффиксный массив]] (''1'')## Англоязычные термины## Пример оформить красивей и понятней## Добавить применений## Оформить правильно Источники информации и см. также, покидать всяких ссылок в источники# [[Построение суффиксного массива с помощью стандартных методов сортировки]] (''2'')## Отформатировать псевдокоды ## Оформить правильно источники информации## Зачем второй сложный алгоритм за O(n log n), если уже есть алгоритм с хешами?## Добавить См. также на алгоритм построения массива с помощью цифровой сортировки# '''!!!''' [[Алгоритм цифровой сортировки суффиксов циклической строки]] (# ''7fixed'')## Добавить ссылку на цифровую сортировку куда-нибудь в конспект## Заменить картинку таблицы на теховскую таблицу## Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать## Возможно придётся чуточку переписать описание алгоритма## Оформить правильно источники информации## Добавить см. также на другие алгоритмы построения# [[Алгоритм Касаи и др.]] (''0.53'')## Оформить правильно англоязычные терминыКажется, что LCP вычисляет не длину общих префиксов циклических сдвигов; или надо что-то ещё добавить## Двойное неравенство "будем использовать промежуточный массив " — лучше написать под минимумом"вспомогательный"## Добавить См. такжефразу и картинку про то, что массив LCP удобно представлять в виде ступенек/столбиков разной высоты## Кстати, не очень понятно, зачем нужен Height, если по сути он выполняет роль LCP## Длинные названия взять Надо сказать, в \mathrmкаком порядке мы фиксируем соседа: lcp[i] содержит префикс i и i-1 или i и i+1## Думаю, что к утверждению 2 нужные пояснения, а то происходят нетривиальные переходы из словесной формулировки в утверждение; ещё надо добавить, что не изменится относительный порядок именно этих двух суффиксов, а не всех# '''!!!''' [[Алгоритм Карккайнена-Сандерса]] (''5'')## Заменить знаки неравенств## Отформатировать псевдокоды## Отформатировать обозначения в шагах## Оформить примеры таблицами## Увеличить дроби## Добавить См. также## Оформить правильно примечания и Источники информации# '''!!!fixed''' [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]] (''7'')

== 5. Задача о наименьшем общем предке (проверяется)==# ''fixed'' [[Метод двоичного подъема]]## Поправить ужасный псевдокод

# '''!!!'fixed'' [[Алгоритм Фарака-Колтона и Бендера]] (решение +/''2'')## Отформатировать псевдокод## Увеличить дроби# '''!!!''' [[Heavy-1 RMQ light декомпозиция]] (''6'')## "решается с помощью метода четырех русских)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## Добавить сведение задачи RMQ к задаче +/-1 RMQ"Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?# ''fixed'' [[Алгоритм Шибера-Вишкина]](''3'')## Англоязычные термины## Интервики на LCA## Чё ещё за подготовка?## Почему-то в определении находится не определение, надо бы нормально переписать## Лучше дать нормальное название обхода: pre-order, in-order или post-, если что-то из этого оно и есть## Увеличить дроби## Добавить См. также## Добавить Категории## Правильно оформить источники информации# [[Сведение задачи RMQ к задаче Алгоритм Тарьяна поиска LCAза O(1) в оффлайн]]# '''fixed''' [[Link-Cut Tree]](5)## Отформатировать псевдокоды## Написать более понятное введение и пояснить подробней остальные смутные операции## Список оформлен некрасиво в начале## Категории## Оформить правильно См. также и Источники информации

== 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>#Оформить правильно источники информации# Константы в texДобавить категорию## Убрать сокращенияКатегория## Добавить интервикиОформить красиво док-во по индукции# <li> '''!!!'fixed'' [[Граф замен для двух матроидов]](''3'') </li>## Нарисовать нормальную картинку## Добавить информацию про граф замен для одного матроида## Исправить ссылки в соответствующих конспектах## Создать новый конспект, в него сделать перенаправление из текущего# Оформиь правильно источники информации# Добавить категорию<li> [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]</li>## Картинки плывут {{---}} разместить нормально## Заменить обозначение графа замен на принятое## Сделать интервики на другие конспекты (паросочетание, кратчайший путь, граф замен)# '''!!!''' <li> [[Алгоритм построения базы в пересечении матроидов]]</li>## Матроиды записать через угловые скобки## Заменить тире на шаблон## Добавить категории## Отформатировать псевдокод## Мелкие правки в tex## Перерисовать картинку## Помёрджить со следующим конспектом# [[Теорема Эдмондса-Лоулера]]## Добавить категории## Заменить знак симметрической разности, а так же другие мелкие правки в tex## Картинки кривовато расположены {{---}} поправить## Исправить ошибки в док-ве</ol>

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

== 97. Теория расписаний (проверяется)===== Общая теория ===

# '''fixed''' [[Методы решения задач теории расписаний]](''5'')## Как-нибудь структурировать конспект, а то много всего рандомного написано## Ссылки оформить как интервики## Оставить только совсем мелкие доказательства, на наборы задач кинуть ссылки или создать новые конспекты## Добавить источники информации## Разнести на отдельные конспекты с доказательством, если такой задачи нет, или оформить как основную статью с ссылкой на оригинал, приведя обзорное решение

# [[Flow shop]]# === Задачи с одним станком ===<ol><li value=4> ''взяли'' [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]](''1.5'') </li># Переименовать конспект и оставить перенаправление# Задачу в шаблон# Отформатировать псевдокод# Добавить категории# Заменить литературу на источники информации<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, потом усложнять# Отформатировать псевдокод# Оформить правильно источники информации# Добавить категории<li> [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]</li><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)# Отформатировать псевдокод# Заменить литературу на источники информации<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''' [[PpmtnriLmaxR2Cmax|<tex>P R2 \mid pmtn, r_i \mid L_C_{max}</tex>]](''5'') </li># Допилить# Доказать корректность# Задачу в шаблон# Отформатировать псевдокод# Добавить категории<li> ''fixed'' [[QpmtnCmaxF2Cmax|<tex>Q F2 \mid pmtn \mid C_{max}</tex>]](''3'') </li># Задачу в шаблон# Заменить знаки неравенств# Отформатировать псевдокод# Красивые картинки<li> ''fixed'' [[QpmtnriLmaxO2Cmax|<tex>Q O2 \mid pmtn, r_{i} \mid L_C_{max}</tex>]](''1'') </li># Заменить знаки неравенств# Категории# задачу в шаблон# Отформатировать псевдокод<li> ''fixed'' [[QSumCiJ2ni2Cmax|<tex>QJ2 \midn_{i} \le 2 \mid\sumC_{C_imax}</tex>]] (''1'') </li># Задачу в шаблон# Знаки неравенств# Источники информации# Дефисы на тире# Исправить теховское обозначение задачи<li> '''fixed''' [[R2CmaxJ2pij1Lmax|<tex>R2 J2\mid p_{ij} = 1\mid C_L_{max}</tex>]](10) </li># [[F2Cmax|Доделать</ol> === Задачи для произвольного числа станков ===<texol>F2 \mid \mid C_{max}</texli value=18>''fixed'' [[Flow shop]](''2'') </li># Таблички оформить как викитаблички, а не как код# Битое примечание# Отформатировать псевдокоды# Добавить категории<li> [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]</li># <li> [[O2CmaxPpmtnriLmax|<tex>O2 P \mid pmtn, r_i \mid C_L_{max}</tex>]]</li># <li> ''fixed'' [[Opi1sumuQpmtnCmax|<tex>O Q \mid pmtn \mid p_C_{ijmax} = 1 \mid \sum U_i</tex>]](''3'')</li># Задачу в шаблон# Отформатировать псевдокоды# Заменить знаки неравенств# Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней<li> ''fixed'' [[J2ni2CmaxQpmtnriLmax|<tex>J2 Q \mid n_pmtn, r_{i} \le 2 \mid C_L_{max}</tex>]](''0.5'') </li># Задачу в шаблон# Заменить знаки неравенств# Добавить информации в источники<li> [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]] </li><li> ''fixed'' [[J2pij1LmaxOpi1sumu| <tex>J2O \mid p_{ij} = 1\mid L_{max}\sum U_i</tex>]](''0.5'') </li># Категории# Шаблон# Знаки неравенств</ol>