Изменения

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

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

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

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

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

# ''взяли'' [[Алгоритм БойераАвтомат Кнута-Мура]] (''4'')## Добавить '''понятную''' табличку примера с пояснением каждого шага## and в Tex заменить на знак конъюнкции## Добавить пояснений в формальные определения## Ссылки заменить на источники информации# [[Алгоритм Колусси]]# [[Алгоритм ShiftМорриса-AndПратта]]# ''взяли'' [[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'')

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

# ''fixed'' [[Суффиксный массив]] (''1'')## Англоязычные термины## Пример оформить красивей и понятней## Добавить применений## Оформить правильно Источники информации и см. также, покидать всяких ссылок в источники# ''взяли'' [[Построение суффиксного массива с помощью стандартных методов сортировки]] (''2'')## Отформатировать псевдокоды ## Оформить правильно источники информации## Зачем второй сложный алгоритм за O(n log n), если уже есть алгоритм с хешами?## Добавить См. также на алгоритм построения массива с помощью цифровой сортировки# '''взяли''' [[Алгоритм цифровой сортировки суффиксов циклической строки]] (# ''7fixed'')## Добавить ссылку на цифровую сортировку куда-нибудь в конспект## Заменить картинку таблицы на теховскую таблицу## Написать нормальный псевдокод: что за ужасный rotate? Можно сразу писать так, чтобы с индексами было удобно работать## Возможно придётся чуточку переписать описание алгоритма## Оформить правильно источники информации## Добавить см. также на другие алгоритмы построения# [[Алгоритм Касаи и др.]] (''3'')

# '''взяли''' [[Алгоритм Карккайнена-Сандерса]] (''5'')## Заменить знаки неравенств## Отформатировать псевдокоды## Отформатировать обозначения в шагах## Оформить примеры таблицами## Увеличить дроби## Добавить См. также## Оформить правильно примечания и Источники информации# '''взялиfixed''' [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]] (''7'')

# ''взяли'' [[Сведение задачи LCA к задаче RMQ]] (''3'')## Оформить правильно англоязычные термины## Убрать пункт "Постановка задачи", добавить Шаблон:Задача## Имена функций взять в \mathrm, имена массивов взять в \mathtt## Нарисовать векторную нормальную картинку## Заменить знаки неравенств## Оформить правильно источники информации# ''взяли'' [[Сведение задачи RMQ к задаче LCA]] (''2'')## Задачу взять в Шаблон## Кинуть интервики на дерево по неявному## Чуть подробней написать алгоритм, более плавное введение сделать## Пункт "Доказательство" тоже немного не к месту выглядит, заменить его на что-нибудь получше## В сложности тоже сказать больше подробностей# ''взяли'' [[Метод двоичного подъема]] (''0.5'')## Англоязычные термины## Интервики на динамическое программирование## Заменить знаки неравенств## min заменить на \min## Добавить См. также[[Решение RMQ с помощью разреженной таблицы]]# ''взялиfixed'' [[Решение RMQ с помощью разреженной таблицыАлгоритм Фарака-Колтона и Бендера]] (''12'')## Что значит online static?## Постановку задачи в Шаблон## Заменить знаки неравенств## fl лучше как функцию оформитьОтформатировать псевдокод

## Заменить вертикальную черту на \mid## Многоточния заменить на \ldots## Заменить источники на Источники информации## ''(+1 в карму за перерисовку картинки на красивую)''# '''!!!''' [[Алгоритм ФаракаHeavy-Колтона и Бендераlight декомпозиция]] (''86'')## Задачу взять в Шаблон"решается с помощью heavy-light декомпозиции" — может быть решена## "Пусть A, B - ко" — дефисы нужно заменить на тире## Переменные В начале у тебя идут вершины a,b и A,B, а потом u,v и константы a,b. Надо сделать единообразно, чтобы начало конспекта и его конец согласовывались. Например, сделать корни путей большими буквами — норм. Тогда можно либо a,b и A,B, либо u,v и U,V.## "В данном случае корень одного из путей является вершиной другого." — а почему пути не могут пересекаться крест-на-крест?## Слишком много повтором «Пусть» в Texдоказательстве леммы.## "Но LCA должен принадлежать двум путям. Но" — дублирование «Но»## Добавить оптимизацию по памяти"Предположим, что LCA не равны" — криво написано, нужно формально исходя из формулировки## Написать псевдокодНу и вообще, как будто слов пожадничал на лемму и кое-как написал## RMQ взять "Построим декомпозицию." — декомпозицию чего и для чего? Очень плохо оставлять открытый контекст, особенно в Texначале пункта. Лучше чуть более подробно описать, чтобы было понятно## Увеличить картинку"Корень пути, на котором лежит текущая вершина.Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева." — вообще непонятно, как связано то, что мы хотим сохранить с тем, что написано потом. Нет предложения-связки## Увеличить дроби"Пусть требуется" — опять пуст## Источники заменить "Пусть на источники информацииданной итерации" — как будто других слов нет## "LCA будет та" — это не по-русски## Возьми LCA в тексте везде в \mathrm## "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?# ''fixed'' [[Алгоритм Шибера-Вишкина]] (''23'')

# '''fixed''' [[Link-Cut Tree]](5)## Отформатировать псевдокоды## Написать более понятное введение и пояснить подробней остальные смутные операции## Список оформлен некрасиво в начале## Категории## Оформить правильно См. также и Источники информации

# [[Примеры матроидов]] (''1'')## Красивые списки в доказательствах## Добавить категорию## Заменить | на \mid

# '''!!!''' [[Теорема о базах]] (''5'')## Англоязычные термины## Добавить ссылок, см. также## Поправить tex## Обернуть семейство в \mathcal## Добавить сильную теорему баз (base exchange) {{---}} см. Chandra Chekuri# [[Аксиоматизация матроида базами]] (''0.5'')## Оформить правильно источники информации## Больше ссылок## Добавить категорию

# ''взяли'' [[Ранговая функция, полумодулярность]] (''1'')## tex## Ссылки## Англоязычные термины## Заменить знаки неравенств## Добавить источники информации## Добавить категорию

# '''!!!''' [[Покрытия, закрытые множества]] (''8'')## Доказать две теоремы

<li value="14"> '''!!!''' [[Пересечение матроидов, определение, примеры]] (''7'') </li># Ссылки# tex# Ещё примеров# Больше общих описаний# Пример, когда пересечение матроидов не является матроидом# Доказательство матроидности уже приведённых примеров# Добавить категорию<li> '''!!!взяли''' [[Лемма о паросочетании в графе замен]] (''5'') </li>

<li> ''fixed'' [[Лемма о единственном паросочетании в графе замен]] (''0.35'') </li>

# Категория# Оформить красиво док-во по индукции<li> '''!!!'fixed'' [[Граф замен для двух матроидов]] (''53'') </li>

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

<li value="21"> '''!!!fixed''' [[Объединение матроидов, проверка множества на независимость]] (''8'') </li>

# Помёрджить со следующим конспектом<li> ''взяли'' [[Объединение матроидов, доказательство того, что объединение является матроидом]] (1) </li>

# Отформатировать по правилам# Помёрджить с предыдущим конспектом<li> '''!!!взяли''' [[Алгоритм построения базы в объединении матроидов]] (''7'') </li>

* Тут неплохо было бы разбить на разделы все задачи, добавить примеров, оформить всё последовательно=== Общая теория ===# [[Классификация задач]] (''1'')## Тех в нотацию Грэхема## Оформить правильно англоязычные термины## Добавить источники информации, см. также, категории# '''!!!''fixed' [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]] (''8'')## Начать с простейших примеров, когда только d_i, потом усложнять## Отформатировать псевдокод## Оформить правильно источники информации## Добавить категории# [[Методы решения задач теории расписаний]] (''35'')

## Оставить только совсем мелки мелкие доказательства, на наборы задач кинуть ссылки или создать новые конспекты

## Разнести на отдельные конспекты с доказательством, если такой задачи нет, или оформить как основную статью с ссылкой на оригинал, приведя обзорное решение# [[Правило Лаулера]] ( === Задачи с одним станком ===<ol><li value=4> ''3взяли'')## Задачу в шаблон## Отформатировать псевдокод## Заменить дефисы на тире## Заменить знаки неравенств## Добавить "информации" в источники # [[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> ''1fixed'')## Задачу в шаблон## Заменить знаки неравенств## Добавить источники информации# [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]] (''0.52'')</li>## Увеличить дроби## Оформить правильно источники информации## Добавить категории## Заменить знаки неравенств# Взять задачу в шаблон, пункт описание не нужен# Добавить нотацию задачи в начало<li>'''fixed''' [[PpmtnriLmaxR2Cmax|<tex>P R2 \mid pmtn, r_i \mid L_C_{max}</tex>]] (''0.5'')</li>#Допилить# Заменить знаки неравенствДоказать корректность# Задачу в шаблон#Отформатировать псевдокод# Добавить категории# <li> ''fixed'' [[QpmtnCmaxF2Cmax|<tex>Q F2 \mid pmtn \mid C_{max}</tex>]] (''23'')</li>## Задачу в шаблон## Отформатировать псевдокоды## Заменить знаки неравенств#Отформатировать псевдокод# Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятнейКрасивые картинки# <li> ''fixed'' [[QpmtnriLmaxO2Cmax|<tex>Q O2 \mid pmtn, r_{i} \mid L_C_{max}</tex>]] (''0.51'')</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>]] (''5''10)</li>## ДопилитьДоделать## Доказать корректность</ol>## Задачу в шаблон## Отформатировать псевдокод=== Задачи для произвольного числа станков ===## Добавить категории<ol># <li value=18> ''fixed'' [[Flow shop]] (''2'')</li>## Таблички оформить как викитаблички, а не как код## Битое примечание## Отформатировать псевдокоды## Добавить категории# [[F2Cmax|<tex>F2 \mid \mid C_{max}</texli>]] (''3'')## Задачу в шаблон## Заменить знаки неравенств## Отформатировать псевдокод## Красивые картинки# [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]] (''2'')</li>## Ранее было доказано, что эта задача сводится к 1|p_ij=1|sumwiUi, поэтому надо просто выпилить отсюда значимую часть и перенести примером в Flow shop# <li> [[O2CmaxPpmtnriLmax|<tex>O2 P \mid pmtn, r_i \mid C_L_{max}</tex>]] (</li><li> ''1fixed'')## Заменить знаки неравенств## Категории## задачу в шаблон## Отформатировать псевдокод# [[Opi1sumuQpmtnCmax|<tex>O Q \mid pmtn \mid p_C_{ijmax} = 1 \mid \sum U_i</tex>]] (''0.53'')</li>## КатегорииЗадачу в шаблон## ШаблонОтформатировать псевдокоды## Знаки Заменить знаки неравенств# Кажется, тут не совсем правильно написано решение; вчитаться, пофиксить все баги и написать понятней<li> ''fixed'' [[J2ni2CmaxQpmtnriLmax|<tex>J2 Q \mid n_pmtn, r_{i} \le 2 \mid C_L_{max}</tex>]] (''10.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>]] (10''0.5'')</li>#Категории# Шаблон# ДоделатьЗнаки неравенств</ol>