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

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:loesungss13 [17.07.2014 13:16] – Alicenpruefungen:bachelor:pfp:loesungss13 [18.02.2017 22:38] (aktuell) – kafalk
Zeile 12: Zeile 12:
 ==== Aufgabe 2: Petri-Netze ==== ==== Aufgabe 2: Petri-Netze ====
  
-(Wer das hier mit Zeichnungen vervollständigen möchte, darf das gerne tun!)+(Das originale Word-Dokument zum Bild habe ich auch hier in denselben Namensraum zwecks etwaigen Änderungen hochgeladen.)
  
-a) +{{:pruefungen:bachelor:pfp:ss13-aufgabe2-petrinetz.png?600|}} 
-Wenn man auch ein Token ergänzen darf:   + 
-Mit einer erneuten Stelle ergänzen. von t1 und t3 zur Stelle hin, von der Stelle zu t2 und t4. +  * a) (Mindestens?) 4 Möglichkeiten:
  
-Wenn man Beschränkungen hinzufügen darf, mit einer Stelle mit Beschränkung 1,  +  - Oben links: Wenn man auch ein Token ergänzen darf: Mit einer erneuten Stelle ergänzen. von t1 und t3 zur Stelle hin, von der Stelle zu t2 und t4.  
-dann von t2 und t4 zur Lockstelle, von der Lockstelle zu t1 und t3. +  - Oben rechts: Wenn man Beschränkungen hinzufügen darf, mit einer Stelle mit Beschränkung 1, dann von t2 und t4 zur Lockstelle, von der Lockstelle zu t1 und t3. 
 +  - Unten links: Ohne Token und Beschränkung Version II: p4 zu t2 und p2 zu t4, jeweils als Doppelpfeil. 
 +  - Unten rechts: Ohne Token und Beschränkung: p4 zu t2, p2 zu t4, t1 zu p4, t3 zu p2 (praxisfern)
  
-Ohne Token und Beschränkung: +  * b)
-p4 zu t2, p2 zu t4, t1 zu p4, t3 zu p2 +
-(Praxisfern)+
  
-   S = ( 0, 1, 1, 0, 0, 0)(Traversiert)+   S = ( 0, 1, 1, 0, 0, 0)(Transponiert)
  
    M:     M: 
Zeile 35: Zeile 35:
     0   0   0   1  -1   0     0   0   0   1  -1   0
  
-c)+  * c)
 Nein. Durch t4->t5->t2->t6->t6 verschwinden alle Marken! Nein. Durch t4->t5->t2->t6->t6 verschwinden alle Marken!
  
-d) +  * d) 
 t4->t5->t6->t1->t4 t4->t5->t6->t1->t4
  
  
-====Augabe 3: Pipeline ====+====Aufgabe 3: Pipeline ====
  
 a)  a) 
  
-for(int i = 0; i < nStages; i++){+  for(int i = 0; i < nStages; i++){ 
 +    boolean lastThread = (i == threads.length - 1); 
 +     
 +    inQueue<Integer> = queues[i];  
 +     
 +    outQueue<Integer> = queues[i+1];  
 +     
 +    threads[i] = new StageThread(i, inQueue, outQueue, lastThread);  
 +    threads[i].start();  
 +  }
  
-boolean lastThread = (i == threads.length - 1); //Vorgegeben+b) 
  
-inQueue<Integer> = queues[i]; +2) Integer value = inQueue.take(); 
  
-outQueue<Integer> = queues[i+1];  
  
-threads[i] = new StageThread(i, inQueue, outQueue, lastThread);  +3) outQueue.put(runStage(value));  
-threads[i].start(); + 
 + 
 +4) if(!lastThread) outQueue.put(value);  
 + 
 +return; break auch möglich! 
 + 
 +==== Aufgabe 4: Schreibtischlauf ==== 
 + 
 +a) 
 +Siehe Zeile 11-12: Prüfe-Handle-Wettlaufsituation.  
 +Beide bekommen die Mitteilung, dass das Lock frei ist. 
 +Eine Behebung des Problems wäre beispielsweise über ein synchronized(this) um das If möglich.
  
-} 
  
 b)  b) 
-2) Integer value = inQueue.take(); +Wenn f==t ist, dann wird zweimal aufs gleiche Konto und somit aufs gleiche Lock zugegriffen wird. Dann bekommt man eine IllegalMonitorStateException. 
  
-3) outQueue.put(runStage(value));  
  
-4) if(!lastThread) outQueue.put(value);  +c)  
-return; //break auch möglich!+in 59-60: Deadly Embrace:  
 +Thread A will von Konto X zu Konto Y buchen, Thread B von Y zu X. Beide lokcen in 59 das erste Konto und warten in 60 auf das zweite Konto, dass sie aber nie bekommen können, da der andere Thread es besitzt.  
 +Möglichkeiten zur Behebung: Globale Ordnung über die Nummer des Kontos, oder Synchronized auf ein Objekt. 
  
 +d) 
 +in 71 kann das Geld abgefragt werden, danach wird die Bank unlocked. In withdraw kann Geld von einem Konto geändert werden, dass in der obigen Funktion bereits angeschaut und das Geld aufaddiert worden ist. Die Beträge sind dann unterschiedlich. 
 +
 +Gefixt über B.L.unlock() von 72 am Ende der Funktion. 
 +
 +
 +==== Aufgabe 5: Collatz ====
 +
 +**a)**
 +  def construct: (Int => Boolean) => (Int => Int, Int => Int) => Int => Int = 
 +i => (e, o) => n => if(i(n)) e(n) else o(n)
 +
 +**b)** 
 +  def f: Int => Stream[Int] = n => n #:: f(c(n))
 +
 +**c)**
 +  // toList vor foldLeft ist optional, Stream bietet auch diese Funktion
 +  def oddCount: (Int, Int) => Int = (n, k) => f(n).take(k).toList.foldLeft(0)( (a, b) => if(isEven(b)) a else a+1)
  
 ==== Aufgabe 6: Scala / Graphen faerben ==== ==== Aufgabe 6: Scala / Graphen faerben ====
Zeile 84: Zeile 121:
  
   def getFreeColor: List[Color] => Color = l => (for(i <- List.range(0, l.length + 1 ) if !l.contains(i))yield i).head   def getFreeColor: List[Color] => Color = l => (for(i <- List.range(0, l.length + 1 ) if !l.contains(i))yield i).head
 +
 +Alternativ mit dropWhile:
 +
 +  def getFreeColor: List[Color] => Color = ms => List.range(0,ms.length+1).dropWhile(ms.contains(_)).head
 +
 +Rekursive Alternative:
 +
 +  def getFreeColor: List[Color] => Color = cs => {
 +    if (cs.contains(0)) {
 +      getFreeColor(cs.map(_-1)) + 1
 +    }
 +    else {
 +      0
 +    }
 +  }
 +
 +Oder mit foldLeft
 +
 +  def getFreeColor: List[Color] => Color = list =>
 +  list.foldLeft(0)((a,b) =>if(list.contains(a))a+1 else a)
 +
  
 **b)** **b)**
    def colorGraph: List[Node] => List[Coloring] => List[Coloring] = {    def colorGraph: List[Node] => List[Coloring] => List[Coloring] = {
-     case Nil => cols => cols +     nod => cols => nod match { 
-     case n::nod => cols => colorGraph(nod)(nextFreeColor(cols)(n)::cols) +          case Nil => cols 
-   }+          case n::ns=> colorGraph(ns)(nextFreeColor(cols)(n)::cols) 
 +          } 
 +    }