EN | DE
Theoretische Informatik

Theorie der Programmierung (SS 2016)

Wiederholungsklausur

Die Wiederholungsklausur fand am 20. Februar im H9 statt. Die Klausureinsicht ist am Donnerstag, den 2. März um 12 Uhr in Raum 11.150-113.

Notenverteilung:

statistik-retake-ws2016.png

Notenschlüssel:

Note ab
1.0 38
1.3 35.5
1.7 33
2.0 30.5
2.3 28
2.7 25.5
3.0 23
3.3 20.5
3.7 18
4.0 15.5

Klausur

Das Datum der Klausur kann mittlerweile in mein campus eingesehen werden. Zur Klausur sind sämtliche papierbasierten Hilfsmittel zugelassen. Wir empfehlen einen rechtzeitigen Blick auf die

Fragestunde: Wir bieten am Freitag, den 7. Oktober um 14 Uhr in Raum 00.131-128 eine Fragestunde für die Klausur an.

Klausurtermin: Die Klausur findet am Freitag, den 14.10.2016 um 11:00 Uhr in der Tentoria statt.

Klausurergebnisse: Die Klausur ist korrigiert und die Ergebnisse im Waffel einsehbar. Die Einsicht findet am Freitag, den 04.11.2016 um 10:00 Uhr in Raum 11.150-113 statt.

Notenverteilung:

statistik-ws2016.png

Notenschlüssel:

Note ab
1.0 38
1.3 35.5
1.7 33
2.0 30.5
2.3 28
2.7 25.5
3.0 23
3.3 20.5
3.7 18
4.0 16

Übungsblätter

Die Blätter enthalten Präsenzaufgaben für die Tutorien und bepunktete Hausaufgaben, die zum Erwerb von Bonuspunkten für die Klausur abgegeben und korrigiert werden.

Verteilung der Bonuspunkte: Bonuspunkte erhält, wer mindestens 50% der Punkte in den Hausaufgaben erreicht hat. Die maximale Anzahl an Bonuspunkten (also 6) gibt es bei 90% der Punkte oder mehr, dazwischen wird linear skaliert. Bonuspunkte können wie immer nicht zum Bestehen der Klausur führen sondern lediglich zur Verbesserung der Note bei bestandener Klausur.

Termine

Vorlesungen

Termin Zeit Ort Dozent Beginn
Di. 12:15 - 13:45 H8 Stefan Milius 12.4.
Mi. 16:15 - 17:45 H8

Intensivübung

Termin Zeit Ort Dozent Beginn
Do. 16:15 - 17:45 0.68 Christoph Rauch 21.4.

Tutorien

Die Anmeldung zu den Tutorien erfolgt über Waffel.

Termin Zeit Ort Dozent Beginn
Mo. 18:15 - 19:45 02.133-113 Daniel Hausmann 25.4.
Mi. 08:15 - 09:45 0.151-115 Rafael Kiesel 20.4.
Mi. 10:15 - 11:45 02.133-113 Martin Schmitt 20.4.
Mi. 10:15 - 11:45 02.134-113 Miriam Polzer 20.4.
Do. 10:15 - 11:45 E1.11 Ulrich Rabenstein 21.4.
Do. 14:15 - 15:45 00.152-113 Dominik Paulus 21.4.
Do. 14:15 - 15:45 01.151-128 Lukas Braun 21.4.
Fr. 10:15 - 11:45 01.255-128 Hans-Peter Deifel 22.4.

Die Abgabe der Übungen erfolgt wöchentlich in Gruppen von 2 bis 3 Personen.

Inhalt

Themen

  • Termersetzung
  • λ-Kalkül
  • Semantik von Programmiersprachen, Bereichstheorie
  • Induktion und Koinduktion
  • Reguläre Sprachen und endliche Automaten
  • Stichpunktartige Themenliste

Skript

Es gibt ein auf einer studentischen Mitschrift vom SoSe 2014 basierendes, vorläufig noch inoffizielles

  • Skript [Revision 11825 12327 12804]

welches im Laufe der Veranstaltung überarbeitet wird (siehe Revisionsnummern).

Zusatzmaterial der Tutoren (ohne Gewähr)

  • Folien zu den Tutorien
    • Übung 1 (Termersetzung)
    • Übung 2 (Termersetzung: Termination)
    • Übung 3 (Termersetzung: Konfluenz)
    • Übung 4 (λ-Kalkül: Reduktion, Church-Kodierung)
    • Übung 5 (λ-Kalkül: Rekursion, Typinferenz)
    • Übung 6 (λ-Kalkül: Curry-Howard Isomorphismus; Induktive Datentypen: Definition von Funktionen)
    • Übung 7 (λ-Kalkül: Subjektexpansion; Induktive Datentypen: Folds)
    • Übung 8 (Induktive Datentypen: Induktionsbeweise)
    • Übung 9 (Koinduktive Prozesstypen: Definition von Funktionen, Bisimulationsbeweise)
    • Übung 10 (Koinduktive Prozesstypen: Exponentiation, Kodatentypen mit Alternativen)
    • Übung 11 (System F: Kodierung von Datentypen, Typinferenz)
    • Übung 12 (Reguläre Ausdrücke, Pumping Lemma, endliche Automaten)

Literatur

  • F. Baader, T. Nipkow: Term rewriting and all that, Cambridge University Press, 1999
  • J.-W. Klop, Term rewriting systems, in S. Abramsky, D. Gabbay and T. Maibaum (eds.), Handbook of Logic in Computer Science, Oxford University Press, 1992
  • J. Giesl, Termersetzungssysteme, RWTH Aachen, 2011
  • H. Barendregt, λ-calculi with types, in S. Abramsky, D. Gabbay and T. Maibaum (eds.), Handbook of Logic in Computer Science, Oxford University Press, 1992
  • T. Nipkow, Lambda-Kalkül, TU München, 2004
  • G. Winskel, Formal Semantics of Programming Languages, MIT Press, 1993
  • J. E. Hopcroft, J. D. Ullman and R. Motwani, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Prentice Hall, 2006
  • B. Jacobs, J. Rutten: A Tutorial on (Co-)Algebras and (Co-)Induction, EATCS Bulletin 42 (1997), 222-259.
  • J. Rutten: Automata and Coinduction (an exercise in coalgebra), Proc. CONCUR'98, LNCS 1466, 194-218, Springer, 2006.
  • P. Taylor: Proofs and Types, Cambridge University, 2003
  • M. H. B. Sørensen, P. Urzyczyn: Lectures on the Curry-Howard Isomorphism, 1998
  • A. Pitts: Lecture Notes on Regular Languages and Finite Automata, Cambridge University, 2013