Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen

Forendiskussionen

Lösungsversuch

Aufgabe 1 - Wissensfragen (16)

  • a) 1 und 4
  • b) 1 und 2
  • c) 4 *Edit*(und 2) vgl. Vl 14 S. 85 *Edit*
  • Erneuter Edit von jemand anderem: 4 ist nicht richtig, der Laufzeitaufwand bei Prim ist O(n*log n + e). O(n + m) = O(max(n, m)), n*log(n) ist hier max, darum stimmt O(n*log(n)). Ausserdem ist 3 sehr wohl richtig: Das steht exakt so in der Vorlesung, Kruskal hat O(e*log e).

Aufgabe 2 - Bäume (9)

Aufgabe 3 - Graphen (18)

a) Endergebnis: 0,2,4,7,6,7 —> Falsch: Von A nach F kommt man mit Pfad A→B→C→F mit Kosten 5, 7 kann also nicht stimmen. Lösung ist: 0,2,4,7,6,5)

b) A→B→C→F→E→D, Distanz 7.

c)

  • B, A
  • A, D
  • E, D
  • E, F
  • F, C

Alternativ:

  • B, C
  • F, C
  • E, F
  • E, D
  • D, A

d)

  • Stark zusammenhängend: keine
  • Schwach zusammenhängend: 1, 6
  • Zusammenhängend: 3
  • Nicht zusammenhängend: 2, 4, 5

Aufgabe 4 - Rekursion (11)

Live auf ideone.com mit AuD-Beispiel: http://ideone.com/jr02d3

static <T> List<List<T>> helfer(T[] s, int idx) {
	// Rückgabe pms ist Potenzmenge von s ab index idx
	List<List<T>> pms = new ArrayList<List<T>>();
	if (idx >= s.length) {
		// Basisfall
		pms.add(new ArrayList<T>());
	} else {
		// aktuelles Kopfelement bestimmen
		T kopf = s[idx];
 
		// Potenzmenge der Restliste bestimmen
		List<List<T>> potRest = helfer(s, idx + 1);
 
		// Ergebnisse zusammenführen
		for (List<T> ohneKopf : potRest) {
			List<T> mitKopf = new ArrayList<>(ohneKopf); // *nocH* ohne Kopf
			mitKopf.add(kopf);
 
			pms.add(ohneKopf);
			pms.add(mitKopf);
		}
	}
	return pms;
}

Aufgabe 5 - Gerichtete azyklische Graphen (15)

boolean eval(HashSet<String> tv) {
    if (this == BDD.TRUE) return true;
    if (this == BDD.FALSE) return false;
    return tv.contains(v) ? trueC.eval(tv) : falseC.eval(tv);
}
 
boolean isDAG(HashSet<BDD> p) {
    if (p.contains(this)) return false;
    p.add(this);
    if (trueC != null && !trueC.isDAG(p)) {
      return false;
    }
    if (falseC != null && !falseC.isDAG(p)) {
      return false;
    }
    p.remove(this);
    return true;
}

Aufgabe 6 - Dynamische Programmierung (17)

a) Verschachtelte Rekursion

b, c)

class DynProg {
 
	private int[] dp;
 
	public DynProg(int max) {
		dp = new int[max];
	}
 
	int fDP(int n) { // Dynamische Programmierung
		int fn = 1; // Basisfall n < 3 trivial
 
		// fn schon einmal berechnet?
		if (n <= dp.length && dp[n-1] != 0) {
			fn = dp[n-1];
		} else if (n >= 3) { // fn muss noch berechnet werden
			if (n <= dp.length) {
				fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1;
				dp[n-1] = fn;
			} else {
				fn = f(n);
			}
		}
		return fn;
	}
}

d)

Hier sind viele Varianten denkbar.

public static int fIter(int n) { // Iterativ
	int k = 1; // Zähler
	int fk = 1;
 
	int z = 2;
	for (; k<=n; k++) {
		if (z == 0) {
			fk++;
			z = 2 * fk - 1;
		}
		else {
			z--;
		}
	}
 
	return fk;
}

Aufgabe 7 - Sortieren (16)

Mit System.out.println() Aufrufen zum Testen:

public class MergeSortUsing4Lists {
     public static void mergeSortExtern(LinkedList<Integer> b) {
         assert b != null;
         assert b.size() > 0;
 
         LinkedList<Integer> b0 = new LinkedList<>();
         LinkedList<Integer> b1 = new LinkedList<>(b.subList(0, b.size() / 2));
         LinkedList<Integer> b2 = new LinkedList<>(b.subList(b.size() / 2, b.size()));
         LinkedList<Integer> b3 = new LinkedList<>();
 
         merge(1, b0, b1, b2, b3);
 
         b.clear();
         b.addAll(b0);
         b.addAll(b1);
     }
 
     public static void merge(int len, LinkedList<Integer> b0, LinkedList<Integer> b1, LinkedList<Integer> b2,
             LinkedList<Integer> b3) {
         LinkedList<Integer> target = b0; // alternating between b0 and b3
 
         do {
             System.out.println();
             System.out.println(b0);
             System.out.println(b1);
             System.out.println(b2);
             System.out.println(b3);
             System.out.println();
             int z1 = 0, z2 = 0; // counter for the already stored integers from
                                 // b1/b2 up to len
 
             // if possible, store integers from b1 AND b2
             while (!b1.isEmpty() && !b2.isEmpty() && z1 < len && z2 < len) {
                 // Wegen <= ist es stabil
                 if (b1.getFirst() <= b2.getFirst()) {
                     target.addLast(b1.removeFirst());
                     z1++;
                 } else {
                     target.add(b2.removeFirst());
                     z2++;
                 }
             }
 
             // if there are still integers from b1
             while (!b1.isEmpty() && z1 < len) {
                 target.addLast(b1.removeFirst());
                 z1++;
             }
 
             // if there are still integers from b2
 
             while (!b2.isEmpty() && z2 < len) {
                 target.addLast(b2.removeFirst());
                 z2++;
             }
 
             target = target == b0 ? b3 : b0;
 
         } while (!b1.isEmpty() || !b2.isEmpty());
         // b3 is not empty => recursion call!
 
         if (!b3.isEmpty()) {
             merge(2 * len, b1, b0, b3, b2);
         } else {
             System.out.println();
             System.out.println(b0);
             System.out.println(b1);
             System.out.println(b2);
             System.out.println(b3);
             System.out.println();
         }
     }
 
     public static void main(String[] args) {
         LinkedList<Integer> a_empty = new LinkedList<Integer>();
    	 mergeSortExtern(a_empty);
 
         LinkedList<Integer> a = new LinkedList<Integer>(
                 Arrays.asList(10, 2, 1, 7, 6, 9, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
 
         mergeSortExtern(a);
 
         // odd number of elements (added number 19)
         LinkedList<Integer> a_odd = new LinkedList<Integer>(
                 Arrays.asList(10, 2, 1, 7, 6, 9, 19, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
 
         mergeSortExtern(a_odd);
     }
 }

Aufgabe 8 - Backtracking (18)

LinkedList<int[]> helfer(int mL, int kL, int b, int mR, int kR) {
	LinkedList<int[]> erg = new LinkedList<>();
	if(mL < 0 || kL < 0 || mR < 0 || kR < 0) {
		// Abbruch wegen negativer Personenzahl
		return null;
	} else if(mem[mL][kL][b][mR][kR]) {
		// Abbruch weil Zustand schon besucht
		return null;
	} else if((mL > 0 && mL < kL) || (mR > 0 && mR < kR)) {
		// Abbruch zu viele Kannibalen an einem der Ufer
		return null;
	} else if(mL == 0 && kL == 0 && b == 1) {
		// Zielzustand erreicht
		erg.add(new int[] { mL, kL, b, mR, kR });
		return erg;
	} else {
		// zulaessiger Zwischenzustand
		erg.add(new int[] { mL, kL, b, mR, kR });
 
		for(int[] fahrt : denkbar[b]) {
			// probiere jede denkbare fahrt, die am Ufer b beginnt
			mem[mL][kL][b][mR][kR] = true;
			LinkedList<int[]> list = helfer(mL - fahrt[0], kL - fahrt[1], (b + 1) % 2, mR + fahrt[0], kR + fahrt[1]);
			if(list != null) {
				erg.addAll(list);
				return erg;
			}
			mem[mL][kL][b][mR][kR] = false;
		}
	}
	return null;
}