Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Randomisiserte Algorithmen 2020 (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Nächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:hauptstudium:ls12:rand_2020 [03.11.2020 13:39] – angelegt Zulleyy3 | pruefungen:hauptstudium:ls12:rand_2020 [11.11.2020 15:12] (aktuell) – Zulleyy3 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | Anmerkung: | + | ===== Randomisiserte Algorithmen 2020 ===== |
- | 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, | + | ====Anmerkung==== |
- | 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. | + | * Hab in der Prüfung sehr unstrukturiert geantwortet, |
- | Vielleicht hab ich mich auch nur von meinem Anfangsschock erholt oder Prof. Wanka hatte ein schlechtes Gewissen? | + | |
Keine Garantie auf Korrektheit, | Keine Garantie auf Korrektheit, | ||
- | Die Prüfung: | + | ====Die Prüfung==== |
- | Warum verwenden wir randomisierte Algorithmen? | + | ===Warum verwenden wir randomisierte Algorithmen? |
- | 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) | + | (Hab angefangen von Einfachheit, |
- | 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) | + | ==Was ist MinCut?== |
- | Warum machen wir das (Wahrscheinlichkeitsverstärkung)? | + | (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" | ||
Ein umgangssprachlich klingender Begriff... (Dann ist's mir urplötzlich eingefallen) | 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/ | + | |
+ | ===Was hatten wir denn mit hoher Wahrscheinlichkeit bei Bällen und Kisten gezeigt?=== | ||
+ | (log/ | ||
stand mehrmals brutal auf dem Schlauch, hab zwischendrin sogar mal durch meine zusammengebissenen Zähne " | stand mehrmals brutal auf dem Schlauch, hab zwischendrin sogar mal durch meine zusammengebissenen Zähne " | ||
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", | 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", | ||
Nach der Frage hatte ich mich dann wieder so ein bisschen gefangen, | 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?) | 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: | + | ===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, | Ich hab mir spaßeshalber mal gemerkt wie meine Blätter dalagen und nach dem Reinkommen erstaunt festgestellt, | ||
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. | 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. |