Prüfung Theorie Boolscher Schaltkreise

absynth

Gründervater

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

1

Monday, August 21st 2006, 2:30pm

Moin,

hat jemand der werten Anwesenden schon mal die Prüfung "Theorie Boolscher Schaltkreise" abgelegt und kann sich noch erinnern, was und wie gefragt wurde?

Danke,

--ck

I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Monday, August 21st 2006, 2:45pm

RE: Prüfung Theorie Boolscher Schaltkreise

Quoted

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.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962