Изменения

{{Теорема|statement===Алгоритм разделения АВЛ-дерева Задача о проверке на два, где в первом дереве все ключи меньше заданного x, а во втором пустоту пересечения двух КС- больше==грамматик неразрешима.|proof=Пусть у нас есть дерево <tex>T</tex>. Мы должны разбить его на два дерева <tex>T_A = \{1(G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex> и . Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>T_\overline{2A}</tex> такие, таким образом показав, что <tex>T_{1} \leqslant x</tex> дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и <tex>x < T_{2}</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 \leqslant xmid w \in \Sigma^* \}</tex>, в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево где обозначение <tex>T_w^R</tex> {1{---}}разворот <tex>w</tex>. Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи * <tex>G_2 : S \leqslant xrightarrow x_iSy^R_i \mid x_i\#y^R_i</tex>). Если же корень оказался для всех <tex>i = 1, 2, \dots n</tex> x. Тогда </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>SL(G_2)</tex>, корень которого содержит хотя бы одну строку вида <tex>w\leqslant x#w^R</tex>. В таком случае этот корень со своим левым поддеревом должен отойти в дерево , поэтому <tex>T_{1}</tex>. Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево <tex>S</tex>, удаляем корень, запоминая его значение L(не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL'амиG_1). Таким образом, мы отделяем сбалансированное АВЛ-дерево \cap L(бывшее левое поддерево <tex>S</tex>G_2). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины <tex>S\ne \varnothing</tex> , и запускаем балансировку. Обозначим полученное дерево за <tex>T'</tex>. Теперь нам нужно объединить его с уже построенным ранее <tex>T_{1}</tex> (оно может быть пустымнаоборот, если мы первый раз нашли такое дерево он не имеет решения, то <tex>S</tex>L(G_2). Для этого мы ищем в дереве <tex>T_{1}</tex> самое правое поддерево <tex>P</tex> высотыне содержит строк такого вида, равной высоте соответственно <tex>T'</tex> L(спускаясь от корня всегда в правые поддеревьяG_1). Делаем новое дерево <tex>K</tex>, сливая <tex>P</tex> и <tex>T'</tex> \cap L(очевидно, все ключи в <tex>T_{1}</tex> меньше ключей в <tex>T'</tex>, поэтому мы можем это сделатьG_2). Теперь в дереве <tex>T_{1}= \varnothing</tex> у отца вершины, в которой мы остановились при поиске дерева <tex>P</tex>, правым поддеревом делаем дерево <tex>K</tex> и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева <tex>S</tex> (по ссылке, которую мы ранее запомнили) и обработать его.

Если Таким образом мы пришли в поддерево свели проблему соответствий Поста к <tex>Q</tex>, корень которого <tex>> x</tex>, совершаем аналогичные действия: делаем NULL'ами ссылки на корень <tex>Q</tex>, запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины <tex>Q</tex> и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее <tex>T_\overline{2A}</tex> аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево <tex>T_{2}</tex>. Рассмотри пример (рис. 1). Цветом выделены поддеревьяследовательно, которые после разделения должны отойти в дерево <tex>T_{1}</tex>. <tex>x = 76</tex>. {| cellpadding="2"| || [[Файл:AVL.jpg|thumb|left|525px|Рис. 1. Разделение АВЛ-дерева задача о проверке на два.]]|} Корень дерева <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). {| cellpadding="2"| || [[Файл:АВВЛ2.jpg|thumb|left|525px|Рис. 2. Создание T'.]]|}{| cellpadding="2"| || [[Файл:AVL3.jpg|thumb|left|1250px|Рис. 3. Объединение T' и T1.]]|} Далее действуем по алгоритму и в итоге получаем (рис. 4): {| cellpadding="2"| || [[Файл:End.jpg|thumb|left|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> не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве <tex>S</tex> нашли самое правое поддерево <tex>K</tex>, высота которого равна высоте <tex>T_{1}</tex>. Тогда сделаем новое дерево <tex>T'</tex>, корнем которого будет вершина <tex>S</tex> (без нее это дерево является сбалансированным), правым поддеревом {{---}} <tex>T_{1}</tex>, левым {{---}} <tex>K</tex>. И подвесим <tex>T'</tex> на то место, где мы остановились при поиске <tex>K</tex>. Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, <tex>> x</tex>, все аналогично. Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла <tex>77</tex>. Ключ больше <tex>x</tex>, поэтому эта вершина станет деревом <tex>T_{2}</tex> и передастся наверх. Теперь мы поднялись в узел <tex>75</tex>. Он со своим левым поддеревом станет деревом <tex>T_{1}</tex> и мы снова поднимемся наверх в узел <tex>70</tex>. Он со своим левым поддеревом снова должен отойти в дерево <tex>T_{1}</tex>, и так как теперь дерево <tex>T_{1}</tex> уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5) {| cellpadding="2"| || [[Файл:Ex.jpg|thumb|left|525px|Рис. 5.]]|} После мы поднимемся в вершину с ключом <tex>80</tex>. Она с правым поддеревом отойдет в дерево <tex>T_{2}</tex> (рис. 6).  {| cellpadding="2"| || [[Файл:Ex2am.jpg|thumb|left|525px|Рис. 6.]]|} И на последней итерации мы поднимемся в корень дерева с ключом <tex>50</tex>, он с левым поддеревом отойдет в дерево <tex>T_{1}</tex>, после чего алгоритм завершитсянесколько примеров.

Пусть поддеревьев с ключами По двум КС-грамматикам <tex>\leqslant xG_1</tex> оказалось больше, чем поддеревьев с ключами и <tex>> xG_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>H_{k}</tex> L(G_1)L(она может быть не равна <tex>1G_2)</tex>, если . По аналогии с этим мы придём в можем рассматривать язык <tex>x</tex>L(G_1)\#L(G_2). Его мы передаем наверх и вставляем в поддерево высотой <tex>H_{k-1}</tex>. <tex>H_{k} \leqslant H_{k-1}#</tex>, так как разница высот поддеревьев у любой вершины не больше где <tex>1\#</tex>, и мы при переходе от <tex>H_{k}</tex> к <tex>H_{k-1}</tex> поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за <tex>H_{k-1-} - H_{k}</tex>новый символ, получим не встречающийся в итоге дерево высоты не большейалфавите. Заметим, что пересечение языков непусто, чем то есть <tex>H_{k-1}L(G_1) \cap L(G_2) \ne \varnothing </tex>. Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за <tex>H_{k-2} - H_{k - 1}</tex> тогда и так далее. Таким образом мы получим только тогда, когда <tex>L(H - H_{1}G_1) + (H_{1} - H_{2}) + (H_{2} - H_{3}) + \cdots + #L(H_{k - 1} - H_{k}G_2) = H - H_{k} = O(\log{n})#</tex>содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].

Итоговая асимптотика алгоритма {{---}} Аналогично можно заметить, что пересечение <tex>OL(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\log{n}#L(G_2)^R</tex>содержит палиндром.

= Гамма-алгоритм =Таким образом, мы имеем:{{ЗадачаУтверждение|definitionstatement=ОпределитьПусть дана грамматика <tex>G</tex>, является <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы:# Содержит ли <tex>L</tex> тандемный повтор.# Содержит ли граф планарным, и, если да, произвести его плоскую укладку<tex>L</tex> палиндром.