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

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:bachelor:pfp:loesungws15 [16.07.2016 16:31] – Aufgaben 1, 4, 5 eingefügt Marcel[Inf]
+++ pruefungen:bachelor:pfp:loesungws15 [19.07.2018 15:50] (aktuell) – evren
@@ Zeile 1: / Zeile 1: @@
 ====== Aufgabe 1 ======
+  * a) 1 und 4
-  * a) volatile, synchronized. (static ? Aber keine Sichtbarkeitsgarantie im 'parallelen' Sinne)
+  * b) 2 und 4
-  * b) p(n) ist der parallele Anteil. B_p ist der Speedup.
+        Da nur nach gefragt ist, was den Speedup verbessern **könne**, ist 4 auch richtig, da es in manchen Fällen eine bessere Lastverteilung sichern könnte. (Mit dieser Logik wäre es auch richtig, auf die Frage, was den Speedup verschlechtern könne, dasselbe zu antworten. Denn kleinere Arbeitspakete können ab einem bestimmten Maße mehr Overhead und Synchronisationsaufwand nach sich ziehen.)
-  * c) Entzug von Betriebsmitteln. Globale Ordnung der Betriebsmittel.
-  * d) Filteroperationen. Abbildungsoperationen (z. B. map)
-====== Aufgabe 4 ======
+  * c) 2 und 3 (siehe Seite 26 VL Folie: https://www2.cs.fau.de/teaching/SS2016/PFP/slides/secure/pfp-08.pdf)
-== Block 1 ==
-  new CyclicBarrier(threads + 1);
+====== Aufgabe 2 ======
-== Block 2 ==
+  * a)
-  for (int i = 0; i < threads; i++) {
+<code=java>AtomicInteger curThreads = new AtomicInteger(0);</code>
-    int end = start + step; // exclusive upper bound
-    if (i == threads - 1) {
+  * b)
-      end = array.length;
+<code=java>
-    }
+boolean manageThreads(String linkUrl) {
-    Thread thread = new CountingThread(start, end);
+  if (curThreads.incrementAndget() <= maxThreads) {
-    thread.start();
+      CrawlThread t = new CrawlThread(linkUrl);
+      t.start();
   }
+  else {
+    curThreads.decrementAndGet();
+    return false;
+  }
+} // END OF manageThreads
+</code>
-== Block 3 ==
+  * c)
-  for (int i = 0; i < count.length; i++) {
+<code=java>
-    globalCounts.addAndGet(i, count[i]);
+public void run() {
-  }
+  process();
+  curThreads.decrementAndGet();
+}
+</code>
-== Block 4 ==
+  * d)
-  // oben
+<code=java>
-  barrier.await();
+synchronized(visitedUrls) {
+  if(!visitedUrls.contains(linkUrl)){
+    doVisit = true;
+    visitedUrls.add(linkUrl);
+  }
+}
+</code>
+====== Aufgabe 3 ======
+{{:pruefungen:bachelor:pfp:ws15-16-aufgabe3.png?200|}}
+Nicht gefragt, hier aber erwähnt:
+Beschränktheit: Da der Erreichbarkeitsgraph endlich ist, ist das Petri-Netz beschränkt.
+Lebendigkeit: Nicht lebendig, da im Zyklus [1, 0, 0, 1], [0, 1, 3, 1] und [0, 2, 0, 1] (rechts im Erreichbarkeitsgraphen) nicht mehr herauskommt und in diesem t1 nicht mehr schaltet.
+====== Aufgabe 4 ======
+  * a) 3
+  Nein ist nicht möglich, s wird bereits mit anderen Werten belegt, bevor das Programm parallel ausgeführt wird. Die Sichtbarkeit der in Zeile 25 festgelegten Werte ist gewährleistet (genauer [nicht VL-Stoff]: Es existiert im Allgemeinen eine Happens-Before Ordnung zwischen Code vor start() und dem Thread-Code.)
+  * b) 2
+  Nein, "Geralt" ist keine mögliche Ausgabe. Das Auslesen der als volatile deklarierten Variable in Zeile 25 garantiert uns, dass im Hauptthread alles sichtbar ist, was ein anderer Thread vor dem letzten Setzen der Variable gesehen hat (genauer: "A write to a volatile field happens-before every subsequent read of that field.", [[https://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html|Abschnitt 17.4.5 in der JLS]]).
+  * c) 4
+  Nein, da die Threads wieder gejoint wurden. Das Programm ist somit nicht mehr parallel. Die Sichtbarkeit ist im (einzigen) Haupt-Thread gewährleistet (genauer [nicht VL-Stoff]: Es existiert im Allgemeinen eine Happens-Before Ordnung zwischen Thread-Code und Code nach einem erfolgreichen join()-Aufruf).
-  // unten
+Was bringt hier, dass s als volatile deklariert ist? volatile wirkt sich nur auf die Referenz selbst aus, diese wird aber nie geändert, könnte also genauso gut finaln sein.
-  barrier.await();
 ====== Aufgabe 5 ======
   * a)
+<code=scala>
+def insert: (List[Int], Int) => List[Int] = (ls, v) => ls match {
+  case Nil => List(v)
+  case x::xs => {
+    if (v <= x) {
+      v :: x :: xs
+    }
+    else {
+      x :: insert(xs, v)
+    }
+}</code>
+Alternativ:
+<code=scala>
+def insert: (List[Int], Int) => List[Int] = (ls, v) => {
+    val p = ls.partition(_ <= v)
+    p._1 ::: v :: p._2
+}
+</code>
+Alternativ:
+<code=scala>
+def insert: (List[Int], Int) => List[Int] = (ls, v) =>
+    (for (l <- ls if l <= v) yield l) ::: (v :: (for (l <- ls if l > v) yield l))
+</code>
-  def flatten: List[(Char, Char)] => List[Char] = input =>
-    input.map(tuple => List(tuple._1, tuple._2)).flatten
   * b)
-  def countPar: List[Char] => List[(Char, Int)] = cs =>
+<code=scala>
-    cs.par.map(c => (c, cs.par.filter(_ == c).size)).toList
+def sort: List[Int] => List[Int] = ls =>
+  ls.foldRight(List[Int]())((v, sortedList) => insert(sortedList, v))
+// Alternativ zu "List[Int]()":
+// Nil: List[Int]
+// Aber unbedingt mit Typangabe, sonst schlägt Scala's Type Inference fehl
+</code>
   * c)
-  def distinct: List[(Char, Int)] => List[(Char, Int)] = xs =>
+<code=scala>
-    xs.foldLeft(List[(Char, Int)]())((res, curEntry) => if (res.contains(curEntry)) res else curEntry :: res)
+def sortAllWith: (List[Int] => List[Int]) => List[List[Int]] => List[List[Int]] =
+  sortFun => ls => for (cur <- ls) yield sortFun(cur)
+</code>
+Falls man nicht unbedingt eine Listenabstraktion hätte verwenden müssen:
+<code=scala>
+def sortAllWith: (List[Int] => List[Int]) => List[List[Int]] => List[List[Int]] = function => list => {
+    list.map(x => function(x))
+}
+</code>
 ====== Aufgabe 6 ======
   * a)
-  def decodeTuple: ((Char, Int)) => Stream[Char] = {
+<code=scala>
-    case (c, count) if count > 0 => c #:: decodeTuple((c, count - 1))
+def testInside: (Ellipse, Ellipse) => (Double, Double) => Boolean =
-    case (c, count) => Stream.Empty
+  (e1, e2) => (x, y) => isInside(e1, x, y) && isInside(e2, x, y)
-  }
+</code>
   * b)
-  def decode: Stream[(Char, Int)] => Stream[Char] = {
+<code=scala>
-    case Stream.Empty => Stream.Empty
+def tupleStream: Stream[Double] => Stream[(Double, Double)] = s =>
-    case ts => {
+  (s.head, s.tail.head) #:: tupleStream(s.tail.tail)
-      decodeTuple(ts.head) #::: decode(ts.tail)
-    }
+  // alternativ
-  }
+  (s(0), s(1)) #:: tupleStream(s.drop(2))
+</code>
+  * c)
+<code=scala>
+def monteCarlo: (Ellipse, Ellipse) => Int => Int = (e1, e2) => count => {
+  // Stream aus Punkten
+  val pointStream = tupleStream(randomStream)
+  pointStream.take(count).par.filter(p => testInside(e1, e2)(p._1, p._2)).length
+  // .count wirft einen komischen Fehler von Scalas Type Inference System
+  // "missing argument list for method count" => .length oder .size benutzen
+}
+</code>