Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » pfp » Aufgabe 1 (Wissensfragen)   (Ü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:loesungws12 [16.07.2014 11:21] – lemurpruefungen:bachelor:pfp:loesungws12 [01.08.2017 19:45] (aktuell) – ab21ajus
Zeile 1: Zeile 1:
 ==== Aufgabe 1 (Wissensfragen) ==== ==== Aufgabe 1 (Wissensfragen) ====
   a) falsch   a) falsch
-  b) richtig (z.B. durch Prüfe-Handle-Situationen)+  b) richtig (z. B. durch Prüfe-Handle-Situationen)
   c) falsch   c) falsch
   d) falsch   d) falsch
Zeile 12: Zeile 12:
  
   S:    S: 
-  (1, 1, 0, 0, 0) (Traversiert)+  (1, 1, 0, 0, 0) (Transponiert)
      
   M:    M: 
Zeile 26: Zeile 26:
 c) Ja c) Ja
  
-d) E: (0, 7, 0, 4) +d) E: (0, 7, 0, 0) 
  
 +====Aufgabe 3 (Java - Präfixsumme) ====
 +a) Gauß-Filter / Weichzeichner (? -> eher Zeigerverdopplung)
 +<code java>
 +import java.util.concurrent.*;
  
 +public class ParallelPrefixSums {
 + private static CyclicBarrier barrier;
 + public static void calculateSums(int[] values) throws InterruptedException {
 + barrier = new CyclicBarrier(values.length);
 + Thread[] workers = new Thread[values.length];
 + for (int i = 0; i < values.length; i++) {
 + workers[i] = new Thread(new Worker(values, i));
 + workers[i].start();
 + }
 + for (int i = 0; i < values.length; i++) {
 + workers[i].join();
 + }
 + }
 +
 + public static class Worker implements Runnable {
 + private int[] values;
 + private int index;
 + public Worker (int[] values, int index) {
 + this.values = values;
 + this.index = index;
 + }
 + public void run() {
 + try {
 + int distance = 1;
 + while (distance < values.length) {
 + barrier.await();
 + int target = index + distance;
 + int rem = values[index];
 + barrier.await();
 + if (target < values.length) {
 + values[target] += rem;
 + }
 + dist *= 2;
 + }
 + } catch (Exception e) {
 + e.printStackTrace();
 + }
 + }
 + }
 +}
 +</code>
 +
 +==== Aufgabe 4 (Schreibtischlauf - Barrieren) ====
 +
 +  * a) a = 1, weil sowohl a++ als auch die System.out.println-Ausgabe in einem synchronized-Block stehen und beide Threads auf dieselbe Marke synchronisieren.
 +  * b) Mögliche Ausgaben sind:
 +
 +<code>
 +a=1
 +a=2
 +a=3
 +Threads 1, 2, 3 started.
 +</code>
 +
 +Und
 +
 +<code>
 +a=1
 +a=2
 +Threads 1, 2, 3 started.
 +a=3
 +</code>
 +
 +Der Main-Thread synchronisiert nicht auf irgendeine Marke (insb. nicht auf BarrierTest.class), daher erscheinen ihm die synchronized-Blöcke der Threads nicht als unteilbare Einheit und er kann bereits nach a++, aber vor System.out.println die While-Schleife verlassen.
 +
 +  * c) 1, 2, 3, oder 4 Mal. Jeder Thread könnte gleichzeitig b=0 am Anfang feststellen oder erst prüfen, nachdem die anderen Threads (oder ein Teil davon) das IF verlassen.
 +  * d) Vorletzte oder letzte Zeile. Der CountDownLatch ist nur mit 3 initialisiert worden. Daher kann sich der letzte Thread irgendwo zwischen barrier.await() und latch.countDown() befinden.
 +
 +
 +==== Aufgabe 5 (Scala - Snake-Sort) ====
 +
 +sortAsc, sortDes waren nicht Teil der Aufgabe, sind aber zum Testen implementiert.
 +
 +<code=Scala>
 +import System.{ currentTimeMillis => ct }
 +
 +type Row = List[Int]
 +type Matrix = List[Row]
 +  
 +def sortAsc: Row => Row = rs => if(rs == Nil) Nil else rs.min :: sortAsc(rs.filter(_ > rs.min))
 +def sortDes: Row => Row = rs => if(rs == Nil) Nil else rs.max :: sortDes(rs.filter(_ < rs.max))
 +  
 +
 +def sortCols: Matrix => Matrix = m =>
 +  (for(col <- m.transpose) yield sortAsc(col)).toList.transpose
 +    
 +def sortColsPar: Matrix => Matrix = m => (for(col<- m.transpose.par) yield sortAsc(col)).toList.transpose
 +  
 +// Alternativ (laut #Scala ist die Paralleliät bei beiden äquivalent gegeben):
 +    
 +def sortColsPar2: Matrix => Matrix = m => m.transpose.par.map(sortAsc(_)).toList.transpose
 + 
 +def sortRows: Matrix => Matrix = m =>{
 +  def helper: (Matrix, Int) => Matrix = {
 +    case (Nil, n) => Nil
 +    case (m::ms, n) if(n % 2 == 0) => sortAsc(m)::helper(ms,n+1)
 +    case (m::ms, n) if(n % 2 != 0) => sortDes(m)::helper(ms,n+1)
 +  }
 +  helper(m,0)
 +}
 +
 +//Alternative ohne Helfer-Funktion:
 +  def sortRows2: Matrix => Matrix = m => m match {
 +    case Nil => Nil
 +    case (row::m)  => if (m.length % 2 == 0)
 +                          sortAsc(row)::sortRows2(m)
 +                     else 
 +                          sortDes(row)::sortRows2(m)
 +  }
 +
 +
 +def sortHelper: (Int, Matrix) => Stream[(Matrix,Matrix)] = { 
 +  case (n,m) =>  if (n%2==0) (m, sortRows(m)) #::sortHelper(n+1,sortRows(m)) else (m,sortCols(m)) #::sortHelper(n+1,sortCols(m))     
 +}
 +  
 +def snakeSort: Matrix => Matrix = m => {
 +  def helper: (Matrix, Int) => Matrix = (m,n) => {
 +      val a = sortHelper(0,m)(n)
 +      if(a._1 == a._2) a._2 else helper(m,n+1)    
 +  }
 +  helper(m,0)
 +}
 +</code>
 +
 +==== Aufgabe 6 ====
 +Nicht mehr Teil des Vorlesungsstoffes.