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.

Link zu der Vergleichsansicht

Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:hauptstudium:ls12:rand_2020 [03.11.2020 13:39] – angelegt Zulleyy3pruefungen: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, sodass Prof. Wanka mich viele Male unterbrechen musste und ich nach der ersten Frage komplett fertig mit den Nerven war --> Hatte nen ziemlichen Blackout. +====Anmerkung==== 
-Laut Prof. Wanka hat mich meine unstrukturierte Antwortweise beinahe um die 1.0 gebracht. +  * 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.  
-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, 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. 
-Vielleicht hab ich mich auch nur von meinem Anfangsschock erholt oder Prof. Wanka hatte ein schlechtes Gewissen?+  * 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: Keine Garantie auf Korrektheit, es sind garantiert Ungenauigkeiten im Protokoll, aber die Fragen sollten alle da sein:
  
  
-Die Prüfung: +====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) +===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, 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) 
-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)? (Wollte auf "mit hoher Wahrscheinlichkeit" hinaus, ich stand soooooo krass auf dem Schlauch)+(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) 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,+ 
 +===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 :-/) 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) 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, 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, dass sie noch genau so dalagen. 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. 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.