Prüfungsprotokolle lesen
Protokolle (1 gefunden)
| Nr. | Prüfer | Fach |
| 1011 | Meyerhenke, Henning Prof. Dr. | GALA - Graphenalgorithmen un Lineare Algebra Hand in Hand |
Protokoll
= Art der Prüfung
- Mündlich
= Datum der Prüfung
- 24.07.2023
= Benötigte Lernzeit als Empfehlung
- 1 Woche, um zu bestehen (3-4 h am Tag)
- 2 Wochen für eine gute Note (3-4 h am Tag)
- 3 Wochen, wenn man eine 1.0 haben will (3-4 h am Tag)
= Verwendete Materialien (Bücher, Skripte etc...)
- Skript
- Folien
- Übungsblätter
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
- Entspannte Atmospähre
- Beisitzer war nett
= Prüfungsfragen
- Skizzieren Sie grob die Themen, die wir in der VL besprochen haben!
-> Daraus leitet sich dann meistens direkt ein Thema ab, was im Detail
besprochen wird.
- 1. Thema: Elektrische Nähe-Zentralität und elektrischer Widerstand
- Formel für elektrische Nähe- und Ferne-Zentralität
- Wie kann man den effektiven Widerstand einer Kante berechnen
- Welche Elemente der pseudoinversen der Laplace-Matrix braucht man konkret
für diese Summe?
- Welche Algorithmen gibt es für das Lösen der Laplace-Gleichungssysteme?
- Welche Laufzeit haben die und warum?
- Wie kann man die Laufzeit verbessern?
- 2. Thema: JLT + Dimensionsreduktion
- Was man die JLT (Johnson-Lindenstrauss-Transformation)
- Wieso verbessert das die Laufzeit?
- Schreiben Sie den Dimensionsreduktionsalgorithmus auf!
- Erklären Sie, was in jeder Zeile gemacht wird.
- Erklären Sie, was die Zeilen und Spalten der berechneten Matrizen
aussagen!
- Wie viele LGS müssen gelöst werden in dem Algorithmus?
- Wie viele müssten ohne den Algorithmus gelöst werden?
- 3. Thema: APD (All Pair Distances)
- Schreiben Sie den Algorithmus für APD auf in Pseudocode!
- Erklären Sie, was in jeder Zeile gemacht wird!
- Welche Laufzeit hat der Algorithmus und warum?
- Woher kommen die log(n) rekursiven Aufrufe?
- Wie berechnet man die Matrix S (gemeint war hier die Matrix, die die Länge
aller Wege von einem Knoten i zu einem Knoten j von den Nachbarn von i
aufsummiert)?
- Wie berechnet sich die Distanzmatrix rekursiv?
- Wann kann der Algorithmus abgebrochen werden?
- 4. Thema: BPWM (Boolean Product Witness Matrix)
- Gegeben war der BPWM-Algorithmus als Folie
- Erklären Sie, was der Algorithmus macht!
- Geben Sie die Laufzeit an!
- Warum wächst die Teilmenge r aus der Knotenmenge V nach jeder der log(n)-
iterationen um den Faktor r = r^t (t = Iteration)?
- Erklären Sie, wieso wir durch das Urnenmodell fast alle Zeugen finden
können mit log^2(n) Iterationen!
- Wie werden die restlichen Zeugen berechnet?
- Wie oft wird der Algorithmus BRUTE-FORCE aufgerufen und warum?
- Welche Laufzeit hat BRUTE-FORCE und warum?
= Note (Optional)
- Sehr gut
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
- Faire Prüfung, gemessen an dem, was man in VL gelernt hat. Es ist überhaupt nicht schlimm, wenn es mal hakt bei einem Thema in der Prüfung und man keine Erklärung parat hat. Dann wird einem geholfen bzw. zur Not auch das Thema gewechselt, damit der Prüfer einen besseren Eindruck davon bekommen kann, viel viel und in welcher Tiefe gelernt wurde. Details sind oft gut zu wissen, aber es gibt einige Dinge, die man auf jeden Fall können sollte: Matrix-Operationen, Matrix-Vektoren Operationen, Formeln und deren Umformungen sowie die besprochenen Algorithmen und ihre Laufzeiten. Weniger relevant sind aus der VL vorgestellte Paper in der Prüfung.