Introduction to Theoretical Computer Science

(A German-language class)

Vorlesung und Übung (6 SWS/9 ECTS)

In dieser Vorlesung wird in die Grundlagen der theoretischen Informatik eingeführt. Im Mittelpunkt stehen mathematische Modelle für Algorithmen, Automaten und formale Sprachen. Ebenso werden die Fragestellungen behandelt, welche Berechnungsprobleme überhaupt algorithmisch lösbar sind und wie die Klasse der effizient lösbaren Berechnungsprobleme aussieht.

Termine

Vorlesung: Dienstag, 15:15-16:45 Uhr, R 512 (Sven Kosub)
  Mittwoch, 10:00-11:30 Uhr, R 511 (Sven Kosub)
Übung: Montag, 13:30-15:00 Uhr, L 829 (1: Franziska . Obergfell @ uni . kn)
  Montag, 15:15-16:45 Uhr, L 829 (2: Christian . Abdullahad @ uni . kn)
  Dienstag, 11:45-13:15 Uhr, P 712 (3: Tobias . 2 . Toepfer @ uni . kn)
  Dienstag, 13:30-15:00 Uhr, P 712 (4: Juliane . Woehrn @ uni . kn)
Klausur: Mittwoch, 24.07.2024, 11:00-13:00 Uhr, R 712 (Ersttermin)
  Mittwoch, 16.10.2024, 17:00-19:00 Uhr, R 611 (Zweittermin)

Übungsblätter

Übungsblätter werden immer am Donnerstag (ausschließlich elektronisch) auf der Vorlesungsseite in ILIAS zur Verfügung gestellt.

Die Aufgaben sind innerhalb einer Woche zu bearbeiten. Die Abgabe der Lösung als PDF-Datei ist bis Donnerstag, 23:59 Uhr, per Upload nach ILIAS in die jeweilige Parallelgruppe möglich. Die Besprechung der Aufgaben und die Rückgabe der korrigierten und mit Punkten bewerteten Abgaben erfolgt in der Übung. Das Erlangen von mindestens der Hälfte der möglichen Punkte ist Voraussetzung für die Zulassung zur Klausur.

Alle Aufgaben können und sollen in Zweiergruppen bearbeitet werden.

Inhalt

Inhalte der Vorlesung:

  • Algorithmentheorie
  • Berechenbarkeitstheorie
  • Komplexitätstheorie
  • Automatentheorie
  • Theorie der Formalen Sprachen
  • Algorithmische Lerntheorie

Skriptum

Im Laufe der Vorlesung wird ein Skript zur Vorlesung zur Verfügung gestellt werden. Die jeweils aktuelle Version finden Sie in ILIAS. Sollten Sie Anregungen zum Skript haben oder Fehler jeglicher Art finden, schreiben Sie bitte eine kurze Email.

[Translate to Englisch:]

Literatur

Ergänzendes und vertiefendes Material zu Vorlesung und Skriptum findet sich in folgenden Lehrbüchern:

  • Klaus W. Wagner. Theoretische Informatik. Eine kompakte Einführung. 2. Auflage, Springer-Verlag, Berlin, 2003.
  • Uwe Schöning. Theoretische Informatik - kurz gefasst. 5. Auflage, Spektrum Akademischer Verlag, Heidelberg, 2008.
  • Norbert Blum. Einführung in Formale Sprachen, Berechenbarkeit, Informations- und Lerntheorie. Oldenbourg, München, 2007.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3. Auflage, Prentice Hall, Upper Saddle River, NJ, 2006.
  • Avi Wigderson: Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press, Princeton, NJ, 2019.