Links und Funktionen
Sprachumschaltung

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


Inhaltsbereich

Theoretische Informatik für Medieninformatiker

Vorlesung, 2-std., Sabel; Übungen 1-std., Kleen

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

Es wird eine Einführung in die zentralen Konzepte und Ergebnisse der Theoretischen Informatik gegeben, mit Anwendungsbeispielen. Themen sind:

  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


Zeit und Ort

VeranstaltungZeitOrtBeginn
Vorlesung Di, 14-16 & 16-18 online 13.04.2021
Übung Mi 16-17 online 14.04.2021
Übung Do 9-10 online 16.04.2021


Material

Das Vorlesungsskript, die Vorlesungsfolien, die Übungsblätter und die Videos sind im Materialbereich in Uni2Workzu finden. Ein Backup als zip-Archive ist hier zu finden. Videos als große Playlisten sind hier zu finden:

 

TerminInhalte
13.04. Begrüßung, Einführung, Inhaltsübersicht, Grundlagen
Chomsky-Grammatiken und die Chomsky-Hierarchie
20.04. Grammatiken: Entscheidungsprobleme und Abschlusseigenschaften
Endliche Automaten: DFAs
27.04 DFAs, DFAs in Typ-3 Grammatiken umformen,NFAs
Typ-3-Grammatiken in NFAs, Determinisieriung (Potenzmengenkonstruktion)
04.05. NFAs mit Epsilon-Übergängen, reguläre Ausdrücke
Satz von Kleene
11.05. Pumping-Lemma
DFA-Minimierung
18.05. Abschlusseigenschaften Typ 3-Sprachen, Entscheidbarkeiten bei Typ-3-Sprachen
CFLs: Normalformen und Abschlusseigenschaften
25.05. CFLs: Wortproblem lösen mit dem CYK-Algorithmus
Kellerautomaten: Definition, Verwendung, Varianten
01.06. Deterministisch kontextfreie Sprachen
Turingmaschinen und Typ 1- und Typ 0-Sprachen
08.06. Intuitive Berechenbarkeit,  Mehrspuren- und Mehrbandmaschinen
Entscheidbarkeit, Unentscheidbarkeit, Halteproblem
15.06. Satz von Rice,
Postsches Korrespondenzproblem
22.06. Laufzeitkomplexität, die Klassen P und NP,
NP-Vollständigkeit,
29.06. Der Satz von Cook
NP-Vollständigkeit von 3-CNF-SAT
06.07. 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-13:30 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.

Artikelaktionen


Funktionsleiste