Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2021 / Formale Sprachen und Komplexität


Inhaltsbereich

Formale Sprachen und Komplexität

Vorlesung, 3+1-std., Sabel; Übungen 2-std., Barth

Aktuelles

 

  • Online-Hausarbeit: Angaben:
    Die Abgabesyntax für Grammatiken war nicht allgemein genug, deswegen wird sie erweitert zu:

      <Grammatik>                -> <Startsymbol> <Zeilenumbruch> <Produktion> {<Zeilenumbruch> <Produktion>}
      <Startsymbol>              -> start <Nichtterminal-Bezeichner>
      <Produktion>               -> <RegelLinks> -> \epsilon | (<RegelRechts> {|<RegelRechts>})
      <RegelLinks>               -> (<Terminal-Symbol> | <Nichtterminal-Bezeichner>) {<Leerzeichen> (<Terminal-Symbol> | <Nichtterminal-Bezeichner>)}
      <RegelRechts>              -> (<Terminal-Symbol> | <Nichtterminal-Bezeichner>) {<Leerzeichen> (<Terminal-Symbol> | <Nichtterminal-Bezeichner>)}
      <Nichtterminal-Bezeichner> -> (A|...|Z){a|...|z|A|...|Z|0|...|9}
      <Terminal-Symbol>          -> a|...|z|0|...|9
  • Online-Hausarbeit: Die Angaben wurden per Email verschickt, und die Abgabefrist um eine Stunde verlängert.
  • Online-Hausarbeit: Uns sind die Probleme mit uni2work bewusst, wir arbeiten an einer Lösung!
  • Backup-Variante des Materials verfügbar (hier)
  • Die Nachholprüfung ist für den 08.10.2021 von 8-14 Uhr als Online-Prüfung geplant.
  • Die Anmeldung zur Online-Hausarbeit ist hier möglich.
    Bitte beachten Sie die Fristen und Termine:
    • Anmeldung bis Mi 14 Jul 2021 23:59
    • Abmeldung bis Di 20 Jul 2021 23:59
    • Prüfung: Mi 21 Jul 2021 08:00
  • Verspätete Abgaben werden nicht mehr akzeptiert


    Ab inkl. dem aktuellen Übungsblatt 5 werden verspätete Abgaben außerhalb von Uni2work nicht mehr akzeptiert. Ebenso werden wir bei technischen oder anderweitigen Problemen mit der Abgabe nicht mehr nach der jeweiligen Abgabefrist helfen.
    Überprüfen Sie, dass Sie die korrekten Dateien hochgeladen haben und Sie diese auch wieder herunterladen und öffnen können. Bitte planen Sie dafür selbstständig einen zeitlichen Sicherheitsabstand vor dem Ende der Abgabefrist ein, damit Sie noch rechtzeitig reagieren können.
    Denken Sie auch daran, dass Sie vor der Abgabefrist so oft eine neue Lösung hochladen können, wie Sie wollen, es also nichts dagegen spricht, vorzeitig eine unvollständige Lösung hochzuladen. Falls Probleme auftreten, kontaktieren Sie uns frühzeitig.
  • Die Prüfung ist geplant am 21.07.2021 von 8-14 Uhr als Online-Prüfung (OpenBook-Exam). Details usw. folgen.
  • Melden Sie sich bei uni2work für die Veranstaltung an.

Inhalt

Die Vorlesung behandelt Grundlagen der theoretischen Informatik: Sie gibt Einführungen in die Theorie der formalen Sprachen und Automaten sowie in die Berechenbarkeits- und Komplexitätstheorie. Die Veranstaltung orientiert sich inhaltlich und strukturell am Lehrbuch von Schöning (Theoretische Informatik - kurz gefasst).


Organisation


Zeit und Ort

VeranstaltungZeitOrtBeginn
Vorlesung und Zentralübung Di 14-18 Uhr online 13.04.2021
Übung Mi 8-10 online 14.04.2021
Übung Mi 12-14 online 14.04.2021
Übung Do 10-12 online 15.04.2021
Übung Do 16-18 online 15.04.2021
Übung Fr 10-12 online 16.04.2021
Übung Fr 12-14 online 16.04.2021

Material

Literatur

  • [AB02] Alexander Asteroth und Christel Baier: Theoretische Informatik, Pearson Studium 2002.
  • [HMU06] John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3. Auflage, 2006
  • [IW05] Ingo Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 3.Auflage, Teubner Verlag, 2005.
  • [US08] Uwe Schöning: Theoretische Informatik - kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008.
  • ...

Nützliche Webseiten


TerminInhalte
13.04. Begrüßung, Einführung, Inhaltsübersicht, Grundlagen
Chomsky-Grammatiken und die Chomsky-Hierarchie
Grammatiken: Entscheidungsprobleme und Abschlusseigenschaften
20.04. Entfernen von Epsilon-Produktionen
Entscheidbarkeit des Wortproblems
Endliche Automaten: DFAs
27.04 DFAs, DFAs in Typ-3 Grammatiken umformen,NFAs
Typ-3-Grammatiken in NFAs, Determinisieriung (Potenzmengenkonstruktion)
Größe von DFAs und NFAs, NFAs mit Epsilon-Übergängen
04.05. NFAs mit Epsilon-Übergängen, reguläre Ausdrücke
Satz von Kleene
Pumping-Lemma
11.05. Nerode-Relation Satz von Myhill-Nerode, Nerode-Automat
DFA-Minimierung
Abschlusseigenschaften Typ 3-Sprachen, Entscheidbarkeiten bei Typ-3-Sprachen
18.05. CFLs: Normalformen und Abschlusseigenschaften
CFLs: Herstellen von Normalformen
Das Pumpinglemma für CFLs
25.05. CFLs: Wortproblem lösen mit dem CYK-Algorithmus
Kellerautomaten: Definition, Verwendung, Varianten
Äquivalenz von PDAs und CFLs
01.06. Deterministisch kontextfreie Sprachen
Turingmaschinen und Typ 1- und Typ 0-Sprachen
Entscheidbarkeiten bei CFLs und Kuroda-Normalform für CSLs
08.06. Beweise  des Satz von Kuroda, LBA-Probleme
Intuitive Berechenbarkeit,  Mehrspuren- und Mehrbandmaschinen
TM-Konstruktionen und LOOP-Programme
15.06. WHILE- und GOTO-Berechenbarkeit
Ackermannfunktion
Primitive Rekursion und mu-Rekursion
22.06. entscheidbar, semi-entscheidbar, rekursiv aufzählbar, Halteproblem
Satz von Rice,
Postsches Korrespondenzproblem
29.06. Laufzeitkomplexität, die Klassen P und NP,
NP-Vollständigkeit,
der Satz von Cook
06.07. NP-Vollständigkeit von 3-CNF-SAT,
NP-Vollständigkeit von CLIQUE, INDEPENDENT SET und VERTEX COVER,
NP-Vollst.v. SETCOVER, SUBSETSUM, KNAPSACK, PARTITION und BINPACKING
13.07. NP-Vollst. von HAMILTONCYCLE, TRAVELLINGSALESMAN und GRAPH-COLORING
Wiederholung und Fragestunde

Die Übungsblätter werden über Uni2work verteilt. Die Abgabe und Korrektur wird ebenfalls über Uni2work abgewickelt, die Abgabefrist ist jeweils auf dem Übungsblatt angegeben.


Klausur / Prüfung

Ersttermin für die Prüfung ist der 21.07.21 von 8-14 Uhr als Online-Prüfung (OpenBook-Exam).
Die Anmeldung zur Prüfung ist hier möglich.

  • Bitte beachten Sie die Fristen und Termine:
    • Anmeldung bis Mi 14 Jul 2021 23:59
    • Abmeldung bis Di 20 Jul 2021 23:59
    • Prüfung: Mi 21 Jul 2021 08:00

 

Die Nachholprüfung ist für den 08.10.2021 von 8-14 Uhr als Online-Prüfung geplant.

https://www.tcs.ifi.lmu.de/lehre/ss-2021/fsk/material/material/view

Artikelaktionen


Funktionsleiste