Circuito (ciência da computação) - Circuit (computer science)

Na ciência da computação teórica , um circuito é um modelo de computação no qual os valores de entrada procedem por meio de uma sequência de portas, cada uma das quais calcula uma função . Circuitos desse tipo fornecem uma generalização dos circuitos booleanos e um modelo matemático para circuitos lógicos digitais. Os circuitos são definidos pelas portas que contêm e pelos valores que as portas podem produzir. Por exemplo, os valores em um circuito booleano são valores booleanos e o circuito inclui portas de conjunção , disjunção e negação . Os valores em um circuito inteiro são conjuntos de números inteiros e as portas calcular união conjunto , conjunto de intersecção , e conjunto de complemento , bem como a operação aritmética adição e multiplicação .

Definição formal

Um circuito é um triplo , onde ${\ displaystyle (M, L, G)}$

• ${\ displaystyle M}$ é um conjunto de valores,
• ${\ displaystyle L}$é um conjunto de rótulos de porta, cada um dos quais é uma função de a para algum número inteiro não negativo (onde representa o número de entradas para a porta), e${\ displaystyle M ^ {i}}$${\ displaystyle M}$${\ displaystyle i}$${\ displaystyle i}$
• ${\ displaystyle G}$é um gráfico acíclico direcionado rotulado com rótulos de .${\ displaystyle L}$

Os vértices do gráfico são chamados de portas . Para cada porta de em graus , a porta pode ser marcado por um elemento de se e só se for definido em . ${\ displaystyle g}$ ${\ displaystyle i}$${\ displaystyle g}$${\ displaystyle \ ell}$${\ displaystyle L}$${\ displaystyle \ ell}$${\ displaystyle M ^ {i}}$

Terminologia

As portas de grau 0 são chamadas de entradas ou folhas . As portas de grau externo 0 são chamadas de saídas . Se houver uma aresta de porta a porta no gráfico, então é chamado de filho de . Supomos que haja uma ordem nos vértices do gráfico, então podemos falar do ésimo filho de um portão quando é menor que o grau externo do portão. ${\ displaystyle g}$${\ displaystyle h}$${\ displaystyle G}$${\ displaystyle h}$${\ displaystyle g}$${\ displaystyle k}$${\ displaystyle k}$

O tamanho de um circuito é o número de nós de um circuito. A profundidade de uma porta é o comprimento do caminho mais longo no início até uma porta de saída. Em particular, os portões de grau 0 são os únicos portões de profundidade 1. A profundidade de um circuito é a profundidade máxima de qualquer portão. ${\ displaystyle g}$${\ displaystyle G}$${\ displaystyle g}$

Nível${\ displaystyle i}$ é o conjunto de todas as portas de profundidade . Um circuito nivelado é um circuito em que as bordas das portas de profundidade vêm apenas das portas de profundidade ou das entradas. Em outras palavras, as bordas existem apenas entre níveis adjacentes do circuito. A largura de um circuito nivelado é o tamanho máximo de qualquer nível. ${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle i + 1}$

Avaliação

O valor exato de uma porta com grau e rótulo é definido recursivamente para todas as portas . ${\ displaystyle V (g)}$${\ displaystyle g}$${\ displaystyle i}$${\ displaystyle l}$${\ displaystyle g}$

${\ displaystyle V (g) = {\ begin {cases} l & {\ text {if}} g {\ text {é uma entrada}} \\ l (V (g_ {1}), \ dotsc, V (g_ {i})) & {\ text {caso contrário,}} \ end {cases}}}$

onde cada um é pai de . ${\ displaystyle g_ {j}}$${\ displaystyle g}$

O valor do circuito é o valor de cada uma das portas de saída.

Circuitos como funções

Os rótulos das folhas também podem ser variáveis ​​que recebem valores . Se houver folhas, o circuito pode ser visto como uma função de para . É então comum considerar uma família de circuitos , uma sequência de circuitos indexada por inteiros onde o circuito tem variáveis. Famílias de circuitos podem, portanto, ser vistas como funções de a . ${\ 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}$

As noções de tamanho, profundidade e largura podem ser naturalmente estendidas a famílias de funções, tornando-se funções de a ; por exemplo, é o tamanho do ésimo circuito da família. ${\ displaystyle \ mathbb {N}}$${\ displaystyle \ mathbb {N}}$${\ tamanho do displaystyle (n)}$${\ displaystyle n}$

Complexidade e problemas algorítmicos

Calcular a saída de um determinado circuito booleano em uma entrada específica é o problema P-completo . Se a entrada for um circuito inteiro , no entanto, não se sabe se esse problema é decidível .

A complexidade do circuito tenta classificar as funções booleanas com relação ao tamanho ou profundidade dos circuitos que podem computá-las.

Veja também

• Complexidade do circuito
• Circuitos sobre conjuntos de números naturais
• As classes de complexidade NC , AC e TC
• Circuito quântico e BQP

Referências

• Vollmer, Heribert (1999). Introdução à complexidade do circuito . Berlim: Springer. ISBN 978-3-540-64310-4.
• Yang, Ke (2001). "A avaliação do circuito inteiro é PSPACE-Complete" . Journal of Computer and System Sciences . 63 (2, setembro de 2001): 288–303. doi : 10.1006 / jcss.2001.1768 . ISSN  0022-0000 .