Sie sind nicht angemeldet.

1

27.03.2005, 11:40

Komplexitätstheorie Prüfung

Hallo,

erstmal Frohe Ostern an Alle!!!

Hat jemand schon die Komplexitätstheorie Prüfung hinter sich und kann mir sagen, was wichtig war, was für Fragen gestellt wurden sind und wie es sonst so ablief? Für jeden Hinweis schon mal einen schönen Dank.

Gruß,
Christian

NixWisse

Trainee

Beiträge: 64

Registrierungsdatum: 11.10.2004

2

27.03.2005, 12:48

RE: Komplexitätstheorie Prüfung

Hallo,

ich habe die Prüfung schon seit Anfang Februar hinter mir. Wahrscheinlich hast Du drauf gehofft, dass ich Dir jetzt einiges sage, was Du nicht lernen musst. Aber da muss ich Dich enttäuschen.
Es wird quer durch das ganze Skript von der ersten bis zur letzten Vorlesung gefragt. Und wenn Du eine 1 vorm Komma haben willst, solltest Du unbedingt auch einen Plan von den Beweisen haben.

Also dann viel Spaß beim Lernen. Ist wirlklich ne ganze Menge. Aber Prof. Vollmer ist ja kein Unmensch und hilft auch weiter, wenn man nicht mehr weiter weiß.
Wenn man sich gut vorbereitet hat, ist die Prüfung ok. Aber das ist wohl fast immer so ;-)

Banshee

Alter Hase

Beiträge: 43

Registrierungsdatum: 09.12.2001

3

27.03.2005, 15:33

Frage zu Beweis von Satz 2.8

Mir ist bei dem o.g. Beweis nicht ganz klar wieso man die Menge B' benutzt. Der einzige Grund der mir einfällt, ist der, daß es dann möglich ist eine Abschätzung der Wahrscheinlichkeit über |x| zu formulieren, die letztlich dann zu der letzten Abschätzung von 2/3 führt.

Ist das korrekt, oder habe ich etwas grundlegenderes bei dem Beweis nicht verstanden?

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

4

28.03.2005, 18:13

RE: Frage zu Beweis von Satz 2.8

Zitat

Original von Banshee
Mir ist bei dem o.g. Beweis nicht ganz klar wieso man die Menge B' benutzt. Der einzige Grund der mir einfällt, ist der, daß es dann möglich ist eine Abschätzung der Wahrscheinlichkeit über |x| zu formulieren, die letztlich dann zu der letzten Abschätzung von 2/3 führt.

Ist das korrekt, oder habe ich etwas grundlegenderes bei dem Beweis nicht verstanden?
Genau. Um zu zeigen, daß BPP^BPP = BPP gilt, simuliert man das verwendete BPP-Orakel durch eine BPP-Maschine. Um bei dieser Simulation in Sachen Laufzeit nicht von den konkreten Orakelfragen abhängig zu sein, fordert man, daß die Eingabe der ursprünglichen Maschine immer Teil der Orakelfragen ist.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

5

30.03.2005, 19:46

RE: Komplexitätstheorie Prüfung

Hallo,

für die, die die Prüfung noch vor sich haben, Definitionen scheinen sehr wichtig zu sein. Also lernt die Sätze auswendig!!! Beweise sind wohl weniger wichtig, aber man sollte erklären können, warum eine Klasse eine Teilmenge einer anderen Klasse ist.

Euch allen viel Glück!!!