Beschreibungskomplexität

Wintersemester 2006/2007

Lehrbeauftragter: Prof. Dr. Jürgen Dassow, Dr. Bernd Reichel
Wochenstunden: 4+0+0
Zuhörerkreis: Hauptstudium Informatik, DKE
Voraussetzungen: Einführung in die Theoretische Informatik, insbesondere Grammatiken und Sprachen
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