Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Parallele Algorithmen   (Übersicht)

Parallele Algorithmen

März 2012
Prüfer war Ronald Veldema, Beisitzer Prof. Philippsen. Beide waren sehr entspannt und freundlich.

Fragen

  • Man steht am Eingang eines Labyrinths und möchte den Weg zu einem Ziel finden, das sich irgendwo darin befindet. Wie macht man das?
  • Wie würde man diese Suche parallel machen?
    Hier habe ich kurz meine Idee erklärt und in ein paar Zeilen Pseudocode skizziert: wenn man an eine Kreuzung kommt mehrere Threads starten und in alle möglichen Abzweigungen „loslaufen“ lassen, wenn sie das Ziel finden melden sie das zurück. War etwas tricky, v.a. weil er explizit Breitensuche haben wollte. Dazu brauchte ich eine Queue zum Speichern der Positionen der Threads, auf die Zugriffe synchronisiert werden mussten, wie macht man das? Zum Beispiel Ticketing-Algorithmus…
  • Er hat eine kleine Schleife hingeschrieben und 2 LTL-Ausdrücke und gefragt ob diese hier zutreffen.
  • Danach hat er die Schleife zu einem parfor gemacht und einen CTL-Ausdruck ganz ähnlich zu dem ersten hingeschrieben. Gilt der auch?
    Ausdruck stimmte hier nicht, weil es in dem parfor zu Race Conditions kam.
  • Kann man ein Schachspiel durch Markov-Ketten darstellen?
    Ja, weil…
  • 4 Zahlen sollen durch ein Sortierernetzwerk geordnet werden, wie sieht das Netz aus?
    Braucht insgesamt 5 Verbindungen, die Zahl von ganz links muss nach ganz rechts wandern können und umgekehrt.