Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » pfp » Lösungsvorschlag   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:pfp:loesungss14 [23.07.2015 15:32] – ThiloKpruefungen:bachelor:pfp:loesungss14 [17.02.2017 22:28] (aktuell) – Ezekiel15
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." ist richtig.
 <note tip> <note tip>
 s(n) = 54 s und p(n) = 2 * 6 + 18 s = 30 s => Sp(n) = 54 / 30 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<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();
 +}
 +</code>
  
 ==== Aufgabe 3 (Fehlersuche) ==== ==== Aufgabe 3 (Fehlersuche) ====
 **a)** **a)**
-Stichwortartige Problembeschreibung: \\+Stichwortartige Problembeschreibung:
 Klasse Error1 hat eigene Kopie von finished im Cache und bekommt möglicherweise die globale Änderung nicht mit. Klasse Error1 hat eigene Kopie von finished im Cache und bekommt möglicherweise die globale Änderung nicht mit.
  
Zeile 27: Zeile 60:
  
 **b)** **b)**
-Stichwortartige Problembeschreibung: \\+Stichwortartige Problembeschreibung:
 Da if-Abfrage nicht synchronisiert, wird latch möglicherweise zweimal dekrementiert und Haupt-Thread schläft ewig. Da if-Abfrage nicht synchronisiert, wird latch möglicherweise zweimal dekrementiert und Haupt-Thread schläft ewig.
  
Zeile 34: Zeile 67:
  
 **c)** **c)**
-Stichwortartige Problembeschreibung: \\+Stichwortartige Problembeschreibung:
 In foo() wird run-Methode direkt aufgerufen! In foo() wird run-Methode direkt aufgerufen!
  
-Beheben Sie den Fehler (Zeile 15):+Beheben Sie den Fehler: 
 + 
 +Zeile 15:
 <code java>thread2.start();</code> <code java>thread2.start();</code>
 +
 +==== 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<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
 +</code>
 +
 +==== Aufgabe 5 (gerichteter Graph) ====
 +
 +**a)**
 +<code>
 +def isInPar: (V, List[V]) => Boolean = (v, vs) =>
 +    // .toList. optional
 +    vs.par.filter(_ == v).toList.nonEmpty
 +</code>
 +
 +**b)**
 +<code>
 +def find: (V, G) => List[V] = (v, g) =>
 +    for (x <- g; if( isIn(v, x.out)) ) yield x.v
 +</code>
 +Alternativ:
 +<code>
 +def find: (V, G) => List[V] = (x, a) =>
 +    a.filter { a2 => isIn(x)(a2.out) }.map { a2 => a2.out }
 +</code>
 +
 +==== Aufgabe 6 (Lauflängenkodierung) ====
 +
 +**a)**
 +<code>
 +def encodeHead: Stream[Char] => ((Char, Int), Stream[Char]) = cs => {
 +    val h = cs.head
 +    ((h, cs.takeWhile(_ == h).length), cs.dropWhile( _ == h))
 +}
 +</code>
 +
 +**b)**
 +<code>
 +def encode: Stream[Char] => Stream[(Char, Int)] = cs =>
 + if (cs.isEmpty) Stream.empty
 + else encodeHead(cs)._1#:: encode(encodeHead(cs)._2)
 +</code>
 +**c)**
 +<code>
 +def decode: List[(Char, Int)] => List[Char] = cs =>
 + cs.foldRight( List[Char]() ) ( (e, ls) => List.fill(e._2)(e._1) ::: ls)
 +</code>