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

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

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

Схема - тройная ${ Displaystyle (М, L, G)}$, куда

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

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

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

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

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

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

Оценка

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

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

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

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

Схемы как функции

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

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

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

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

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

Смотрите также

• Сложность схемы
• NC
• AC
• TC
• Цепи над наборами натуральных чисел

Рекомендации

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