Devre (bilgisayar bilimi) - Circuit (computer science)

Olarak teorik bilgisayar biliminin , bir devre a, hesaplama modeli girdi değerleri hesaplar her biri kapıları bir dizisi ile devam ettiği fonksiyonu . Bu tür devreler , Boole devrelerinin genelleştirilmesini ve sayısal mantık devreleri için matematiksel bir model sağlar . Devreler, içerdikleri kapılar ve kapıların üretebileceği değerler ile tanımlanır. Örneğin, bir Boolean devrede değerler mantıksal değerleri ve devre içerir bağlaç , ayrılma ve olumsuzluk kapılar. Bir değerler tamsayı devresi olan bebekler arasında tamsayı ve girişler hesaplamak grubu birlik , resim kesişim ve resim tamamlayıcı , hem de aritmetik işlemler ilave ve çarpma .

Resmi tanımlama

Bir devre üçlüdür , burada

  • değerler kümesidir,
  • Bir fonksiyon, her biri kapı etiket, bir dizi için bir negatif olmayan bir tamsayı ( kapısı girişlerinin sayısını temsil eder), ve
  • a, etiketli yönlendirilmiş asiklik grafik gelen etiketlerle .

Grafiğin köşelerine kapılar denir . Her kapı için bir in-derece , kapı bir eleman tarafından etiketlenebilir arasında , ancak ve ancak tanımlanır .

terminoloji

0 dereceli kapılara girişler veya yapraklar denir . 0 derece dışı kapılara çıkışlar denir . Kapıdan bir kenar varsa kapısına grafikte sonra bir adlandırılır çocuk arasında . Grafiğin köşelerinde bir sıra olduğunu varsayıyoruz, bu nedenle kapının dış değerinden küçük olduğunda kapının inci çocuğu hakkında konuşabiliriz .

Boyutu , bir devrenin bir devre düğüm sayısı. Bir kapının derinliği uzunluğudur en uzun yolu içinde başlayan bir çıkış kapısına kadar. Özellikle, 0 dereceli kapılar, derinlik 1'in yegane kapılarıdır . Bir devrenin derinliği, herhangi bir kapının maksimum derinliğidir.

Seviye , tüm derinlik kapılarının kümesidir . Bir tesviye devre derinliği kapıları kenarları olan bir devredir derindeki kapılarından gelir veya girişlerden. Başka bir deyişle, kenarlar yalnızca devrenin bitişik seviyeleri arasında bulunur. Genişliği , bir tesviye devresinin herhangi bir seviyede maksimum boyutudur.

Değerlendirme

Dereceli ve etiketli bir geçidin tam değeri , tüm kapılar için özyinelemeli olarak tanımlanır .

her birinin ebeveyni olduğu yer .

Devrenin değeri, çıkış kapılarının her birinin değeridir.

Fonksiyon olarak devreler

Yaprakların etiketleri de değer alan değişkenler olabilir . Yapraklar varsa , devre 'den ' ye bir fonksiyon olarak görülebilir . Devrelerin bir aileyi düşünün sonra olağandır , devre tamsayılar tarafından dizine devrelerin dizisi vardır değişkenleri. Devre aileleri bu nedenle 'den ' ye kadar olan fonksiyonlar olarak görülebilir .

Boyut, derinlik ve genişlikte kavramları doğal işlevleri olma işlevleri ailelerine uzatılabilir için ; örneğin, ailenin inci devresinin boyutudur .

Karmaşıklık ve algoritmik problemler

Belirli bir girdi üzerinde belirli bir Boolean devresinin çıktısını hesaplamak , P-tam bir problemdir. Ancak giriş bir tamsayı devresi ise , bu sorunun karar verilebilir olup olmadığı bilinmemektedir .

Devre karmaşıklığı , Boole işlevlerini , onları hesaplayabilen devrelerin boyutuna veya derinliğine göre sınıflandırmaya çalışır .

Ayrıca bakınız

Referanslar

  • Vollmer, Heribert (1999). Devre Karmaşıklığına Giriş . Berlin: Springer. ISBN'si 978-3-540-64310-4.
  • Yang, Ke (2001). "Tamsayı Devresi Değerlendirmesi PSPACE-Tamamlandı" . Bilgisayar ve Sistem Bilimleri Dergisi . 63 (2 Eylül 2001): 288-303. doi : 10.1006/jcss.2001.1768 . ISSN  0022-0000 .