Vorlesung Theoretische Informatik für Berufsschullehrer im berufsbegleitenden Studium
Wintersemester 2004/05

Prüfung/Schein:

Inhalt:

1. Theorie der Berechenbarkeit
2. Komplexitätstheorie
3. Formale Sprachen

Literatur:

• Skript (PDF-Format)
  • script0.pdf Vorwort, Inhalt, Literatur (7.10.2004)
  • script1.pdf Mathematische Grundlagen (7.10.2004)
  • script2a.pdf Begriffe der Berechenbarkeit
  • script2b.pdf Unentscheidbarkeit
  • script3.pdf Komplexitätstheorie
  • script4.pdf Formale Sprachen
• U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag, 1994.

Folien: (PDF-Format)

• folien00.pdf Mathematische Grundlagen (7.10.2004)
• folien01.pdf Turingmaschinen (7.10.2004)
• folien02.pdf WHILE-Programme (28.10.2004)
• folien03.pdf Entscheidungsprobleme (9.11.2004)
• folien04.pdf Komplexitätstheorie (25.11.2004)
• folien05.pdf Formale Sprachen - Teil 1 (04.01.2005)
• folien06.pdf Reguläre Sprachen (04.01.2005)
• folien07.pdf Kontextfreie Sprachen (21.01.2005)
• halteproblem-naiv.pdf das Halteproblem und seine Unentscheidbarkeit in naiver Formulierung
• domino.pdf Beispiel für die Reduktion von einer NTM auf das Domino-Problem
  Achtung: Seiten 1,2 im Querformat, Seiten 3,4 im Hochformat
• nea_beispiel.pdf Beispiel für das Verhalten eines nichtdeterministischen endlichen Automaten

Übungsblätter:

• uebung01.pdf Serie 1
• uebung02.pdf Serie 2
• uebung03.pdf Serie 3
• uebung04.pdf Serie 4
• uebung05.pdf Serie 5

Informationen:

• Stundenplan laut Univis
• Die Vorlesungen beginnen jeweils um 11:00 Uhr
• Die Vorlesungen finden ab dem 23.11.2004 im Raum G29-E037 statt.
• Die Gespräche zum Erwerb des Scheines finden am 08.02.2005 von 11:00-13:00 Uhr im Raum G29-020 statt.