Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2012 / Theoretische Informatik für Medieninformatiker


Inhaltsbereich

Theoretische Informatik für Medieninformatiker

Lehrveranstaltung, 3-std., Di 14-17 Uhr, Johannsen


Inhalt

Es wird eine Einführung in die zentralen Konzepte und Ergebnisse der Theoretischen Informatik gegeben, mit Anwendungsbeispielen. Die folgenden Themen werden vertiefend behandelt:

  1. Automaten und Formale Sprachen
    Deterministische und nicht-deterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, Pushdown-Automaten
  2. Berechenbarkeit
    Turing-Maschinen, Church'sche These, Unentscheidbarkeit, Halteproblem, Reduktion
  3. Komplexitätstheorie
    Die Klassen P und NP, NP-vollständige Probleme

Organisation

  • Umfang: 3 Semesterwochenstunden
  • Vorlesung & Übung: Dr. Jan Johannsen
  • Korrektoren: Benjamin Eder, Zara Martinetti, Sascha Oberhuber
  • Hausaufgaben sind einzeln abzugeben, sie werden korrigiert und bewertet. Wer bei den Hausaufgaben 50% der Punkte erreicht, erhält einen Bonus für die Klausur. Dabei entsprechen 100% der Übungspunkte einem Bonus in Höhe von einer von sechs Klausuraufgaben (ca. 16%).

Zeit und Ort

Veranstaltung Zeit Ort Beginn
Vorlesung & Übung
Di, 14:15 - 16:45 Uhr
Hörsaal 004 (Schellingstr. 3) 17.04.2012

Material zur Vorlesung

Annotierte Vorlesungsfolien

Die Vorlesungsfolien mit Anmerkungen waren hier erhältlich.

    Es gibt ein Forum zur Vorlesung auf die-informatiker.net, das von den Veranstaltern gelesen wird. Bitte nutzen Sie dies für Feedback und Fragen!

    Literatur

    • John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 2. Auflage, Pearson Studium, 2002.
    • Alexander Asteroth und Christel Baier: Theoretische Informatik, Pearson Studium 2002.
    • Uwe Schöning: Theoretische Informatik - kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008.

    Übungen

      Übungsblätter und Musterlösungen waren hier erhältlich.

       


      Klausur

      Die Klausur fand am Montag, den 23. Juli 2012 um 17 Uhr c.t. in den Hörsälen M 118 und M 105 im Hauptgebäude statt.

      Die Nachholklausur fand am Donnerstag, den 25. Oktober 2012 um 18 Uhr c.t. im Hörsaal B 001 in der Oettingenstraße 67 statt.

      Artikelaktionen


      Funktionsleiste