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
Examinations and Interviews for Credits ("Schein") will be on August 2 and September 20, 2004.
Registrations are possible in the lecture or directly at B. Reichel.