Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » pfp » Lösungsvorschlag
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Nächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:pfp:loesungss14 [23.07.2015 15:07] – angelegt ThiloK | pruefungen:bachelor:pfp:loesungss14 [24.07.2015 09:17] – awkward_Silence | ||
---|---|---|---|
Zeile 4: | Zeile 4: | ||
**a)** | **a)** | ||
* Bei 3 Arbeitspaketen wird ein Speedup von 1.8 gemessen. | * Bei 3 Arbeitspaketen wird ein Speedup von 1.8 gemessen. | ||
+ | * Auch "bei 2 Arbeitspaketen wird ein Speedup von 1.5 gemessen." | ||
<note tip> | <note tip> | ||
- | s(n) = 54 s und p(n) = 2 * 6 + 18 s = 30 s => Speedup | + | s(n) = 54 s und p(n) = 2 * 6 + 18 s = 30 s => Sp(n) = 54 / 30 |
</ | </ | ||
Zeile 13: | Zeile 14: | ||
**c)** | **c)** | ||
- | * def g: ((Int, Int) => Int) => Int | + | * 1. & 4. |
- | * (def g: ((Int, Int) => Int) => Int) | + | |
==== Aufgabe 2 (Longest Common Subsequence) ==== | ==== Aufgabe 2 (Longest Common Subsequence) ==== | ||
+ | |||
+ | <code java> | ||
+ | public char[] lcs() throws Exception { | ||
+ | for (int i = 0; i < threads; i++) { // Anfang der for-Schleife #1 | ||
+ | final int threadId = i; | ||
+ | queues[threadId] = new LinkedBlockingQueue< | ||
+ | // TODO: 1 | ||
+ | int step = (columns - 1) / threads; | ||
+ | final int start = 1 + i * step; | ||
+ | final int end = (i == threads - 1) ? columns - 1 : start + step; | ||
+ | |||
+ | Thread t = new Thread() { public void run() { try { | ||
+ | for (int row = 1; row < rows; row++) { | ||
+ | // TODO: 2 | ||
+ | if (threadId > 0) { | ||
+ | queues[threadId - 1].take(); | ||
+ | } | ||
+ | for (int c = start; c < end; c++) { // fuelle Zeile des Blocks | ||
+ | table[row][c] = calcValue(row, | ||
+ | } | ||
+ | queues[threadId].put(READY); | ||
+ | } | ||
+ | } catch (InterruptedException e) {}}}; | ||
+ | t.start(); | ||
+ | } // Ende der for-Schleife #1 | ||
+ | // TODO: 3 | ||
+ | for (int i = 1; i < rows; ++i) { | ||
+ | queues[threads - 1].take(); | ||
+ | } | ||
+ | return readMatrix(); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ==== Aufgabe 3 (Fehlersuche) ==== | ||
+ | **a)** | ||
+ | Stichwortartige Problembeschreibung: | ||
+ | Klasse Error1 hat eigene Kopie von finished im Cache und bekommt möglicherweise die globale Änderung nicht mit. | ||
+ | |||
+ | Beheben Sie den Fehler: | ||
+ | <code java> | ||
+ | |||
+ | **b)** | ||
+ | Stichwortartige Problembeschreibung: | ||
+ | Da if-Abfrage nicht synchronisiert, | ||
+ | |||
+ | Beheben Sie den Fehler: | ||
+ | <code java> | ||
+ | |||
+ | **c)** | ||
+ | Stichwortartige Problembeschreibung: | ||
+ | In foo() wird run-Methode direkt aufgerufen! | ||
+ | |||
+ | Beheben Sie den Fehler: | ||
+ | |||
+ | Zeile 15: | ||
+ | <code java> | ||
+ | |||
+ | ==== Aufgabe 4 (Monte-Carlo-Simulation) ==== | ||
+ | |||
+ | <code java> | ||
+ | import java.util.Random; | ||
+ | import java.util.concurrent.*; | ||
+ | public class MonteCarlo { | ||
+ | |||
+ | public static double pi(int tasks, int globalCnt) throws Exception { | ||
+ | ExecutorService exec = Executors.newFixedThreadPool(tasks); | ||
+ | Future< | ||
+ | // TODO: 1 | ||
+ | for(int i = 0; i < tasks; i++){ | ||
+ | | ||
+ | } | ||
+ | int hits = 0; | ||
+ | // TODO: 2 | ||
+ | for (int i = 0; i < tasks; i ++){ | ||
+ | hits += hitArray[i].get(); | ||
+ | } | ||
+ | exec.shutdown(); | ||
+ | return (((double) hits) / globalCnt) * 4; | ||
+ | } // Ende pi | ||
+ | |||
+ | static class MonteCarloTask implements Callable< | ||
+ | private Random rnd; | ||
+ | private int id; | ||
+ | private int tasks; | ||
+ | private int globalCnt; | ||
+ | |||
+ | public MonteCarloTask(int id, int tasks, int globalCnt) { | ||
+ | this.id = id; // des Task-Objekts und des 1. simulierten Punktes | ||
+ | this.tasks = tasks; | ||
+ | this.globalCnt = globalCnt; | ||
+ | this.rnd = new Random(); | ||
+ | } | ||
+ | |||
+ | private double nextDouble() { | ||
+ | return rnd.nextDouble(); | ||
+ | } | ||
+ | |||
+ | public Integer call() { | ||
+ | int mySum = 0; | ||
+ | // TODO: 3 | ||
+ | for (int i = id; i < globelCnt; i += tasks){ | ||
+ | double x = nextDouble(); | ||
+ | double y = nextDouble(); | ||
+ | x = x * x; | ||
+ | y = y * y; | ||
+ | if(x + y <= 1) mySum++; | ||
+ | } | ||
+ | return mySum; | ||
+ | } // Ende call | ||
+ | } // Ende class MonteCarloTask | ||
+ | } // Ende class MonteCarlo | ||
+ | </ | ||
+ | |||
+ | ==== Aufgabe 5 (gerichteter Graph) ==== | ||
+ | |||
+ | **a)** | ||
+ | < | ||
+ | def isInPar: (V, List[V]) => Boolean = (v, vs) => | ||
+ | vs.par.filter(_ == v).toList.nonEmpty | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | < | ||
+ | def find: (V, G) => List[V] = (v, g) => | ||
+ | for (x <- g; if( isIn(v, x.out)) ) yield x.v | ||
+ | </ | ||
+ | |||
+ | ==== Aufgabe 6 (Lauflängenkodierung) ==== | ||
+ | |||
+ | **a)** | ||
+ | < | ||
+ | def encodeHead: Stream[Char] => ((Char, Int), Stream[Char]) = cs => { | ||
+ | val h = cs.head | ||
+ | ((h, cs.takeWhile(_ == h).length), cs.dropWhile( _ == h)) | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | < | ||
+ | def encode: Stream[Char] => Stream[(Char, | ||
+ | if (cs.isEmpty) Stream.empty | ||
+ | else encodeHead(cs)._1#:: | ||
+ | </ | ||
+ | **c)** | ||
+ | < | ||
+ | def decode: List[(Char, Int)] => List[Char] = cs => | ||
+ | cs.foldRight( List[Char]() ) ( (e, ls) => List.fill(e._2)(e._1) ::: ls) | ||
+ | </ |