Proseminar Ausgewählte Themen der Theoretischen Informatik

Prof. Dr.-Ing. Franz Baader
Dr.-Ing. Stefan Borgwardt

Das Proseminar "Ausgewählte Themen der Theoretischen Informatik" ist ein Angebot für Studierende im Studiengang Bachelor Informatik (Modul INF-B-610, INF-B-510, INF-B-520) und im Diplomstudiengang Informatik (Modul INF-D-520). Wünschenswert ist, dass die Studierenden Interesse an der Theoretischen Informatik haben (z.B. an der inhaltlichen Ausrichtung der Lehrveranstaltungen "Formale Systeme" und "Theoretische Informatik und Logik").

Vortragstermine

Datum Zeit Thema (siehe unten) Sprache
6.7. 13:00 Gesetze für reguläre Ausdrücke de
13:45 Abgeschlossenheit von regulären Sprachen unter Homomorphismen und inversen Homomorphismen de
14:50 Mehrdeutigkeit von Grammatiken und Sprachen de
15:35 Entscheidungsbäume de
7.7. 13:00 Datentyp-Zuordnung im Lambda-Kalkül de
13:45

Measuring with Jugs

 de
14:50 Der Satz von Cayley de
15:35 Vervollständigung von Lateinischen Quadraten de
13.7. 13:00 The Recursion Theorem en
13:45 Kolmogorov-Komplexität de
14:50

The Complexity of Counting

 en
15:35

Komplexität von Real-Time Strategie Spielen

 de
14.7. 13:00

Decidability of Logical Theories

 en
13:45

Modallogik

 de

Themen

Die benötigte Literatur wird den Studierenden zur Verfügung gestellt. Einige Quellen sind auf Deutsch, die meisten aber auf Englisch.

  • Uwe Schöning: Perlen der Theoretischen Informatik. BI Wissenschaftsverlag, 1995.

    • (VERGEBEN!)
      Die Berman-Hartmanis Vermutung und spärliche Mengen       (Kapitel 15)
       

      Es wird gezeigt, dass P=NP gilt, falls es eine NP-vollständige "spärliche" Sprache gibt, d.h. eine Sprache, die nur eine polynomielle Anzahl an Wörtern der maximalen Länge n enthält, für alle natürlichen Zahlen n.
       

      Voraussetzungen: Komplexität

  • Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise. Springer-Verlag Berlin Heidelberg, 2010.

    • (VERGEBEN!)
      Cayleys Formel für die Anzahl der Bäume       (Kapitel 30)
       

      Es werden verschiedene Beweise für eine Formel vorgestellt, die die Anzahl der Bäume auf einer gegebenen Menge von Knoten berechnet. Dabei werden verschiedene interessante kombinatorische Ansätze benutzt.


      Voraussetzungen: Mathematik, Kombinatorik

    • (VERGEBEN!)
      Vervollständigung von Lateinischen Quadraten       (Kapitel 32)

      Es wird eine Methode vorgestellt, mit der man Lateinische Quadrate beliebiger Größe erstellen kann.

      Voraussetzungen: Mathematik, Kombinatorik

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage, Addison-Wesley Longman Verlag, 2002.
    • (VERGEBEN!)
      Gesetze für reguläre Ausdrücke       (Kapitel 3.4.6 und 3.4.7, Satz 3.14)


      Es gelten verschiedene algebraische Gesetze für reguläre Ausdrücke, wie z.B. Kommutativität der Vereinigung oder Distributivitätsgesetze für Konkatenation und Vereinigung. Es wird ein Verfahren besprochen, solche Zusammenhänge einfach zu beweisen oder zu widerlegen, indem statt beliebiger Sprachen einzelne Buchstaben als Platzhalter benutzt werden.
       

      Voraussetzungen: Formale Sprachen, Reguläre Ausdrücke

    • (VERGEBEN!)
      Abgeschlossenheit von regulären Sprachen unter Homomorphismen und inversen Homomorphismen       (Kapitel 4.2.3 und 4.2.4, Satz 4.16, Beispiel 4.17)

      Neben der Abgeschlossenheit unter Vereinigung, Durschnitt und Komplement haben reguläre Sprachen noch weitere verwandte Eigenschaften. Es wird gezeigt, dass sie unter Anwendung von (inversen) Sprach-Homomorphismen abgeschlossen sind. Dies erweitert die Sammlung von formalen Werkzeugen, mit denen man die Regularität von Sprachen zeigen kann.

      Voraussetzungen: Reguläre Sprachen, Endliche Automaten

    • (VERGEBEN!)
      Mehrdeutigkeit von Grammatiken und Sprachen       (Kapitel 5.4)

      Kontextfreie Grammatiken können genutzt werden, um die Struktur von Programmcode zu definieren. Abhängig von der Grammatik ist aber die Struktur eines Programms nicht immer eindeutig bestimmt. Dieses Kapitel bespricht diese Problematik und zeigt mögliche Lösungsansätze auf. Es wird aber auch gezeigt, dass es formale Sprachen gibt, die nur von mehrdeutigen kontextfreien Grammatiken beschrieben werden können.
       

      Voraussetzungen: Formale Sprachen, Kontextfreie Grammatiken

  • Michael Sipser: Introduction to the Theory of Computation. Thomson Course Technology, 2006.

    • (VERGEBEN!)
      The Recursion Theorem       (Kapitel 6.1)

      The recursion theorem talks about Turing machines that can output an encoding of their own program code, i.e., the transition relation. The theorem is useful for proving various computability and decidability results.
       

      Vorraussetzungen: Turingmaschinen, Entscheidbarkeit

    • (VERGEBEN!)
      Decidability of Logical Theories       (Kapitel 6.2)

      The decidability of logical consequences is an old problem of computability theory. Depending on the expressivity of the logic, its consequence relation can be either decidable or undecidable. Such results about first-order logic theories allow us to prove Gödel's first incompleteness theorem.
       

      Voraussetzungen: Prädikatenlogik, Entscheidbarkeit

    • (VERGEBEN!)
      A Definition of Information (Kapitel 6.4)

      The Kolmogorov complexity describes the complexity of a string as the minimal length of an encoding of a Turing machine that can output this string. This gives rise to a theory of information content of strings and results about the compressibility of strings.

      Voraussetzungen: Turingmaschinen

  • Michael Huth, Mark Ryan: Logic in Computer Science: Modelling and Reasoning about Systems. Second Edition, Cambridge University Press, 2004.

    • (VERGEBEN!)

      Modal Logic (Kapitel 5.1-5.3)

      Modal logics extend propositional logic by modality operators to express different beliefs, temporal states, or knowledge held by different agents. This introduction to modal logic includes basic definitions of syntax and semantics, and a discussion of the properties of different modal operators.
       

      Voraussetzungen: Prädikatenlogik

  • Uwe Schöning: Logik für Informatiker. 5. Auflage, Spektrum Akademischer Verlag Heidelberg Berlin, 2000.

    • (VERGEBEN!)
      Auswertungsstrategien für Hornklauselprogramme       (Kapitel 3.2 und 3.3)
       

      Die Logikprogrammierung basiert auf der SLD-Resolution für Hornklauselprogramme, die sehr effizient ist. In diesen Kapiteln werden verschiedene Semantiken und Auswertungsstrategien für Hornklauselprogramme verglichen.


      Voraussetzungen: Prädikatenlogik, Resolution

  • Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

    • (VERGEBEN!)
      Decision Trees       (Kapitel 12)

      This chapter explores an alternative notion of complexity based on decision trees. Various measures are introduced and compared to each other.


      Voraussetzungen: Komplexität, Mathematische Grundkenntnisse

    • (VERGEBEN!)
      Complexity of Counting       (Kapitel 17 außer Satz 17.11 und Abschnitte 17.4.1ff)

      Intuitively, counting complexity classes describe how difficult it is to count the number of solutions to NP-problems, e.g. the number of satisfying assignments of a propositional formula. This chapter studies polynomial counting complexity classes and their relation to classes of decision problems.

      Voraussetzungen: Komplexität, NP, SAT

  • (VERGEBEN!)
    Henk Barendregt, Erik Barendsen: Introduction to Lambda Calculus. 1994.

    • Type Assignment (Kapitel 5)

      Type systems in programming languages are useful for a variety of static and dynamic tasks, such as type checking and compilation. This chapter describes a type system for the lambda calculus and investigates its properties.

      Voraussetzungen: Funktionale Programmierung

  • (VERGEBEN!)
    Paolo Boldi, Massimo Santini, Sebastiano Vigna: Measuring with Jugs. Theoretical Computer Science, volume 282, issue 2, pages 259–270, 2002.
    https://doi.org/10.1016/S0304-3975(01)00060-3

    This paper shows which quantities of liquids can be measured given a collection of jugs with different capacities. Moreover, it shows lower and upper bounds on the number of steps needed for any measurement.

    Voraussetzungen: Mathematische Grundkenntnisse

  • (VERGEBEN!)
    Timothy Furtak, Michael Buro: On the Complexity of Two-Player Attrition Games Played on Graphs. In Proceedings of the Sixth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), pages 113–119, 2010. https://aaai.org/ocs/index.php/AIIDE/AIIDE10/paper/view/2132

    Inspired by real-time strategy games, this paper studies the complexity of finding winning strategies for abstract games where each player controls a number of units with associated health and attack power.


    Voraussetzungen: Komplexität, PSpace, ExpTime

Ziel und Aufbau des Proseminars

Im Seminar wird das gewählte Thema mithilfe der Literaturquelle selbstständig erarbeitet und das neu angeeignete Wissen in einem Vortrag vor den anderen Teilnehmern präsentiert. Dabei kommt es insbesondere darauf an, das erworbene Wissen mit eigenen Worten zu transportieren. Wenn der Umfang des Themas es nicht ausschließt, ist auch eine Gruppenarbeit möglich.

Der Vortrag im Umfang von 30 Minuten (+ 15 Minuten Diskussion) soll demonstrieren, dass der Inhalt des gewählten Kapitels verstanden wurde. Das Vortragsmaterial muss der Zeit angemessen gewählt werden und alle Resultate sollen geeignet illustriert werden. Unabhängig von der Sprache der Quelle kann der Vortrag nach Absprache auf Deutsch oder Englisch gehalten werden. Für den erfolgreichen Scheinerwerb ist es notwendig, dass sich die Studierenden aktiv an den Diskussionen zu anderen Vorträgen im Proseminar beteiligen.

Im Vorfeld der Vorträge werden Ratschläge und Anregungen, wie man einen guten Vortrag hält und einer anschließenden Diskussion ebenso gut standhält, vermittelt.

Weitere Organisation

Die Studierenden werden von Mitarbeitern der Professur für Automatentheorie betreut: Dr.-Ing. Stefan Borgwardt, Dr. Patrick Koopmann, Dipl.-Inf. Walter Forkel. Die Abschlussveranstaltungen mit den Vorträgen zum Proseminar finden in den letzten Lehrveranstaltungswochen im Sommersemester statt.

Literatur

Die benötigte Literatur wird den Studierenden zur Verfügung gestellt.

Begleitende Materialen zu den Theorie-Vorlesungen im Grundstudium:

Zu dieser Seite

Stefan Borgwardt
Letzte Änderung: 26.06.2020