Formale Sprachen und Komplexität

Description

Die Veranstaltung “Theoretische Informatik für Medieninformatiker (TIMI)” aus früheren Semestern wird im SS20 in diese Veranstaltung (FSK) integriert und ist entsprechend anrechenbar.

Inhalt

Das Modul vermittelt Grundkenntnisse in den Gebieten Formale Sprachen, Berechenbarkeit und Komplexitätstheorie. Im einzelnen werden vermittelt:

  • Automatentheorie und Formale Sprachen: Chomsky-Hierarchie, reguläre Sprachen und endliche Automaten, kontextfreie Sprachen und Kellerautomaten, kontextsensitive Sprachen,
  • Berechenbarkeit: Turingmaschinen und andere Berechnungsmodelle, Unentscheidbarkeit, Halteproblem, rekursiv aufzählbare Probleme,
  • Komplexitätstheorie, insbesondere die Klassen P und NP, Definition und Beweise für NP-Vollständigkeit, Beispiele NP-vollständiger Probleme.

Literaturhinweise:

  • Theoretische Informatik kurzgefasst, Uwe Schöning, Spektrum Hochschultaschenbuch, ISBN 978-3-8274-1824-1

Das Modul besteht aus einer Vorlesung sowie Übungen in kleinen Gruppen. Die in der Vorlesung besprochenen Inhalte werden im Übungsteil anhand von praktischen Anwendungen eingeübt.

Links zu Veranstaltungen aus frühreren Semestern:

Videoaufzeichnung aus früheren Semestern:

Department
Institut für Informatik
Lecturer
Assistants
Course participants
0
Enrolment

Wed 01 Apr 2020 00:00 – Wed 30 Sep 2020 23:59

Deregistration only until Wed 30 Sep 2020 23:59

Material
Only course participants may access course material
Occurrences
TypeTimeRegular room
Vorlesung
  • Tue 14:00–17:00
Geschwister-Scholl-Platz 1, M018
Tutorials
TypeNameTutorsRegular roomTimeRegister fromRegister toDeregister untilFree capacity
Übung
Gruppe 01
    Professor-Huber-Platz 02, VU104
    • Mon 10:00–12:00
    50
    Übung
    Gruppe 02
      Professor-Huber-Platz 02, VU104
      • Mon 14:00–16:00
      50
      Übung
      Gruppe 03
        Professor-Huber-Platz 02, VU104
        • Mon 16:00–18:00
        50
        Übung
        Gruppe 04
          Geschwister-Scholl-Platz 1, A119
          • Wed 16:00–18:00
          50
          Übung
          Gruppe 05
            Geschwister-Scholl-Platz 1, A120
            • Thu 16:00–18:00
            50