Links und Funktionen
Sprachumschaltung

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


Inhaltsbereich

Formale Sprachen und Komplexität

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

Aktuelles

  • Montagsübung, 18-20, beginnt auf Wunsch der Teilnehmenden ab sofort um 18 s.t.
  • Bitte melden Sie sich bei Uni2work zur Vorlesung 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

Veranstaltung Zeit OrtBeginn
Vorlesung Mi 12-14 Uhr Schellingstr. 3 (S), S 002 24.04.2019
Vorlesung / Zentralübung Do 16-18 Uhr Schellingstr. 3 (S), S 002 25.04.2019
Übung (Stephan Barth) Mo 10-12 Uhr Geschw.-Scholl-Pl. 1 (A), A 022 29.04.2019
Übung (Sebastian Sturm) Mo 16-18 Uhr Geschw.-Scholl-Pl. 1 (A), A 022 29.04.2019
Übung (Elisabeth Lempa) Mo 18:00 - 19:30 Uhr Geschw.-Scholl-Pl. 1 (A), A 022 29.04.2019
Übung (David Sabel) Di 16-18 Uhr Geschw.-Scholl-Pl. 1 (M), M 203 30.04.2019
Übung (David Tellenbach) Di 18-20 Uhr Geschw.-Scholl-Pl. 1 (M), M 203 30.04.2019

Material

Folien

Skript

Das Skript zur Vorlesung wird ständig erweitert. Die aktuelle Version ist hier verfügbar.

Zentralübung

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.
  • ...

Protokoll

  • Mittwoch 24. April: Begrüßung, Einführung, Inhaltsübersicht, Alphabete, Worte, Formale Sprachen
  • Donnerstag 25. April: Chomsky Grammatiken und die Chomsky-Hierarchie
  • Mittwoch 1.Mai: Feiertag, keine Vorlesung
  • Donnerstag 2.Mai: Elimination von epsilon-Produktionen, Wortproblem, Typ-3 Sprachen, endliche Automaten (DFA)
  • Mittwoch 8.Mai:  DFA (Konstruktion DFA in Typ 3 Grammatik), NFAs, reguläre Grammatik in NFA überführen, NFA in DFA  mit Potenzmengenkonstruktion
  • Donnerstag 9.Mai: Grösse von DFA vs NFA, NFA mit Epsilon-Übergängen, Zentralübung (DFAs, NFAs)
  • Mittwoch 15.Mai: NFA mit Epsilon-Übergängen und mit eindeutigen Start- und Endzuständen, Reguläre Ausdrücke, Satz von Kleene
  • Donnerstag 16.Mai: Pumping-Lemma  und Zentralübung (Reguläre Ausdrücke und Anwenden des Pumping-Lemmas)

Planung für die bald kommenden Vorlesungen


  • Mittwoch 22. Mai: Pumping-Lemma (Wdh),  Satz von Myhill-Nerode
  • Donnerstag 23. Mai: Satz von Myhill-Nerode, Konstruktion des Minimalautomaten (evtl.)

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

Klausur

Die Klausur findet am Dienstag, 30. Juli um 16:00 Uhr statt (Bearbeitungszeit 120 Minuten).
Eine Anmeldung ist zur Teilnahme an der Klausur ist erforderlich. Die Anmeldung ist noch nicht möglich und wird rechtzeitig (d.h. ca. 4 Wochen vor dem Klausurtermin) freigeschaltet und hier erläutert.

 

Nachklausur

Die Nachklausur findet am Dienstag, 24. September um 14:00 Uhr statt (Bearbeitungszeit 120 Minuten).
Eine Anmeldung ist zur Teilnahme an der Nachklausur ist erforderlich. Die Anmeldung ist noch nicht möglich und wird rechtzeitig (d.h. ca. 4 Wochen vor dem Klausurtermin) freigeschaltet und hier erläutert.

Artikelaktionen


Funktionsleiste