|
|
| (не показано 139 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | ===Алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше заданного x, а во втором - больше=== | + | {{Теорема |
| − | Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_{1}</tex> и <tex>T_{2}</tex> такие, что <tex>T_{1} \leqslant x</tex> и <tex>x < T_{2}</tex>. | + | |statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| | + | |proof= |
| | + | Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы. |
| | | | |
| − | Предположим, что корень нашего дерева <tex>\leqslant x</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево <tex>T_{1}</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи <tex>\leqslant x</tex>). Если же корень оказался <tex>> x</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>S</tex>, корень которого <tex>\leqslant x</tex>. В таком случае этот корень со своим левым поддеревом должен отойти в дерево <tex>T_{1}</tex>. Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево <tex>S</tex>, удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево <tex>S</tex>). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины <tex>S</tex> и запускаем балансировку. Обозначим полученное дерево за <tex>T'</tex>. Теперь нам нужно объединить его с уже построенным ранее <tex>T_{1}</tex> (оно может быть пустым, если мы первый раз нашли такое дерево <tex>S</tex>). Для этого мы ищем в дереве <tex>T_{1}</tex> самое правое поддерево <tex>P</tex> высоты, равной высоте <tex>T'</tex> (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево <tex>K</tex>, сливая <tex>P</tex> и <tex>T'</tex> (очевидно, все ключи в <tex>T_{1}</tex> меньше ключей в <tex>T'</tex>, поэтому мы можем это сделать). Теперь в дереве <tex>T_{1}</tex> у отца вершины, в которой мы остановились при поиске дерева <tex>P</tex>, правым поддеревом делаем дерево <tex>K</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>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_{2}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>.
| + | Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| | + | }} |
| | + | Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров. |
| | | | |
| − | Рассмотри пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</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|тандемный повтор]]. |
| | | | |
| − | [[Файл:AVL.jpg|525px||Рис. 1. Разделение АВЛ-дерева на два.]]
| + | Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром. |
| | | | |
| − | Корень дерева <tex>\leqslant x</tex>, поэтому он со всем выделенным поддеревом должен отойти в дерево <tex>T_{1}</tex>. По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево <tex>T'</tex> (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был <tex>\leqslant x</tex>, <tex>T'</tex> становится <tex>T_{1}</tex>. Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень <tex>> x</tex>. Следовательно, строим из него и его правого поддерева <tex>T_{2}</tex> и спускаемся в левое поддерево. Снова корень <tex>\leqslant x</tex>. Строим новое <tex>T'</tex> и объединяем его с уже существующим <tex>T_{1}</tex> (рис. 3).
| + | Таким образом, мы имеем: |
| − | | + | {{Утверждение |
| − | [[Файл:АВВЛ2.jpg|525px||Рис. 2. Создание T'.]]
| + | |statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы: |
| − | [[Файл:AVL3.jpg|1250px||Рис. 3. Объединение T' и T1.]]
| + | # Содержит ли <tex>L</tex> тандемный повтор. |
| − | | + | # Содержит ли <tex>L</tex> палиндром. |
| − | Далее действуем по алгоритму и в итоге получаем (рис. 4):
| + | }} |
| − | | |
| − | [[Файл:End.jpg|525px||Рис. 4. АВЛ-деревья после разделения.]]
| |
| − | | |
| − | Данный алгоритм имеет сложность <tex>O(\log^{2} n)</tex>. Рассмотрим решение, которое имеет сложность <tex>O(\log{n})</tex>.
| |
| − | | |
| − | Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья <tex>T_{1}</tex> и <tex>T_{2}</tex>, передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево <tex>T_{1}</tex> придет вершина <tex>75</tex> с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением <tex>70</tex> и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.
| |
| − | | |
| − | Алгоритм построения следующий: пусть мы пришли в поддерево <tex>S</tex> с корнем <tex>\leqslant x</tex>. Тогда сольем его с уже построенным на тот момент <tex>T_{1}</tex> (<tex>T_{1}</tex> пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, <tex>S \leqslant T_{1}</tex> и <tex>h(T_{1}) \leqslant h(S)</tex>). Но так как обычная процедура слияния сливает два АВЛ-дерева, а <tex>S</tex> не является корректным АВЛ-деревом, мы немного ее изменим.
| |
| Теорема: |
Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| Доказательство: |
| [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]. Тогда следующие задачи неразрешимы:
- Содержит ли [math]L[/math] тандемный повтор.
- Содержит ли [math]L[/math] палиндром.
|
