Изменения

<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>Теорема{{|statement= Задачао проверке на пустоту пересечения двух КС-грамматик неразрешима.|definitionproof=Дано Пусть <tex>m</tex> одинаковых станковA = \{ (G_1, которые работают параллельно, и <tex>nG_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>d_i\overline{A}</tex> {{---}} время, до которого она должна быть выполненатаким образом показав, что дополнение проблемы неразрешимо. Необходимо минимизировать суммарную Так как рекурсивные языки [[Классификация_задач#Критерий оптимизацииЗамкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|медлительностьзамкнуты относительно дополнения]].}} == Описание алгоритма ===== Идея ===Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы. {{Лемма|statement=Пусть есть работы Для любого экземпляра ПСП <tex>1 \ldots n</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Тогда существует оптимальное расписание(x_1, в котором времена завершения работ идут в том же порядкеx_2, то есть <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.|proof=Рассмотрим две работы <tex>i.., x_n)</tex> и <tex>j</tex> из какого-либо оптимального расписания такие(y_1, y_2, что <tex>C_i > C_j</tex> и <tex>d_i < d_j</tex>. Поменяем эти работы в расписании местами.., то есть <tex>C'_i = C_jy_n)</tex> и над алфавитом <tex>C'_j = C_i\Sigma</tex>. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как можно подобрать символ <tex>d_i < d_j\# \notin \Sigma</tex>, значит по-прежнему . Для каждого экземпляра построим грамматики:* <tex>T_i = 0G_1 : S \rightarrow aSa \mid a\#a</tex> и для всех <tex>T_j = 0a \in \Sigma</tex>, то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа Тогда <tex>jL(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex> успевала выполниться, а где обозначение <tex>iw^R</tex> {{---}} нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было разворот <tex>T_i + T_j = C_i - d_iw</tex>, так как .* <tex>T_j = 0G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex>. После того, как мы поменяли работы местами, для всех <tex>T_i + T_j i = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)1, 2, \dots n</tex>. Но так как работа Тогда <tex>j</tex> успевает выполниться до дедлайнаL(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, то <tex>C_j - d_j m \geqslant 1 \leqslant 0}</tex>.}}

Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>, и наоборот, если он не имеет решения, то <tex>L(G_2)</tex> не содержит строк такого вида, соответственно <tex>L(G_1) \cap L(G_2) === Псевдокод ===\varnothing</tex>.

== См. также ==* [[O2Cmax|Аналогично можно заметить, что пересечение <tex>O2 L(G_1) \mid cap L(G_2) \mid C_{max}</tex>]]* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid ne \sum U_ivarnothing </tex>]]* [[Opij1di|<tex> O \mid p_{i, j} = 1тогда и только тогда, d_i \mid - когда </tex>]]* [[Opij1sumwu|<tex> O \mid p_{i, j} = 1 \mid - L(G_1)\sum w_{i} U_{i}#L(G_2)^R</tex>]]== Источники информации ==* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} ссодержит палиндром. 171-174 ISBN 978-3-540-69515-8

[[КатегорияТаким образом, мы имеем: Алгоритмы и структуры данных]][[Категория{{Утверждение|statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы: Теория расписаний]]# Содержит ли <tex>L</tex> тандемный повтор.# Содержит ли <tex>L</tex> палиндром.}}