Klausur SS2013

[_hedgehogs_dilemma_4]

---

also ich versuch mal das ganze zu erklären:

Es gibt zwei Seiten - Quelleseite und Senkeseite mit Verteileren.

zuerst wird der entsprechende neue “Schnitt” berechnet.

in jedem rekursionsabstieg wird von der Senkeseite ein Verteiler zur Quellseite hinzugefügt.
//dabei wird sichergestellt, dass man nicht die Senke hinzufügt, denn die ist ja das Ziel, außerdem wird sichergestellt, dass wir keine Knoten doppelt auf der Quellseite erfassen.

da wir alle Möglichkeiten durchprobieren müssen wird hier eine Form des Backtracking angewandt, sodass bei aufstieg aus der Rekursion der zuletzt hinzugefügte Verteiler wieder gelöscht wird, davor wird noch der Schnitt aktualisiert, da aus den tiefen der Rekursion ein neuer Schnitt kommt der eventuell besser ist.

Eigentlich ist das fast wie das GridRiddle aus unseren Übungen:
https://www2.cs.fau.de/teaching/WS2013/AuD/uebungen/secure/uebung05_slides.pdf
https://www2.cs.fau.de/teaching/WS2013/AuD/uebungen/secure/uebung06_slides.pdf

[Kuno_See]

---

Alleine diese Zeile bereitet mir schon Schwierigkeiten:

Verteiler ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]);

Umso länger ich da drauf schaue, umso weniger weiß ich was das heißt.
also was heißt das in den Klammern

new Verteiler [senkeSeite.size()]

?

Ich hätte dort nur

senkeSeite.size()

erwartet.

[ict]

---

Ein Blick in die Doku sollte helfen.

[Kuno_See]

---

Danke. Ich hatte selbst schon in der Doku nachgeschaut, aber irgendwie an der falschen Stelle nachgeschlagen=)

Okay und warum ist es jetzt Math.max?

df = Math.max(df, durchfluss(quelleSeite, s, senke));

Den maximalen Durchfluss von Q nach S erhält man, indem man alle möglichen
Schnitte (gestrichelt) durchs Gebäude zieht, zu jedem Schnitt die Rohr-Durchfluss-Summe
bestimmt, und von allen Schnitten den MINIMALEN Durchfluss wählt –

[_hedgehogs_dilemma_4]

---

Ich denke das sollte eigentlich min sein

[Kuno_See]

---

Kann ich die zwei Zeilen nicht auch weglassen?

ssa [ i ] = quelleSeite.get(quelleSeite.size() - 1);
quelleSeite.remove(quelleSeite.get(quelleSeite.size() - 1));

Die kommen erst NACH dem rekursiven Aufruf. Habe es eben ausprobiert, ohne diese zwei Zeilen kommt das gleiche raus wie mit.
Ich verstehe nicht, was die bewirken sollen.

Alternative, abgeänderte Version von mir:

double durchfluss(List quelleSeite, List senkeSeite, Verteiler senke){

	double df = schnittDurchfluss(quelleSeite, senkeSeite);
	if(senkeSeite.size() == 1){			
		return df;
	} else {
		for(Verteiler i : senkeSeite){				
			if(!i.equals(senke) && !quelleSeite.contains(i)){
				quelleSeite.add(i);
				senkeSeite.remove(i);
				df = Math.min(df, durchfluss(quelleSeite, senkeSeite, senke));
							
			}
		}
	}		
	return df;
}

[system]

---

@ Kuno_See:

Das soll schon Math.min sein, ich habe bloß die Aufgabenstellung falsch verstanden. Die Zeile mit dem Array braucht man imo. nicht, die Methode funktioniert auch so. Ich bin bloß beim Arbeiten mit Listen auf eine die Concurrent Modification Exception gestoßen, weshalb ich zunächst vorgezogen habe, mit Arrays zu arbeiten. So soll es aber auch funktionieren:

double durchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite, Verteiler senke){		
	double df = schnittDurchfluss(quelleSeite, senkeSeite);
	if(senkeSeite.size() == 1){			
		return df;
	}
	for(int i = 0; i < senkeSeite.size(); i++){				
		if(!senkeSeite.get(i).equals(senke) && !quelleSeite.contains(senkeSeite.get(i))){
			quelleSeite.add(senkeSeite.get(i));
			senkeSeite.set(i, null);
			ArrayList<Verteiler> s = new ArrayList<Verteiler>();
			for(Verteiler v : senkeSeite){
				if(v != null){
					s.add(v);
				}
			}
			df = Math.min(df, durchfluss(quelleSeite, s, senke));
			senkeSeite.set(i, quelleSeite.get(quelleSeite.size() - 1));
			quelleSeite.remove(quelleSeite.get(quelleSeite.size() - 1));					
		}
	}			
	return df;
}

Die zwei Zeilen dienen zur Rücksetzung des alten Zustands. Von daher würde ich sie nicht weglassen. Teste doch mal deine Methode mit Math.max statt Math.min ohne die Zeilen

senkeSeite.add(v);
quelleSeite.remove(v); 

und dann mit (aber ersetze dabei die Zeile “for(Verteiler v : senkeSeite)” durch “for(Verteiler v : ssa)”) und du siehst mit den Zeilen das Ergebnis 12 (was auch richtig wäre) und ohne das Ergebnis 9.

Die einfachste Lösung wäre imo. der Code:

double durchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite, Verteiler senke){ Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]); double df = schnittDurchfluss(quelleSeite, senkeSeite); if(senkeSeite.size() == 1){ return df; } for(Verteiler v : ssa){ if(!v.equals(senke) && !quelleSeite.contains(v)){ quelleSeite.add(v); senkeSeite.remove(v); df = Math.min(df, durchfluss(quelleSeite, senkeSeite, senke)); senkeSeite.add(v); quelleSeite.remove(v); } } return df; }

[Kuno_See]

---

for(Verteiler v : ssa){

Warum machst du deine Schleife nicht einfach so:

for(Verteiler v : senkeSeite) {

?

[system]

---

@Kuno_See

for(Verteiler v : ssa){

Warum machst du deine Schleife nicht einfach so:

for(Verteiler v : senkeSeite) {

?

Wegen der Concurrent Modification Exception.

[Kuno_See]

---

Wenn du diese zwei Zeilen, die den Grunzustand wieder herstellen sollen auskommentierst,
kommt diese Exception nicht. Ist zumindest bei mir so.

[system]

---

@Kuno_See

Wenn du diese zwei Zeilen, die den Grunzustand wieder herstellen sollen auskommentierst,
kommt diese Exception nicht. Ist zumindest bei mir so.

Das ist richtig, aber ohne Rücksetzung hast du wiederum in manchen Spezialfällen falsche Lösungen.

[Kuno_See]

---

Wäre toll, wenn dir so ein Spezialfall einfällt, dann könnte ich es vielleicht sogar verstehen=) Ist aber nicht so wichtig.
Ich will dich auch nicht vom Klausur lernen abhalten, wenn du da noch anderes zu tun hast.

Ich habe aber noch weitere Fragen:

Bei der Aufgabe2, der Schreibtischlauf:

Gleich am Anfang:

Trinkbar tv = new Vodka();
System.out.println(tv.verdauen(1));

Warum kommt hier „ist unverdaulich raus?“
Ich hätte „dauert mehrere Stunden“ gewählt. Das wird ja einfach mit ner 1 aufgerufen, da hätte ich gedacht dass das eher in den Integer fällt und nicht in Long.

Hier gehts zur Angabe: https://www2.cs.fau.de/teaching/WS2013/AuD/organisation/oldexams/secure/13-08-01_klausur.pdf

Und auch gleich das zweite gibt mir Rätsel auf:

Trinkbar tm = new MilchShake();
System.out.println(tm.menge);

Angeblich kommt 42 raus. OK, das hat wohl wieder mit dem statischen Typ oder so zu tun. menge ist bei MilchShake statisch, und der statische Typ ist hier Trinkbar
und bei Trinkbar ist Menge gleich 42 und dahere wird das ausgegeben, war das richtig?

[Volschaf]

---

@Kuno_See

Trinkbar tv = new Vodka();
System.out.println(tv.verdauen(1));

Warum kommt hier „ist unverdaulich raus?“
Ich hätte „dauert mehrere Stunden“ gewählt. Das wird ja einfach mit ner 1 aufgerufen, da hätte ich gedacht dass das eher in den Integer fällt und nicht in Long.

Es kommen nur Methoden in Frage, die der statische Typ kennt. Und [m]Trinkbar[/m] kennt nur [m]verdauen(long)[/m].

[system]

---

@Kuno_See

Wäre toll, wenn dir so ein Spezialfall einfällt, dann könnte ich es vielleicht sogar verstehen=)

Rohr r1 = new Rohr(q, 1, one); // altes Gewicht: 7
Rohr r2 = new Rohr(q, 8, two); // altes Gewicht: 2
Rohr r3 = new Rohr(one, 1, two); // altes Gewicht: 1
Rohr r4 = new Rohr(one, 8, s); // altes Gewicht: 3
Rohr r5 = new Rohr(two, 1, s); // altes Gewicht: 4

[Kuno_See]

---

Es kommen nur Methoden in Frage, die der statische Typ kennt. Und Trinkbar kennt nur verdauen(long).

Danke.
Gilt diese Regel immer?
Ich dachte bislang, dass man halt schaut, ob die methode oder das attribut um das es geht, mit „static“ deklariert ist. Wenn das der Fall ist,
dann schaut man was der statische Typ, in diesem Fall Trinkbar, dort eingetragen hat.

[Volschaf]

---

@Kuno_See

Ich dachte bislang, dass man halt schaut, ob die methode oder das attribut um das es geht, mit „static“ deklariert ist. Wenn das der Fall ist,
dann schaut man was der statische Typ, in diesem Fall Trinkbar, dort eingetragen hat.

Da bringst du grade Sachen durcheinander. Das Keyword [m]static[/m] hat nichts mit statischem Typ zu tun.
Kurz gesagt bedeutet [m]static[/m] bei Methoden, dass diese auch ohne ein existierendes Objekt der Klasse aufgerufen werden koennen (bspw. [m]Integer.parseInt(String s)[/m]) und bei Attributen, dass diese existieren, auch wenn zur Zeit kein Objekt der Klasse existiert.

Zum Nachlesen empfiehlt sich vielleicht auch Java ist auch eine Insel.

[Kuno_See]

---

Okay ich gehe also davon aus, dass diese Regel immer gilt. Auch bei Attributen?

Es kommen nur Methoden in Frage, die der statische Typ kennt. Und Trinkbar kennt nur verdauen(long).

[Volschaf]

---

@Kuno_See

Okay ich gehe also davon aus, dass diese Regel immer gilt. Auch bei Attributen?

Es kommen nur Methoden in Frage, die der statische Typ kennt. Und Trinkbar kennt nur verdauen(long).

Ja.
Solche Aufgaben eignen sich übrigens wunderbar dafür, mal schnell eine Ober- und Unterklasse zu schreiben und selbst ein wenig rumzuspielen.

[Kuno_See]

---

Danke Chayyam für deinen Spezialfall. Ich habe das gestern schon gelesen,
ABER JETZT HAB ICH S ERST VERSTANDEN ! JUHU! Puuh, die Aufgabe hat mir echt Kopfzerbrechen bereitet.

[lemur]

---

Die Regel ist übrigens das, was die “Typsicherheit” besagt.
Typsicherheit: Es dürfen nur Methoden aufgerufen werden,
die schon beim statischen Typ von m (Oberklasse Medium) verfügbar sind.
[aus Vorlesungsfolien]