Übungen zu Berechenbarkeit und Komplexität


Nächstes Semester

Für das nächste Semester suchen wir studentische Hilfskräfte für die Vorlesung Automaten und Sprachen (Vorlesung: Prof. Dr. Herre, Übungen: Dr. Waldmann).

Informieren Sie sich über Theoretische Informatik im Hauptstudium! Sie können zum Beispiel Kombinatorische Spieltheorie hören, und noch vieles andere.


Aktuelles

Übungsscheine

Die Prüfung über das 3. und 4. Semester (Automaten, Sprachen, Berechenbarkeit, Komplexität) findet am Montag, dem 24. September, um 10 Uhr statt.

So wird programmiert! Jetzt anmelden zum Haskell-compact-Kurs!

Hier steht, was nicht mehr aktuell ist.


Übungsaufgaben

In Klammern steht das Datum der Vorlesung, auf die sich die Aufgaben beziehen. Bereiten Sie sich darauf vor, im jeweils folgenden Seminar Ihre Lösungen vortragen zu können.

Weitere Informationen

Woher kommen die (nicht)erfüllbaren aussagenlogischen Formeln (Aufgaben SAT*)? Lesen Sie ab Seite 41 im Skript Kombinatorik (SS00).

Hier ist das PCP-Puzzle.

Wie lautet der Vorname von Herrn Ackermann? Finden Sie hier Biographien von Mathe- und Informatikern.

Die Lösung der Aufgabe zur Takeuchi-Funktion, nebst weiteren Erläuterungen, finden Sie in dem Artikel Textbook Examples of Recursion von Donald E. Knuth.

Eine Sammlung von Fakten und Verweisen zu Busy Beaver-Maschinen ist hier.


Koordinaten

Vorlesungs-Ankündigung

Webseiten zur Berechenbarkeits-Vorlesung


http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de
best viewed with any browser