Theoretische Informatik II (Sommersemester 2005)

Dozent:

Allgemeine Information

Semesterwochenstunden: 4
ECTS: 6
Benotet: Ja
Einschreibefrist: 01.01.1970
Lehrform:
Belegungsart: Wahlpflichtmodul

Studiengänge

IT-Systems Engineering BA

Beschreibung

Der zweisemestrige Kurs "Theoretische Informatik" liefert eine Einführung in die grundlegenden Begriffe, Methoden und Ergebnisse der Theoretischen Informatik unter besonderer Berücksichtigung der Erfordernisse der Softwaresystemtechnik.

Von den traditionellen Gebieten der Theoretischen Informatik wurden und werden besonders diejenigen schwerpunktmäßig behandelt, die theoretisch die Grenzen des Programmierbaren abstecken und somit die Notwendigkeit der strukturierten Beschreibung großer, komplexer Systeme und der Kommunikation zwischen den Entwicklern von Teilsystemen beweisen. Dazu gehören:

Berechnungstheorie
Endliche Automaten, Akzeptoren, Syntaxanalyse, Algorithmen, Turing-Maschinen, Pushdown-Automaten, Zählermaschinen, Berechenbarkeit, Entscheidbarkeit, Unentscheidbarkeit, Aufzählbarkeit.
Komplexitätstheorie
O- und Omega-Notation, Zeit- und Platz-Komplexität, Untere Schranken, Determinismus versus Nichtdeterminismus, polynomiale Berechenbarkeit, NL- und NP-vollständige Probleme

Die traditionell in der Vorlesung "Theoretische Informatik" vermittelten Begriffsbildungen der Theorie der formalen Sprachen wie Reguläre Sprachen, kontextfreie und kontextsensitive Sprachen, Chomsky-Hierarchie, Grundlagen der Programmiersprachen, waren z.T. bereits Gegenstand der schon in den ersten beiden Semestern laufenden Vorlesung "Systeme und ihre Modellierung". Sie wurden im ersten Semester dieser Vorlesung in verkürzter Form behandelt. Statt dessen wurden und werden theoretische Problemstellungen im Umkreis des Entwurfs und der Spezifikation großer Systeme behandelt:

Theoretische Grundlagen der imperativen und objektorientierten Programmierung (erstes Semester)
Grenzen der Berechenbarkeit (zweites Semester)
Algebraische und konstruktive Spezifikation (zweites Semester)
Fragen der Korrektheit von Spezifikationen: Validierung und Verifizierung (zweites Semester)

Voraussetzungen

Die Vorlesung "Theoretische Informatik II" setzt die Beherrschung der im ersten Semester entwickelten Methoden sowie Kenntnisse voraus, wie sie etwa in einer einsemestrigen Vorlesung "Diskrete mathematische Strukturen" vermittelt werden (Elemente der Mengentheorie, abzählbare, überabzählbare Mengen, Relationen, Relationenkalkül, Funktionen als Spezialfälle von Relationen, teilweise geordnete Mengen, Graphen). In der Vorlesung werden diese Grundkenntnisse, soweit erforderlich, noch einmal wiederholt.

Literatur

Allgemeine Grundlagen

A. V. Aho, J.D. Ullman, Informatik, Datenstrukturen und Konzepte der Abstraktion (Intern. Thomson Publ. 1996).
A. V. Aho, J.E.Hopcroft, J.D. Ullman, Data Structures and Algorithms (Addison-Wesley 1983).

Berechnungstheorie und Komplexität

Ergänzungen aus der Theorie der formalen Sprachen und endlichen Automaten

N. Blum, Theoretische Informatik: Eine anwendungsorientierte Einführung (München, Wien, Oldenburg, 1998).
J. E. Hopcroft, R. Motvani, J. D. Ullman, Introduction to automata theory, languages and computation (Addison-Wesley Boston, San Francisco, New York, London, Toronto, Sydney, Tokyo, Singapore, Madrid, Mexico City, Munich, Paris, Cape Town, Hong Kong, Montreal, 2001).
K. Erk, L. Priese, Theoretische Informatik: Eine umfassende Einführung (Springer-Verlag, Berlin, Heidelberg, New York, Barcelona, Hongkong, London, Mailand, Paris, Singapur, Tokyo 2000).
F. Stetter, Grundbegriffe der Theoretischen Informatik (Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo 1988).
U. Schöning, Theoretische Informatik kurz gefasst (BI-Wiss.-Verlag, Mannheim, Leipzig, Wien, Zürich, 1992).
K. W. Wagner, Einführung in die Theoretische Informatik (Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo 1991).
I. Wegener, Theoretische Informatik: Eine algorithmenorientierte Einführung (Teubner, Stuttgart 1993).
A. Asteroth, Ch. Baier, Theoretische Informatik, Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen (Pearson Studium, München 2002)

Leistungserfassung

Für die Belegung der Vorlesung sind 6 Belegungspunkte zu entrichten. Ein erfolgreicher Abschluss wird mit 6 benoteten Leistungspunkten bestätigt. Die Belegungsfrist endet am 26. April 2005.
In jeder Woche werden in der Übung zur Vorlesung Übungsaufgaben gestellt und erläutert. In der darauf folgenden Woche werden die Aufgaben besprochen. Die Lösungen werden von Dr. Wilhelm im Netz veröffentlicht. Die Übungsaufgaben bilden die Basis für die Klausuren.
Im Laufe des Semesters werden zwei Klausuren geschrieben, die jeweils 90 Minuten dauern. Der Modus der Duchführung der Klausuren und der erwartete Wissensumfang werden eine Woche vorher in der Vorlesung mitgeteilt.
Für alle Klausuraufgaben wird die Zahl der erreichbaren Punkte vorgegeben. Die Klausurnorm wird auf der Basis der Gesamtzahl der von den besten Studenten erreichten Punkte definiert. Der Quotient aus der Gesamtzahl der erreichten Punkte und der Klausurnorm ist Basis für die (algorithmisch definierte) Festlegung der Benotungsinformation der Leistungspunkte.
Ist die erhaltene Note schlechter als 4,0, wird kein Leistungspunkt vergeben. Nur in diesem Fall kann auf Antrag eine mündliche Prüfung durchgeführt werden, um die Benotungsinformation auf 4,0 zu erhöhen und die Vergabe der Leistungspunkte zu ermöglichen.

Termine

Vorlesung: Mo 9.15-10.45 Uhr, HPI HS 1, Mi 13.30-15.00, HPI HS 1

Übung: Mo 11.00-12.30 Uhr, HPI HS 1

Zurück