Die Übungszettel werden ausschlie├člich online erscheinen und zwar hier auf dieser Seite.

Themenübersicht

  • Grundlagen
    • Alphabete, Sprachen, Wörter
    • einfache Operationen auf Sprachen
  • reguläre Sprachen
    • reguläre Ausdrücke
    • endliche Automaten und Nichtdeterminismus
    • Äquivalenz der Darstellungen
    • Pumping Lemma
    • Nerode-Relation und Minimalautomaten
    • Anwendungen regulärer Sprachen, Lexer, Grep
  • Turing Maschinen
    • Definition(en) und Eigenschaften, Universalität
    • Grenzen der Berechenbarkeit: Universalsprache, Halteproblem, PKP
    • Reduktionskonzept
    • Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit
  • kontextfreie Sprachen
    • Grammatiken und Chomsky-Hierarchie
    • kontextfreie Grammatiken
    • Eindeutigkeit
    • Chomsky-Normalform und der CYK-Algorithmus
    • Pumping-Lemma
    • Kellerautomaten und Äquivalenz der Darstellungen
    • Varianten: eindeutig kontextfrei, deterministisch kontextfrei, u.a.
    • Anwendungen im Übersetzerbau, Parser

Tatsächlicher Inhalt

  • Mittwoch, den 16.04.2014
    • Administrativa
    • Einleitung
      • Was ist theoretische Informatik?
      • Geschichte, Motivation und Fragestellungen
  • Montag, den 21.04.2014 (Ostermontag)
    • keine Vorlesung
  • Mittwoch, den 23.04.2014
    • Alphabete, Wörter, Sprachen
    • Operationen auf Sprachen
    • reguläre Ausdrücke und reguläre Sprachen
  • Montag, den 28. 04. 2014
    • weitere Beispiele zu regulären Ausdrücken
    • deterministische endliche Automaten (DEAs) mit Beispielen
  • Mittwoch, den 30. 04. 2014
    • nichtdeterministische endliche Automaten (NEAs)
    • Äquivalenz von NEAs und DEAs; Potenzmengenkonstruktion
  • Montag, den 05. 05. 2014
    • Abschluss Potenzmengenkonstruktion und Beweis
    • Äquivalenz von endlichen Automaten und regulären Ausdrücken: rA → NEA
  • Mittwoch, den 07. 05. 2014
    • Äquivalenz von endlichen Automaten und regulären Ausdrücken
      • Abschluss rA → NEA
      • Algorithmus von Kleene: DEA → rA
      • weitere Eigenschaften von regulären Sprachen
  • Montag, den 12. 05. 2014
    • Algorithmus von Kleene: Abschluss
    • weitere Eigenschaften von regulären Sprachen
    • Pumping-Lemma: Intuition und Beweis
  • Mittwoch, den 14. 05. 2014
    • Pumping-Lemma: Anwendungen
    • Myhill-Nerode-Relation und Minimalautomaten
  • Montag, den 19. 05. 2014
    • Myhill-Nerode-Relation und Minimalautomaten
    • Konstruktion von Minimalautomaten -- Theorie
  • Mittwoch, den 21. 05. 2014
    • Konstruktion von Minimalautomaten -- Algorithmus
    • Reguläre Sprachen im Übersetzerbau
    • Turing-Maschinen
  • Montag, den 26. 05. 2014
    • Turing-Maschinen: Beispiele und Varianten
  • Mittwoch, den 28. 05. 2014
    • Berechenbarkeit, Church-Turing These
    • Kodierung von Turing-Maschinen
    • Diagonalsprache
    • universelle Sprache und universelle Turingmaschine
  • Montag, den 02. 06. 2014
    • Semientscheidbarkeit/rekursive Aufzählbarkeit
    • Halteproblem
    • Reduktionskonzept
    • Abschlusseigenschaften von entscheidbaren und semientscheidbaren Sprachen
  • Mittwoch, den 04. 06. 2014
    • Weitere unentscheidbare Probleme:
      • Postsches Korrespondenzproblem,
      • Hilberts Entscheidungsproblem und Gödelscher Unvollständigkeitssatz,
      • diophantische Gleichungen,
      • Erkennen von Computerviren
    • Rekursionssatz und sich-fortpflanzende Programme
    • Satz von Rice: Alle interessanten semantischen Eigenschaften von Turing-Maschinen sind nicht entscheidbar.
  • Montag, den 09. 06. 2014 (Pfingstmontag)
    • keine Vorlesung
  • Mittwoch, den 11. 06. 2014
    • Grammatiken: Definition und Beispiele
  • Montag, den 16. 06. 2014
    • Chomsky-Hierarchie: Definition und Eigenschaften
    • Die Chomsky-Hierarchie ist echt
  • Mittwoch, den 18. 06. 2014
    • Kontextfreie Grammatiken: Syntaxbäume, Eindeutigkeit und inhärente Mehrdeutigkeit
    • Chomsky-Normalform: Notizen
  • Montag, den 23. 06. 2014
    • Probeklausur
  • Mittwoch, den 25. 06. 2014
  • Montag, den 30. 06. 2014
    • CYK-Algorithmus
    • Pumping-Lemma für kontextfreie Sprachen
  • Mittwoch, den 02. 07. 2014
    • Pumping-Lemma für kontextfreie Sprachen
    • Beispielanwendungen des Pumping-Lemmas
  • Montag, den 07. 07. 2014
    • weitere Beispiele für das Pumping-Lemma für kontextfreie Sprachen
    • Abschlusseigenschaften kontextfreier Sprachen
    • Kellerautomaten
  • Mittwoch, den 09. 07. 2014
    • Kellerautomaten: formale Definition und Beispiel
    • Zusammenfassung und Ausblick
  • Montag, den 14. 07. 2014
    • Wiederholung und Klausurvorbereitung.
    • Themen:
      • Entscheidbarkeit und Reduktionen
      • Nerode-Relation und Minimalautomat
  • Mittwoch, den 16. 07. 2014
    • Klausur
  • Dienstag, den 22. 07. 2014
    • Klausureinsicht
  • Dienstag, den 07. 10. 2014
    • Nachklausur
  • Freitag, den 10. 10. 2014
    • Einsicht der Nachklausur

Voraussetzungen

Literatur

Es wird eine Klausur am Ende des Semesters geben, sowie eine Ersatzklausur vor Beginn des nächsten Semesters. Dabei gilt die Freiversuchsregel. Das heißt, man kann die Ersatzklausur nutzen, um das Ergebnis aus der Hauptklausur zu verbessern (nur bei erstmaligem Absolvieren des Moduls).

Der Klausurtermin ist Mittwoch, der 16.07.2014, von 10–12 Uhr, im großen Hörsaal der Physiologie, Arnimallee 22, im HS ZIB und im Hörsaal Informatik.

Für den Scheinerhalt muss man

Die erfolgreiche Teilnahme am Übungsbetrieb und Teilnahme an der Klausur sind unabhängige Leistungen.

Die Scheine sind benotet. Die Note beruht nur auf den Klausurergebnissen.

Die Vorlesung findet statt Montag und Mittwoch, 10–12 Uhr, im großen Hörsaal in der Takustraße 9. Es gibt fünf Tutor_innen (Katharina Klost, Kristin Knorr, Justus Pfannschmidt, Simon Tippenhauer und Max Willert).

Montag
14:00–16:00 Takustr. 9 Seminarraum 051 Simon Tippenhauer
Dienstag
12:00–14:00 Takustr. 9 Seminarraum 053 Kristin Knorr
Mittwoch
08:00–10:00 Takustr. 9 Seminarraum 051 Katharina Klost
12:00–14:00 Takustr. 9 Seminarraum 051 Simon Tippenhauer
12:00–14:00 Takustr. 9 Seminarraum 055 Kristin Knorr
14:00–16:00 Takustr. 9 Seminarraum 005 Max Willert
Donnerstag
12:00–14:00 Takustr. 9 Seminarraum 051 Max Willert
12:00–14:00 Arnimallee 3 HS 001 Justus Pfannschmidt
12:00–14:00 Animallee 7 Seminarraum 1.1.53 Katharina Klost
16:00–18:00 Takustr. 9 Seminarraum 051 Justus Pfannschmidt
18:00–20:00 Takustr. 9 großer Hörsaal Wunschkonzert

Sprechzeit des Dozenten: Dienstag 14–15 Uhr in Zimmer 114 und nach Vereinbarung

Die Übungszettel werden jede Woche hier verlinkt. Sie werden ausschließlich online erscheinen. Die normale Bearbeitungszeit ist von Mittwoch bis zum Freitag 9 Tage später. Die Zettel sind vor 10 Uhr in die entsprechenden Tutorenfächer einzuwerfen. Die Bearbeitung erfolgt in Zweiergruppen.

Übungszettel, die nach dem angegebenen Termin abgegeben werden, zählen als nicht bearbeitet.

Nr.AusgabeAbgabe pdftexBemerkungen
1 02.04.2014 25.04.2014  
2 23.04.2014 02.05.2014  
3 30.04.2014 09.05.2014  
4 07.05.2014 16.05.2014 Aufgabe 1b) wurde geändert.
5 14.05.2014 23.05.2014  
5a 15.05.2014 keine Pumping-Lemma Aufgaben.
6 21.05.2014 30.05.2014 summe.flex
7 28.05.2014 06.06.2014  
8 04.06.2014 13.06.2014  
9 11.05.2014 20.06.2014  
10 18.06.2014 27.07.2014 Chomsky Normalform
vorletztes Aufgabenblatt
11 04.07.2014 11.07.2014 letztes Aufgabenblatt
Probeklausur 23.06.2014 keine  
Impressum