edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Clemens Gröpl
Titel: Binary Decision Diagrams for Random Boolean Functions
Gutachter: Anand Srivastav; Hans Jürgen Prömel; Ingo Wegener
Erscheinungsdatum: 03.05.1999
Volltext: pdf (urn:nbn:de:kobv:11-1008985)
ps (urn:nbn:de:kobv:11-1008996)
Fachgebiet(e): Informatik
Schlagwörter (ger): Binäres Entscheidungsdiagramm, Boolesche Funktion, probabilistische Analyse, Shannon Effekt
Schlagwörter (eng): Binary decision diagram, Boolean function, probabilistic analysis, Shannon effect
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Gröpl, Clemens: Binary Decision Diagrams for Random Boolean Functions; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 03.05.1999, urn:nbn:de:kobv:11-1008996
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Binary Decision Diagrams (BDDs) sind eine Datenstruktur für Boolesche Funktionen, die auch unter dem Namen branching program bekannt ist. In ordered binary decision diagrams (OBDDs) müssen die Tests einer festen Variablenordnung genügen. In free binary decision diagrams (FBDDs) darf jede Variable höchstens einmal getestet werden. Die Effizienz neuer Varianten des BDD-Konzepts wird gewöhnlich anhand spektakulärer (worst-case) Beispiele aufgezeigt. Wir verfolgen einen anderen Ansatz und vergleichen die Darstellungsgrößen für fast alle Booleschen Funktionen. Während I. Wegener bewiesen hat, daß für die `meisten' n die erwartete OBDD-Größe einer zufälligen Booleschen Funktion von n Variablen gleich der worst-case Größe bis auf Terme kleinerer Ordnung ist, zeigen wir daß dies nicht der Fall ist für n innerhalb von Intervallen konstanter Länge um die Werte n = 2h + h. Ferner gibt es Bereiche von n, in denen minimale FBDDs fast immer um mindestens einen konstanten Faktor kleiner sind als minimale OBDDs. Unsere Hauptsätze ha ben doppelt exponentielle Wahrschein- lichkeitsschranken (in n). Außerdem untersuchen wir die Entwicklung zufälliger OBDDs und ihrer worst-case Größe und decken dabei ein oszillierendes Verhalten auf, das erklärt, warum gewisse Aussagen im allgemeinen nicht verstärkt werden können.
Abstract (eng):
Binary Decision Diagrams (BDDs) are a data structure for Boolean functions which are also known as branching programs. In ordered binary decision diagrams (OBDDs), the tests have to obey a fixed variable ordering. In free binary decision diagrams (FBDDs), each variable can be tested at most once. The efficiency of new variants of the BDD concept is usually demonstrated with spectacular (worst-case) examples. We pursue another approach and compare the representation sizes of almost all Boolean functions. Whereas I. Wegener proved that for `most' values of n the expected OBDD size of a random Boolean function of n variables is equal to the worst-case size up to terms of lower order, we show that this is not the case for n within intervals of constant length around the values n = 2h + h. Furthermore, ranges of n exist for which minimal FBDDs are almost always at least a constant factor smaller than minimal OBDDs. Our main theorems have doubly exponentially small probability bounds (in n). We also investigate the evolution of random OBDDs and their worst-case size, revealing an oscillating behaviour that explains why certain results cannot be improved in general.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 2 Zugriffe PDF: 1 Zugriffe Startseite: 1 Zugriffe PDF: 6 Zugriffe Startseite: 4 Zugriffe PDF: 2 Zugriffe PDF: 2 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe Startseite: 1 Zugriffe PDF: 4 Zugriffe Startseite: 1 Zugriffe PDF: 4 Zugriffe PDF: 5 Zugriffe PDF: 5 Zugriffe Startseite: 2 Zugriffe PDF: 2 Zugriffe Startseite: 3 Zugriffe PDF: 10 Zugriffe PDF: 3 Zugriffe PDF: 3 Zugriffe PDF: 3 Zugriffe PDF: 3 Zugriffe Startseite: 5 Zugriffe PDF: 13 Zugriffe Startseite: 5 Zugriffe PDF: 17 Zugriffe Startseite: 1 Zugriffe PDF: 16 Zugriffe PDF: 6 Zugriffe Startseite: 1 Zugriffe PDF: 15 Zugriffe Startseite: 4 Zugriffe PDF: 12 Zugriffe Startseite: 3 Zugriffe PDF: 7 Zugriffe Startseite: 5 Zugriffe PDF: 8 Zugriffe Startseite: 1 Zugriffe PDF: 4 Zugriffe Startseite: 7 Zugriffe PDF: 12 Zugriffe Startseite: 4 Zugriffe PDF: 10 Zugriffe Startseite: 7 Zugriffe PDF: 11 Zugriffe Startseite: 4 Zugriffe PDF: 7 Zugriffe Startseite: 1 Zugriffe PDF: 16 Zugriffe PDF: 18 Zugriffe Startseite: 3 Zugriffe PDF: 13 Zugriffe Startseite: 3 Zugriffe PDF: 11 Zugriffe Startseite: 2 Zugriffe PDF: 18 Zugriffe Startseite: 3 Zugriffe PDF: 16 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Startseite 2 1 4   2 1 1     2 3         5 5 1   1 4 3 5 1 7 4 7 4 1   3 3 2 3
PDF 1 6 2 2 6 4 4 5 5 2 10 3 3 3 3 13 17 16 6 15 12 7 8 4 12 10 11 7 16 18 13 11 18 16

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 75 (2.14 pro Monat)
  • PDF – 289 (8.26 pro Monat)
 
 
Generiert am 27.08.2014, 04:44:58