Links und Funktionen
Sprachumschaltung

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


Inhaltsbereich

Theoretische Informatik für Medieninformatiker

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

 


Aktuelles

     


    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
    • Korrektor: Sinisa Kurtusic
    • Hausaufgaben sind einzeln abzugeben, sie werden korrigiert und bewertet. Wer bei den Hausaufgaben 40% 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 005 (Schellingstr. 3) 03.05.2011

    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 Samstag, den 30.07. um 10 Uhr c.t. in den Hörsälen B 101 und A 140 im Hauptgebäude statt.

        Die Wiederholungsklausur fand am Freitag, den 21.10. um 16 Uhr c.t. im Hörsaal B 101 im Hauptgebäude statt.

        Artikelaktionen


        Funktionsleiste