Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Forendiskussionen

Lösungsversuch

Aufgabe 1 Wissensfragen

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 (achtung, falsch: Folgendes beachten)

  • 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.
    • Meiner Meinung nach: 3 und 4 sind richtig! Da 1 die definition von gross Omega und 2 von gross Theta ist, wobei die 3 und 4 mit den Rechenregeln des O Kalkuels, bzw 3 bei genauerem Nachdenken ueber den Logarithmus richtig sein muessen. T(n) = T(0.666 * n) = T(c * n) = T(n) + w mit c als Konstante > 1 ist.

Aufgabe 2 Streuspeicherung

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

Aufgabe 3 Binäre Suche

>>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;
	}

Aufgabe 4 Halden

>>>Tool zum selber Testen<<<

a) Min Heap

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

b) ⇒ Min-Halde

26371054891211

c) ⇒ Min-Halde

0217634891011125

Aufgabe 5 Sortieren

a)

L * A1 B1 F A2 B2
A1L*B1F A2B2
A1B1L*F A2B2
A1B1F L*A2B2
A1A2B1F L*B2
A1A2B1B2F L*

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
	}
}

Aufgabe 6 Dynamische Programmierung

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];
 
	}

Aufgabe 7 Graphen

a)

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);
        }
    }
  }
}

b)

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;
	}

c)

void itg(boolean[][] am, Set<Integer> vs) {
    for (int i = 0; i < am.length; i++) {
        for (int j = 0; j < am.length; j++) {
            if (am[i][j]) {
                if (!vs.contains(i) || !vs.contains(j)) {  // es muss sowohl x als auch y in vs enthalten sein
                    am[i][j] = false; // der Graph ist gerichtet, daher reicht die Betrachtung an einer Stelle
		}
	    }
	}			
    }
}
 
// alte Loesung:
void itg(boolean[][] am, Set<Integer> vs) {
		for (int i = 0; i < am.length; i++) {
			for (int j = 0; j < am.length; j++) {
				if (am[i][j]) {
					if (!(vs.contains(i) && vs.contains(j))) {
		                                am[i][j] = false;
                                                am[j][i] = false;
					}
				}
			}			
		}
}

Code zum selber testen:

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()); 
	}
}

Aufgabe 8 ADT

TODO

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