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:29] – 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) ====
Zeile 35: Zeile 68:
 **c)** **c)**
 Stichwortartige Problembeschreibung: Stichwortartige Problembeschreibung:
-In foo() wird run-Methode direkt aufgerufen!  +In foo() wird run-Methode direkt aufgerufen! 
-Beheben Sie den Fehler: \\+ 
 +Beheben Sie den Fehler: 
 Zeile 15: 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>