Letztes Semester

Formale Sprachen und Berechenbarkeit

Dozent:innen: Univ.-Prof. Dr. Ernst Althaus
Kurs-Nr.: 08.079.050
Kurstyp: Vorlesung/Übung

Empfohlene Literatur


  1. Dirk Hoffmann: Theoretische Informatik
  2. Asteroth/Baier: Theoretische Informatik
  3. Schöning: Theoretische Informatik - kurz gefaßt
  4. Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie
  5. Priese, Erk: Theoretische Informatik - Eine umfassende Einführung

Inhalt


  1. Mathematische Grundlagen
  2. Formale Sprachen
    3. [list]
  3. Reguläre Sprachen und endliche Automaten
  4. Kontextfreie Sprachen und Kellerautomaten

  • Berechenbarkeit

    1. Turing-Maschine als Berechnungsmodell
    2. Weitere Berechnungsmodelle und Äquivalenz zur TM
    3. Church’s-These: TM-Berechenbarkeit stimmt mit der intuitiven Definition von Berechenbarkeit überein
    4. Unentscheidbare Probleme

    [/list]

    Termine

    Datum (Wochentag) Zeit Ort
    18.04.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    25.04.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    02.05.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    09.05.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    16.05.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    23.05.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    30.05.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    06.06.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    13.06.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    20.06.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    27.06.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    04.07.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    11.07.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut
    18.07.2023 (Dienstag) 10:00 - 12:00 00 212 S 1
    1534 - Hörsaalgebäude Sportinstitut