Theoretische Informatik I (3. Semester) (Wintersemester 2004/2005)

Lecturer:
Course Website: http://www.cs.uni-potsdam.de/~lbudach/AnkuendigungTI04b.htm

General Information

Weekly Hours: 4
Credits: 6
Graded: yes
Enrolment Deadline: 01.01.1970
Teaching Form:
Enrolment Type: Compulsory Elective Module

Programs

IT-Systems Engineering BA

Description

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 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
Algorithmen, Turing-Maschinen, Register-Maschinen, Rekursive Funktionen, 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, Endliche

Automaten, Pushdown-Automaten, Akzeptoren, Syntaxanalyse waren z.T. bereits

Gegenstand der schon in den ersten beiden Semestern laufenden Vorlesung "Systeme

und ihre Modellierung". Sie werden also nur verkürzt oder gar nicht in die

"Theoretische Informatik" aufgenommen. Statt werden theoretische

Problemstellungen im Umkreis des Entwurfs und der Spezifikation großer Systeme

behandelt:

Theoretische Grundlagen der imperativen und objektorientierten Programmierung
Grenzen der Berechenbarkeit
Algebraische und konstruktive Spezifikation (zweites Semester)
Komplexitätstheoretische Schranken des Entwurfs großer Softwaresysteme (zweites Semester)
Theoretische Prinzipien der Gestaltung von Softwarearchitekturen (zweites Semester)
Fragen der Korrektheit von Spezifikationen: Validierung und Verifizierung (zweites Semester)

Requirements

Die Vorlesung "Theoretische Informatik I" setzt 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 noch einmal wiederholt.

Literature

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)

Examination

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. Oktober 2004.
In jeder Woche werden am Dienstag Übungsaufgaben gestellt und erläutert. Lösungen werden von Dr. Wilhelm eine Woche später im Netz veröffentlicht. Die Übungsaufgaben bilden die Basis für die Klausuren. Die Lösungen der Studenten werden mit Punkten bewertet. Für die Zulassung zur Klausur müssen wenigstens 60% der Sollpunktzahl erreicht werden.
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.

Dates

Vorlesung: Mo 15.15-16.45 Uhr, HPI HS 2

Vorlesung oder Übung: Di 11.00-12.30 Uhr, HPI HS 3

Zurück