Áramkör (informatika) - Circuit (computer science)

Az elméleti számítástechnikában az áramkör a számítás olyan modellje, amelyben a bemeneti értékek egy kapusorozaton haladnak keresztül, amelyek mindegyike kiszámít egy funkciót . Az ilyen típusú áramkörök a Boole -áramkörök általánosítását és a digitális logikai áramkörök matematikai modelljét biztosítják . Az áramköröket a bennük lévő kapuk és a kapuk által előállítható értékek határozzák meg. Például egy logikai áramkör értékei logikai értékek, és az áramkör konjunkciós , diszjunkciós és tagadási kapukat tartalmaz. Az értékek egy egész áramkörben vannak készletek a egész számok , és a kapu kiszámításához beállított Unió , set kereszteződés , és a beállított komplement , valamint az aritmetikai műveletek mellett és szorzás .

Formális meghatározás

Egy áramkör egy hármas , ahol ${\ displaystyle (M, L, G)}$

• ${\ displaystyle M}$ értékek halmaza,
• ${\ displaystyle L}$egy sor kapu címkék, amelyek mindegyike egy funkciót , hogy néhány nem negatív egész szám (ahol a számát jelenti, a bemenetek a kapu), és${\ displaystyle M^{i}}$${\ displaystyle M}$${\ displaystyle i}$${\ displaystyle i}$
• ${\ displaystyle G}$egy címkézett irányított aciklikus gráf , címkék innen .${\ displaystyle L}$

A gráf csúcsait kapuknak nevezzük . Minden egyes kapu az in-fokos , a kapu jelölhetjük egy eleme a , ha, és csak akkor, ha van definiálva . ${\ displaystyle g}$ ${\ displaystyle i}$${\ displaystyle g}$${\ displaystyle \ ell}$${\ displaystyle L}$${\ displaystyle \ ell}$${\ displaystyle M^{i}}$

Terminológia

A 0 fokos kapukat bemeneteknek vagy leveleknek nevezzük . A 0 fokú kapukat kimeneteknek nevezzük . Ha van egy él kaputól kapuig a grafikonon , akkor nevezzük gyerek az . Feltételezzük, hogy a gráf csúcsain van egy sorrend, tehát akkor beszélhetünk egy kapu harmadik gyermekéről, amikor kisebb, mint a kapu külső foka. ${\ displaystyle g}$${\ displaystyle h}$${\ displaystyle G}$${\ displaystyle h}$${\ displaystyle g}$${\ displaystyle k}$${\ displaystyle k}$

Az áramkör mérete az áramkör csomópontjainak száma. A mélysége egy kapu hossza a leghosszabb út a kezdődő akár egy kimeneti kaput. Különösen a 0 fokos kapuk jelentik az 1 mélység egyetlen kapuját. Az áramkör mélysége bármely kapu maximális mélysége. ${\ displaystyle g}$${\ displaystyle G}$${\ displaystyle g}$

A szint${\ displaystyle i}$ a mélység minden kapujának halmaza . A kiegyenlített áramkör olyan áramkör, amelyben a mélységkapuk élei csak a mélységkapukból vagy a bemenetekből származnak. Más szóval, az élek csak az áramkör szomszédos szintjei között léteznek. A kiegyenlített áramkör szélessége minden szint maximális mérete. ${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle i+1}$

Értékelés

A fokozattal és címkével ellátott kapu pontos értékét rekurzívan határozzák meg minden kapu esetén . ${\ displaystyle V (g)}$${\ displaystyle g}$${\ displaystyle i}$${\ displaystyle l}$${\ displaystyle g}$

${\ displaystyle V (g) = {\ begin {case} l & {\ text {if}} g {\ text {is a input}} \\ l (V (g_ {1}), \ dotsc, V (g_ {i})) & {\ text {egyébként,}} \ end {case}}}$

ahol mindegyik szülő . ${\ displaystyle g_ {j}}$${\ displaystyle g}$

Az áramkör értéke az egyes kimeneti kapuk értéke.

Áramkörök mint funkciók

A levelek címkéi is változók lehetnek, amelyek értékeket vesznek fel . Ha vannak levelek, akkor az áramkör lehet tekinteni, mint egy funkciót a . Ilyenkor szokásos a család áramkörök egy sorozat áramkörök által indexelt egészek, ahol az áramkör van változókat. Családok áramkörök Látható tehát, mint funkciók az . ${\ 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}$

A fogalmak mérete, mélysége és szélessége is természetesen kiterjeszthető családok funkciók egyre funkciók az ; például a család ötödik körének mérete . ${\ displaystyle \ mathbb {N}}$${\ displaystyle \ mathbb {N}}$${\ displaystyle size (n)}$${\ displaystyle n}$

Összetett és algoritmikus problémák

Egy adott Boole-áramkör kimenetének kiszámítása egy adott bemenetre P-teljes probléma. Ha a bemenet egész kör , akkor nem ismert, hogy ez a probléma eldönthető -e .

Az áramkör összetettsége megpróbálja osztályozni a Boole -függvényeket a számításukra alkalmas áramkörök mérete vagy mélysége alapján.

Lásd még

• Az áramkör összetettsége
• Áramkörök természetes számok halmazán
• Az NC , AC és TC komplexitási osztályok
• Quantum áramkör és BQP

Hivatkozások

• Vollmer, Heribert (1999). Bevezetés az áramkör komplexitásába . Berlin: Springer. ISBN 978-3-540-64310-4.
• Yang, Ke (2001). "Integer Circuit Evaluation Is PSPACE-Complete" . Journal of Computer and System Sciences . 63 (2, 2001. szeptember): 288–303. doi : 10.1006/jcss.2001.1768 . ISSN  0022-0000 .