Theoretische Informatik I (3. Semester) (Wintersemester 2004/2005)
Dozent:
Website zum Kurs:
http://www.cs.uni-potsdam.de/~lbudach/AnkuendigungTI04b.htm
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 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)
Voraussetzungen
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.
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. 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.
Termine
Vorlesung: Mo 15.15-16.45 Uhr, HPI HS 2
Vorlesung oder Übung: Di 11.00-12.30 Uhr, HPI HS 3
Zurück