[Home]  [Ebene höher]  [Seitenende]  [Suchen]  [Kontakt]

Animationen Anmeldung Das akademische Ehrenprinzip Millennium Prizes (1 Mio. USD for P=NP) Prüfungsleistungen Skript (mit Übungen, PDF) Skript (mit Übungen, Postscript) Übungen Umfragebogen Vorlesungen Der Kummerkasten   Informatik III Typ: Einführende Vorlesung Veranstalter: Prof. Dr. Thomas Ottmann Mitwirkung: Dr. Stefan Edelkamp Bernhard Seckinger Zeit und Ort: Mi, Fr   09-11   (Geb. 101, HS 00-036) Beginn: Fr, 20. Oktober 2000 Die Vorlesung gibt eine Einführung in die Theoretische Informatik. Sie führt in die Themen Endliche Automaten, Formale Sprachen und Grammatiken ein und liefert mehrere äquivalente präzise Fassungen des Berechenbarkeitsbegriffs. Es schliesst sich eine Einführung in die Komplexitätstheorie, speziell die Theorie der NP-Vollständigkeit, an. Behandelt werden abstrakte Modelle von Maschinen und Sprachen und mit ihrer Hilfe werden Komplexitätsmaße wie Schrittzahl (Laufzeit) und Speicherbedarf von Algorithmen präzise definiert. Der Inhalt der Vorlesung wird in zahlreichen Lehrbüchern behandelt. Wir orientieren uns an den Büchern: Michael Sipser: Introduction to the Theory of Computation, PWS Publishing, 1997, ISBN/ISSN: 0-534-94728-X Uwe Schöning: Theoretische Informatik - kurzgefasst, Spektrum Hochschultaschenbuch, 3. Auflage, 1997, ISBN 3-8274-0250-6, Spektrum Akademischer Verlag, Heidelberg Jürgen Albert, Thomas Ottmann: Automaten, Sprachen und Maschinen für Anwender, BI Wissenschaftsverlag, Mannheim 1982, ISBN 3-411-01651-5 Die Vorlesung wird durch Übungen ergänzt.

[Seitenanfang]