Схема (информатика)

В теоретической информатике схема — это модель вычислений, в которой входные значения проходят через последовательность вентилей, каждый из которых вычисляет функцию. Схемы такого типа представляют собой обобщение булевых схем и математическую модель цифровых логических схем. Схемы определяются элементами, которые они содержат, и значениями, которые эти элементы могут создавать. Например, значения в логической схеме являются логическими значениями, и схема включает в себя элементы соединения, дизъюнкции и отрицания. Значения в целочисленной схеме представляют собой наборы целых чисел, а вентили вычисляют объединение множеств, пересечение множеств и дополнение множеств, а также арифметические операции сложения и умножения.

Формальное определение [ править ]

Схема представляет собой тройку $(M,L,G)$ , где

$M$ это набор ценностей,
$L$ представляет собой набор меток вентилей, каждая из которых является функцией от $M^{i}$ к $M$ для некоторого неотрицательного целого числа $i$ (где $i$ представляет количество входов в вентиль), и
$G$ представляет собой помеченный ориентированный ациклический граф с метками из $L$ .

Вершины графа называются воротами . Для каждых ворот $g$ степени $i$ , ворота $g$ может быть помечен элементом $\ell$ из $L$ тогда и только тогда, когда $\ell$ определяется на $M^{i}.$

Терминология [ править ]

Ворота степени 0 называются входами или листьями . Ворота исходящей степени 0 называются выходами . Если есть грань от ворот $g$ воротам $h$ на графике $G$ затем $h$ называется ребенком $g$ . Мы предполагаем, что в вершинах графа существует порядок, поэтому мы можем говорить о $k$ й ребенок ворот, когда $k$ меньше, чем степень выхода затвора.

Размер схемы — это количество узлов схемы. Глубина ворот $g$ длина самого длинного пути в $G$ начиная с $g$ до выходных ворот. В частности, вентили исходящей степени 0 являются единственными вентилями глубины 1. Глубина схемы — это максимальная глубина любого вентиля.

Уровень $i$ это совокупность всех врат глубины $i$ . – Выровненный контур это контур, в котором края к воротам глубины $i$ приходит только из врат глубины $i+1$ или от входов. Другими словами, ребра существуют только между соседними уровнями схемы. Ширина . выровненной цепи — это максимальный размер любого уровня

Оценка [ править ]

Точное значение $V(g)$ ворот $g$ со степенью $i$ и пометить $l$ определяется рекурсивно для всех ворот $g$ .

V(g)={\begin{cases}l&{\text{if }}g{\text{ is an input}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{otherwise,}}\end{cases}}

где каждый $g_{j}$ является родителем $g$ .

Значение схемы — это значение каждого из выходных вентилей.

Схемы как функции [ править ]

Метки листьев также могут быть переменными, которые принимают значения в $M$ . Если есть $n$ листьев, то схему можно рассматривать как функцию от $M^{n}$ к $M$ . Тогда обычно рассматривают семейство цепей $(C_{n})_{n\in \mathbb {N} }$ , последовательность схем, индексированных целыми числами, где схема $C_{n}$ имеет $n$ переменные. Таким образом, семейства схем можно рассматривать как функции от $M^{*}$ к $M$ .

Понятия размера, глубины и ширины можно естественным образом распространить на семейства функций, становясь функциями из $\mathbb {N}$ к $\mathbb {N}$ ; например, $size(n)$ это размер $n$ й контур семьи.

и алгоритмические проблемы Сложность

Вычисление вывода данной логической схемы на определенном входе является P-полной задачей. Однако если входные данные представляют собой целочисленную схему , неизвестно, разрешима ли эта проблема .

Сложность схемы пытается классифицировать булевы функции по размеру или глубине схем, которые могут их вычислять.

См. также [ править ]

Ссылки [ править ]

Воллмер, Гериберт (1999). Введение в сложность схем . Берлин: Шпрингер. ISBN 978-3-540-64310-4 .
Ян, Кэ (2001). «Вычисление целочисленной схемы является PSPACE-полным» . Журнал компьютерных и системных наук . 63 (2 сентября 2001 г.): 288–303. дои : 10.1006/jcss.2001.1768 . ISSN 0022-0000 .