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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Асимптотика)
 
(не показаны 33 промежуточные версии 2 участников)
Строка 1: Строка 1:
<tex dpi = "200"> O \mid p_{i,j} = 1, d_i \mid - </tex>
+
{{Теорема
{{Задача
+
|statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
|definition=
+
|proof=  
Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</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>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.
}}
 
== Описание алгоритма ==
 
=== Идея ===
 
[[Файл:Shd2.jpg|300px|thumb|right|Рис. 1. Работа <tex>i</tex> назначена на интервалы <tex>d_i - m + 1 \ldots d_i</tex>.]]
 
Заметим, что если <tex>d_i < m</tex>, то очевидно, что <tex>C_i > d_i</tex>, следовательно, расписания не существует. Поэтому будем полагать, что <tex>m \leqslant d_i</tex> для <tex>i = 1 \ldots n</tex>.
 
  
Определим <tex>T = \max\limits_{i \in [1, n]}d_i</tex> {{---}} количество временных интервалов <tex>[t - 1, t]</tex>, где <tex>t = 1 \ldots T</tex>. Будем обозначать <tex>[t - 1, t]</tex> как <tex>t</tex>. Для каждого из них мы можем назначить не более <tex>m</tex> работ (по одной на каждый станок). Для каждой работы <tex>i</tex> будем назначать времена обработки на каждой из машин следующим образом: на машине <tex>m</tex> работа займет временной интервал <tex>d_i</tex>, на машине <tex>(m - 1)</tex> {{---}} интервал <tex>(d_i - 1)</tex> и так далее, на машине <tex>1</tex> работа займет временной интервал <tex>d_i - m + 1</tex>. В случае коллизий, то есть если найдется временной интервал <tex>k > 1</tex>, содержащий <tex>m + 1</tex> работу, возьмем минимальный такой <tex>k</tex> и перенесем лишнюю работу из него на ту же машину, но на один временной интервал левее. Будем повторять этот процесс, пока необходимо (и пока <tex>k > 1</tex>). Таким образом, только первый временной интервал может содержать более <tex>m</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>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>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>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>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>.
 
  
'''void''' checkExistenceOfSchedule('''int'''* <tex>d</tex>):
+
Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
  <tex>T = \max\{d_i \mid i = 1 \ldots n\}</tex>
+
}}
  '''for''' <tex>t = 1</tex> '''to''' <tex>T</tex>
+
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.
      <tex>h(t) = 0</tex>
 
  '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
 
      '''for''' <tex>j = d_i</tex> '''to''' <tex>d_i - m + 1</tex>          <font color=green>(1)</font>
 
        <tex>h(j) = h(j) + 1</tex>
 
      '''while''' <tex>\exists k > 1</tex> '''and''' <tex>h(k) = m + 1</tex>    <font color=green>(2)</font>
 
        '''find''' <tex>\min\{k_0 \mid h(k_0) = m + 1\}</tex>
 
        <tex>h(k_0 - 1) = h(k_0 - 1) + 1</tex>
 
        <tex>h(k_0) = m</tex>
 
  '''if''' <tex>h(1) \leqslant m</tex>
 
      '''return''' true
 
  '''else'''
 
      '''return''' false
 
''Замечание:'' если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы <tex>i</tex> на момент <tex>j</tex> в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале <tex>k_0 - 1</tex>, но которая есть в <tex>k_0</tex>, на момент <tex>k_0 - 1</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>O(nm)</tex>.<br>
+
 
Для начала рассмотрим следующий вопрос: пусть <tex>U</tex> {{---}} множество работ, для которого существует расписание, в котором отсутствуют опаздывающие работы, пусть <tex>i</tex> {{---}} работа, не принадлежащая <tex>U</tex>, для которой выполняется неравенство <tex>d_j \leqslant d_i</tex> для любой <tex>j \in U</tex>. Можно ли построить расписание для множества <tex>V = U \cup \{i\}</tex>, в котором так же будут отсутствовать опаздывающие работы.<br>
+
Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром.  
Введем несколько обозначений. Вектора <tex>h</tex>, соответствующие множествам <tex>U</tex> и <tex>V</tex> обозначим как <tex>h^U</tex> и <tex>h^V</tex> соответственно. <tex>x(d_i)</tex> {{---}} количество временных интервалов <tex>t</tex> со свойствами
 
*<tex>d_i - m + 1 \leqslant t \leqslant d_i</tex>,
 
*<tex>h^U(t) < m</tex>.
 
Будем говорить, что множество работ может быть выполнено ''вовремя'', если существует расписание, в котором все работы из этого множества успевают выполниться без опозданий.
 
{{Лемма
 
|statement=
 
Пусть даны работы <tex>1, 2 \ldots i</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_i</tex>, <tex>U = \{1, 2, \ldots i - 1\}</tex> и <tex>V = U \cup \{i\}</tex>. Тогда для всех работ <tex>j = d_i - m + 1 \ldots d_i</tex>, для которых <tex>h^U(j) < m</tex>, будет верно, что <tex>h^V(j) = h^U(j) + 1</tex>.
 
|proof=
 
Рассмотрим вектора <tex>h^U</tex> и <tex>h^V</tex> после <tex>i - 1</tex> и <tex>i</tex> итераций алгоритма. Заметим, что значения вектора <tex>h</tex>, не превосходящие <tex>m</tex>, то есть <tex>h(j) < m</tex>, никогда не уменьшаются. Следовательно, если <tex>d_i - m + 1 \leqslant j \leqslant d_i</tex> и <tex>h^U(j) < m</tex>, то <tex>h^V(j) \geqslant h^U(j) + 1</tex>. Чтобы показать, что ситуация, когда при тех же условиях <tex>h^V(j) \geqslant h^U(j) + 2</tex>, невозможна, рассмотрим расписание, построенное алгоритмом.<br>
 
Если <tex>h^V(j) \geqslant h^U(j) + 2</tex>, то это значит, что в течение <tex>i</tex> итерации во временной интервал <tex>j</tex> была добавлена работа <tex>i</tex> и еще как минимум одна работа, пусть работа <tex>k</tex>, была перемещена из временного интервала <tex>j + 1</tex> в <tex>j</tex>. Это возможно только если работа <tex>k</tex> ни на одной машине не была назначена до временного интервала <tex>j</tex>. Следовательно, работа <tex>k</tex> выполняется во временной интервал <tex>j</tex> и некоторые временные интервалы <tex>v > j + 1</tex>, откуда следует, что <tex>j < d_k - m + 1 \leqslant d_i - m + 1</tex>, что приводит нас к противоречию.
 
}}
 
{{Теорема
 
|statement=
 
Пусть <tex>U</tex> {{---}} множество работ, которое может быть выполнено вовремя, пусть <tex>i</tex> {{---}} работа, не принадлежащая <tex>U</tex>, для которой выполняется неравенство <tex>d_j \leqslant d_i</tex> для любой <tex>j \in U</tex>. Тогда множество работ <tex>V = U \cup \{i\}</tex> может быть выполнено вовремя тогда и только тогда, когда <tex>x(d_i) + \sum\limits_{t = 1}^{d_i - m}(m - h^U(t)) \geqslant m</tex> (1).
 
|proof=
 
Неравенство (1) равносильно <tex>(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t) + m - x(d_i)</tex>.
 
}}
 
  
== Доказательство корректности ==
+
Таким образом, мы имеем:
{{Теорема
+
{{Утверждение
|statement=
+
|statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы:
Для множества работ с дедлайнами <tex>d_1, d_2, \ldots d_n</tex> задача имеет решение тогда и только тогда, когда <tex>h(1) \leqslant m</tex>.
+
# Содержит ли <tex>L</tex> тандемный повтор.
|proof=
+
# Содержит ли <tex>L</tex> палиндром.
<tex>\Rightarrow</tex><br>
 
Если задача имеет решение, то очевидно, что первый временной интервал не может быть переполнен.<br>
 
<tex>\Leftarrow</tex>
 
Изначально алгоритм присваивает все стадии обработки каждой работы <tex>i</tex> (то есть обработку на каждом станке) попарно различным временным интервалам. Если <tex>\exists k > 1 : h(k) = m + 1</tex> и <tex>h(k - 1) \leqslant m</tex>, то это значит, что существует как минимум одна работа, которая назначена временному интервалу <tex>k</tex>, но которой нет во временном интервале  <tex>k - 1</tex>. Следовательно, после перемещения вектор <tex>h</tex> по-прежнему будет удовлетворять условию, что каждая работа принадлежит <tex>m</tex> разным временным интервалам, причем в каждом из них она будет выполняться на разных машинах, так как при перемещении работ машины остаются прежними. Таким образом, если <tex>h(1) \leqslant m</tex>, то <tex>h(t) \leqslant m</tex>, где <tex>t = 1 \ldots T</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] палиндром.