Theoretische Informatik
Theoretische Informatik II
Theoretische Informatik 

Theoretische Informatik II - Sommersemester 2024

Dozent: Dominik Scheder vorname.nachname@@informatik.tu-chemnitz.de

 

Termine: Vorlesung Dienstag 13:45 - 15:15 A10.205 (alt: 1/205) Dominik Scheder
    Mittwoch 11:30 - 13:00 A12.346 (alt: 1/346) Dominik Scheder
           
  Übung Montag 09:15 - 10:45 A10.205 (alt: 1/205) Simon Schulze
    Freitag 13:45 - 15:15 A10.208.1 (alt: 1/208A) Simon Schulze

Nach aktuellem Stand sollen die mündlichen Probeprüfungen am Freitag, den 02.08. im Zeitraum von 11:00-12:30 Uhr stattfinden (Raum: A12.346 (alt: 1/346)). Bitte melden Sie sich bei mir (Simon Schulze) per Mail, falls Sie teilnehmen möchten. Falls Sie zum angegebenen Zeitpunkt verhindert sind, schreiben Sie mir bitte ebenfalls eine Mail, damit wir eine Lösung finden. Eventuell wird, je nach Interesse, noch ein weiterer Slot angeboten. Informationen dazu folgen in Kürze.

Prüfung: Die mündlichen Prüfungen finden am 7. und 8. August 2024 statt oder nach Absprache per Email. Um sich für einen Zeitslot am 7. oder 8. August anzumelden, gehen Sie bitte auf

https://www.tu-chemnitz.de/informatik/theoretische-informatik/TI-2/2024-07-pruefung-registration-A(3,6)=XXX/

wobei Sie XXX durch den tatsächlichen Wert der Ackermann-Funktion $A(3,6)$ ersetzen.

Hinweis zur mündlichen Prüfung: Es wird einen Aufgabenzettel geben, anhand dessen wir uns durch den Stoff bewegen werden. Wichtig: Ich erwarte nicht, dass wir alle Fragen in den 20 Minuten schaffen. Die Fragen dienen als Gerüst für die mündliche Prüfung. Hier sehen Sie zwei solcher Zettel aus meiner Zeit an der Hochschule Zittau/Görlitz, die ähnliche Themen wie hier abgedeckt haben, damit Sie sich einen Eindruck machen können (Zettel 1 und Zettel 2). Die Themenauswahl auf diesen beiden Zetteln ist als Beispiel zu betrachten. Die Themen der Modulprüfung muss nicht auf die Themen beschränkt sein, die auf diesen Zetteln vorkommen!

Vorlesungsskript

Mein Vorlesungsskript liegt ausschließlich online vor. Sie finden es hier. Über Hinweise zu Fehlern, toten Links etc. freue ich mich!

Übungsblätter

Sprechstunden

Dienstag, 15:30 - 17:00 und Mittwoch, 9:15 - 10:45. An anderen Tagen gerne auch, dann aber online und nach Verabredung!

Inhalt

  1. Boolesche Schaltkreise.
  2. Unendliche Mengen.
  3. Berechenbarkeitsbegriff auf natürlichen Zahlen: Primitive Rekursion.
  4. Formale Sprachen, insbesondere: reguläre Sprachen, endliche Automaten, reguläre Ausdrücke.
  5. Kontextfreie Sprachen. Parser.
  6. Turingmaschinen und Berechenbarkeit.
  7. Komplexitätstheorie: Laufzeit und Speicherbedarf.

Literatur

  • Michael Sipser: Introduction to the Theory of Computing
  • Uwe Schöning: Theoretische Informatik - kurz gefasst

TUCaktuell