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

Модель вычислений

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

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

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

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

Вершины графа называются воротами . Для каждого вентиля in -степени вентиль может быть помечен элементом тогда и только тогда, когда определен на ${\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}$

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

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

Оценка

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

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

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

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

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

Метки листьев также могут быть переменными, принимающими значения в . Если листья есть , то схему можно рассматривать как функцию от до . Тогда обычно рассматривают семейство схем , последовательность схем, индексированных целыми числами, где схема имеет переменные. Таким образом, семейства схем можно рассматривать как функции от до . ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle M^{n}}$ ${\displaystyle M}$ ${\displaystyle (C_{n})_{n\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). Введение в сложность схем . Берлин: Шпрингер. ISBN 978-3-540-64310-4.
• Ян, Кэ (2001). «Оценка целочисленной схемы является PSPACE-полной». Журнал компьютерных и системных наук . 63 (2 сентября 2001 г.): 288–303. дои : 10.1006/jcss.2001.1768 . ISSN  0022-0000.