Обсуждение участницы:Анна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
 
(не показано 49 промежуточных версий 2 участников)
Строка 1: Строка 1:
= <tex> P \mid p_i=1 \mid \sum w_i U_i</tex> =
+
{{Теорема
{{Задача
+
|statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
|definition=
+
|proof=  
Дано <tex>m</tex> одинаковых станков, на которых нужно выполнить <tex>n</tex> работ. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} ожидается, что до этого времени она будет закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
+
Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.
}}
+
 
== Описание алгоритма ==
+
Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики:
Оптимальное расписание для этой задачи будем задавать множеством работ <tex>S</tex>, которые будут выполнены в начале, как после будет показано, именно за эти работы штраф начислен не будет. Работы, которые не войдут в <tex>S</tex>, то есть завершатся с опозданием, могут быть выполнены в конце в любом порядке.<br>
+
* <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>w^R</tex> {{---}} разворот <tex>w</tex>.
Чтобы построить множество <tex>S</tex>, будем добавлять работы в порядке неуменьшения их времен окончания, и как только некоторая работа <tex>j</tex> опаздывает, удалим из <tex>S</tex> работу с минимальным значением <tex>w_i</tex> и поставим <tex>j</tex> на ее место.<br>
+
* <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> для всех <tex>i = 1, 2, \dots n</tex>. Тогда <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 \}, m \geqslant 1 \}</tex>.
Пусть есть работы <tex>1 \cdots n</tex> с временами окончания <tex>d_1 \leq d_2 \leq \cdots \leq d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Тогда следующий алгоритм вычислит оптимальное множество <tex>S</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>.
  
  <tex>S \leftarrow  \varnothing</tex>
+
Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
  '''for''' <tex>j = 1</tex> '''to''' <tex>n</tex>:
+
}}
      '''if''' <tex>j</tex> опаздывает, и все более ранние простои заполнены:
+
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.
        найти <tex>i: w[i] = \min\limits_{k \in S}(w[k])</tex>
+
 
        '''if''' <tex>w[i] < w[j]</tex>:
+
По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].
            заменить <tex>i</tex> на <tex>j</tex> в <tex>S</tex>
+
 
      '''else''':
+
Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром.  
        добавить <tex>i</tex> в <tex>S</tex> и поставить <tex>i</tex> на место самого раннего простоя
+
 
Таким образом, работы, не попавшие в <tex>S</tex>, будут иметь минимальное значение <tex>w_i</tex>.
+
Таким образом, мы имеем:
== Доказательство корректности ==
+
{{Утверждение
{{Теорема
+
|statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы:
|statement=
+
# Содержит ли <tex>L</tex> тандемный повтор.
Вышеописанный алгоритм корректен и строит оптимальное множество работ <tex>S</tex>.
+
# Содержит ли <tex>L</tex> палиндром.
|proof=
 
Пусть <tex>S</tex> {{---}} множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа <tex>j</tex> заменила работу <tex>i</tex>, которая успевала выполниться до истечения <tex>d_i</tex>, то <tex>j</tex> так же успеет выполниться в срок, потому что <tex>d_i \leq d_j</tex>.<br>
 
Пусть <tex>S^*</tex> {{---}} множество работ без штрафов в оптимальном расписании.<br>
 
Определим работы <tex>l</tex> и <tex>k</tex> следующим образом:
 
* <tex>l</tex> {{---}} первая работа в <tex>S</tex>: <tex>l \notin S^*</tex>
 
* <tex>k</tex> {{---}} первая работа в <tex>S^*</tex>: <tex>k \notin S</tex>
 
Покажем, что в <tex>S^*</tex> работа <tex>k</tex> может быть заменена работой <tex>l</tex> без увеличения значения целевой функции. Рассмотрим два случая:<br>
 
1. Пусть <tex>l < k</tex>.<br>
 
То, что <tex>k</tex> не принадлежит множеству <tex>S</tex>, значит, что либо на некотором шаге появилась опаздывающая работа <tex>j</tex>, которая заменила <tex>k</tex>, либо работа <tex>k</tex> опаздывала и <tex>w_k</tex> было меньше <tex>\min\limits_{i \in S}w_i</tex>, и поэтому она не была добавлена. В любом случае в это время работа <tex>l</tex> уже принадлежала <tex>S</tex>. Во втором случае очевидно, что <tex>w_k \leq w_l</tex>. То же неравенство выполняется и в первом случае, так как на этапе замены мы выбрали <tex>k</tex>, а не <tex>l</tex>. Следовательно, мы не ухудшим целевую функцию заменой <tex>k</tex> на <tex>l</tex>.<br>
 
2. Пусть <tex>l > k</tex>.<br>
 
Замена работы <tex>k</tex> в <tex>S^*</tex> на работу <tex>l</tex> не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как <tex>k</tex> выполнялась в срок, а <tex>d_k \leq d_l</tex> и все работы выполняются одинаковое количество времени. Следовательно, <tex>l</tex> так же будет выполнена в срок. Осталось доказать, что <tex>w_k \leq w_l</tex>. <br>
 
Пусть работа <tex>k_{i_0} = k</tex> была заменена работой <tex>i_0</tex>, а так же <tex>k_{i_1} \cdots k_{i_r}</tex> {{---}} последовательность работ из <tex>S</tex>, каждая из которых была на некотором шаге заменена работой <tex>i_1 \cdots i_r</tex> соответственно. Тогда <tex>i_0 < i_1 < \cdots < i_r</tex>.<br>
 
[[Файл:Sh.jpg|250px|thumb|right|Рис. 1. <tex>i_v</tex> превосходит <tex>i_u</tex>.]]
 
Будем говорить <tex>i_v</tex> ''превосходит'' <tex>i_u</tex>, где <tex>u < v</tex>, если <tex>k_{i_v} \leq i_u</tex>. Тогда <tex>w_{k_{i_v}} \geq w_{k_{i_u}}</tex>, так как когда мы вставляли работу <tex>i_u</tex> мы выбрали для замены <tex>k_{i_u}</tex>, то есть ее вес был минимальным среди всех работ, находившихся на тот момент в <tex>S</tex>, включая <tex>k_{i_v}</tex>. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга согласно их номерам.<br>
 
Если из последовательности <tex>i_0 < i_1 < \cdots < i_r</tex> можно выделить подпоследовательность <tex>j_0 = i_0 < j_1 < \cdots < j_s</tex> со свойствами:
 
* <tex>j_{v + 1}</tex> превосходит <tex>j_v</tex>, где <tex>v \in [0 \cdots s - 1]</tex>
 
* <tex>j_{s - 1} < l \leq j_s</tex> ,
 
то <tex>w_l \geq w_{k_{j_s}} \geq \cdots \geq w_{k_{j_0}} = w_k</tex>, что доказывает теорему.<br>
 
В противном случае найдем такую работу <tex>i_t</tex> с наименьшим <tex>t</tex>, что никакая работа <tex>i_v</tex>, где <tex>v > t</tex>, не превосходит <tex>i_t</tex>, причем <tex>i_t < l</tex>. По определению это значит, что после того, как работа <tex>i_t</tex> будет добавлена в <tex>S</tex>, ни одна работа <tex>i \leq i_t</tex> не будет удалена из этого множества. Так как <tex>i_t < l</tex>, то по определению <tex>l</tex> все работы, которые на момент добавления <tex>i_t</tex> находятся в <tex>S</tex>, так же должны принадлежать <tex>S^*</tex>. Покажем, что это приведет нас к противоречию.<br>
 
Пусть <tex>S_t</tex> {{---}} множество <tex>S</tex> после удаления <tex>k_{i_t}</tex> и добавления <tex>i_t</tex>. Рассмотрим два случая:<br>
 
а). Если <tex>k^* = k_{i_t} > k</tex>, то есть <tex>d_{k^*} \geq d_k</tex>, то мы можем заменить <tex>k</tex> на <tex>k^*</tex> в <tex>S^*</tex>, сохранив условие, что <tex>S^*</tex> не содержит опаздывающих работ. Следовательно, множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что противоречит построению <tex>S</tex>.
 
б). Пусть <tex>k^* < k</tex>. Тогда все работы из <tex>S_t \cup \{k\}</tex> могут быть выполнены в срок, так как <tex>S_t</tex> и <tex>k</tex> принадлежат <tex>S^*</tex>. Более того, все работы из множества <tex>\{j \in S_t | j < k\}</tex> могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что является противоречием.
 
 
}}
 
}}

Текущая версия на 16:16, 4 января 2017

Теорема:
Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
Доказательство:
[math]\triangleright[/math]

Пусть [math]A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}[/math]. Сведем проблему соответствий Поста к [math]\overline{A}[/math], таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки замкнуты относительно дополнения, то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.

Для любого экземпляра ПСП [math](x_1, x_2, ..., x_n)[/math] и [math](y_1, y_2, ..., y_n)[/math] над алфавитом [math]\Sigma[/math] можно подобрать символ [math]\# \notin \Sigma[/math]. Для каждого экземпляра построим грамматики:

  • [math]G_1 : S \rightarrow aSa \mid a\#a[/math] для всех [math]a \in \Sigma[/math]. Тогда [math]L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}[/math], где обозначение [math]w^R[/math] — разворот [math]w[/math].
  • [math]G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i[/math] для всех [math]i = 1, 2, \dots n[/math]. Тогда [math]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 \}, m \geqslant 1 \}[/math].

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

Таким образом мы свели проблему соответствий Поста к [math]\overline{A}[/math], следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
[math]\triangleleft[/math]

Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.

По двум КС-грамматикам [math]G_1[/math] и [math]G_2[/math] можно построить КС-грамматику для конкатенации задаваемых ими языков [math]L(G_1)L(G_2)[/math]. По аналогии с этим мы можем рассматривать язык [math]L(G_1)\#L(G_2)\#[/math], где [math]\#[/math] — новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть [math]L(G_1) \cap L(G_2) \ne \varnothing [/math], тогда и только тогда, когда [math]L(G_1)\#L(G_2)\#[/math] содержит тандемный повтор.

Аналогично можно заметить, что пересечение [math]L(G_1) \cap L(G_2) \ne \varnothing [/math] тогда и только тогда, когда [math]L(G_1)\#L(G_2)^R[/math] содержит палиндром.

Таким образом, мы имеем:

Утверждение:
Пусть дана грамматика [math]G[/math], [math]L(G) = L[/math]. Тогда следующие задачи неразрешимы:
  1. Содержит ли [math]L[/math] тандемный повтор.
  2. Содержит ли [math]L[/math] палиндром.