Links und Funktionen
Sprachumschaltung

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


Inhaltsbereich

Theoretische Informatik für Medieninformatiker

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

Aktuelles

    • Die Klausureinsicht findet am Di 17.09. von 15 - 17 Uhr im Raum L 109 (Oettingenstr. 67) statt.
    • Die Nachholklausur findet am 24.10. um 18 Uhr im Hörsaal M 118 (Hauptgebäude) statt.

    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:  Olivia Hofer, Alexander Koos, Sascha Oberhuber
    • Hausaufgaben sind einzeln abzugeben, sie werden korrigiert und bewertet. Die Lösungen können über UniWorx oder vor der Vorlesung auf Papier abgegeben werden, im zweiten Fall ist bei UniWorx eine leere Lösung abzugeben und die Lösungs-ID auf dem Blatt zu vermerken.
      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%).
      Plagiate bei der Lösung der Hausaufgaben werden mit der Nichtwertung des gesamten Blattes geahndet. Im Wiederholungsfall können weitergehende Sanktionen in Erwägung gezogen werden.

    Zeit und Ort

    VeranstaltungZeitOrtBeginn
    Vorlesung & Übung Di, 14:15 - 16:45 Uhr Hörsaal 004 (Schellingstr. 3) 16.04.2013

    Material zur Vorlesung

    Annotierte Vorlesungsfolien

    Die Vorlesung wird für die Unterrichtsmitschau auf Video aufgezeichnet, die Videoaufzeichnungen sind teilweise bereits online.

    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.


    Klausur

    Die Klausur fand am 31.07. um 14 Uhr c.t. in den Hörsälen B 051 und B 052 (Theresienstr. 39) statt.

    Die Nachholklausur findet am 24.10. um 18 Uhr c.t. im Hörsaal M 118 (Hauptgebäude) statt. Bitte melden Sie sich zur Klausur bei UniWorx bis zum 6.10. an. Eine Abmeldung ist bis zum 20.10. möglich.

    Artikelaktionen


    Funktionsleiste