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

Dies ist eine alte Version des Dokuments!


Forendiskussionen

Lösungsversuch

Aufgabe 1 - Wissensfragen

a) E + Unterklassen von E

b) O(|n|)
Begründung:
Nach einmaliger Abarbeitung der inneren Schleife gilt „n == 0“. Dadurch ergibt die Auswertung des Schleifenkopfs der äußeren Schleife „false“ und die Funktion endet.

c) O(n) Begründung:
Im ersten Durchgang der Schleife werden alle drei Unterfunktionen einmal aufgerufen, das heißt: O(log n) + O(n) + O(1) = O(n) für die erste Iteration.
In allen weiteren Durchläufen wird nur mehr „doSomethingInO(1)“ ausgeführt, das heißt O(1) für alle weiteren Iterationen.
Da es insgesamt n-1 weitere Iterationen gibt, lautet der Gesamtaufwand der weiteren Iterationen O(n)
Insgesamt ergibt sich damit: O(n) + O(n) = O(n)

d) 2. Antwort ist richtig

e) 1. Antwort ist richtig: „Überlädt meth aus C“, da beide Methoden gleich heißen, aber andere Parameter erwarten

f) 2. und 3. Antwort sind richtig

g) false, denn der „==“-Operator vergleicht die Referenzen, nicht den Inhalt der Objekte (das wäre equals())

h) O(log n)
Begründung:
Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden.
Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht.

i) 2. Antwort ist richtig

j) 3. Antwort ist richtig

Aufgabe 2 - Binärbäume

a)

  • Für jeden Knoten gilt: Alle Knoten des linken Teilbaums sind echt kleiner und alle des rechten Teilbaums echt größer sind als der Knoten selbst.
  • Mathematisch: ∀ Teilbäume T' des Binärbaums T, T' = (T_l, y, T_r) gilt:
    • a) ∀ x ∈ T_l: value(x) < value(y)
    • b) ∀ z ∈ T_r: value(z) > value(y)

b)

boolean isSearchTree() {
	if(left != null) {
		if(getMax(left.data) >= data || !left.isSearchTree())
			return false;
	}
 
	if(right != null) {
		if(getMin(right) <= data || !right.isSearchTree())
			return false;
	}
 
	return true;
}

c)

  • Für jeden Knoten gilt: Der Wert seiner Kinder muss größer als sein eigener Wert sein.
  • Mathematisch: Ein partiell geordneter Baum ist ein knotenmarkierter Binärbaum, in dem für jeden Teilbaum T' mit Wurzel x gilt:
    • In der Wurzel steht immer das Minimum des Teilbaums, also ∀y ∈ T': value(x) ≤ value(y)

d)

void sanitize() {
	int smallest = getSmallest();
 
	// aktueller Knoten der kleinste -> fertig
	if(data == smallest)
		return;
 
	if(left != null && left.data == smallest) {
		swap(this, left);
		left.sanitize();
	} else {
		swap(this, right);
		right.sanitize();
	}
}

e)

Ein AVL-Baum ist ein binärer Suchbaum, bei dem für jeden Knoten gilt: Die Höhe seiner beiden Teilbäume unterscheidet sich maximal um eins.

f)

public int getHeight() {
	if(left == null && right == null)
		return 1;
 
	if(left == null)
		return 1 + right.getHeight();
 
	if(right == null)
		return 1 + left.getHeight();
 
	return 1 + Math.max(left.getHeight(), right.getHeight());
}

g)

void getInOrderHelper(ArrayList<Integer> a){
	if(left != null)
		left.getInOrderHelper(a);
 
	a.add(data);
 
	if(right != null)
		right.getInOrderHelper(a);
}

h)

2. und 3. Antwort sind richtig

Aufgabe 3 - Streutabellen

a)

boolean exists(int h) {
	if(h >= urls.size() || urls.get(h).isEmpty())
		return false;
 
	return true;
}

b)

Mit der Kollisionsliste ist die ArrayList eines Buckets gemeint, durch die Kollisionen aufgelöst werden.

int getIndex(String url, ArrayList<String> urlList) {
	for(int i = 0; i < urlList.size(); i++) {
		if(urlList.get(i).equals(url))
			return i;
	}
	return -1;
}

Alternativ:

int getIndex(String url, ArrayList<String> urlList) {
	return urlList.indexOf(url);
}

Bemerkung:
Der Parameter urlList ist eigentlich überflüssig, da man mit Hilfe der url und der Hashfunktion die korrekt urlList selbstständig identifizieren kann.

c)

String loopkup(String url) throws UnknownHostException {
	int h = hash(url);
 
	if(!exists(h))
		throw new UnknownHostException();
 
	ArrayList<String> bucket = urls.get(h);
	int index = getIndex(url, bucket);
 
	if(index == -1)
		throw new UnknownHostException();
 
	return ips.get(h).get(index);
}

d)

void resize(int h) {
	while(urls.size() <= h) {
		urls.add(new ArrayList<String>());
		ips.add(new ArrayList<String>());
	}   
}   

e)

void register(String url, String ip){
	int h = hash(url);
 
	// Hashtabelle vergrößern (resize verändert nichts, wenn ein Vergrößern nicht notwendig ist)
	resize(h);
 
	int index = getIndex(url, urls.get(h));
 
	// URL wurde nicht gefunden -> URL und IP neu hinzufügen
	if(index == -1) {
		urls.get(h).add(url);
		ips.get(h).add(ip);
 
	// URL ist bereits vorhanden -> aktualisiere IP
	} else {
		ips.get(h).set(index, ip);
	}
}   

Bemerkung:
Die Aufgabe baut auf der Annahme auf, dass es sich praktisch um zwei eigenständige, aber gleichzeitig (!) verwaltete Hashtabellen handelt.
Nur aufgrund diese Annahme funktionieren die obigen Funktionen korrekt.

Aufgabe 4 - Dynamische Programmierung

a)

public static boolean isPrimeDP(long p, long primes[]) {
	for(int i = 0; primes[i] * primes[i] <= p; i++) {		
		if(primes[i] != 0 && p % primes[i] == 0)
			return false;
	}
 
	return true;
}

Optimierung beim Abbruchskriterium des naiven Primzahltests:
Überprüfe nur alle Primzahlen zwischen 2 und √n

b)

public static long getPrimeDPHelper(int n, long primes[]) {
	if(n <= 0)
		return 2;
 
	// Geforderte Primzahl wurde noch nicht berechnet
	if(primes[n] == 0) {
		// Berechne den vorherige Primzahl
		long p = getPrimeDPHelper(n - 1, primes);
 
		// Berechne ausgehend von der vorherigen, die aktuelle Primzahl
		do {
			p++;
		} while(!isPrimeDP(p, primes));
 
		primes[n] = p;
	}
 
	return primes[n];
}

Programm zum selber Testen: :pruefungen:bachelor:aud:primes.java.txt

Aufgabe 5 - Graphen

a)

Kara A B C D E Klee
[0]
0 18 [3] 7 9
0 13 18 3 [7] 7
0 13 18 3 7 [7] 19
0 [11] 18 3 7 7 19
0 11 [16] 3 7 7 17
0 11 16 3 7 7 [17]
0 11 16 3 7 7 17

b)

Kürzester Pfad:
Kara → C → E → A → Klee

c)

(Kara, C), (C, E), (E, A), (A, B), (A, Klee), (Kara, D)

Länge der Leitung: 29 (die Leitung in den zwei Kästchen unter A ist doppelt verlegt)

Aufgabe 6 - Formale Verifikation

a)

Induktionsanfang:

IA_0 (n = 0): 
C_0 = (0 + 2) * 2^(0 - 1) = 2 * 2^(-1) = 2 / 2 = 1 
cpRec(0) = 1 (Basisfall)

IA_1 (n = 1): 
C_1 = (1 + 2) * 2^(1 - 1) = 3*2^0 = 3 * 1 = 3 
cpRec(1) = 3 (Basisfall)

Induktionsschritt:
Induktionsvorraussetzung:

IV_(n-2) (n-2):
cpRec(n-2) = C_(n-2) gilt für ein n ∈ N_0
 
IV_(n-1) (n-1):
cpRec(n-1) = C_(n-1) gilt für ein n ∈ N_0

Aus dem Programmfragment ist zu entnehmen:

cpRec(n) = 4 * cpRec(n-1) - 4 * cpRec(n-2) = ...

Über die obigen Induktionsvoraussetzungen kommt man auf:

... = 4 * C_(n-1) - 4 * C_(n-2) = 
= 4 * [((n - 1) + 2) * 2^((n - 1) - 1)] - 4 * [((n - 2) + 2) * 2^((n - 2) - 1)] = 
= 4 * [(n + 1) * 2^(n - 2)] - 4 * [n * 2^(n - 3)] = 
= 4 * (n + 1) * 2^(n - 2) - 4 * n * 2^(n - 3) = 
= 2^2 * (n + 1) * 2^(n - 2) - 2^2 * n * 2^(n - 3) = 
= (n + 1) * 2^2 * 2^(n - 2) - n * 2^2 * 2^(n - 3) = 
= (n + 1) * 2^(n - 2 + 2) - n * 2^(n - 3 + 2) = 
= (n + 1) * 2^n - n * 2^(n - 1) = 
= (n + 1) * 2^(n - 1) * 2 - n * 2^(n - 1) = 
= (2n + 2) * 2^(n - 1) - n * 2^(n - 1) = 
= 2^(n - 1) * (2n + 2 - n) = 
= 2^(n - 1) * (n + 2) = C_n

q.e.d.

b)

LO: Falsch
	n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung)
	(a = (n + 2) * 2^(n - 1)) = (1 = (n + 2) * 2^(n - 1))
	-> kann nicht für jedes n ≥ 0 gelten

RO: Falsch
	n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung)
	(p = 2^(n - k)) = (1 = 2^(n - (n - 1))) = 
	(1 = 2^1) = (1 = 2)
	-> stimmt nicht

LU: Richtig
	n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung)
	(p = 2^(n - k - 1) ∧ k ≥ 0) = (1 = 2^(n - (n - 1) - 1) ∧ n - 1 ≥ 0) =
	(1 = 2^0 ∧ n - 1 ≥ 0) = (1 = 1 ∧ n - 1 ≥ 0)
	Falls n eine Ganzzahl ist, folgt: (n > 0) ∧ (n - 1 ≥ 0) = true
	-> stimmt

RU: Falsch
	n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung)
	(C_k = (k + 2) * p) = (C_(n-1) = (n + 1) * 1) =
	(C_(n-1) = n + 1) 
	-> kann nicht für jedes n ≥ 0 gelten

c)

wp(A, I) =
wp("a = 1; k = n - 1; p = 1; if(n > 0)", p = 2^(n - k - 1) ∧ k ≥ 0) =
[(n > 0) ∧ wp("a = 1; k = n - 1; p = 1;", p = 2^(n - k - 1) ∧ k ≥ 0)] ∨ [n ≤ 0] =
[(n > 0) ∧ (1 = 2^(n - (n - 1) - 1) ∧ (n - 1) ≥ 0)] ∨ (n ≤ 0) =
[(n > 0) ∧ (1 = 2^0 ∧ n ≥ 1)] ∨ (n ≤ 0) =

(n ≥ 1) = (n > 0), da n Ganzzahl vom Typ long

[(n > 0) ∧ (1 = 1) ∧ (n > 0)] ∨ (n ≤ 0) =
[(n > 0) ∧ (true)] ∨ (n ≤ 0) =
(n > 0) ∨ (n ≤ 0) =
(true)

d)

Zu zeigen: {I ∧ b} => wp(A, I)

wp(A, I) = 
wp("p = p * 2; k = k - 1;", p = 2^(n - k - 1) ∧ k ≥ 0) =
(p * 2 = 2^(n - (k - 1) - 1) ∧ (k - 1) ≥ 0) =
(p * 2 = 2^(n - k) ∧ k - 1 ≥ 0) =
(p * 2 = 2^(n - k) ∧ k ≥ 1) =

(k ≥ 1) = (k > 0), da k Ganzzahl vom Typ long

(p * 2 = 2^(n - k) ∧ k > 0)

{I ∧ b} => wp(A, I) =
{(p = 2^(n - k - 1) ∧ k ≥ 0) ∧ (k > 0)} => wp(A, I) =
¬{(p = 2^(n - k - 1) ∧ k ≥ 0) ∧ (k > 0)} ∨ wp(A, I) =
¬(p = 2^(n - k - 1)) ∨ ¬(k ≥ 0) ∨ ¬(k > 0) ∨ wp(A, I) =
(p ≠ 2^(n - k - 1)) ∨ (k < 0) ∨ (k ≤ 0) ∨ wp(A, I) =
(p ≠ 2^(n - k - 1)) ∨ (k ≤ 0) ∨ wp(A, I) =
(p ≠ 2^(n - k - 1)) ∨ (k ≤ 0) ∨ (p * 2 = 2^(n - k) ∧ k > 0) =

Überlegung:
(p * 2 = 2^(n - k)) =
(p = 2^(n - k) / 2) = 
(p = 2^(n - k - 1))

Somit folgt:
(p ≠ 2^(n - k - 1)) ∨ (k ≤ 0) ∨ (p = 2^(n - k - 1) ∧ k > 1)

Und hieraus folgt offensichtlich:
Sind (p ≠ 2^(n - k - 1)) und (k ≤ 0) beide nicht erfüllt, dann muss (p = 2^(n - k - 1) ∧ k > 1) erfüllt sein.
Die Invariante ist somit gültig.

e)

V := k

Aufgabe 7 - UML

:pruefungen:bachelor:aud:08-2011-uml.png

Dia Sourcefile (für etwaige Korrekturen): :pruefungen:bachelor:aud:08-2011-uml.dia.txt