Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » pfp » Lösungsvorschlag (Übersicht)
Inhaltsverzeichnis
Lösungsvorschlag
Aufgabe 1 (Wissensfragen)
a)
- Bei 3 Arbeitspaketen wird ein Speedup von 1.8 gemessen.
- Auch „bei 2 Arbeitspaketen wird ein Speedup von 1.5 gemessen.“ ist richtig.
s(n) = 54 s und p(n) = 2 * 6 + 18 s = 30 s ⇒ Sp(n) = 54 / 30
b)
- Das Schalten von Transitionen ist atomar.
- Keine Belegung des Petri-Netzes ist im Erreichbarkeitsgraph doppelt vorhanden.
c)
- 1. & 4.
Aufgabe 2 (Longest Common Subsequence)
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<Object>(); // 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, c); } 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:
static volatile boolean finished = false;
b) Stichwortartige Problembeschreibung: Da if-Abfrage nicht synchronisiert, wird latch möglicherweise zweimal dekrementiert und Haupt-Thread schläft ewig.
Beheben Sie den Fehler:
synchronized(Error2.class) { /* if-Abfrage */ }
c) Stichwortartige Problembeschreibung: In foo() wird run-Methode direkt aufgerufen!
Beheben Sie den Fehler:
Zeile 15:
thread2.start();
Aufgabe 4 (Monte-Carlo-Simulation)
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<Integer>[] hitArray = new Future[tasks]; // TODO: 1 for(int i = 0; i < tasks; i++){ hitArray[i] = exec.submit(new MonteCarloTask(i, tasks, globalCnt)); } 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<Integer> { 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) => // .toList. optional 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
Alternativ:
def find: (V, G) => List[V] = (x, a) => a.filter { a2 => isIn(x)(a2.out) }.map { a2 => a2.out }
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, Int)] = cs => if (cs.isEmpty) Stream.empty else encodeHead(cs)._1#:: encode(encodeHead(cs)._2)
c)
def decode: List[(Char, Int)] => List[Char] = cs => cs.foldRight( List[Char]() ) ( (e, ls) => List.fill(e._2)(e._1) ::: ls)