Prüfungsprotokolle lesen
Protokolle (2 gefunden)
| Nr. | Prüfer | Fach |
| 989 | Kratsch, Prof | Parameterized Algorithms |
Protokoll
27.7.2022 === Benötigte Lernzeit als Empfehlung === Hab ungefähr eine Woche 2-4 Stunden pro Tag gelernt. Im Nachhinein hätte ich vermutlich ein paar Tage früher angefangen. Hab die Vorlesungen und Übungen immer besucht, und mich ab und zu mal mit Kommilitonen über bestimmte Fragen ausgetauscht. === Verwendete Materialien (Bücher, Skripte etc...) === Folien der Vorlesung. === "Atmosphäre" der Prüfung / Verhalten der Beisitzer === Normal für eine mündliche Prüfung. War während der Prüfung weniger gestresst als kurz davor. Prof. Kratsch war sehr freundlich. === Prüfungsfragen === (Nur ungefähr, und kann sein, dass ich was vergessen/verdrängt habe) 1. Allgemeines über das Thema - Was sind FPT Algorithmen? - Warum funktionieren FPT Algorithmen nicht für alle Paramter (z.B. Vertex Cover mit Parameter der den minimalen Grad beschreibt)? 2. Kernelization - Zusammenhang zwischen Kernelization und FPT? - Wie kann man aus FPT eine Kernelization machen? - Was ist eine Crown Decomposition? - Wie kann man Crown Decomposition benutzen, um Kernelization hinzubekommen? 3. Bounded Search Trees - Wie funktioniert Branching mit Vertex Cover? Welche Lauzeit? 4. Iterative Compression - Was ist Iterative Compression (also Foo Deletion Problem, Foo Compression, Foo Disjoint)? - Warum gilt der Trick, dass wenn Disjoint Foo Laufzeit a^k hat, dass dann Compression Foo Laufzeit (a+1)^k hat? - Wie funktioniert Iterative Compression für Feedback Vertex Set? Laufzeit? 5. Randomized Methods - Wie kann man Feedback Vertex Set noch schneller hinbekommen? (Antwort: Randomized Methods) - Wie funktioniert das? - Wie kann man Long Path derandomisieren? 6. Tree Width - Was ist Baumweite? - Was ist eine Tree Decomposition? - Wie benutzt man das, um Maximum Independent Set zu lösen? - Was ist eine Nice Tree Decomposition? - Was ist eine Join Node? - Wie funktioniert die Rekurrenz von Forget Node (für Maximum Independent Set)? === Note == 2.7 - Wie man von FPT zu Kernelization kommt, wusste ich nicht richtig. - Ich hab Crown Decomposition nicht wirklich gelernt (nur das für Maximum Satisfiability, was aber nicht dran kam :P). - Wie man derandomisiert wusste ich auch nicht wirklich, nur halt irgendwas von wegen Färbungsfamilien mit bestimmten Eigenschaften - Beim ganzen Treewidth Kapitel hatte ich Schwierigkeiten mich auszudrücken, hätte da bei den Fragen auch mehr Zeit gebraucht, um mich da nochmal einzuarbeiten. Hab deswegen auch bei der Frage über die Rekurrenz von Forget Node das glaube ich mit Introduce Node verwechselt. - Ansonsten, bis auf die oben genannten Punkte hatte ich zumindest das Gefühl, dass ich die Fragen gut beantworten konnte, also vom Verständnis her. Das Erklären hat dann doch nicht so gut funktioniert: Insgesamt legt er sehr viel Wert darauf, dass man sich klar und präzise ausdrückt, also sodass "Kommilitone das verstehen könnten". Das hab ich wohl eher nicht so gut hinbekommen. Fairerweise hat Prof. Kratsch mehrfach in den Vorlesungen gesagt, dass man üben sollte, die Konzepte und Algorithmen anderen Leuten zu erklären. === Fazit (Gute/schlechte Prüfung, angemessene Benotung etc...) === Benotung finde ich größtenteils angemessen. Finde aber insgesamt, dass die Prüfung zu kurz ist, als dass man genug Zeit haben könnte, jede Frage schön, ordentlich, und präzise zu beantworten, ohne dass man das vorher zu jedem Thema auswendig gelernt hat. Kann aber auch an mir liegen, bin eher ein bisschen langsam im Denken.
| Nr. | Prüfer | Fach |
| 1069 | Kratsch, Prof | Parameterized Algorithms |
Protokoll
= Datum der Prüfung | 29.07.26 = Benötigte Lernzeit als Empfehlung | Habe selbst 5 Tage gebraucht, hatte aufgrund vorheriger Prüfung auch nicht mehr Zeit. = Verwendete Materialien (Bücher, Skripte etc...) | Skript und Mitschriften = "Atmosphäre" der Prüfung / Verhalten der Beisitzer | Siehe Unten = Prüfungsfragen | Grundlegend gingen alle Fragen in die Richtung: Problem | Wie löst man das? Ging los mit Closest String, habe den Algorithmus erklärt. Nachfrage: Wieso braucht man maximal d Schritte. Odd Cycle Transversal: Iterative Compression erklären am Beispiel, Algorithmus erklären, Laufzeit mit Binomialthereom erklären. Habe ich alles gekonnt. Ob es eine Frage zu DP gab, weiß ich nicht mehr. Randomized Method mit Beispiel Feedback Vertex Set. Baumzerlegungsalgorithmen anhand von Dominating Set, wollte aber nur DP für Forget und Join Node. Dann ging es noch kurz um Intractability Reduktionen mit Clique von und zu Set Packing. Dann noch erklärung Exponential Time Hypothesis und wie man damit Lower-Bounds für Vertex Cover impliziert. Sparsification Lemma sollte auch erklärt werden. Die Prüfung ist jetzt 2 Wochen her, ich könnte also Dinge vergessen haben. = Note (Optional) | 1,0 = Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...) Die Prüfung kam mir sehr schnell getaktet vor, auch weil fast alle Themen abgefragt wurden. Fand sie um ehrlich zu sein eher unentspannt und oberflächlich. Habe mich einige male verhaspelt etc. Punkte übersprungen die ich eigentlich wusste und bei denen nochmal nachgehakt wurde. Hatte also einige Unsicherheiten, bin dennoch mit 1,0 davongekommen, Note also eindeutig wohlwollend.