In der letzten Sitzung der Studienkommission wurde die letztes Jahr beschlossene Lösung für das Aufwands- und Kapazitätsproblem der LVA “Verteilte Algorithmen” um ein Jahr verlängert: Es ist nun auch im Sommersemester 2011 möglich, statt der LVA “Verteilte Algorithmen” zwei von drei Lehrveranstaltungen aus Komplexitätstheorie, SAT Solving und Erweiterungen und Semantik von Programmiersprachen zu absolvieren. Der entstehende Überhang von 1.5 ECTS (Verteilte Algorithmen hat 4.5 ECTS, die drei anderen LVAs haben jeweils 3) wird als Wahlfach anerkannt.
Wir wurden in der Studienkommission gebeten, jene Kenntnisse, die die Kollegen Pichler, Egly und Gramlich in ihren LVAs erwarten, explizit hervor zu heben:
- Komplexitätstheorie: Prinzipiell werden die in den LVAS “Theoretische Informatik & Logik” sowie Formale Methoden der Informatik als bekannt vorausgesetzt. Wichtig sind insbesondere Kenntnisse in Mathematischer Logik, den grundlegenden Konzepten der Komplexitätstheorie und vor allem Reduktion. Passend dazu ist z.B. das erste Übungsblatt (Referenzlösung) aus Formale Methoden. Weitere Informationen bietet auch die HP der LVA.
- Semantik von Programmiersprachen: Die Homepage wird in den nächsten Tagen noch aktualisiert. Sobald wir die Infos haben, werden sie auch hier erwähnt.
- SAT Solving & Erweiterungen:
- Aussagen- und Prädikatenlogik: Syntax, Normalformen und Normalformtransformationen. Semantik, Evaluierung einer gegebenen Formel bzgl. einer gegebenen Interpretation, Konzept der logischen Folgerbarkeit (entailment) auch unter Theorien, Überführung von Validity, Entailment, Equivalence und Satisfiablity ineinander, Beweisverfahren (Tableau, Sequenzsysteme oder NK anwenden koennen)
- Einfache Beweise führen: Prinzip des Induktionsbeweis (+ einfache Beispiele). Einfache Beispiele zur Abschätzung von Laufzeiten und Speicherbedarf (Beispiel: Zeige, dass die Zeitkomplexität der Breitensuche bei fixem Verzweigungsgrad b und Tiefe d in O(b^d) liegt. Erwartet wird ein formal korrekter Beweis inkl. Erklärungen wie O-Notation.)
Die Vorkenntnisse entstammen der LVAs Theoretischer Informatik und Logik, Formale Methoden der Informatik, Algorithmen und Datenstrukturen und den einführenden Mathematikveranstaltungen. Die Logikkenntnisse werden vor allem im TIL Skriptum und in den Folien von Block Satisfiability (SAT) aus Formale Methoden der Informatik vermittelt.
Abschließend wollen wir noch darauf hinweisen, dass die LVA Verteilte Algorithmen im neuen Studienplan (höchstwahrscheinlich) kein Pflichtfach mehr sein wird. Studierende, die von der Regelung dieses Semester lieber noch nicht Gebrauch machen wollen (etwa, weil ihnen Formale Methoden noch fehlt), können also auch einfach abwarten.
update (3.März): Es gibt nun den aktuellen Beschluss der Stuko im Mitteilungsblatt vom 2.3.2011