Theoretische Informatik für Berufsschullehrer im berufsbegleitenden Studium

Sommersemester 2007

Prüfung/Schein:

• Klausur zum Erwerb eines unbenoteten Übungsscheines findet am 17. Juli 2007 von 8:00 bis 09:30 Uhr m Raum G29-E037 statt.
  Alle, die die Klausur mitgeschrieben haben, haben bestanden!

Inhalt:

• Modelle der Berechenbarkeit
  Turingmaschinen, Loop-Programme, While-Programme
• Entscheidbarkeit
  Entscheidungsprobleme, Halteproblem für Turingmaschine und seine Unentscheidbarkeit
• Komplexitätstheorie
  Zeit- und Platzkomplexität, Komplexitätsklassen, NP-Vollständigkeit
• Formale Sprachen
  Regelgrammatiken, Chomsky-Hierarchie, endliche Automaten, reguläre Ausdrücke, Kellerautomaten, Pumping-Lemmata für reguläre und kontextfreie Sprachen

Literatur:

• Skriptum
• U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag, 1994.

Folien:

• Inhalt und Literatur
• Mathematische Grundlagen
• Berechenbarkeit
• Entscheidbarkeit
• Komplexität
• Beispiel Domino
• Formale Sprachen

Übungsblätter:

• Übungsblatt zu mathematischen Grundlagen
• 1. Übungsblatt
• 2. Übungsblatt
• 3. Übungsblatt
• 4. Übungsblatt
• 5. Übungsblatt
• Weiteres Übungsblatt

Informationen:

• Stundenplan laut Univis
• Die Übungen finden 14-tägig statt, immer in den geraden Kalenderwochen, das erste Mal also am 17. April.