3622
правки
Изменения
м
# Помёрджить со следующим конспектом<li> ''взяли'' [[Объединение матроидов, доказательство того, что объединение является матроидом]] (0.51) </li>
Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 4ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))
# [[Основные определения, связанные со строками]]
# [[Период и бордер, их связь]]
# '''!!!'fixed'' [[Слово Фибоначчи]] (''72'')
## Убрать лишние пункты
## Англоязычные термины
## Написать, почему строка Фибоначчи будет (2, 4) исключением
## Можно написать про исключения отдельный конспект даже, если там много информации наберётся
# '''!!!fixed''' [[Слово Туэ-Морса]] (''75'')## Интересно, как можно задать строку Туэ-Морса иначе (там что-то говорится про клеточные автоматы). Вдруг получтся что-то интересное? В любом случае сначала куратору надо написать.
## Англоязычные термины
## Правильно оформить См. также и Источники информации
## Доказать разные прикольные факты какой-нибудь нетривиальный факт про строку Туэ-Морса (''+3'' за факт)
# [[Декомпозиция Линдона]]
# [[Алгоритм Ландау-Шмидта]]
# '''!!!взяли''' [[Алгоритм Крочемора]] (''5'')
## Пояснить наивную реализацию в начале
## Доказать первую лемму
# [[Автомат Кнута-Морриса-Пратта]]
# [[Z-функция]]
# '''!!!''' [[Автомат для поиска образца в тексте]] (''10'')## Дописать до нормальной статьи о суффиксном автомате (если это оно и есть), см. список предлагаемых тем# '''взялиfixed''' [[Бор]] (''8'')
## Больше ссылок
## Кое-где надо подправить tex
## Добавить см. также, оформить правильно источники информации
## Категория
# '''!!!fixed''' [[Алгоритм Ахо-Корасик]] (''8'')
## Задачу в шаблон
## Написать асимптотику нормально
## Отформатировать раздел с масками
## Категория
# ''fixed'' [[Алгоритм Бойера-Мура]] (''4'')
## Добавить '''понятную''' табличку примера с пояснением каждого шага
## and в Tex заменить на знак конъюнкции
## Ссылки заменить на источники информации
## Категория
## Отформатировать псевдокод
# [[Алгоритм Колусси]]
# [[Алгоритм Shift-And]]
# ''fixed'' [[Двусторонний алгоритм]] (0.5)
## Список с большой буквы начать
## Неправильный порядок разделов в конце конспекта
== 3. Суффиксное дерево ==
# [[Суффиксный бор]]
# ''взялиfixed'' [[Сжатое суффиксное дерево]] (''2'')
## Немного пояснить про эквивалентность определений сжатого суффиксного бора и сжатого дерева, а то путаница какая-то сейчас
## Англоязычные термины
# [[Алгоритм Укконена]]
# [[Алгоритм МакКрейта]]
# ''взялиfixed'' [[Алгоритм Фарача]] (''2'')
## В конспекте полно опечаток - исправить
## Интервики на поразрядную сортировку
# [[Построение суффиксного массива с помощью стандартных методов сортировки]]
# [[Алгоритм цифровой сортировки суффиксов циклической строки]]
# ''fixed'' [[Алгоритм Касаи и др.]] (''3'')
## Кажется, что LCP вычисляет не длину общих префиксов циклических сдвигов; или надо что-то ещё добавить
## "будем использовать промежуточный массив " — лучше написать "вспомогательный"
## Отформатировать псевдокод
## Увеличить дроби
# '''!!!''' [[Heavy-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
## "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?
# ''fixed'' [[Алгоритм Шибера-Вишкина]] (''3'')
## Англоязычные термины
# Заменить xor на треугольник
# Добавить категорию
<li> ''fixed'' [[Лемма о единственном паросочетании в графе замен]] (''0.5'') </li>
# Оформить правильно источники информации
# Добавить категорию
=== Объединение матроидов ===
<ol>
<li value="21"> '''!!!fixed''' [[Объединение матроидов, проверка множества на независимость]] (''8'') </li>
# Добавить формальное определение
# Структурировать конспект, а не оставлять просто набором тезисов
# Добавить содержательный примеры
# Заменить тире на [[Шаблон:---]]
# Добавить категории
# Добавить интервики
# Отформатировать по правилам# Помёрджить с предыдущим конспектом<li> '''!!!взяли''' [[Алгоритм построения базы в объединении матроидов]] (''7'') </li>
# В определение само определение выделить жирным
# Тире заменить на [[Шаблон:---]]
</ol>
== 7. Теория расписаний (проверяется) ==* Тут неплохо было бы разбить на разделы все задачи, добавить примеров, оформить всё последовательно=== Общая теория ===# ''fixed'' [[Классификация задач]] (''1'')## Тех в нотацию Грэхема## Оформить правильно англоязычные термины## Добавить источники информации, см. также, категории# '''!!!fixed''' [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]] (''8'')## Начать с простейших примеров, когда только d_i, потом усложнять## Отформатировать псевдокод## Оформить правильно источники информации## Добавить категории# [[Методы решения задач теории расписаний]] (''35'')
## Как-нибудь структурировать конспект, а то много всего рандомного написано
## Ссылки оформить как интервики
## Оставить только совсем мелки мелкие доказательства, на наборы задач кинуть ссылки или создать новые конспекты
## Добавить источники информации
# ''fixed'' # Разнести на отдельные конспекты с доказательством, если такой задачи нет, или оформить как основную статью с ссылкой на оригинал, приведя обзорное решение# [[Правило Лаулера]] ( === Задачи с одним станком ===<ol><li value=4> ''3взяли'')## Задачу в шаблон## Отформатировать псевдокод## Заменить дефисы на тире## Заменить знаки неравенств## Добавить "информации" в источники # [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]] (''1.5'')</li>#Переименовать конспект и оставить перенаправление# Задачу в шаблон## Отформатировать псевдокод## Добавить категории## Заменить литературу на источники информации# '''fixed''' <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>]] (''48'')</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>## Задачу в шаблон## Отформатировать псевдокоды## Более подробное и понятное описание, чтобы было понятно, как закодить## Увеличить дроби# ''fixed'' <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'')## Задачу в шаблон## Заменить знаки неравенств## Отформатировать псевдокод## Красивые картинки# ''fixed'' [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]] (''1'')</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>
