Представление формул деревьями и оптимизация формул по глубине

Дерево формулы — упорядоченное ориентированное корневое дерево, которое точно отражает синтаксическую структуру формулы. Листья помечаются входными переменными, внутренние вершины — функциональными символами базиса, а корень соответствует всей формуле. Число листьев равно рангу R(F), число внутренних вершин равно сложности L(F), а глубина корня равна D(F).1

Оптимизация по глубине выполняется среди подобных формул, получаемых перестановкой аргументов и изменением порядка выполнения однотипных операций \(\wedge\) и \(\vee\). Для формулы над \(\text{Б}_{0}\) с поднятыми отрицаниями существует подобная формула F̌ с \(D(\check F)\le \lceil \log_{2}(L(F)+1)\rceil+\operatorname{Alt}(F)\), где Alt(F) — максимальное число чередований \(\wedge\) и \(\vee\) вдоль пути дерева. Для одной конъюнкции или дизъюнкции достигается минимальная глубина \(\lceil \log_{2}(L+1)\rceil\).1

Что важно запомнить
  • Листья дерева формулы соответствуют вхождениям переменных, внутренние вершины — операциям базиса.
  • R(F) — число листьев, L(F) — число внутренних вершин, D(F) — глубина корня.
  • Для формул базиса \(\{\wedge,\vee,\neg \}\) выполняется нижняя оценка \(D(F)\ge \lceil \log_{2}(L(F)+1)\rceil\).1
  • Подобные формулы реализуют одну функцию и отличаются только перестановкой аргументов и расстановкой скобок в цепочках \(\wedge /\vee\).
  • Балансировка дерева уменьшает глубину и моделирует распараллеливание вычисления.1

Как формула задаётся деревом

Формуле над базисом Б индуктивно сопоставляют упорядоченное ориентированное корневое дерево. Если формула состоит из одной переменной, дерево имеет одну вершину. Для \(F=\varphi (F_{1},\ldots,F_k)\) берут деревья подформул \(F_{1},\ldots,F_k\), добавляют новый корень с меткой \(\varphi\) и соединяют его с корнями поддеревьев в порядке аргументов. Глубина построенного дерева совпадает с глубиной формулы.1

Это представление сохраняет всю позиционную структуру: каждой позиционной подформуле соответствует определённое корневое поддерево и наоборот. Поэтому дерево удобно для анализа сложности и эквивалентных перестроений формулы.

Функционалы через дерево

Для формул курса R(F) равно числу листьев дерева, L(F) — числу остальных, то есть внутренних, вершин, а D(F) — глубине корня. Для базиса \(\text{Б}_{0}=\{\wedge,\vee,\neg \}\) из структурных соотношений следует важная нижняя граница \(D(F)\ge \lceil \log_{2}(L(F)+1)\rceil\). Она показывает, что при фиксированном числе операций глубину нельзя уменьшать произвольно.1

Подобные формулы и оптимизация глубины

Формулы называют подобными, если одну можно получить из другой применением коммутативности и ассоциативности \(\wedge\) и \(\vee\). Такие преобразования не меняют число операций и переменных, но меняют форму дерева и потому могут менять глубину. В лекциях подчёркивается вычислительный смысл: L связано с объёмом последовательной работы, а D — с временем параллельного вычисления при неограниченном числе процессоров. Поэтому балансировка дерева является частным случаем распараллеливания.1

Для формулы F над \(\text{Б}_{0}\) с поднятыми отрицаниями вводится Alt(F) — максимальное число смен операций \(\wedge\) и \(\vee\) вдоль пути дерева. Теорема курса гарантирует существование подобной формулы F̌ такой, что \(D(\check F)\le \lceil \log_{2}(L(F)+1)\rceil+\operatorname{Alt}(F)\). Для элементарной конъюнкции или дизъюнкции, где чередований нет, существует подобная формула глубины ровно \(\lceil \log_{2}(L+1)\rceil\), и эта глубина минимальна. Для любой ДНФ или КНФ можно получить подобную формулу с глубиной не больше \(\lceil \log_{2}(L(A)+1)\rceil +1\).1

Пример простыми словами

Пусть нужно вычислить конъюнкцию восьми переменных. Запись \((((((((x_{1}\wedge x_{2})\wedge x_{3})\wedge x_{4})\wedge x_{5})\wedge x_{6})\wedge x_{7})\wedge x_{8})\) имеет глубину 7. Если сгруппировать переменные попарно, затем объединять результаты попарно, получится сбалансированное дерево глубины 3. Функция и число операций не изменятся, но критический путь станет намного короче.

Частые ошибки
  • Путать дерево формулы с произвольной СФЭ. У дерева каждая внутренняя вершина, кроме корня, используется ровно одним родителем, а в СФЭ результат может разветвляться.
  • Считать, что подобные формулы могут отличаться функцией. Подобие строится на эквивалентных перестановках и ассоциативных перегруппировках.
  • Отождествлять L(F) и D(F). Большая формула может иметь малую глубину после балансировки.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 2, §3, лемма 3.1, теорема 3.1 и следствия, МГУ, факультет ВМК