Klausurlösung WS 13(/14): 18.02.2014

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Klausurlösung WS 13(/14): 18.02.2014
Hey :slight_smile: Ich hab mir gedacht wir könnten vielleicht ein paar Lösungen zu dieser Altklausur zusammentragen und dann im Wiki hochladen. Damit mans dann beim Lernen leichter hat.
Dabei kann man dann auch darüber diskutieren und Fragen stellen, wenn man was nicht versteht. Ich würde ja meine Lösungen gleich im Wiki hochladen, aber ich bin mir bei einigen Antworten nicht so ganz sicher…
Hier nochmal der Link zur Altklausur:
https://www2.cs.fau.de/teaching/SS2014/PFP/organisation/oldexams/secure/14-02-18_klausur.pdf

Ich mach mal den Anfang:

Aufgabe 1: Wissensfragen
a) falsch
b) nein
c) nein
d) richtig
e) 30s
f) def f: (Int, Int) => Int => Int => Int
g) falsch

Aufgabe 2: Petri-Netze
a) Verknüpfung von Service aktiv mit Transition t0. Zweiten Ausgang von t0 an Service aktiv setzen (Dann wird aber nie abgebrochen…?)
b) Verknüpfung von Stelle Arbeitspakete jeweils mit Transitionen t1, t2 und t3. Stellenbeschränkung bei A, B, C auf 1 setzen. Verknüpfen von Transitionen t4, t5, t6 mit Stelle Arbeitsergebnisse
c)

  • Token in Stelle Service aktiv
  • Keine Token in Stelle Arbeitspakete
  • Jeweils ein Token in Stellen A und B
  • 2 Token in Stelle Arbeitsergebnisse

“Endbild”

Edit: Denkt euch die Tokens aus Teilaufgabe c) noch dazu …

d) Nein
e) S = {0, 1, 1}T ; M = {t1: {-1, 1, 0}, t2: {-1, 0, 1}, t3: {2, -1, -1} }T

Aufgabe 3: Datei-Suche
a)

activeFolderSearchers = new AtomicInteger(0);
Thread t = new FolderSearcher(rootDir);
t.start();
activeFolderSearchers.incrementAndGet();
//t.join();

b)

if(file.isDirectory){
Thread t = new FolderSearcher(file);
activeFolderSearchers.incrementAndGet();
t.start();
} else { //file.isFile();
	pool.submit(new FileSearcher(file));
}

c)

activeFolderSearchers.decrementAndGet();
if(activeFolderSearchers.get() == 0){
	pool.shutdown(); // Shall only be called once!
}

Aufgabe 5: Schreibtischlauf
a)
Ausgabe Alternative Ausgaben
Question to Deep Thought: Keine Alternative
Leerzeile Keine Alternative
Answer to the: Keine Alternative
Ultimate Question Douglas
of Life Keine Alternative
Adams The Universe
and Everything Keine Alternative

b)
Ultimate Question:
Zeile 7:[m] int counter = 0[/m] => [m]AtomicInteger counter = new AtomicInteger(0);[/m]
Zeile 16 & 69: [m]counter++[/m] => [m]counter.IncrementAndGet();[/m]

The Universe:
Zeile 30 & 82: [m]synchronized(this)[/m] => [m]synchronized(map)[/m]

Komplett fehlende Aufgaben:

  • Aufgabe 4
  • Aufgabe 6
3 Likes

Aufgabe 1 und 2 hätte ich auch so gemacht. :slight_smile:

Bei Aufgabe 3 bin ich mir nicht sicher, ob man immer t.join() setzen sollte, aber dann würde an dieser Stelle gewartet werden :-/

Deshalb meine einzige Anmerkung: if(file.isFile()) sollte extra abgefragt werden, da in der Aufgabenstellung steht: „… alle Dateien eines Verzeichnisbaumes (also auch Dateien in Unterverzeichnissen beliebiger Tiefe, jedoch keine symbolischen Links)…“ und ich das so verstehe, dass es eben nicht nur Directories und Files gibt. D.h. „!file.isDirectory“ bedeutet nicht gleich, dass file.isFile() ist.


Warum nicht lebendig?


Wenn t3 schaltet und zwei mal z.B. t1 geht ja nichts mehr voran. Damit wieder t3 schaltet, muss ja an der Stelle A und B jeweils ein Token vorhanden sein.


an der Stelle B und C.
Danke, hab auch so später gedacht.


Edit: gelöscht…


Ich bin mir nicht sicher, ob du hier wirklich Lösungen zu Aufgaben veröffentlichen willst, auf die es aktuell Bonuspunkte gibt. (s. Aufgabe 12.4)


Ich hab noch Kleinigkeiten ausgebessert und mal auf der FSI Seite unter den Klausurlösungen hochgeladen
Aufgabe 4 hab ich noch wegen dem aktuellen Übungsblatt weggelassen. Aufgabe 6 fehlt allerdings immernoch…
https://fsi.informatik.uni-erlangen.de/dw/pruefungen/bachelor/pfp/loesungws13


Da bei der Aufgabe 6 niemand was dazu schreiben will, teil ich einfach mal meine primitive und wahrscheinlich nicht richtige Version davon:

a)
Beim parallelen Teil bin ich mir nicht sicher. Habs einfach so aus den Vorlesungsfolien übernommen. Sequentielle Alternative beim case x::xs:
outEdges(vs, x) ::: outEdges(vs, xs)

def outEdges: (List[V], G) => List[E] = (vs, g) => match g {
 	case Nil => Nil
 	case x::Nil => if(vs.contains(x._1) && !vs.contains(x._2) List(x) else Nil
 	case x::xs => {
 		val a = Future { outEdges(vs, List(x)) }
 		val b = outEdges(vs, xs)
 		Await.result(a, Duration.Inf) ::: b
 	}
}

b)
Sehr umständlich. Kann mir nicht vorstellen, dass das so für eine 8 Punkte Aufgabe gedacht war.

def tree: (V, G) => G = (v, g) => {
	def helper: List[V] => G = vs => {
 		def edgesToNodes: G => List[V] = { // Gibt die Ausgangsknoten zurück. (z.B. List((1, 2), (3, 4)) => List(2, 4))
 			case Nil => Nil
 			case x::Nil => List(x._2)
 			case x::xs => List(x._2) ::: edgesToNodes(xs)
 		}
 		case Nil => Nil
 		case x::Nil => val nachbarn = outEdges(List(v), g); helper(edgesToNodes(nachbarn)) 
 		case x::xs => tree(x) ::: outEdges(xs)
 	}
 	helper(List(v))
}

Ich glaub das geht kürzer:

	def outEdges: (List[V],G) => List[E] = (vs,g) =>
	 g.par.filter(x => vs.contains(x._1) && !vs.contains(x._2)).toList

g.par wandelt die liste in eine parSeq um, die man dann am schluss wieder in eine liste umwandeln muss.

bei der b) bin auch noch am überlegen. da bin ich auf nichts gekommen bisher


Ich taste mich hier mal vorsichtig bei der b) voran:

def tree: (V, G) => G = (v,g) => {
     def helper: List[V] => G = vs {
        //einfach für die gegebene Liste alle Kanten nach außen ausgeben lassen, und in val speichern
        val eins: outEdges(vs, g)

      //die neu hinzu gekommenen Knoten holen
     val zwei: for(x <- eins) yield x._2

     //die neuen Knoten mit den alten verbinden
     val drei: vs ::: zwei

     //das ergebnis ist der erste aufruf, also val eins
     // und dazu noch rekursiv einen weiteren Aufruf mit den neu gewonnenen Knoten
     eins ::: helper (drei)
}

helper (List(v))

}

Und nein, ich habe es nicht ausprobiert, wahrscheinlich fliegt es einem schon beim Kompilieren krachend um die Ohren, oder ?

Was meint ihr ?


Die 4) darf jetzt wohl auch veröffentlicht werden:

a) def construct: (Int => List[Int]) => (List[Int] => Int) => Int => Int = facs => sum => n => sum(facs(n))
b) def fss: Int => Stream[(Int, Int)] = n => (n, fss(n)) #::fss(n+1)
c) def count: (Int, Int) => Int = (start, nElem) => fss(start).take(nElem).foldLeft(0)(soFar, cur => if(cur._1 > cur._2) soFar+1 else soFar)

Hab’s jetzt nicht nochmal durch den Compiler geschickt, erinnere mich aber daran, die Bonusaufgabe ziemlich äuqivalent zu haben. Ich denke, bei der b) ist keine zusätzliche Helper-Funktion notwendig.

Die 6b) habe ich im Übrigen auch nicht verstanden, die wäre wohl in der “Realklausur” dann mangels Zeit rausgeflogen. 6a) wäre auch eher raten gewesen.


Ich bin mir ziemlich sicher, dass es hier beim Starten der FileSearcher pool.execute(…) heißen muss und nicht pool.submit(…).
Schließlich gibt submit doch ein Future-Objekt zurück und erwartet ein call() im erzeugten Thread.
Oder liege ich da völlig daneben?


Du kannst auch submit mit einem Runnable aufrufen. In PFP ist der wichtigste Unterschied, dass submit ein Future-Objekt zurückgibt (was man bei einem Runnable-Objekt nicht unbedingt braucht) und execute tut dies nicht.

Offensichtlich gibt es aber auch Unterschiede beim daraus resultierenden Exception-Handling.

1 Like

Okay, danke! Bis auf die Exception Behandlung spricht also mehr oder weniger nichts dagegen pauschal submit aufzurufen?


kann mal jemand die 1e begründen?


Fließband [2, 4, 5, 6, 1],
3 Pakete

(2+4+5+6+1) + 2*6 = 18 + 12 = 30

zur 4)

Die a) sollte stimmen. Bei der b) musst du im String-Head fs(n) statt fss(n) setzen und bei der c) fehlen die Klammern ums Tupel (soFar, cur).

Also sollte das (mit anderen Variablennamen) so aussehen:

object DivisorFunction {
 
	def facs: Int => List[Int] = 
            n => List.range(1, n/2 + 1).toSet.filter(t => (n.toDouble/t).isValidInt).toList

	def sum: List[Int] => Int = 
            ls => ls.sum
	
	def fs: Int => Int = construct(facs)(sum)
	
	def construct: (Int => List[Int]) => (List[Int] => Int) => Int => Int = 
		f => s => n => s(f(n))
	
	def fss: Int => Stream[(Int, Int)] = 	
		n => (n, fs(n)) #:: fss(n+1)
	
	def count: (Int, Int) => Int = 
		(n0, m) => fss(n0).take(m).foldLeft(0)((n, c) => if(c._1 > c._2) n+1 else n) 
}
1 Like

Aufgabe 5 (Schreibtischlauf)

ich hätte eine Frage bezüglich „Ultimate Question/Douglas“-Ausgabe, und zwar: Warum ist es eine Alternative hier möglich? Ich dachte, dass CyclicBarrier Sichtbarkeitssynchronisation garantiert → counter wird dann garantiert zwei mal erhöht… und die Abfrage if(counter == 2) steht doch nach dem barrier und dazwischen passiert auch keine Änderungen der counter…Und wie genau bewirken die drei nacheinander stehende barrier.await() (Z. 52-54) auf die Ausführung des Codes? Ich glaube, ich verstehe das Konzept des CyclicBarriers nicht sehr gut…