Hasso-Plattner-Institut
Hasso-Plattner-Institut
  
Login
  • de
 

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

Dozent:
Website zum Kurs: http://www.cs.uni-potsdam.de/~lbudach/AnkuendigungTI04b.htm

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

Allgemeine Information

  • Semesterwochenstunden : 4
  • ECTS : 6
  • Benotet : Ja
  • Einschreibefrist : 01.01.1970
  • Programm : IT-Systems Engineering BA
  • Lehrform :
  • Belegungsart : Wahl

Zurück