Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Randomisiserte Algorithmen 2020   (Übersicht)

Randomisiserte Algorithmen 2020

Anmerkung

  • Hatte mich sehr intensiv vorbereitet (Potenzielle Fragen zu beinahe allem, Skript + Übungen, aufgeschrieben und simuliert, die sehr hässlichen Beweise (Chernoff) hab ich allerdings nur gelernt, bis ich sie verstanden hatte, nicht so, dass ich sie zweifelsfrei hätte rekonstruieren können.
  • Hab in der Prüfung sehr unstrukturiert geantwortet, sodass Prof. Wanka mich viele Male unterbrechen musste und ich nach der ersten Frage komplett fertig mit den Nerven war –> Hatte nen ziemlichen Blackout. Laut Prof. Wanka hat mich meine unstrukturierte Antwortweise beinahe um die 1.0 gebracht.
  • Prof. Wanka hilft weiter wenn man mal feststeckt und die Fragen werden gefühlt netter, je schlechter die Prüfung läuft. Vielleicht hab ich mich auch nur von meinem Anfangsschock erholt oder Prof. Wanka hatte ein schlechtes Gewissen?

Keine Garantie auf Korrektheit, es sind garantiert Ungenauigkeiten im Protokoll, aber die Fragen sollten alle da sein:

Die Prüfung

Warum verwenden wir randomisierte Algorithmen?

(Hab angefangen von Einfachheit, beweisbarer Abschätzung des Erwartungswerts etc. zu erzählen, aber er wollte nur hören: „Weil's einfacher ist“. Dann hab ich noch ganz frech ungefragt ergänzt, dass es die prob. Methode gibt die ja auch irgendwie mit dieser Einfachheit verwandt ist)

Was ist MinCut?

(Problem + Algo erklären + Analyse, das war die Stelle an der ich vor lauter Nochmal-fragen fast irre geworden bin weil's doch eigentlich extrem easy ist, ich aber offenbar zu jedem Zeitpunkt genau das gesagt habe, was Prof. Wanka wann anders hören wollte)

Wahrscheinlichkeitsverstärkung für MinCut?

Warum ist denn da der Erwartungswert im Exponenten?

(Also ich kurz auf dem Schlauch stand weil ich die Form (1 - 1/x)^x nicht erkannt hab obwohl ich's kurz davor sogar noch allgemein erklärt hatte)

Warum machen wir das (Wahrscheinlichkeitsverstärkung)?

(Wollte auf „mit hoher Wahrscheinlichkeit“ hinaus, ich stand soooooo krass auf dem Schlauch) Ein umgangssprachlich klingender Begriff… (Dann ist's mir urplötzlich eingefallen)

Was hatten wir denn mit hoher Wahrscheinlichkeit bei Bällen und Kisten gezeigt?

(log/log(log)-Schranke für größte Ballzahl in einer Kiste, gesamte Analyse schriftlich, stand mehrmals brutal auf dem Schlauch, hab zwischendrin sogar mal durch meine zusammengebissenen Zähne „Sch ich konnte das doch gestern noch“ hindurchgeflucht :-/) Als ich gefragt hab, ob ich die Abschätzung (n k) >= (ne/k)^n zeigen soll meinte er, wenn ich's kann soll ich's machen, also hab ich's schnell hergeleitet und dabei erklärt. Das klang so ein bisschen nach „Hier ich schenk Ihnen ein paar Punkte“, ich hab sie natürlich dankend angenommen) Nach der Frage hatte ich mich dann wieder so ein bisschen gefangen, den letzten Teil der Rechnung wollte er dann leider nur noch beschreibend hören (vielleicht war die Zeit knapp?)

Was hatten wir denn zuerst mit Monte-Carlo gemacht?

  • Ich bin mir jetzt mit der Reihenfolge unsicher…
  • #COL, #DNF, Pi annähern in der Übung, …Bei der Annäherung an Pi haben wir zwei Schranken gezeigt… was war denn da der Unterschied?
  • Einmal mit Tscheb und einmal mit Chern, Tscheb hatte die bessere Konstante, war also im ungenauen, uninteressanten Bereich besser, aber die Abschätzung mithilfe von Chern hatte das explosive 1/Delta im Logarithmus statt als Faktor, was natürlich viel toller ist.

Danach

Ich hab mir spaßeshalber mal gemerkt wie meine Blätter dalagen und nach dem Reinkommen erstaunt festgestellt, dass sie noch genau so dalagen. Auf Nachfrage meinte Prof. Wanka auch, dass das nur eine Hilfe für den Prüfling sei woraufhin ich gefragt hab, ob ich auch eine Katze hätte malen können. Da hat Prof. Wanka seine Brille abgenommen, große Augen gemacht und gemeint, dass er das dank seiner Weitsichtigkeit schon gemerkt hätte. Schließlich hat er mir noch sehr eindringlich empfohlen an meiner Fähigkeit strukturiert zu antworten zu arbeiten, weil mich jemand der nicht im Thema drin ist wohl nicht besonders toll verstanden hätte :-/ Ich war nach dieser Prüfung so fertig mit den Nerven, dass ich um ein Haar die Maske abgenommen hätte um meine Prüfungsbanane zu essen…