Beschreibungskomplexität

Sommersemester 2008


Lehrbeauftragter: Prof. Dr. Jürgen Dassow, Dr. Bianca Truthe
Wochenstunden: 4+0+0
Zuhörerkreis: Hauptstudium IF;i, DKE
Voraussetzungen: Grundlagen der Theoretischen Informatik
Prüfung bzw. Scheinerwerb: jeweils durch eine mündliche Prüfung von 20-30 Minuten

Inhalt:

Formale Definition von Schaltkreisen über Graphen; Realisierung von Booleschen Funktionen durch Schaltkreise; Komplexitätsmaße für Schaltkreise, wie Anzahl der Schaltelemente, Tiefe des Schaltkreises, Formellänge; Zusammenhang zwischen den Komplexitätsmaßen; obere und untere Abschätzungen für die Komplexitätsmaße; andere Realisierungen von Booleschen Funktionen und zugehörige Komplexitätsmaße;
Syntaktische Komplexitätsmaße für Automaten (Anzahl der Zustände) und Grammatiken (Anzahl der Nichtterminale, Regeln etc.); Komplexität der Sprachen als minimale Komplexität des akzeptierenden Automaten bzw. der generierenden Grammatiken; Sprachen beliebig hoher Komplexität; Minimierung von Automaten und Grammatiken.

Scriptum:

Folien:

Informationen:

Stundenplan laut Univis


Bernd Reichel