Beschreibungskomplexität

Sommersemester 2010

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.

Skriptum

Folien: Teil 1, Teil 2

Informationen:

Stundenplan laut Univis

Zurück zur Lehreseite der Forschungsgruppe Theoretische Informatik

Webmaster