Institute of

Theoretical Computer Science

Carl-Friedrich-Gauß-Fakultät

Technische Universität Braunschweig

Bäume, Ordnungen und Anwendungen 2015/2016

Neuigkeiten

Organisation

Vorlesungstermine:

Prüfungsmodalitäten:

Ob es eine mündliche oder eine schriftliche Prüfung gibt, wird zu Beginn der Vorlesungszeit festgelegt. Um zur Prüfung zugelassen zu werden sind die folgenden Voraussetzungen zu erfüllen:
  1. Es sind 60% der Übungsaufgaben mit einem Plus zu lösen (sinnvoll bearbeitet).
  2. Es ist eine Aufgabe an der Tafel vorzustellen.

Vorlesungsaufzeichnungen

Zur Vorlesung gibt es Folien (Stand 12.11.2013) sowie handschriftliche Notizen, die jeweils an dieser Stelle veröffentlicht werden.
  1. Verbände und der Satz von Knaster und Tarski (Woche 1)
  2. Ketten und Monotone Frameworks (Woche 2, korrigierte Version)
  3. Intraprozedurale Analysen (Woche 3, siehe Folien)
  4. Intraprozedurale Analysen (Woche 4, siehe auch Folien)
  5. Interprozedurale Analyse mit Procedure-Summaries (Woche 5)
  6. Interprozedurale Analyse mit Procedure-Summaries und Call-Strings (Woche 6)
  7. Galois-Verbindungen (Woche 7)
  8. Konstruktion von Galois-Verbindungen und konkrete Semantik (Woche 8)
  9. Abstrakte Semantik (Woche 9)
  10. Prädikatenabstraktion (Woche 10)
  11. Abstrakte Semantik zur Prädikatenabstraktion (Woche 11)
  12. Abstraktionsverfeinerung (Woche 12)
  13. Bisimulation (Woche 13)
  14. CTL (Woche 14)

Exercises

Organisatorisches:

Übungsblätter:

Bei Fragen zu oder Problemen mit den Übungen wenden Sie sich bitte an Reiner Hüchting. — Kommen Sie einfach vorbei oder schreiben Sie eine Mail.

Inhalt der Vorlesung

  1. Termersetzung und Programmiersprachen
    • Strukturierte operationelle Semantik (und Induktion)
    • Konfluenz und Backtracking
    • Terminierung und Wohlfundiertheit
  2. Verbandstheorie und Statische Analyse
    • Verbände
    • Fixpunkte
    • Statische Analyse
  3. Baumautomaten und XML
    • XML-Schema und Baumautomaten
    • Abschlusseigenschaften
    • Entscheidungsprobleme
    • Gleichheit und Kardinalität

Literatur