Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Einführung in die Informatik IV (SS94)

Dozent: Prof. Dr. Ernst W. Mayr Zeit und Ort: Mo 10:00 - 12:00, Hörsaal S0320 Fr 08:00 - 10:00, Hörsaal N1190 Übung 3 SWS Übung zur Vorlesung Inhalt: Endliche Automaten, reguläre Sprachen Endliche Automaten Reguläre Ausdrücke Reguläre Sprachen Abschlußeigenschaften regulärer Sprachen Konstruktion minimaler endlicher Automaten Grammatiken, die Chomsky-Hierarchie Phrasenstrukturgrammatiken Chomsky-0-Sprachen Chomsky-1-Sprachen Chomsky-3-Sprachen Kontextfreie Grammatiken und Sprachen Grundlagen Chomsky-Normalform CYK-Algorithmus Pumping/Ogden's Lemma Algorithmen für kontextfreie Sprachen Greibach-Normalform Kellerautomaten Kellerautomaten und kontextfreie Sprachen Deterministische Kellerautomaten Berechenbarkeit, Entscheidbarkeit Church'sche These Aufzählbarkeit Gödelisierung von Turingmaschinen Unentscheidbarkeit Anwendung für kontextfreie Sprachen Primitive Datenstrukturen und Algorithmen Grundlegende Datentypen Hash-Tabellen, Streuspeicherung Einfache Sortierverfahren Heapsort Untere Schranke Suchbäume Natürliche binäre Suchbäume Balancierte Binärbäume Höhenbalancierte Binärbäume (AVL) Vorrangwarteschlangen, Binomial Queues Kürzeste Pfade (Dijkstra) Zusammenhang, Transitive Hülle (Warshall) Union-Find Strukturen Minimale Spannbäume (Kruskal) NP-Vollständigkeit Kurze Wiederholung und Geschichte Grundlagen Die NP-Vollständigkeit von SAT Weitere NP-vollständige Probleme Skript: Postscript-Datei. Zu finden unter Skripten. Literatur: John E. Hopcroft, Jeffrey D. Ullman Introduction to automata theory, languages, and computation Addison-Wesley Publishing Company, Reading MA, 1979 Uwe Schöning Theoretische Informatik kurz gefaßt B.I., Mannheim-Leipzig-Wien-Zürich, 1992 Ingo Wegener Theoretische Informatik B.G. Teubner, Stuttgart 1993 Sprechstunde: siehe hier