Original von absynth
hat jemand der werten Anwesenden schon mal die Prüfung "Theorie Boolscher Schaltkreise" abgelegt und kann sich noch erinnern, was und wie gefragt wurde?
Das ist bei mir schon zwei Jahre her, die Erinnerungen sind also ziemlich dunkel. Das folgende habe ich mir beim Überfliegen des Skriptes zusammengereimt:
- Definitionen der Komplexitätsmaße und -klassen
- Beziehungen der Klassen zueinander
- Definitionen der Reduzierbarkeiten
- Reduktionen zwischen verschiedenen Problemen erklären und "vorrechnen" (natürlich nur die nicht extrem komplizierten)
- Aussage des Satzes von Smolensky erklären und mit Inklusionsdiagramm der Komplexitätsklassen verdeutlichen
- Beweis für eine der beiden Schranken für die Größe allgemeiner Schaltkreis vormachen
Die Art der Fragen ist so wie immer bei Herrn Vollmer. Es werden möglichst präzise Antworten erwartet, Beweise sollten zudem auch vorgemacht werden können. Die eher zahlentheoretischen Beweise in dieser Vorlesung sind dabei nicht ganz so wichtig. Da reicht es, die Aussage und die Beweisidee erklären zu können.