1632
правки
Изменения
м
rollbackEdits.php mass rollback
= Линейные программы =Определения и основные понятия, связанные с булевыми функциями описаны в статье [[Определение булевой функции|"определение булевой функции"]].<br>{{Определение|definition='''Линейная программа''' {{---}} последовательность строк вида <tex>{\{s_i\}}_{i=n}^t</tex>, в которой <tex>s_i</tex> имеет вид <tex>x_i = F(x_{a_1}, x_{a_2}, \ldots , x_{a_m})</tex>, где <tex>x_i, x_{a_1}, \dots , x_{a_m}</tex> {{---}} переменные, каждое из чисел <tex>a_j</tex> меньше <tex>i</tex>, а <tex>F</tex> {{---}} <tex>m</tex>-местная базисная функция. Такая линейная программа имеет <tex>n</tex> входных переменных, которые не выражаются через операции вычисления.}}'''Пример'''<br>Для базиса <tex>B_0 = \{\vee, \wedge, \neg \}</tex> линейная программа может выглядеть следующим образом: * <tex>A_2 = A_0 \wedge A_1</tex>;* <tex>A_2 = A_0 \vee A_1</tex>;* <tex>A_1 = \neg A_0</tex>.<br>Линейная программа <tex>P</tex> с выделенными переменными <tex>x_1,\dots , x_n</tex> порождает для каждого набора <tex>\sigma_1, \dots , \sigma_n</tex> значений входных переменных естественный процесс вычисления:# Переменным <tex>x_1, \dots , x_n</tex> присваиваются значения <tex>\sigma_1, \dots , \sigma_n</tex>, соответственно, а каждой из остальных переменных присваивается значение <tex>0</tex>;# Последовательно выполняются присваивания программы <tex>P</tex>, в результате чего каждая из переменных <tex>x_i</tex> программы получит итоговое значение <tex>P_i(\sigma_1, \dots , \sigma_n)</tex>. {{Определение|definition='''Программа''' <tex>P</tex> со входными переменными <tex>x_1,\dots , x_n</tex> '''вычисляет''' в выходной переменной <tex>x_m</tex> '''функцию''' <tex>F(x_1, \dots , x_n)</tex>, если для любого набора значений входов <tex>\sigma_1, \dots , \sigma_n</tex> после завершения работы <tex>P_m(\sigma_1, \dots , \sigma_n) = F(\sigma_1, \dots , \sigma_n)</tex>.}} = Связь между схемами и линейными программами =Как известно, [[Реализация булевой функции схемой из функциональных элементов|булевы функции представимы в виде схем из функциональных элементов]]. В разработкеданном пункте мы определим связь между такими схемами и линейными программами.<br> {{Теорема|statement=<br># По каждой логической схеме <tex>S</tex> со входами <tex>x_1, \dots , x_n</tex> и функциональными элементами <tex>v_1, \dots , v_m</tex> можно эффективно построить линейную программу <tex>P_S</tex> со входными переменными <tex>x_1, \dots , x_n</tex> и рабочими переменными <tex>x_{n + 1}, \dots , x_{n + m}</tex>, которая в любой переменной <tex>x_i, i \in [1 + n, m + n]</tex> вычисляет функцию <tex>f_{x_i}(x_1, \ldots , x_n)</tex>;<br><br># По каждой линейной программе <tex>P</tex> со входными переменными <tex>x_1, \dots , x_n</tex>, вычисляющей в выходной переменной <tex>x_m</tex> некоторую функцию <tex>F(x_1, \dots , x_n)</tex> можно эффективно построить логическую схему <tex>S_P</tex> со входами <tex>x_1,\dots , x_n</tex>, в которой имеется вершина <tex>v</tex> такая, что <tex>f_v(x_1, \dots , x_n) = F(x_1, \dots , x_n)</tex>.|proof='''(1)'''<br>Пусть <tex>S</tex> {{---}} схема со входами <tex>x_1, \dots , x_n</tex> и функциональными элементами <tex>v_1, \dots , v_m</tex>. Построим по ней линейную программу <tex>P_S</tex> со входными переменными <tex>x_1, \dots , x_n</tex> следующим образом. [[Использование обхода в глубину для топологической сортировки | Топологически отсортируем]] все входные и функциональные вершины <tex>S</tex>: <tex>u_1, \dots , u_{n + m}</tex>. Программа <tex>P_S</tex> будет последовательностью <tex>m</tex> присваиваний.<br>* Пусть вершина <tex>u_{i + n}</tex> помечена <tex>\neg</tex>, и в нее входит ребро из <tex>u_j</tex>. Тогда в качестве <tex>i</tex>-ой команды поместим в <tex>P_S</tex> присваивание <tex>x_{i + n}= \neg x_j</tex>;* Пусть вершина <tex>u_{i + n}</tex> помечена <tex>\circ \in \{ \wedge , \vee \}</tex>, и в нее входят ребра из <tex>u_j</tex> и <tex>u_k</tex>. Тогда в качестве <tex>i</tex>-ой команды поместим в <tex>P_S</tex> присваивание <tex>x_{i + n} = x_j \circ x_k</tex>.<br>Топологическая сортировка вершин гарантирует, что <tex>j < n + i \wedge k < n + i</tex>. Поэтому при вычислении <tex>x_{n + i}</tex> значения аргументов уже получены и индукцией по глубине легко показать, что для любого <tex>i \in [1, m]</tex> программа <tex>P_S</tex> вычисляет в переменной <tex>x_i</tex> функцию <tex>f_{x_i}(x_1, \dots, x_n)</tex>.}} '''Пример'''[[Файл:Logic_scheme_sample_boolean_functions_and_linear_programs.gif|300px|thumb|left|Пример схемы]]Воспользуемся только что доказанной теоремой, и построим на основании этой схемы линейную программу.<br>Установим соответствие между вершинами схемы и переменными: <tex>x \; — \; x_0, \; y \; — \; x_1, \; z \; — \; x_2, \; a \; — \; x_3, \; b \; — \; x_4, \; c \; — \; x_5, \; d \; — \; x_6, \; e \; — \; x_7, \; f \; — \; x_8</tex>.<br>Результатом топологической сортировки данного графа может стать последовательность вершин: <tex>x, y, z, a, b, c, d, e, f</tex>. Тогда программа <tex>P_S</tex> будет иметь следующий вид:<br><tex>x_3 = x_0 \wedge x_1</tex><br><tex>x_4 = \neg x_2</tex><br><tex>x_5 = \neg x_3</tex><br><tex>x_6 = x_5 \wedge x_2</tex><br><tex>x_7 = x_3 \wedge x_4</tex><br><tex>x_8 = x_6 \vee x_7</tex><br><br>{{Утверждение|statement=Число команд в линейной программе <tex>P_S</tex>, т.е. время ее выполнения, совпадает со сложностью <tex>L(S)</tex> схемы <tex>S</tex>. Глубина схемы <tex>D(S)</tex> также имеет смысл с точки зрения времени вычисления. Именно, <tex>D(S)</tex> {{---}} это время выполнения <tex>P_S</tex> на многопроцессорной системе. Действительно, все команды, соответствующие вершинам одинаковой глубины, можно выполнять параллельно на разных процессорах, так как результаты любой из них не используются в качестве аргументов другой.}} = См. также =* [[Определение булевой функции]]* [[Реализация булевой функции схемой из функциональных элементов]]* [[Использование обхода в глубину для топологической сортировки]] = Литература =# Дехтярь М.И. Реализация булевых функций с помощью логических схем // Введение в схемы, автоматы и алгоритмы, 2007. URL: https://www.intuit.ru/studies/courses/1030/205/lecture/5306 [[Категория: Дискретная математика]][[Категория: Дискретная математика и алгоритмы]][[Категория: Булевы функции ]]
