FSI Informatik/pruefungen/hauptstudium/ls2/paralg-2014-02-10

Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » paralg-2014-02-10 (Übersicht)

Fach: Parallele Algorithmen
Prüfer: Veldema, Beisitzer Dotzler
Stimmung: Allgemein sehr angenehme Stimmung, Prüfer waren gut drauf und freundlich. Wenn man etwas nicht wusste wurde nachgeholfen.
Vorbereitung: Die Programmieraufgaben gemacht, dann 3 Tage lang die Übungen gemacht und die fehlenden Begriffe aus der Vorlesung aus den entsprechenden Folien gelernt.
Vorbereitungsverbesserung: Die Vorlesung selbst zumindest durchzulesen wäre wohl nicht verkehrt gewesen, da die Übungen zwar einen Großteil, aber eben nicht alles abgedeckt haben.
Note: 1,3
Dauer: ~30 min.

P: Prüfer
S: Student

P: Warum sollte man sich mit Parallelen Algorithmen beschäftigen?
S: Prozessoren gehen mehr in Richtung viele Kerne anstatt ein immer schnellerer Kern.

P: Was ist Lastverteilung?
S: Aufteilung der Arbeit auf die verschiedenen Kerne.

P: Was ist gute Lastverteilung?
S: Wenn alle Kerne in etwa gleich viel rechnen können.

P: Was ist schlechte Lastverteilung?
S: Wenn ein Kern viel rechnet und andere Kerne im idle sind.

P: Was ist parallele Effizienz?
S: Wusste es nicht. (Gemeint war wohl Amdahl, das war die nächste Frage)

P: Ok, was ist das Gesetz von Amdahl?
S: SpeedUp = (Tseq / (Tpseq + Tpar / Np)).
Hatte das / Np vergessen, da wurde mir dann ein Tip gegeben, dass noch eine Linie und ein Buchstabe mit einem P fehlt.

P: Man hat die Zahlen -1 3 4 8 0. Mach mal ein Comparator Network, das diese Zahlen sortiert.
S: Nur für den speziellen Fall oder allgemein?
P: Allgemein ist immer besser.
S: *Aufgezeichnet*

-1    3    4    8    0
 |    |    |    |    |
 +----+    |    +----+
 |    +----+    |    |
 |    |    +----+    |
 |    +----+    +----+
 +----+    |    |    |
 |    |    |    |    |

P: Wir haben in der Vorlesung einen Algorithmus gemacht mit dem man beliebige Comparator Networks erzeugen kann. Wie würde das funktionieren?
S: *Rumgestöpselt ohne tatsächlich was zu sagen*
P: Da gabs doch was mit geraden und ungeraden Inputs.
S: *Schlicht nicht gewusst.*
Gemeint war der Algorithmus aus der VL bei dem zunächst gerade und ungerade inputs aufgesplittet werden und der dann rekursiv wieder auf die kleineren Listen angewandt wird, bis man nur noch 2 Inputs pro Comparator hat. Danach werden die Outputs dann wieder aufsteigend rekursiv zusammengemerged.

P: Was ist Data Mining?
S: Das Finden von Zusammenhängen zwischen verschiedenen Datensätzen, wie zum Beispiel welche Items in einem Supermarkt oft zusammen gekauft werden.

P: Sie arbeiten bei der NSA und möchten Telefongespräche der Leute abhören. Wenn jetzt Person A mit Person B immer zur gleichen Uhrzeit telefoniert, und Person C mit Person D auch immer am gleichen Tag zur gleichen Uhrzeit telefoniert ist das verdächtig. Wie finden Sie das heraus?
S: Map Reduce. Input partitionieren und auf Prozesse aufteilen, alle Telefongespräche aller Personen auf Uhrzeiten mappen und dann parallel Reduce machen. Dann evtl. nach Uhrzeit sortieren und dann kann man sehen ob viele Telefongespräche der gleichen Leute zur gleichen Uhrzeit stattgefunden haben.
P: Also machen Sie eine Frequency Table?`
S: Genau.

P: Wie findet man die Anzahl aller strongly connected nodes (also nodes die mit allen anderen Nodes verbunden sind) in einem Graphen?
S: Für jeden Node einen Thread starten, testen wie viele Nachbarn der Node hat, wenn Anzahl Nachbarn == Anzahl Nodes - 1, dann hat man einen strongly connected node gefunden → counter erhöhen.

P: Wie findet man alle Komponenten eines Graphen?
S: Für jeden Node wieder einen Thread starten, jeder Node verschmilzt mit seinen Nachbarn (Election → nur die mit kleinerem Index dürfen verschmelzen), Anzahl der Nodes die übrig bleiben ist die Anzahl der Komponenten.

P: Was ist die Laufzeit von diesem Algorithmus?
S: O(n)? … *nachdenken* O(logn). (O(logn) ist richtig)

P: Wie macht man eine Tiefensuche parallel?
S: Für jeden besuchten Knoten startet man für jedes Kind einen neuen thread.

P: Wie macht man eine Breitensuche parallel?
S: Beim Einstieg in root todo liste machen. Dann alle ersten Knoten sammeln, in todo liste, dann todo liste parallel besuchen, wobei es eine 2. todo liste gibt, in die jeder Thread die Kinder des besuchten Knotens schreibt. Dann die neue Todo liste besuchen und wiederholen.

P: Was ist IDA*?
S: Nicht gewusst, auch nach Nachhelfen nicht.

P: Sie haben das Integral von 0 bis 10 von cos(x) * tan(x) * x, wie rechnet man das parallel aus? Tip: Gibt 2 Methoden.
S: 1. Methode Monte-Carlo, Punkte auf den Graphen 'schießen', Verhältnis Treffer/Nichttreffer == Fläche
S: 2. Methode Finite Element, Viele kleine Rechtecke unter den Graph matchen, dann Fläche der Rechtecke zusammenzählen.

P: Was ist eine Markov Kette?
S: Eine Berechnungskette, bei der jeder Zustand einen festen Nachfolger hat.

P: Kann man Schnick Schnack Schnuck (Stein Schere Papier) als Markov Kette simulieren?
S: Ja, wenn die Spieler nicht versuchen sich gegenseitig einzuschätzen und nicht dazulernen.

P: Was ist das Knapsack Problem und wie kann man es parallel lösen?
S: Man hat einen Rucksack mit begrenzter Kapazität und Gegenstände mit gewissem Wert und gewisser Größe, diese möchte man so in den Rucksack packen, dass man möglichst viel Wert im Rucksack hat. NP-vollständiges Problem, alle Möglichkeiten mit Heuristik durchprobieren: „Wertdichte“ der Gegenstände berechnen und dann parallel verschiedene Kombinationen im Rucksack ausprobieren.

P: Sie haben eine Cocktailbar, mit 1000 Zutaten und möchten den perfekten grünen Cocktail mischen. Wie würde man das anstellen?
S: Mit genetischen Algorithmen rumgestöpselt, man kann zufällig Zutaten ändern oder Zutaten von bereits gelungenen Cocktails miteinander mischen.
Hätte wohl noch mehr sein können, war aber scheinbar in Ordnung.

P: Wie kann man die Cocktails so mischen, dass ein parallel ausgeführter genetischer Algorithmus exakt das gleiche Ergebnis bringt wie ein sequentiell ausgeführter?
S: Nicht gewusst.
Gemeint war ein Manager, der entscheidet was gut und was schlecht ist, und der dann Arbeit auf die Worker verteilt, die dann die tatsächliche Berechnung durchführen.

P: Wie kann man parallel Bitstreams multiplizieren?
S: Aufteilen, dann parallel substreams miteinander multiplizieren, auf exponent achten, dann alle Ergebnisse addieren.

P: Wie kann man parallel Bitstreams addieren?
S: Aufteilen, dann substreams parallel addieren, dabei beachten dass man einen Übertrag bekommen kann. Dementsprechend spekulativ einmal mit und einmal ohne Übertrag addieren und beim zusammenfügen die entsprechenden Werte nehmen.

P: Wie kann herausfinden, aus welchen zwei größten Primzahlen addiert eine Zahl besteht? Also gegeben wäre 3, Ergebnis wäre 2 + 1, 6 wäre 3 + 3, 8 wäre 5 + 3 etc.
S: Man berechnet alle Primzahlen bis zur gefragten Zahl, und subtrahiert dann parallel jede Primzahl einmal von der Zahl, die Ergebnisse die eine weitere Primzahl ergeben kann man dann auswerten und die größten Zahlen nehmen.