• 27.01.2016: Am 02.02.2016 beginnt das Proseminar um 16:00 st.
• 29.11.2015: Am 01.12.2015 beginnt das Proseminar um 16:00 st.
• 21.09.2015: Die Themenvergabe findet statt in der ersten Sitzung am 13. Oktober 2015.
• 21.09.2015: Die Website ist online.

Voraussetzungen

Erfolgreicher Abschluss der Veranstaltung "Grundlagen der Theoretischen Informatik".

Termin

Das Proseminar findet statt am Dienstag von 16–18 Uhr im SR 051.

Literatur

• [ALSU]
  A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman. Compiler: Prinzipien, Techniken und Werkzeuge. Pearson Studium, 2. Auflage, 2008
• [HMU]
  J. E. Hopcroft, R. Motwani, J.D. Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexität. Pearson Studium, 3. Auflage, 2011.
• [Sch]
  U. Schöning. Theoretische Informatik – kurz gefasst. Spektrum Akademischer Verlag, 5. Auflage, 2008.
• [S]
  Michael Sipser. Introduction to the Theory of Computation, Thomson Course Technology, 2. Auflage, 2006.
• [W]
  Ingo Wegener. Theoretische Informatik – Eine algorithmenorientierte Einführung. Teubner, 3. Auflage, 2005.

Scheinkriterien

Für den Scheinerhalt muss man

• einen erfolgreichen Vortrag von insgesamt 40 Minuten Dauer halten.
• eine Kurzbeschreibung des Vortrags, ca. 4 DIN A4-Seiten in PDF, vorbereiten. Davon sind vor dem Vortrag Kopien an alle Teilnehmer_innen auszuteilen und ein elektronisches Exemplar abzugeben. Hier ist eine LaTex-Vorlage.
• regelmäßig am Proseminar teilnehmen (max. 2 Fehltermine).

Perspektiven

Im Anschluss an die Veranstaltung können Bachelorarbeiten vergeben werden.

Das Proseminar baut auf der Vorlesung "Grundlagen der Theoretischen Informatik" auf und vertieft die dort behandelten Themen.

• 01. Anwendungen regulärer Sprachen und endlicher Automaten [Aiko Pipo]

  Reguläre Sprachen und endliche Automaten erfreuen sich vieler Anwendungen in der theoretischen und praktischen Informatik. Hiervon sollen einige vorgestellt werden.

  Literatur: [ALSU, Kapitel 3] [HMU, Abschnitte 2.4 und 3.3]

• 02. Kontextfreie Grammatiken im Übersetzerbau [Nico Stephan]

  Kontextfreie Grammatiken bilden die Basis für den Entwurf und die Implementierung von Programmiersprachen. Leider sind Algorithmen zur Analyse von allgemeinen kontextfreien Sprachen nicht effizient genug. In diesem Vortrag soll es darum gehen, unter welchen Umständen sich kontextfreie Sprachen effizient analysieren lassen und wie die entsprechenden Algorithmen funktionieren.

  Literatur: [ALSU, Kapitel 4] [HMU, Abschnitt 5.3]

• 03. Kellerautomaten [Sebastian Oltmanns und Dorian Wachsmann]

  Kellerautomaten sind das Maschinenmodell für kontextfreie Sprachen. Das Modell der Kellerautomaten soll in seinen Varianten eingeführt werden und die Äquivalenz zu kontextfreien Grammatiken bewiesen werden.

  Literatur: [HMU, Abschnitte 6.1–6.3] [Sch, Abschnitt 1.3.5] [S, Abschnitt 2.2]

• 04. Deterministisch kontextfreie Sprachen [Boris Dimitrov]

  Deterministisch kontextfreie Sprachen bilden eine Teilklasse der kontextfreien Sprachen mit besonders guten Eigenschaften. Diese Teilklasse soll erklärt werden und gegen die Klasse der allgemeinen kontextfreien Sprachen abgegrenzt werden.

  Literatur: [HMU, Kapitel 6.4] [Sch, Abschnitt 1.3.6] [S, Abschnitt 2.4]

• 05. Kontextsensitive Sprachen [Hanna Lachnitt und Christopher Mühl]

  Die Klasse der kontextsensitiven Sprachen sitzt zwischen den kontextfreien und den entscheidbaren Sprachen und kann in der GTI-Vorlesung leider nur knapp behandelt werden. In diesem Vortrag soll diese Klasse mit ihren Eigenschaften genauer betrachtet werden.

  Literatur: [Sch, Abschnitt 1.4]

• 06. Ausgewählte unentscheidbare Sprachen [Jakob Köhler und Marian Sigler]

  Der Vortrag soll ausgewählte unentscheidbare Sprachen vorstellen, wie z.B. das Postsche Korrespondenzproblem, das Entscheidungsproblem der Prädikatenlogik oder das Parkettierungsproblem.

  Literatur: [HMU, Abschnitte 9.4–9.5] [Sch, Abschnitte 2.7–2.9] [S, Kapitel 5]

• 07. Weitere Themen der Berechenbarkeitstheorie

  Weitere Themen aus der Berechenbarkeitstheorie sollen vorgestellt werden, wie z.B. der Satz von Rice, der Rekursionssatz, oder das Konzept der Turing-Reduktion.

  Literatur: [HMU, Abschnitt 9.3.3] [S, Abschnitt 6.1 und 6.3]

• 08. Alternative Berechnungsmodelle [Andreas Berg, Pascal Müller und Marius Schidlack]

  Neben Turingmaschinen und Lambda-Kalkül gibt es noch weitere äquivalente Modelle von Berechenbarkeit, z.B. μ-Rekursion, WHILE-Berechenbarkeit oder Zählermaschinen. Diese sollen vorgestellt und verglichen werden.

  Literatur: [Sch, Abschnitte 2.3–2.4]

• 09. Die Komplexitätsklasse P [Albert Mkhitaryan und Maria Sparenberg]

  Komplexitätstheorie beschäftigt sich damit, welche Probleme sich wie schnell lösen lassen. Die Komplexitätsklasse P stellt die Menge der effizient lösbaren Probleme dar. Diese Klasse soll präsentiert und an Beispielen erläutert werden.

  Literatur: [S, Abschnitte 7.1–7.2]

• 10. Die Komplexitätsklasse NP [Elmar Frerichs und Michael Tran Xuan]

  Die Komplexitätsklasse NP enthält alle Sprachen, für die es effizient überprüfbare Mitgliedschaftszertifikate gibt. Die P-NP Frage ist eines der größten ungelösten Probleme der Informatik und Mathematik. Der Vortrag soll die Klasse NP einführen und durch einige Beispiele abgrenzen.

  Literatur: [S, Abschnitt 7.3]

• 11. NP-Vollständigkeit

  NP-vollständige Probleme sind Probleme in der Komplexitätsklasse NP, welche die gesamte Schwierigkeit von NP in sich tragen. Dies soll formal definiert und durch Beispiele verdeutlicht werden.

  Literatur: [S, Abschnitte 7.4–7.5]

• 12. Die Komplexitätsklassen L und NL [Bianca George und Anja Wolffgramm]

  Neben der Laufzeit spielt auch der Platzbedarf von Algorithmen eine wesentliche Rolle. Dies wird durch Komp[lexitätsklassen wie L, NL oder PSPACE formalisiert. Diese Klassen sollen im Vortrag vorgestellt werden.

  Literatur: [S, Abschnitte 8.1 und 8.4–8.5]

• 13. Probabilistische Algorithmen [Diane Hanke und Alexander Korzec]

  Der Zufall spielt heutzutage in der theoretischen Informatik eine wesentliche Rolle. Der Vortrag soll zeigen, wie der Zufall beim Entwurf effizienter Algorithmen helfen kann und was die Komplexitätstheorie zu diesem Phänomen zu sagen hat.

  Literatur: [S, Abschnitt 10.2]

• 14. Komplexitätstheorie und Kryptographie [Marl Joos]

  Die moderne Kryptologie basiert wesentlich auf Konzepten aus der Komplexitätstheorie. Dieser Zusammenhang soll erläutert und von traditionellen Ansätzen abgegrenzt werden.

  Literatur: [S, Abschnitt 10.6]

(Die Zusammenfassungen und Folien der Teilnehmer_innen sind ohne Gewähr der Richtigkeit.)

Im Web gibt es viele Ressourcen mit nützlichen Tipps zur effektiven Gestaltung eines Vortrags. Hier einige Beispiele, die mir gefallen haben.

1. Christian Knauer und Frank Hoffmann.
   Wie gestalte ich einen Seminarvortrag?
   Etwas alt, aber immer noch interessant.
2. Ian Parberry.
   How to Present a Paper in Theoretical Computer Science: A Speaker's Guide for Students.
   Spezielle Tipps für die theoretische Informatik.
3. Paul Halmos.
   How to talk Mathematics.
   Für Mathematiker, aber vieles trifft auch auf die theoretische Informatik zu.
4. Patrick Winston.
   How to speak.
   Lustiges Video. Die ersten fünf Minuten kann man getrost überspringen.
5. Proseminar vom letzten Jahr.

Hier die Fragen, von denen ich mich bei der Bewertung eines Seminarvortrags leiten lasse.