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

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:bachelor:pfp:loesungws15 [16.07.2016 16:09] – Angelegt :) Marcel[Inf]
+++ pruefungen:bachelor:pfp:loesungws15 [18.07.2016 16:35] – Marcel[Inf]
@@ Zeile 1: / Zeile 1: @@
 ====== Aufgabe 1 ======
-  * a) Sequentieller Umstieg, Beschränkung der Parallelität.
+  * a) 1 und 4
-  * b) Das Schalten einer Transition erfolgt atomar. (Hat jmd. (Gegen-)argumente für "Die Petri-Netze enthalten lebendige Transitionen"?)
-  * c) Die parallale Effizienz ist 2. Der Speedup ist 16.
+  * b) 2 und 4 (???) (einerseits bessere Lastverteilung, andererseits mehr Overhead / Synchronisationsaufwand)
+  * c) 2 und 3 (siehe Seite 26 VL Folie: https://www2.cs.fau.de/teaching/SS2016/PFP/slides/secure/pfp-08.pdf)
 ====== Aufgabe 2 ======
-== Block 1 ==
+  * a)
-  new CyclicBarrier(nThreads);
+<code=java>AtomicInteger curThreads = new AtomicInteger(0);</code>
-== Block 2 ==
+  * b)
-  // Lösung mit einzelnen Thread-Objekten auch denkbar
+<code=java>
-  ExecutorService es = Executors.newFixedThreadPool(nThreads);
+boolean manageThreads(String linkUrl) {
-  for (int i = 0; i < nThreads; i++) {
+  if (curThreads.incrementAndget() <= maxThreads) {
-    GRunnable gr = new GRunnable(i, nThreads, barrier);
+      CrawlThread t = new CrawlThread(linkUrl);
-    es.execute(gr),
+      t.start();
-  }
-== Block 3 ==
-  es.shutdown();
-  es.awaitTermination(60, TimeUnit.SECONDS);
-== Block 4==
-  for (int col = id; col < size; col += nThreads) {
-    for (int row = 0; row < size; row++) {
-      dest[row][col] = step(row, col);
-    }
   }
+  else {
+    curThreads.decrementAndGet();
+    return false;
+  }
+} // END OF manageThreads
+</code>
-== Block 5 ==
+  * c)
-  if (barrier.await() == 0) { // alternativ auch if (id == 0)
+<code=java>
-    swap();
+public void run() {
+  process();
+  curThreads.decrementAndGet();
+}
+</code>
+  * d)
+<code=java>
+synchronized(visitedUrls) {
+  if(!visitedUrls.contains(linkUrl)){
+    doVisit = true;
+    visitedUrls.add(linkUrl);
   }
-  barrier.await();
+}
+</code>
-== Block 6 ==
-  barrier.await(); // Eigentlich unnötig bei Nutzung eines ExecutorServices, oder?
-====== Aufgabe 3======
+====== Aufgabe 3 ======
+{{:pruefungen:bachelor:pfp:ws15-16-aufgabe3.png?200|}}
-  * a) {{:pruefungen:bachelor:pfp:ss15-aufgabe3-petrinetz1.png?500|}}
+Nicht gefragt, hier aber erwähnt:
-  * b) Ein Pfeil von Q zu t1 (Gewicht 1) und ein Pfeil von t2 zu Q (Gewicht 2).
-====== Aufgabe 4======
+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) 3
+  Ja, "Geralt" ist eine mögliche Ausgabe. Die Sichtbarkeit der Veränderungen der Threads ist nicht garantiert.
+  * 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 .join()).
+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.
+====== Aufgabe 5 ======
   * a)
-    * Zeile 27: Ja, weil AtomicInteger intern synchronisiert ist.
+<code=scala>
-    * Zeile 34: Ja, weil jeder Thread nur die lokale Variable modifiziert (und synchronized(this) eh sinnlos ist).
+def insert: (List[Int], Int) => List[Int] = (ls, v) => ls match {
-    * Zeile 38: Nein, globalHits ist allen Threads gemein
+  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>
   * b)
-    * 14/46: Nein, weil i in #47 zur Berechnung benötigt wird.
-    * 19/49: Ja, da v eine volatile Referenz ist und Spin (= aktives Warten) existent.
-    * 22/52: Nein, denn ohne die Barriere bei 19/49 könnte in Thread 3 k=0 aufgrund fehlender Synchronisationspunkte bei der While-Schleife in #53 gelten => Falsche Ausgabe
-======  Aufgabe 5 ======
+<code=scala>
+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>
-Ist aktuell eine Bonusaufgabe, daher zur Vermeidung von Plagiaten noch nicht veröffentlicht.
+  * c)
-====== Aufgabe 6 ======
+<code=scala>
+def sortAllWith: (List[Int] => List[Int]) => List[List[Int]] => List[List[Int]] =
+  sortFun => ls => for (cur <- ls) yield sortFun(cur)
+</code>
+====== Aufgabe 6 ======
   * a)
-  def first: List[Solution] => Solution = sols =>
+<code=scala>
-    sols.foldLeft(List[Transition]())((acc, cur) => acc match {
+def testInside: (Ellipse, Ellipse) => (Double, Double) => Boolean =
-      case Nil => cur
+  (e1, e2) => (x, y) => isInside(e1, x, y) && isInside(e2, x, y)
-      case default => acc
+</code>
-    })
   * b)
-  case (s::ss, sol) if s == end => sol
+<code=scala>
-  case (s::ss, sol) if ss.contains(s) => helper(ss, sol)
+def tupleStream: Stream[Double] => Stream[(Double, Double)] = s =>
+  (s.head, s.tail.head) #:: tupleStream(s.tail.tail)
-  // Unsicher! Bitte Kommentare/Ergänzungen/Verbesserungen
-  case (s::ss, sol) => {
+  // alternativ
-    val next = passage(s)
+  (s(0), s(1)) #:: tupleStream(s.drop(2))
-    first(next.map((nextState, nextTransition) => helper(nextState::ss, sol ::: List(nextTransition)))))
+</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>