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:47] – 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) ====
-<note important>Not verified yet!</note> 
  
 <code java> <code java>
Zeile 24: Zeile 24:
  final int threadId = i;  final int threadId = i;
  queues[threadId] = new LinkedBlockingQueue<Object>();  queues[threadId] = new LinkedBlockingQueue<Object>();
 + // TODO: 1
  int step = (columns - 1) / threads;  int step = (columns - 1) / threads;
  final int start = 1 + i * step;  final int start = 1 + i * step;
Zeile 30: Zeile 31:
  Thread t = new Thread() { public void run() { try {  Thread t = new Thread() { public void run() { try {
  for (int row = 1; row < rows; row++) {  for (int row = 1; row < rows; row++) {
 + // TODO: 2
  if (threadId > 0) {  if (threadId > 0) {
  queues[threadId - 1].take();  queues[threadId - 1].take();
Zeile 41: Zeile 43:
  t.start();  t.start();
  } // Ende der for-Schleife #1  } // Ende der for-Schleife #1
 + // TODO: 3
  for (int i = 1; i < rows; ++i) {  for (int i = 1; i < rows; ++i) {
  queues[threads - 1].take();  queues[threads - 1].take();
Zeile 50: Zeile 53:
 ==== 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 57: 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 64: 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>