Fachrat Informatik - Forum

Hi,

SAT-Algorithmen ist, wie der Name schon sagt, nah an der algorithmischen Seite. Hier sollte man sich das Verständnis der Algorithmen erarbeiten und ihre Laufzeiten erläutern können. Da alle Algorithmen prinzipiell mit Erfüllbarkeit von aussagenlogischen Formeln zu tun haben, muss man einen guten Überblick haben, um nicht die verschiedenen Ansätze zu vermischen. Ein weiterer Teil der Vorlesung behandelt Enumeration (auch eher algorithmisch) und Resolution, welches natürlich beweistheoretischer ist. Hier wird ein theoretisches Spiel eingeführt mit dem man untere Schranken für Beweisgrößen beweisen kann. Außerdem ist der Teil über parametrisierte Komplexität zu SAT aus den Übungen prüfungsrelevant.

Für Logik und Komplexität benötigt man ein gutes Verständnis von Reduktionen sowie Komplexitätsklassen (über P und NP hinaus). Hier werden viele (Modallogik, Default Logik, Temporale Logik, Hybride Logik) verschiedene Logik-Formalismen eingeführt und an Hand von Fragmenten genauer komplexitätstheoretisch klassifiziert. Der rote Faden der Vorlesung ist der Post'sche Verband. Hier geht es darum eine vollständige Klassifikation bzgl. aller Boole'schen Fragmente von einer betrachteten Logik zu untersuchen. Hierzu muss man einige (doch recht theoretische) Konzepte wie Clones und Funktioneneigenschaften verstehen und anwenden können. Hier sind Zusammenhänge (warum man etwas macht) auch wichtig. Außerdem tauchen auch recht ungewöhnliche Komplexitätsklassen wie Schaltkreisklassen oder NLOGTIME/coNLOGTIME auf. Das letzte drittel der Veranstaltung beschäftigt sich mit deskriptiver Komplexitätstheorie. Hier muss man in erststufiger Logik fit sein und die Zusammenhänge der einzelnen Resultate gut verstehen.

Wie üblich werden Beweise die länger als 5min dauern zu erklären nicht in der Prüfung im Detail sondern im Verständnis und in der Vorgehensweise abgefragt. Definitionen und Sätze sollten aber ohne großes Warten erläutert und (notfalls) auch aufgeschrieben werden können.

Nicht zu vergessen, dass es auch eine neue Veranstaltung im Bereich THI geben wird, nämlich Kryptografie… Vielleicht ist das auch was für Dich ;-)