• https://fsi.cs.fau.de/forum/thread/14556-Klausur-WS15-Loesungsdiskusion
• Diskussion zur Aufgabe 4

a) 1 und 3

b) 2 und 3

c) 2 || Ziemlich sicher, dass auch 1 richtig ist.

• zu 1) (2. Meinung: „(stimmt hier nicht auch 1?)“) ⇒ wenn man bei der linearen Suche („< oder “=„) überprüft, müsste man sicherstellen, dass die zu durchsuchende Zahlenreihe immer aufsteigend sortiert ist. Mit einer allgemeinen Methode zur linearen Suche würden die Suchen mit Sicherheit für alle anderen Fälle daneben gehen.
• zu 2) Lineare Suche überprüft im intervall [0:n] ob das i-te-Element == gesuchte Element ist, wenn das gesuchte Element das erste Element ist, dann ist man sofort fertig. Die binäre Suche braucht dazu mindestends noch ein schritt.
• zu 3) unsicher, ob das hier eine Rolle spielt ( 2.Meinung: „Denke ich nicht“)
• zu 4) scheidet aus, weil 2 richtig ist

d) 3

e) 1 und 4

• Man spricht nur bei „ungerichteten“ Graphen von „Grad“, bei gerichteten unterscheidet man Eingangs- und Ausgangsgrad. Wenn ein Knoten ein Grad 0 hat, dann gibt es keine Kante auf ihn. Der Graph ist also bereits ab einem Knoten mit Grad 0 nicht mehr zusammenhängend. Vorausgesetzt der Graph besteht aus mehr als einem Knoten. Da nichts anderes Korrekt scheint, muss dass also so passen.
• Ein stark zusammenhängender Graph hat zyklen, womit der Graph kein DAG mehr sein kann

f) 2 und 4

• „löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.“: Unsicher, ob man mit dem Algorithmus das Problem lösen kann oder wie die Lösung aussieht.

g) 2 (Meiner Meinung nach: 1 und 4 sind richtig!)

• unsicher
• Ich denke 4 müsste stimmen
• Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), in den Folien aber steht, dass man mit dem O-Kalkül meistens das meint.

a) Liste

• 0 E
• 1 A
• 2
• 3 B → C → D
• 4
• 5
• 6

b) (P)→ entspricht dem Pfeil mit P und (S) dem Pfeil mit S

• A 1
• B 3
• C 3 (P)→ 4
• D 3 (P)→ 4 (S)→ 0
• E 0 (S)→ 1 (P)→ 4 (S)→ 2

>>code zum selber testen<<

<T> int suche(T[] ts, T t, Comparator<T> c1, Comparator<T> c2){
		int a=0, m, z=ts.length -1; //Anfang, Mitte, Ende
		while(z >= a){
			m= (a+z)/2;
 
			if(c1.compare(t, ts[m]) < 0){
				z=m-1;
 
			}else if(c1.compare(t, ts[m]) == 0){
 
				if(c2.compare(t, ts[m]) < 0){
					z=m-1;
 
				}else if(c2.compare(t, ts[m]) == 0){
					return m;
 
				}else{
					a=m+1;
				}
			}else {
				a=m+1;
			}
 
		}
		return -1;
	}

>>>Tool zum selber Testen<<<

a) Min Heap

• 0
• 2 3
• 7 6 5 4
• 8 9 10 11 12

b) ⇒ Min-Halde

c) ⇒ Min-Halde

a)

b) >>code zum selber testen<<

void sortierenDurchEinfuegen(String[] a) {
	String tmp;
 
	for (int n = 1; n < a.length; n++) {
 
		tmp = a[n]; // entnommenes Element merken
 
			int i = n - 1;
 
		while (i >= 0 && tmp.compareTo(a[i]) < 0) {
			a[i + 1] = a[i];
			i--;
		}
 
		a[i + 1] = tmp; // entnommenes Element
		// einsetzen
	}
}

a)

• kaskadenartige

b) Quelle

long a(int n) {
   if (n <= 1) {
        // Basisfall:
        return 1;
   } else {
        // Rekursion:
        long an = a(n-1);
        for(int i = 1; i < n; i++){
                  an+= a(i)*a(n-i); 
        }
        return an;
  }
}

c)

>>>code zum selber testen<<<

long aDP(int n){
		if(mem == null || n >= mem.length){
			long[] oldMem=mem;
			mem=new long[n+1];
 
			if(oldMem != null){
				for(int i=0; i < oldMem.length;i++)
				mem[i]=oldMem[i];
			}
 
		}
 
		if(n <= 1){
			mem[n]=1;
 
		}else if(mem[n] == 0){
 
			mem[n]=aDP(n-1);
 
			for(int i=1; i<n; i++)
				mem[n] += aDP(i)*aDP(n-i);
		}
 
		return mem[n];
 
	}

public class GraphWS15 {
 
	void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) {
		if (!bes.contains(k)) {
			verb.add(k);
			bes.add(k);
			for (int i = 0; i < am[k].length; i++) {
				if (am[k][i]){
					sammle(am, i, verb, bes);
				}
			}
 
			for (int i = 0; i < am.length; i++) {
				if (am[i][k]){
					sammle(am, i, verb, bes);
				}
			}
		}
	}
 
	List<Set<Integer>> mszt(boolean[][] am) {
		// Ergebnisliste:
		List<Set<Integer>> ergebnis = new LinkedList<>();
		// Menge besuchter Knoten:
		Set<Integer> bk = new HashSet<>();
		// Ermittle alle Teilgraphen mittels Hilfsmethode sammle:
		for (int k = 0; k < am.length; k++) {
			if (!bk.contains(k)){
				// falls k noch nicht besucht => sammle mit k verbundene Knoten
				Set<Integer> verb = new HashSet();
				sammle(am,k,verb, bk);
				ergebnis.add(verb);
                                //einfacher waere hier statt den letzten drei zeilen folgendes:
                                //sammle(am,k,ergebnis.get(k), bk); //!!
			}
 
		}
 
		return ergebnis;
	}
 
	void itg(boolean[][] am, Set<Integer> vs) {
		for (int i=0;i<am.length;i++){
			for (int j=0;j<am[i].length;j++){
				if (am[i][j]){
					if (!(vs.contains(i) && vs.contains(j))){
		                                am[i][j] = false;
                                                am[j][i] = false;
					}
				}
			}
 
		}
	}
 
	public static void main(String[] args){
                //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph
		GraphWS15 g = new GraphWS15();
		boolean[][] am = {{false, true, false, true, false, false},
                                              {false, false, false, true, false, false},
                                              {false, false, false, false, true, false},
                                              {false, true, false, false, false, false},
                                              {false, false, false, false, false, false},
                                              {false, false, false, false, false, false}};
		//Set<Integer> verb = new HashSet();
		List<Set<Integer>> n = g.mszt(am);
		System.out.println(n.size()); 
		System.out.println(n.get(0).size()); 		 
		System.out.println(n.get(1).size()); 
		System.out.println(n.get(2).size()); 
	}
}

a)

• collect(Node(g, n)) = add(collect(g), n)
• collect(Edge(g, a, b)) = add(add(collect(g), a), b)

b)

• path(Node(g, n), x, y) = path(g, x, y)
• path(Edge(g, a, b), x, y) = true falls (path(g, x, a) ^ path(g, b, y)) v (path(g, y, a) ^ path(g, b, x)) ; path(g, x, y) sonst

c)

• isRoot(Edge(g, a, b), x) = isRoot(g,x) falls x!=b

false sonst