• https://fsi.informatik.uni-erlangen.de/forum/thread/8074-Wissensfragen-24-02-2011
• https://fsi.informatik.uni-erlangen.de/forum/thread/8875-AK-24-2-11-Aufgabe-6-Graphen-Dijkstra-Stack
• https://fsi.informatik.uni-erlangen.de/forum/thread/8059-Dynamische-Programmierung 3c
• https://fsi.informatik.uni-erlangen.de/forum/thread/9409-24-02-2011

a) Da die Klasse AssertionError eine Unterklasse von java.lang.Error ist, können Ausnahmen dieser Art nicht abgefangen und daher nicht behandelt werden.

falsch: Alle Fehlertypen, auch java.lang.Error und davon abgeleitete können mit catch abgefangen werden, obwohl das u.U. nicht immer sinnvoll ist; Fehler die von java.lang.Error abgeleitet sind, haben meist ein schwerwiegendes Problem als Ursache, so dass es sinnvoller sein kann, das Programm zu beenden als unter unklaren Bedingungen zu versuchen weiterzuarbeiten.

b) Ein AssertionError tritt in einer seiteneffektfreien assert-Anweisung auf, wenn die Zusicherung während der Programmausführung nicht erfüllt ist, jedoch nur, falls das Prüfen von Zusicherungen durch die Java-VM beim Programmstart aktiviert wurde.

wahr.

c) Es kann kein Sortierverfahren für n Schlüssel existieren, das auf Vergleichen von Schlüsselpaaren beruht und dessen Laufzeitkomplexität besser als O(n · log₂ n) ist.

wahr. Ich (dario) würde sagen, dass da log₂ steht, prüft einfach nochmal ab, ob dem Prüfling klar ist dass O(log₂ n) = O(log_a n) = O(log n)

d) : code eintragen f ∈ O(log n); g ∈ O(n log n);

e) Die Suche nach einem Element in einer sortierten doppelt-verketteten Liste der Länge n ohne wahlfreien Zugriff hat eine Laufzeitkomplexität von O(n).

wahr: „ohne wahlfreien Zugriff“ ⇒ man muss die Liste entlanglaufen, bis man das gesuchte Element gefunden hat, die Tatsache dass die Liste sortiert ist, hilft in demt Moment nicht allzuviel.

f) Verwendet man zum Einfügen in einen Streuspeicher (Tabellenlänge n) das sogenannte quadratische Sondieren, so hat die Operation eine Laufzeitkomplexität von O(log(n)).

falsch: Die Reihenfolge wie die Felder der Streutabelle sondiert werden, ist zwar unterschiedlich, insgesamt werden im worst case aber trotzdem alle Felder einmal besucht, also ist die Komplexität O(n).

g) In einem gerichteten Graphen G = (V, E) repräsentiert der Ausgangsgrad eines Knotens n ∈ V die Anzahl aller Knoten m ∈ V , für die es eine Kante (n, m) ∈ E gibt.

wahr.

h) Mehrfachvererbung von mehreren nicht-abstrakten Oberklassen ist in UML-Klassendia- grammen (genau wie in Java) verboten.

falsch: Da UML nicht Java-spezifisch ist, und z.B. in C++ Mehrfachvererbung möglich ist, ist auch in UML Mehrfachvererbung erlaubt.

i) Folgender Code verwendet Generics korrekt im Sinne der Sprache Java und ist daher gültig und ubersetzbar: : add code

wahr (ich (dario) kann keinen fehler erkennen ;)

Frage: Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler? (Dank an dario für die guten Erklärungen)

Antwort: Man kann alle Methoden die der generische Typ hat Aufrufen. Im Fall von <T> waere das in der Tat nur Methoden von Object (weil in Java alle Klassen von Object automatisch erben). Hier steht aber <T extends Book>, d.h. es koennen auch Methoden der Klasse Book aufgerufen werden, da der generische Typ von Book erben muss.

a)

b) Geben Sie zu jedem Knoten des neuen Baums X dessen Höhe in X an:

c) Betrachten Sie den neuen Baum X als sogenannten Out-Tree“ (bei dem die Kanten gerichtet von der Wurzel ausgehen) und geben Sie ihn in Mengenschreibweise an:

Mengenschreibweise X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r
V = {A, B, C, D, E, F, G}
E = ab_ag_bd_be_bf_dc
r = A

d) Schreiben Sie eine Methode isUndirected, die feststellt ob eine Adjazenzmatrix amx einen ungerichteten Graphen darstellt.

Zunächst einmal muss man sich klar machen, dass ein Graph genau dann ungerichtet ist, wenn die Adjazenzmatrix sowohl einen Eintrag (AB) als auch einen Eintrag (BA) hat.

/**
 * die idee is, einfach die ganze adjazenzmatrix durch zu gehen
 * und zu schaun ob alle einträge mit ihren "gegenüberliegenden"
 * - also an der diagonale gespiegelten (indices vertauscht) -
 * übereinstimmen. falls nicht, ist der graph gerichtet.
 **/
public boolean isUndirected(boolean[][] amx) {
	for(int i= 0; i < amx.length; i++) {
		for(int j= 0; j < amx[0].length; j++) {
			if(amx[i][j] != amx[j][i]) {
				return false;
			}
		}
	}
	return true;
}

(dario): ich geb zu, es is nicht der effizienteste code (wer will kann den mal dazuschreiben), aber in der klausur kommts erstmal drauf an, dass der code tut was er soll, und nicht ob er dass in O(n) oder O(n²) tut (abgesehen davon, dass es selbst wenn man nur die hälfte vergleicht noch O(n²) bleibt).

e) TODO

	public static boolean allReach(boolean[][] ug, int node){
		boolean schonGehabt[] = new boolean[ug[node].length];
 
		help(ug, node, schonGehabt);
 
		for (int i=0; i<schonGehabt.length; i++){
			if (schonGehabt[i] == false){
				return false;
			}
		}
		return true;
	}
 
 
	public static void help(boolean[][] ug, int node, boolean[] schonGehabt){
		schonGehabt[node] = true;
 
		for (int i=0; i<ug[node].length; i++){
			if (schonGehabt[i] == false && ug[node][i] == true){
				help(ug, i, schonGehabt);
			}
		}
	} //Gruesse Gaku :)

a) 96

b) von hinten nach vorne

c)

d)

public static char getChar(String str, int pos){
		return (pos < str.length()) ? (str.charAt(pos)) : (char) 96;
	}
 
	public static void radixSort(String[] array){
		ArrayList<String>[] buckets = (ArrayList<String> []) new ArrayList[27];
 
		for(int i = 0; i < 3; ++i){
			for(int j = 0; j < 27; ++j){
 
				buckets[j] = new ArrayList<String>();
 
 
			}
			for(int j = 0; j < array.length; ++j){
				buckets[(int)getChar(array[j],2-i) - 96].add(array[j]);
 
			}
			int k = 0;
			for( int j = 0; j < 27; ++j){
				for(String str : buckets[j]){
					array[k++] = str;
 
				}
			}
		}
	}

a) getPublishDate(createPost(„Hallo“, 24.02.2011, false) = 24.02.2011
ist mit „vereinfachen“ wirklich die Normalform (Ergebnis) gemeint?

b) 01.01.1970

c) createPost(s,d,v)

d) F4: getUrl(publish(P , id, F )) = getURL(F);

e)

					                 F		falls id1 == id2	
F6: revoke(id1 , publish(P , id2 , F )) = 
					                 publish(P,id2,revoke(id1, F)	sonst

f)

					                   publish(setSeen(P,true), id2, F)    	falls id1 = id2
F8: markSeen(id1 , publish(P , id2 , F )) = 
					                   publish(P, id2, markSeen(id1,F))  	sonst

a) A –> [B,9] –> [C,6] B –> A,9 –> E,3 –> C,21 F –> E,4 –> K,2 –> G,10 Z –> H,5 –> K,3

b)

c) Für diese Aufgabe sollte man die angegebene Entfernungstabelle benutzen.
Lösung: D-H, F-K, B-E, C-G, K-Z, D-E, E-F, A-C, D-G

Wie viele Meter Kabel werden verlegt? 33

a) Rechts oben ist richtig, da in der Schleife und aus der Schleife der Invariante die Nachbedingung sein muss Die Schleife berechnet die Summer der Betraege jedes a's es können nur die rechten sein, da die linken nur die Summe zum betrag berechnet.

Rechts unten kann man direkt wegfallen lassen, da i irgendwann = n sein muss, da sonst die Schleife nie terminiert

b)

s einsetzen, s = 0
wp("n=a.length; s=0; i=0;I)
0=|ai|^0<=n --> 0=0^0<=n  --> stimmt!

c)

I∧b --> wp(A,I)
wp("if/else;i=i+1,I)  ---> [b∧wp(Ai,I)]...
-->[a[i]>0∧wp("s=s + a[i]", s=(Summenzeichen) ∧ c <=n)
a[i] <= 0 ∧ wp("s = s-a[i], s = (Summenzeichen) ∧ i <= n)]

--> a[i] >0 s + a[i] = (Summenzeichen) |aj| ∧ 1+1| sn) ....
kp wie das weiter funktioniert
Ende: (ai > 0 ∧ s = (Summenzeichen)|ai| ∧ i + 1 <= n)) (umgedrehtes  ∧) (ai <= 0 0 ∧ s = (Summenzeichen)|ai| ∧ i + 1 <= n))

I ∧ b => wp(a,I)
s = (Summenzeichen)|aj| ∧ i + 1 <= n ∧ i < n) --> s = (Summenzeichen)|aj| ∧ i + 1 <= n)
daraus sieht man: A --> A  ist korrekt!

class Firma{
 
	String name;
	Person geschaeftsfuehrer;
	Person[] mitarbeiter;
 
	Integer gibAnzahlMitarbeiter() { //Objekt vom Typ Integer, nicht der Datentyp int 
	}
 
}
 
class Person {
 
	String name;
	Integer gebJahr; 
 
	Person vorgesetzter;
	Person[] unterstellteMitarbeiter;
 
	Person[] gibAlleUnterstelltenMitarbeiter() {
	}
 
}