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

редактировать

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

Содержание

1 Формальное определение
- 1.1 Терминология
- 1.2 Оценка
2 Цепи как функции
3 Сложность и алгоритмические проблемы
4 См. Также
5 Ссылки

Формальное определение

Цепь - это тройная $( M, L, G) {\ displaystyle (M, L, G)}$ $(M, L, G)$ , где

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

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

Терминология

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

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

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

Оценка

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

V (g) = {l, если g является входом l (V (g 1),…, V (gi)) в противном случае, {\ displaystyle V (g) = {\ begin { case} l {\ text {if}} g {\ text {является входом}} \\ l (V (g_ {1}), \ dotsc, V (g_ {i})) {\ text {иначе, }} \ end {cases}}}

V (g) = \ begin {case} l \ text {if} g \ text {является входом} \\ l (V (g_1), \ dotsc, V (g_i)) \ text {иначе,} \ end {case}

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

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

Цепи как функции

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

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

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

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

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

См. Также

Ссылки

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