Direkt zum Inhalt | Direkt zur Navigation

Sektionen
Benutzerspezifische Werkzeuge
Sie sind hier: Startseite Willkommen Professuren Ordentliche Professuren Theoretische Informatik Lehrveranstaltungen Sommersemester 2012 Theoretische Informatik II

Theoretische Informatik II

  • Prüfung-Klausur am 19.07.2012, 10:00-14:00 Uhr, HPI Hörsäle 1,2 und 3
  • Vorlesung, Dr. rer. nat. Richter, Fr. 08:00-10:00, HPI.HS1
  • Tutorium, N.Brede, Do. 10:30-12:00, HPI.HS1
  • Übung, Mario Frank, Mo. 09:00-11:00, HPI.A-1.2
  • Übung, Malte Swart, Mo. 09:00-11:00, HPI.A-1.1
  • Übung, Hannes Schröder, Mo. 13:00-15:00, HPI.A-2.2
  • Übung, Michael Görner, Mo. 13:00-15:00, HPI.A-2.1
  • Übung, Anna Melzer, Di. 10:00-12:00, 3.04.0.02
  • Übung, Margrit Dittmann, Di. 12:00-14:00, 3.04.0.02
  • Übung, Charlotte Gerlitz, Mi. 10:00-12:00, 3.04.0.02
  • Übung, Alexander Schulze, Mi. 18:00-20:00, 3. HPI H2.51

Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.

Die Automatentheorie und die Theorie der formalen Sprachen (Thema des ersten Semesters) ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.

Die Berechenbarkeitstheorie befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen.

Die Komplexitätstheorie untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

Gliederung der Theoretischen Informatik II

  • Berechenbarkeitstheorie 
    • Turingmaschinen
    • Algorithmen,  Churchsche These und Lambda-Kalkül 
    • Entscheidbarkeit:entscheidbare Sprachen, Halteproblem,  nicht Turing-akzeptierbare Sprachen
    • Reduzierbarkeit: unentscheidbare Probleme, Post'sches Korrespondenzproblem,
      Abbildungsreduzierbarkeit
    • Rekusionssatz, Entscheidbarkeit logischer Theorien
  • Komplexitätstheorie
    • Zeitkomplexität und Platzkomplexität: Hierarchiesätze
    • Klassen P und NP, Polynomielle Reduzierbarkeit,
    • NP-vollständige Probleme
    • Satz von Cook
    • Probabilistische Algorithmen

Literatur

  • Michael Sipser: Introduction to the Theory of Computation. 2. Auflage, PWS 2005, (Leitbuch  für die Vorlesung mit gleicher Notation)
  • J. Hopcroft, R. Motwani, J. Ullman: Einfuehrung in die Automatentheorie, Formale Sprachen und Komplexitaetstheorie, Pearson 2002
  • Jörg Rothe: Komplexitätstheorie und Kryptologie, Springer-Verlag 2008
Artikelaktionen
Auf einen Blick
Lehrform diverse Formen
Empfohlen ab FS 4
Voraussetzungen Erfolgreiche Teilnahme an Theoretische Informatik I ist sehr zu empfehlen.
Benotet Ja
Punkte gesamt 6
davon praktisch 0
Sprache deutsch
Fremdhörer zugelassen? Nein
Teilgebiete Theoretische Informatik(2000), Wahlfrei(7000)
Studiengang Bachelor
Belegung via PULS