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

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

pruefungen:hauptstudium:ls12:rand_2023-10-10_1 [10.10.2023 09:55] – angelegt captainrppruefungen:hauptstudium:ls12:rand_2023-10-10_1 [10.10.2023 10:01] (aktuell) – Formatierung angepasst captainrp
Zeile 1: Zeile 1:
-# Stimmung+====== Randomisierte Algorithmen (10.10.2023) ======
  
-- Die Atmosphäre war entspannt. Wir waren mit Professor Wanka und Matthias in einem Büro an einem kleinen Rundtisch. Ich erinnere mich an eine Klausur im Jahr 2020 bei Professor Wanka, die mir stressiger erschien. Das könnte möglicherweise auch Corona geschuldet gewesen sein. +===== Meta Informationen =====
-- Ich habe mich bemüht, langsamer zu sprechen (da ich normalerweise sehr schnell spreche) und alles detailliert zu erläutern. Das schien hilfreich zu sein, und die Zeit verging rasch. +
-- Die Untersuchung der ersten Algorithmen, insbesondere die zugrundeliegenden Konzepte, wurden detailliert abgefragt. Der Fokus lag weniger auf Arithmetik, sondern eher darauf, wie man beispielsweise bestimmte Wahrscheinlichkeit abschätzen kann. +
-- Die späteren Algorithmen wurden bei mir nicht abgefragt. Bei den anderen Prüfungsprotokollen hatte ich aber das Gefühl, dass dort die genauen Berechnungen weniger wichtig werden und es mehr um die Ideen geht.+
  
-# Prüfung+* Randomisierte Algorithmen (7.5ECTS) im SS23 
 + 
 +* Datum: 10.10.2023 
 + 
 +* Prüfer: Professor Wanka und Matthias Kergaßner 
 + 
 +* Evaluation: 
 +  * Die Atmosphäre war entspannt. Wir waren mit Professor Wanka und Matthias in einem Büro an einem kleinen Rundtisch. Ich erinnere mich an eine Klausur im Jahr 2020 bei Professor Wanka, die mir stressiger erschien. Das könnte möglicherweise auch Corona geschuldet gewesen sein. 
 +  * Ich habe mich bemüht, langsamer zu sprechen (da ich normalerweise sehr schnell spreche) und alles detailliert zu erläutern. Das schien hilfreich zu sein, und die Zeit verging rasch. 
 +  * Die Untersuchung der ersten Algorithmen, insbesondere die zugrundeliegenden Konzepte, wurden detailliert abgefragt. Der Fokus lag weniger auf Arithmetik, sondern eher darauf, wie man beispielsweise bestimmte Wahrscheinlichkeit abschätzen kann. 
 +  * Die späteren Algorithmen wurden bei mir nicht abgefragt. Bei den anderen Prüfungsprotokollen hatte ich aber das Gefühl, dass dort die genauen Berechnungen weniger wichtig werden und es mehr um die Ideen geht. 
 + 
 +===== Prüfung =====
  
 Ich beschreib hier größtenteils nur die Fragen, da die meisten Antworten im Skript stehen Ich beschreib hier größtenteils nur die Fragen, da die meisten Antworten im Skript stehen
  
-## MinCut+==== MinCut ====
  
-### Einführung +=== Einführung === 
-- Was ist das MinCut Problem? +* Was ist das MinCut Problem? 
-- Wie schnell wäre der deterministische Algorithmus+ 
 +* Wie schnell wäre der deterministische Algorithmus
   * Hier hat gereicht dass er polynomiell und recht kompliziert ist   * Hier hat gereicht dass er polynomiell und recht kompliziert ist
   * Anscheinend kennt Wanka mittlerweile einen einfacheren deterministischen MinCut Algorithmus, den er bei EffKombAlg vorstellen will   * Anscheinend kennt Wanka mittlerweile einen einfacheren deterministischen MinCut Algorithmus, den er bei EffKombAlg vorstellen will
-- Wie funktioniert der randomisierte Algorithmus? 
-- Warum wählen wir die Kanten uniformly at random? 
  
-### Analyse+* Wie funktioniert der randomisierte Algorithmus?
  
-- Wie haben wir den analysiert (Referenzschnitt genommen, etc., Wahrscheinlichkeit dass Referenzschnitt genommen wird ist untere Schranke für Korrektheit) +* Warum wählen wir die Kanten uniformly at random? 
-- Ist die Größe eines minimalen Schnitts im verkleinerten Graphen gleich? + 
-- Was bringt es uns, |K|/|E_i| durch <= 2/|V_i| (In der Abschätzung kommt |K|, das wir nicht kennen, nicht mehr vor) +=== Analyse === 
-- Wie oft müssen wir erwartet wiederholen (1/p, geometrische Verteilung, Wahrscheinlichkeitsverstärkung) + 
-- Wie nennt man das dann?+* Wie haben wir den analysiert (Referenzschnitt genommen, etc., Wahrscheinlichkeit dass Referenzschnitt genommen wird ist untere Schranke für Korrektheit) 
 + 
 +* Ist die Größe eines minimalen Schnitts im verkleinerten Graphen gleich? 
 + 
 +* Was bringt es uns, |K|/|E_i| durch <= 2/|V_i| (In der Abschätzung kommt |K|, das wir nicht kennen, nicht mehr vor) 
 + 
 +* Wie oft müssen wir erwartet wiederholen (1/p, geometrische Verteilung, Wahrscheinlichkeitsverstärkung) 
 + 
 +* Wie nennt man das dann?
   * Mit Hoher Wahrscheinlichkeit   * Mit Hoher Wahrscheinlichkeit
   * Man kann die Fehlerwahrscheinlichkeit über das c beliebig drücken.   * Man kann die Fehlerwahrscheinlichkeit über das c beliebig drücken.
   * c geht linear in die Anzahl Versuche aber exponentiell in die Wahrscheinlichkeit   * c geht linear in die Anzahl Versuche aber exponentiell in die Wahrscheinlichkeit
  
-## MaxCut+==== MaxCut ====
  
-### Einführung+=== Einführung ===
  
-- Was ist das MaxCut Problem?+* Was ist das MaxCut Problem?
   * Unterteilen von V in disjunkte A und B   * Unterteilen von V in disjunkte A und B
   * Entscheidungsproblem ist NP-Vollständig   * Entscheidungsproblem ist NP-Vollständig
   * Wir können aber mit probablistischer Methode zeigen, dass A und B mit c(A, B) >= |E|/2 existieren   * Wir können aber mit probablistischer Methode zeigen, dass A und B mit c(A, B) >= |E|/2 existieren
-- Worüber iteriert der Algorithmus? + 
-- Warum iteriert der Algorithmus über die Knoten, nicht die Kanten?+* Worüber iteriert der Algorithmus? 
 + 
 +* Warum iteriert der Algorithmus über die Knoten, nicht die Kanten?
   * Weil wir dann für manche Kanten gar nicht mehr würfeln könnten, das wäre dann kein Schnitt   * Weil wir dann für manche Kanten gar nicht mehr würfeln könnten, das wäre dann kein Schnitt
  
-### Analyse +=== Analyse === 
-- Wie analysieren wir den MaxCut Algorithmus? +* Wie analysieren wir den MaxCut Algorithmus? 
-- Wie kommen wir auf die Erfolgswahrscheinlichkeit? (per Erwartungswert) + 
-- Was ist die erwartete Anzahl Wiederholungen?+* Wie kommen wir auf die Erfolgswahrscheinlichkeit? (per Erwartungswert) 
 + 
 +* Was ist die erwartete Anzahl Wiederholungen?