Sie sind nicht angemeldet.

NanoBug

Zuhörer

  • »NanoBug« ist der Autor dieses Themas

Beiträge: 1

Registrierungsdatum: 25. September 2016

1

Sonntag, 25. September 2016, 12:18

Wahl einer THI Veranstaltung

Hallo meine Lieben,

ich bin mit meinem Masterstudium fast am Ende und habe jetzt noch das Problem mich für eine der beiden THI Veranstaltungen "SAT-Algorithmen" und "Logik und Komplexität" zu entscheiden und wollte da mal eure Meinung hören. GTI und KVA habe ich beide ganz gut meistern können und würde mir das Fach jetzt gerne im Selbststudium aneignen. Hat jemand von euch schon eines oder idealerweise beide Fächer belegt und kann mir einen kleinen Tipp geben welches der beiden Fächer "besser" ist? :)

Vielen Dank und liebe Grüße!

Arne

ThI

  • »Arne« ist männlich

Beiträge: 1 797

Registrierungsdatum: 7. Oktober 2002

Wohnort: Hannover :)

Beruf: Lecturer ThI

2

Montag, 26. September 2016, 09:37

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.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

deHaar

Trainee

  • »deHaar« ist männlich

Beiträge: 49

Registrierungsdatum: 7. März 2013

3

Dienstag, 27. September 2016, 08:08

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 ;-)
time flies like arrows and fruit flies like apples