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

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

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

Схема - это тройка , где${\ 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 называются выходами . Если в графе есть ребро от ворот к воротам, то он называется дочерним элементом . Мы предполагаем, что вершины графа упорядочены, поэтому мы можем говорить о th дочернем элементе элемента, если он меньше исходящей степени элемента.${\ 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}$

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

Точное значение ворот с внутренней степенью и меткой определяется рекурсивно для всех ворот .${\ 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. DOI : 10,1006 / jcss.2001.1768 . ISSN  0022-0000 .