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

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:pfp:loesungss15 [16.07.2016 17:09] – 6b korrigiert dank tomabrafix Marcel[Inf]pruefungen:bachelor:pfp:loesungss15 [02.08.2019 08:30] (aktuell) – Destranix
Zeile 1: Zeile 1:
 ====== Aufgabe 1 ====== ====== Aufgabe 1 ======
   * a) Sequentieller Umstieg, Beschränkung der Parallelität.   * a) Sequentieller Umstieg, Beschränkung der Parallelität.
-  * b) Das Schalten einer Transition erfolgt atomar. (Hat jmd. (Gegen-)argumente für "Die Petri-Netze enthalten lebendige Transitionen"?)+  * b) Das Schalten einer Transition erfolgt atomar. Es gilt: P-Überdeckung => Beschränkt. Lebendig && Beschränkt => T-Überdeckung. Aus P- & T-Überdeckung kann man daher keine Lebendigkeit folgern.
   * c) Die parallale Effizienz ist 2. Der Speedup ist 16.   * c) Die parallale Effizienz ist 2. Der Speedup ist 16.
  
Zeile 29: Zeile 29:
  
 == Block 5 == == Block 5 ==
-  if (barrier.await() == 0) { // alternativ auch if (id == 0)+  if (barrier.await() == 0) { // alternativ auch barrier.await() und dann if (id == 0)
     swap();     swap();
   }   }
Zeile 35: Zeile 35:
      
 == Block 6 == == Block 6 ==
-  barrier.await(); // Eigentlich unnötig bei Nutzung eines ExecutorServices, oder?+  // Beabsichtigt leer gelassen 
 +  // Falls in 1 new CyclicBarrier(nThreads + 1) und im Mainthread in 3 mittels barrier.await() synchronisiert wird, muss hier auch ebarrier.await() stehen.
  
 ====== Aufgabe 3====== ====== Aufgabe 3======
  
   * a) {{:pruefungen:bachelor:pfp:ss15-aufgabe3-petrinetz1.png?500|}}   * a) {{:pruefungen:bachelor:pfp:ss15-aufgabe3-petrinetz1.png?500|}}
-  * b) Ein Pfeil von Q zu t1 (Gewicht 1) und ein Pfeil von t2 zu Q (Gewicht 2).+  * b) Ein Pfeil von Q zu t1 (Gewicht 1) und ein Pfeil von t2 zu Q (Gewicht 2). Desweiteren muss noch verhindert werden, dass t3 schalten und somit unendlich viele Marken generieren kann. Dazu ist z.B. eine Kante von Q zu t3 mit dem Gewicht 3 nötig.
  
 ====== Aufgabe 4====== ====== Aufgabe 4======
  
   * a)   * a)
-    * Zeile 27: Ja, weil AtomicInteger intern synchronisiert ist. +    * Zeile 27: Nein, weil AtomicInteger zwar intern synchronisiert ist, der Wert aber mit eienm anderen verglichen wird, wodurch eine Prüfe-Handle-Situation entsteht. 
-    * Zeile 34: Ja, weil jeder Thread nur die lokale Variable modifiziert (und synchronized(this) eh sinnlos ist). +    * Zeile 34: Ja, weil jeder Thread nur die lokale Variable modifiziert und synchronized(this) eh sinnlos ist. 
-    * Zeile 38: Nein, globalHits ist allen Threads gemein+    * Zeile 38: Nein, globalHits ist allen Threads gemein => sonst Lesen-Ändern-Schreiben-Wettlaufsituation.
   * b)   * b)
-    * 14/46: Nein, weil i in #47 zur Berechnung benötigt wird. +    * 14/46: Nein, weil i in #47 zur Berechnung benötigt wird. D.h. man benötigt sowohl Datensichtbarkeit (wäre mit volatile auch möglich) als auch zeitliche Synchronisation (nur dank barrier.await() hier möglich). 
-    * 19/49: Ja, da v eine volatile Referenz ist und Spin (= aktives Warten) existent. +    * 19/49: Ja, da v eine volatile Referenz ist und Spin (= aktives Warten) existent. (Die volatile-Deklaration verhindert, dass ein Objekt bei Zugriff noch nicht vollständig initialisiert ist.) 
-    * 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+    * 22/52: Laut Tutor soll man jede Barriere einzeln betrachten. Wir gehen also davon aus, dass die Barriere 19/49 immer noch existent ist. Dann gilt k=-1 sicher in Zeile 50 in Thread 3. Es ist jedoch nicht garantiert, dass wir jemals den neuen Wert aus Zeile 21 in Thread 3 auslesen werden, da k nicht volatile ist. Daher entweder k volatile deklarieren oder die Barriere dort lassen (=> Antwort "Nein"). 
 +    * 22/52: Begründung unter Annahme, dass 19/49 bereits gestrichen wurde: Nein, denn in Thread 3 könnte k=0 (Default-Wert bei Instanzinitialisierung der "echten" Barrier-Klasse aus Zeile 2) aufgrund fehlender Synchronisationspunkte bei der While-Schleife in #53 gelten => Falsche Ausgabe.
  
 ======  Aufgabe 5 ====== ======  Aufgabe 5 ======
  
-Ist aktuell eine Bonusaufgabe, daher zur Vermeidung von Plagiaten noch nicht veröffentlicht.+<code=Scala> 
 +def aliveNeighbors: (Cell => List[Cell]) => Cell => Int = 
 +  f => cell => f(cell).count(_.alive)
  
 +def tick: Field => Field = field => field.map(cell => aliveNeighbors(neighbors(field))(cell) match {
 +  case n i f(n < 2 || n > 3) => Cell(cell.x, cell.y, false)
 +  case 3 => Cell(cell.x, cell.y, true)
 +  case default => cell
 +})
 +
 +def game: Field => Stream[Field] = f => f #:: game(tick(f))
 +</code>
 ====== Aufgabe 6 ======  ====== Aufgabe 6 ====== 
  
   * a)   * a)
- +<code=Scala> 
-  def first: List[Solution] => Solution = sols => +def first: List[Solution] => Solution = sols => 
-    sols.foldLeft(List[Transition]())((acc, cur) => acc match { +  // alternativ sols.foldLeft(Nil: List[Transition)... 
-      case Nil => cur +  sols.foldLeft(List[Transition]())((acc, cur) => acc match { 
-      case default => acc +    case Nil => cur 
-    })+    case default => acc 
 +  }) 
 +</code>
  
   * b) Das Kopfelement ist immer das aktuell zu bearbeitende Element. Der Rest der Liste entspricht den bereits besuchten Zuständen.   * b) Das Kopfelement ist immer das aktuell zu bearbeitende Element. Der Rest der Liste entspricht den bereits besuchten Zuständen.
  
-  case (s::ss, sol) if s == end => sol +<code=Scala> 
-  case (s::ss, sol) if ss.contains(s) => Nil       +case (s::ss, sol) if s == end => sol 
-  // Unsicher! Bitte Kommentare/Ergänzungen/Verbesserungen +case (s::ss, sol) if ss.contains(s) => Nil       
-  case (s::ss, sol) => { +case (s::ss, sol) => { 
-    val next = passage(s) +  val next = passage(s) 
-    first(next.map({ +  first(next.map({ 
-      case (nextState, nextTransition) => helper(nextState::s::ss, sol ::: List(nextTransitiont)) +    case (nextState, nextTransition) => helper(nextState::s::ss, sol ::: List(nextTransition)) 
-    })) +  })) 
-  }+} 
 +</code>