Proseminar 13/14

________________________________________________________________________________________________

Proseminar Theoretische Informatik

Prof. Dr. Helmut Alt, WS 2014/15, Di. 16-18, SR 051

________________________________________________________________________________________________

Noten

Voraussetzungen

Das Proseminar baut auf der Vorlesung "Grundlagen der theoretischen Informatik" auf. Diese sollte absolviert und bestanden sein.

Liste der Vorträge

   0. Vorbesprechung: Vergabe der Themen am 14.10 2014

   1. Anwendungen regulärer Sprachen und endlicher Automaten [HMU] 2.4, 3.3, [ASU] Kap.3, [MC] 5.8
        28.10.2014
        Karck, Celina

   2. Anwendungen kontextfreier Grammatiken [HMU] 5.3, [ASU] Kap.4,
    4.11.2014
        Boenisch, Franziska
        Zusammenfassung

3. Lindenmayer-Systeme
       11.11.2014
       Berendsohn, Benjamin Aram
       Zusammenfassung

4. Die Komplexitätsklasse P [S] 7.1-7.2
         18.11.2014
         Domiks, Samuel
         Zusammenfassung

5. Die Komplexitätsklasse NP [S] 7.3
       25.11.2014
       Kleinert, Marvin
       Zusammenfassung

6. NP-Vollständigkeit 1 [S] 7.4
      2.12.2014
Alt, Helmut

7. NP-Vollständigkeit 2 [S] 7.5
      9.12.2014
      Tilgner, Marten
      Zusammenfassung

8. Berechnungsmodelle [HMU] 8.5, [Sch] 2.1-2.3
       6.1.2015
     Wieder, Benedikt John
       Zusammenfassung

9. Kryptographie [S] 10.6
       13.1.2015
       Gu, William
       Zusammenfassung

10. Entscheidbarkeit der Presburger-Arithmetik [S] 6.2
       20.1.2015
       Pauli, Tim
      Zusammenfassung

11. Gödels Unvollständigkeitssatz [S] 6.2
       27.1.2015
       Weber, Philipp Leon
       Zusammenfassung

12. Kolmogoroff-Komplexität [S] 6.4
      3.2.2015
      Borghardt, Anna
      Zusammenfassung

Literatur:

[ASU]
A.V.Aho, R. Sethi, J.D.Ullmann
Compilerbau Teil 1
Oldenbourg 1999

oder

Compiler. Prinzipien, Techniken und Tools (Pearson Studium): Prinzipien, Techniken und Werkzeuge
von Ravi Sethi, Monica S. Lam und Alfred V. Aho von PEARSON STUDIUM 2008

[HMU]
J.E.Hopcroft, R. Motwani, J.D.Ullman
Introduction to Automata Theory, Languages, and Computation, 2nd ed.
Addison-Wesley 2001

[MC]
M. Morris Mano, M.D.Ciletti
Digital Design, 4th Ed., Pearson Edu. 2007
ISBN 0-13-198924-3

[Sch]
U.Schöning
Theoretische Informatik-kurzgefaßt
Spektrum Akad. Verlag 1995

[S]
M. Sipser
Introduction to the Theory of Computation
PWS Publ.Comp. 1997