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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:pfp:loesungws12 [16.07.2014 08:46] – Alicen | pruefungen: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 11: | Zeile 11: | ||
a) | a) | ||
- | S: (1, 1, 0, 0, 0) (Traversiert) | + | S: |
- | M: (-1, 0, 0, 0, 1) | + | |
+ | | ||
+ | M: | ||
+ | | ||
+ | ( 1, 2, -1, -1, 0) | ||
+ | ( 0, -1, 1, 0, 0) | ||
+ | ( 0, -1, 0, 1, 0) | ||
+ | ( 0, -1, 0, 1, -1) | ||
b) | b) | ||
- | ( 1, 2, -1, -1, 0) | + | t1 -> t4 -> t3 -> t5 |
- | ( 0, -1, 1, 0, 0) | + | c) Ja |
- | ( 0, -1, 0, | + | d) E: (0, 7, 0, 0) |
- | ( 0, -1, -1, 1, -1) | + | ====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; | ||
+ | workers[i] = new Thread(new Worker(values, | ||
+ | workers[i].start(); | ||
+ | } | ||
+ | for (int i = 0; i < values.length; | ||
+ | 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(); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | ==== 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: | ||
+ | < | ||
+ | a=1 | ||
+ | a=2 | ||
+ | a=3 | ||
+ | Threads 1, 2, 3 started. | ||
+ | </ | ||
+ | Und | ||
+ | |||
+ | < | ||
+ | a=1 | ||
+ | a=2 | ||
+ | Threads 1, 2, 3 started. | ||
+ | a=3 | ||
+ | </ | ||
+ | |||
+ | Der Main-Thread synchronisiert nicht auf irgendeine Marke (insb. nicht auf BarrierTest.class), | ||
+ | |||
+ | * 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. | ||
+ | |||
+ | < | ||
+ | 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: | ||
+ | | ||
+ | // Alternativ (laut #Scala ist die Paralleliät bei beiden äquivalent gegeben): | ||
+ | | ||
+ | def sortColsPar2: | ||
+ | |||
+ | def sortRows: Matrix => Matrix = m =>{ | ||
+ | def helper: (Matrix, Int) => Matrix = { | ||
+ | case (Nil, n) => Nil | ||
+ | case (m::ms, n) if(n % 2 == 0) => sortAsc(m):: | ||
+ | case (m::ms, n) if(n % 2 != 0) => sortDes(m):: | ||
+ | } | ||
+ | helper(m,0) | ||
+ | } | ||
+ | |||
+ | // | ||
+ | def sortRows2: Matrix => Matrix = m => m match { | ||
+ | case Nil => Nil | ||
+ | case (row:: | ||
+ | sortAsc(row):: | ||
+ | | ||
+ | sortDes(row):: | ||
+ | } | ||
+ | |||
+ | |||
+ | def sortHelper: (Int, Matrix) => Stream[(Matrix, | ||
+ | case (n,m) => if (n%2==0) (m, sortRows(m)) #:: | ||
+ | } | ||
+ | | ||
+ | def snakeSort: Matrix => Matrix = m => { | ||
+ | def helper: (Matrix, Int) => Matrix = (m,n) => { | ||
+ | val a = sortHelper(0, | ||
+ | if(a._1 == a._2) a._2 else helper(m, | ||
+ | } | ||
+ | helper(m,0) | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ==== Aufgabe 6 ==== | ||
+ | Nicht mehr Teil des Vorlesungsstoffes. | ||