Lösung der Klausur GdI 2 (Herbst 2007)

ice
Erstie
Erstie
Beiträge: 13
Registriert: 22. Mär 2006 14:19

Lösung der Klausur GdI 2 (Herbst 2007)

Beitrag von ice »

Hallo zusammen!
Die Aufgabenstellung der Klausur steht ja seit gestern online und ich habe mich zusammen mit einem Komilitonen nun einmal dran gemacht diese zu lösen. Unsere Lösung erhebt keinen Anspruch auf Vollständigkeit und Richtigkeit.
Wer Verbesserungsvorschläge zu (Teil-)Lösungen hat postet die bitte mit hier hinein.
Wir konnten noch nicht alle Aufgaben lösen. Wer andere als die hier hineingeposteten Aufgaben schon gelöst hat tut es uns bitte nach!

Hier nun zum Anfang unsere Lösung für Aufgabe 1:

a) f(n) = n
b) g(n)=2^n
c) h(n)=1
d) i(n)=n^2
e) Menge aller Funktionen
f) A->B->C->D (plus zusätlichliche Verbindung A->D weil D auch schon vor B und C erreicht werden kann.
g) Bei Knoten D ist Summe der Eingänge nicht Summe der Ausgänge, damit folgt daß dieser Algo nicht korrekt arbeitet, wenn er wie in Aufgabenstellung gegeben NACH Ermittlung und Bearbeitung eines zunehmenden Flusses abgebildet sein soll.
1. Korrektur: D->B->C um 1 erhöhen damit Flußgraph wieder korrekt.
Der maximale Durchfluss ist (nach kompletter Beendigung des Algo) 20.
Aufteilung: AEC (7); AEDC (1); ADC (5); ABC (7)
Ende ist erreicht weil A->B der einzige mögliche Ausgang der Quelle ist, von B allerdings keinen weiteren Fluß hin zur Senke bilden kann, da BC mit 7/7 ausgelastet ist und bei D->B kein Fluß existiert der eine Rückkante ermöglichen würde.
h)
zusätzlich möglicher Fluß (über Rückkanten des TeilFlusses E->D->B) ist A->B->D->E->C
Aufgrund der Beschränkung durch die RückflussKante B->D ist der maximale zusätzliche Fluß =1.
Kein weiterer zunehmender Fluß mehr möglich, selbe Situation wie in g)
Allein eine Umlegung des TeilFlusses E->D->C auf E->C direkt ist noch als Veränderung möglich. Dies zieht jedoch keine weitere Kapazität nach sich.
i)
Neue Knoten Q (Quelle) und S (Senke)
Q wird mit gerichteten Kanten mit A,B,C verbunden. Diese wie angegeben mit D,E,F,G. und D,E,F,G mit gerichteten Kanten auf die Senke.
Die Kanten zwischen Q und A-C sowie zwischen D-G und S werden jeweils mit der maximalen Flußkapazität 1 gewichtet um keine doppelte Verwendung eines Kntotens in 2 Paaren zu verhindern.
j) Erreichbarkeitsmatrix
k) Bilde Inverse folgendermaßen:
A 1; B 001; C 000; D 01;
l) 17 oder 18
m) 2
n) Array (konnte genaue Bezeichnung im Skript nicht finden) auf jeden Fall ist es die Matrix W(x,y) die den Baum speichert.
o) Uns wären hier lediglich verschieden lange Schlüssel eingefallen, die kann Radix aber sortieren wenn die fehlenden Stellen durch "0" ersetzt werden. -> hat hier jemand einen besseren Einfall??
p) in-place: Quicksort, Heapsort
not-in-place: Mergesort, Radix, Proxmap
q) Primärkollision
r) Gleichverteilung der Schlüssel über den Wertebereich
s) O(1)
t) O(s)

Das war erst mal die Aufgabe 1... to be continued soon....

anno
Neuling
Neuling
Beiträge: 1
Registriert: 1. Nov 2007 21:14

Beitrag von anno »

Bei deinem Punkt q.) würde ich Schlüssenkollision vorschlagen zumindest laut Hashingkapitel Folie 14.

Benutzeravatar
\Hannes
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 18. Nov 2005 17:24

Beitrag von \Hannes »

Primärkollision stand in der Musterlösung bei der Klausureinsicht :)
Schwabbeldiwapp hier kommt die Grütze.

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag von Dutchie »

Meine Antwort auf die 2a.)

2a.):

Code: Alles auswählen

public class MyStack<T>  {

private Linkable<T> head;


public MyStack(){

head = null;
}

public boolean isEmpty() {

return( head == null);
}

public void push(T e){

Linkable<T> tmp = new Linkable<T>(e);

tmp.setNext(head);

head = tmp;
}

public T pop(){

Linkable<T> tmp = head;

head = head.getNext();

return tmp;
}
}

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag von Dutchie »

und jetzt die 2b:

Code: Alles auswählen

public class MyQueue<T>{

private Linkable<T> head;
private Linkable<T> tail;

public MyQueue(){

head= null;
tail = null;
}

pubic boolean isEmpty(){
return(head == null);
}

public void push(T e){

tail.setNext(new Linkable<T>(e));

tail= tail.getNext();

if(head==null){
head = tail;
}
}

public T pop (){

Linkable<T> tmp = head;
head = head.getNext();
return tmp;
}

}

ice
Erstie
Erstie
Beiträge: 13
Registriert: 22. Mär 2006 14:19

Beitrag von ice »

Aufgabe 3d)

Ein Quad-Tree-Knoten (QTK) benötigt 9 Byte (1 Farbbyte, 4*2 Zeiger Byte).

Im 2d-Array benötigt die gegebene Fläche konstant (2^n)*(2^n)*1 Byte. Es gibt also fürs 2d-Array keinen Best- bzw. Worst Case

Beim Quad-Tree ist der Bestcase eine einfarbige Fläche, schwarz oder weiß. Diese benötigt genau 9 Byte.

Das Verhältnis Quad/2dArray ist also 9/4^n Byte. Bei hinreichend großem n ist der Speicherbedarf im 2d-Array also exorbitant höher als beim Quad-Tree.


Worst-Case:
Der Quad-Tree ist so aufgebaut, daß für jedes einzelne Pixel bis auf die unterste Ebene des Baums unterteilt werden muß, bsp: Schachbrett.
Hier verbraucht allein die Unterste Ebene der Blätter im Baum schon 9-mal mehr Speicher als das Array.

Berechnung für den ganzen Baum:
Der Baum hat in der untersten Ebene 4^n QTKs. Um alle QTKs des ganzen Baums zu errechnen muß man also die Summe (i=0 -> i=n) (4^i) bilden.
Dies ist die geometrische Reihe und ergibt (1-4^(n+1))/(1-4). Umgeformt: (4^(n+1)-1)/(4-1). Ein QTK benötigt immer noch 9 Byte. Es ergibt sich also als Gesamtspeicherbedarf für den Quad: 9*(4^(n+1)-1)/3 = 3*(4^(n+1)-1)

Das Verhältnis zum 2d-Array ist also 3*(4^(n+1)-1) / 4^n
Dies kann man weiter umformen zu (12*4^n-3) / 4^n
Betrachtet man diesen Bruch nun für große n (mathematisch korrekt man bildet den limes) so kann man die "-3" vernachlässigen und es ergibt sich ein Verhältnis von Quad zu 2d-Array von 12 / 1
Ein Quad-Tree benötigt also im worstcase 12 mal mehr Speicherplatz als ein Array.



^^ obiges sollte auf jeden Fall noch mal jemand nachrechnen !!!
Zuletzt geändert von ice am 3. Nov 2007 13:23, insgesamt 1-mal geändert.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Na dann, hier ein Vorschlag für die 2c). Ich hab nicht ausprobiert, dass es wirklich korrekt ist, ich kann nur sagen, dass es kompiliert und dass es vom Prinzip in etwa stimmen sollte.

Code: Alles auswählen

public class MyPrioQueue 
{
	// Array für Heap
	private PrioElement[] heap;
	// Aktuelle Anzahl Elemente
	private int count;
		
	public MyPrioQueue(int n)
	{
		heap = new PrioElement[n];
	}
	
	public boolean isEmpty()
	{
		// die PrioQueue ist leer genau dann, wenn sie aktuell 
		// keine Elemente speichert
		return count == 0;
	}
	
	public void push(PrioElement e)
	{
		// lege das Element *hinter* das Ende des Heaps
		heap[count] = e;
		// tausche das eingefügte Element so lange mit dem Parent im Heap,
		// bis es an der richtigen Position steht
		moveUpwards();
		// Heap hat jetzt ein Element mehr
		++count;
	}
	
	public PrioElement pop()
	{
		// das vorderste Element hat maximale Priorität
		PrioElement result = heap[0];
		// da das Element aus dem Heap entfernt werden soll, 
		// haben wir ein Element weniger
		--count;
		// Zum Entfernen wird das letzte Element des Heaps nach oben verschoben
		heap[0] = heap[count];
		heap[count] = null;
		// dieses Element muss jetzt von der Spitze nach unten in 
		// den Heap einsinken
		moveDownwards();
		
		return result;
	}
	
	
	private void moveUpwards()
	{
		// diese Methode bringt ein neu eingefügtes Element am Ende des Heaps
		// nach oben bis zur richtigen Position, indem es so lange mit dem 
		// Parent tauscht, bis die Priorität des Parents größer oder gleich ist.
		int pos = count;
		while (pos > 0)
		{
			// Position des Parent im Heap (ACHTUNG: Zählen von 0)
			int parent = (pos-1)/2;
			if (heap[parent].getPriority() < heap[pos].getPriority())
			{
				// tausche mit Parent
				swap(parent, pos);
				pos = parent;
			}
			else
				break;  // Objekt ist richtig platziert
		}
	}
	
	
	private void moveDownwards()
	{
		// diese Methode tauscht das oberste Element so lange mit einem seiner
		// Kinder, bis beide Kinder kleiner/gleich sind.
		int pos = 0;
		while (pos < count)
		{
			// Positionen der Kinder (ACHTUNG: Zählen von 0)
			int childL = pos*2+1;
			int childR = pos*2+2;
			// prüfe, dass wenigstens 1 Kind noch innerhalb des Heaps liegt
			if (childL >= count)
				break;
			// bestimme das größere der beiden Kinder
			int maxChild = childL;
			if (childR < count && heap[childR].getPriority() > heap[childL].getPriority())
				maxChild = childR;
			// tausche Objekt mit maxChild, falls nötig
			if (heap[pos].getPriority() < heap[maxChild].getPriority())
			{
				swap(maxChild, pos);
				pos = maxChild;
			}
			else
				break;  // Objekt ist richtig platziert
		}
	}
	
	
	private void swap(int p1, int p2)
	{
		// vertauscht die Elemente an den gegebenen Positionen
		PrioElement tmp = heap[p1];
		heap[p1] = heap[p2];
		heap[p2] = tmp;
	}
}

ice
Erstie
Erstie
Beiträge: 13
Registriert: 22. Mär 2006 14:19

Beitrag von ice »

Aufgabe 3c)

Eingang auf (x;y) | 2d-Trie Codierung bzw. z-order:
(0,5; 3,5) | 000101
(3,5; 3,5) | 001111
(0,5; 5,5) | 010001
(2,5; 5,5) | 011001
(0,5; 7,5) | 010101
(3,5; 7,5) | 011111

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag von Dutchie »

kann jemand seine Lösung von der 5. Aufgabe hier reinstellen?
das wäre sehr hilfreich, weil ich da keine ahnung habe.

ice
Erstie
Erstie
Beiträge: 13
Registriert: 22. Mär 2006 14:19

Beitrag von ice »

nun ja, viel hab ich da nicht und ich bin mir auch überhaupt nicht sicher ob der quatsch richtig ist, daher unter vielen vorbehalten die ersten beiden Teilaufgaben

5a)
Modifizierung durch Datenstruktur B-Baum,
dabei sollten die Knoten inkl. Verweiskosten und Schlüsseln von der Größe her einer Seite (Speicherbereich) entsprechen.

5b)
p entspricht Größe B-Baum-Knoten
Dann ist p/s die Anzahl der maximal möglichen Einträge in einem Knoten (allerdings ohne Verweise)
Wieviel Platz die Verweise auf den nächst tieferen Knoten ausmachen sollen war nicht explizit gegeben. Ich nehme für die weitere Lösung nun an, daß ein Verweis genauso viel kostet wie ein Schlüssel.
Es passen dann p/(2s+1) Schlüssel in einen B-Baum-Knoten (maximal).

Ziel ist nun die Parameter eines B-Baums durch die gegebenen Variablen zu bestimmen.

... soviel erstmal, mache gleich bzw. morgen weiter, muß erst noch was nachrechnen!

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag von Dutchie »

hallo,

können die, die heute mdl Prüfung hatten, mal berichten was so dran kam und was ihr geantwortet habt. wäre sehr cool vor allem für die Leute, die morgen geprüft werden.

danke schon mal!

ice
Erstie
Erstie
Beiträge: 13
Registriert: 22. Mär 2006 14:19

Beitrag von ice »

bin bei der 5 leider nicht viel weiter gekommen.

noch ein paar überlegungen zur c):
SORTIEREN:
zum sortieren muß ich - angefangen bei der wurzel - pro einzufügendem Schlüssel einmal die Höhe h (entspricht log(n)) überwinden um einen Platz für den Schlüssel zu finden.
Bei einem Split muß ich zusätzlich den Median eins nach oben setzen, aus dem alten Blatt zwei Blätter machen und anfügen. Im worst case passiert mir das h-mal (log(n))-mal so daß die Gesamthöhe um eins heraufgesetzt werden muß.

Das alles muß ich für n Knoten machen

Als (grobe) Abschätzung kommt da also O(n*(log(n))^2) heraus

Werwolf
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 10. Sep 2004 10:25

Re: Lösung der Klausur GdI 2 (Herbst 2007)

Beitrag von Werwolf »

ice hat geschrieben: o) Uns wären hier lediglich verschieden lange Schlüssel eingefallen, die kann Radix aber sortieren wenn die fehlenden Stellen durch "0" ersetzt werden. -> hat hier jemand einen besseren Einfall??
Datenstrukturen, die man nur mittels eines eigen erstellten Vergleichers (Comperator) vergleichen kann.

Antworten

Zurück zu „Archiv“