Informatik 3/Gedächtnisprotokoll Klausur SS07 - Versionsgeschichte

Bmay: Formatierung korrigiert, Kategorisiert

2013-02-24T13:07:34Z

Formatierung korrigiert, Kategorisiert

← Nächstältere Version		Version vom 24. Februar 2013, 13:07 Uhr
Zeile 2:		Zeile 2:

	Kreuzen Sie jeweils wahr bzw. falsch an:		Kreuzen Sie jeweils wahr bzw. falsch an:
	* ..
	* Ein zusammenhängender, ungerichteter Graph mit \|V\| Knoten hat immer \|V\| * (\|V\| - 1) / 2 Kanten.		* Ein zusammenhängender, ungerichteter Graph mit \|V\| Knoten hat immer \|V\| * (\|V\| - 1) / 2 Kanten.
	* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.		* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
Zeile 8:		Zeile 7:
	* Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.		* Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
	* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.		* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
	~~<br>~~

	Worst Case Aufwand von		Worst Case Aufwand von:
	* Wert in eine Hashliste mit Separate Chaining einfuegen		* Wert in eine Hashliste mit Separate Chaining einfuegen
	* Einen Wert in einer Skipliste finden		* Einen Wert in einer Skipliste finden
Zeile 21:		Zeile 19:

	Hashtabelle der Größe 4.		Hashtabelle der Größe 4.
	*Hashfunktion: h(k) = k mod 4		* Hashfunktion: h(k) = k mod 4
	*Kollisonsauflösung"double hashing" a(k) = k+2		* Kollisonsauflösung: z.B. "double hashing" a(k) = k+2
			* Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
	Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.

	(A,5) (B,11) (C,9) (D,14)		(A,5) (B,11) (C,9) (D,14)
Zeile 33:		Zeile 30:
	C -> 1,0		C -> 1,0
	D -> 2		D -> 2


	Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.		Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.

	== Aufgabe 3: Suchbäume (11 Punkte) ==		== Aufgabe 3: Suchbäume (11 Punkte) ==

	'''AVL-Bäume'''		'''AVL-Bäume'''
	*Einfügen von 3 in den folgenden AVL-Baum:		*Einfügen von 3 in den folgenden AVL-Baum:
Zeile 44:		Zeile 41:
	*Löschen von 10 aus dem folgenden AVL-Baum:		*Löschen von 10 aus dem folgenden AVL-Baum:
	[[Bild:Info3-ss2007-3-avltree.png]]		[[Bild:Info3-ss2007-3-avltree.png]]


	'''Rot/Schwarz-Bäume'''		'''Rot/Schwarz-Bäume'''
	*Einfügen von '9' in den folgenden Rot/Schwarz-Baum:		*Einfügen von '9' in den folgenden Rot/Schwarz-Baum:
	[[Bild:Info3-ss2007-3-rbtree.png]]		[[Bild:Info3-ss2007-3-rbtree.png]]


	*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes: int getBlackHeight(Node root)		*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes: int getBlackHeight(Node root)
Zeile 57:		Zeile 52:
	*** boolean isBlack(Node node);		*** boolean isBlack(Node node);
	*** class Node{ int color; Node left; Node right; }		*** class Node{ int color; Node left; Node right; }
	~~<br>~~

	'''B-Baum'''		'''B-Baum'''
	* Element in B-Baum einfügen.		* Element in B-Baum einfügen.
	[[Bild:Info3-ss2007-3-btree.png]]		[[Bild:Info3-ss2007-3-btree.png]]
	~~<br>~~

	== Aufgabe 4: Graphen (10 Punkte) ==		== Aufgabe 4: Graphen (10 Punkte) ==

	a) Baue eine Adjazenzmatrix zu folgendem Graphen:		a) Baue eine Adjazenzmatrix zu folgendem Graphen:

Zeile 84:		Zeile 78:

	== Aufgabe 5: Übungsorganisation (4 Punkte) ==		== Aufgabe 5: Übungsorganisation (4 Punkte) ==

	Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.		Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.

Zeile 105:		Zeile 100:

	Algorithmus:		Algorithmus:



	Ablauf:		Ablauf:
Zeile 125:		Zeile 118:

	== Aufgabe 7: Geld wechseln (6 Punkte) ==		== Aufgabe 7: Geld wechseln (6 Punkte) ==

	Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.		Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.

Zeile 138:		Zeile 132:

	[[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007]]		[[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007]]

			[[Kategorie: Prüfungsprotokolle]]
			[[Kategorie: Informatik]]
			[[Kategorie: StuPO90]]

85.178.58.114: /* Aufgabe 7: Geld wechseln (6 Punkte) */

2008-01-28T19:13:05Z

Aufgabe 7: Geld wechseln (6 Punkte)

← Nächstältere Version		Version vom 28. Januar 2008, 19:13 Uhr
Zeile 132:		Zeile 132:

	c) Geben Sie ein Greedy-Verfahren zur Lösung des Optimierungsproblems an (als Pseudocode oder verbal).		c) Geben Sie ein Greedy-Verfahren zur Lösung des Optimierungsproblems an (als Pseudocode oder verbal).

			Diese Aufgabe war auch als Hausaufgabe im WS 06/07 im 7. Übungsblatt Aufgabe 7.6 als 'Theorie' zu lösen

	== Siehe auch ==		== Siehe auch ==

	[[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007]]		[[Informatik 4 (StuPO90)/Gedächtnisprotokoll Klausur SoSe 2007]]

TomyLobo: /* Aufgabe 1: Multiple Choice (7 Punkte) */

2007-08-02T10:16:29Z

Aufgabe 1: Multiple Choice (7 Punkte)

← Nächstältere Version		Version vom 2. August 2007, 10:16 Uhr
Zeile 11:		Zeile 11:

	Worst Case Aufwand von		Worst Case Aufwand von
	* ~~Hash~~ einfuegen		* Wert in eine Hashliste mit Separate Chaining einfuegen
	* Einen Wert in einer Skipliste finden		* Einen Wert in einer Skipliste finden
	* Rotieren in einem AVL-Baum		* Rotieren in einem AVL-Baum

TomyLobo: /* Aufgabe 1: Multiple Choice (7 Punkte) */

2007-08-02T09:49:29Z

Aufgabe 1: Multiple Choice (7 Punkte)

← Nächstältere Version		Version vom 2. August 2007, 09:49 Uhr
Zeile 3:		Zeile 3:
	Kreuzen Sie jeweils wahr bzw. falsch an:		Kreuzen Sie jeweils wahr bzw. falsch an:
	* ..		* ..
	* Ein zusammenhängender, ungerichteter Graph mit \|V\| Knoten hat immer \|V\|*(\|V\|-1)/2 Kanten.		* Ein zusammenhängender, ungerichteter Graph mit \|V\| Knoten hat immer \|V\| * (\|V\| - 1) / 2 Kanten.
	* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.		* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
	* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.		* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.

77.132.128.7: /* Aufgabe 1: Multiple Choice (7 Punkte) */

2007-08-02T08:56:40Z

Aufgabe 1: Multiple Choice (7 Punkte)

← Nächstältere Version		Version vom 2. August 2007, 08:56 Uhr
Zeile 3:		Zeile 3:
	Kreuzen Sie jeweils wahr bzw. falsch an:		Kreuzen Sie jeweils wahr bzw. falsch an:
	* ..		* ..
			* Ein zusammenhängender, ungerichteter Graph mit \|V\| Knoten hat immer \|V\|*(\|V\|-1)/2 Kanten.
	* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.		* Traversierung mit Breitensuche erzeugt einen aufspannenden Baum.
	* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.		* Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.

TomyLobo: /* Aufgabe 2: HashTables (7 Punkte) */

2007-07-31T11:15:56Z

Aufgabe 2: HashTables (7 Punkte)

← Nächstältere Version		Version vom 31. Juli 2007, 11:15 Uhr
Zeile 27:		Zeile 27:
	(A,5) (B,11) (C,9) (D,14)		(A,5) (B,11) (C,9) (D,14)

			Lösung:
	A -> 1		A -> 1

	B -> 3		B -> 3
			C -> 1,0
	C -> 1, ~~3, 1 , 3 .. (kann nicht eingefügt werden) - Unsinn, bitte korrigieren [[Benutzer:TomyLobo\|TomyLobo]]~~

	D -> 2		D -> 2

	~~0 blieb leer.~~

	~~Andere Lösung:~~
	~~A -> 1~~
	~~B -> 3~~
	~~C -> 1,0~~
	~~D -> 2~~
	~~<br>~~
	Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.		Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
	~~<br>~~

	== Aufgabe 3: Suchbäume (11 Punkte) ==		== Aufgabe 3: Suchbäume (11 Punkte) ==

Sodoku: /* Aufgabe 1: Multiple Choice (7 Punkte) */

2007-07-30T18:34:01Z

Aufgabe 1: Multiple Choice (7 Punkte)

← Nächstältere Version		Version vom 30. Juli 2007, 18:34 Uhr
Zeile 8:		Zeile 8:
	* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.		* Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
	<br>		<br>

			Worst Case Aufwand von
			* Hash einfuegen
			* Einen Wert in einer Skipliste finden
			* Rotieren in einem AVL-Baum
			* Tiefensuch
			* Kruskal
			* Edmonds Karp Alg

	== Aufgabe 2: HashTables (7 Punkte) ==		== Aufgabe 2: HashTables (7 Punkte) ==

TomyLobo: /* Aufgabe 3: Suchbäume (11 Punkte) */

2007-07-30T17:46:30Z

Aufgabe 3: Suchbäume (11 Punkte)

← Nächstältere Version		Version vom 30. Juli 2007, 17:46 Uhr
Zeile 40:		Zeile 40:
	== Aufgabe 3: Suchbäume (11 Punkte) ==		== Aufgabe 3: Suchbäume (11 Punkte) ==
	'''AVL-Bäume'''		'''AVL-Bäume'''
	*Einfügen in AVL-Baum		*Einfügen von 3 in den folgenden AVL-Baum:
	*Einfügen in AVL-~~Baum~~		[[Bild:Info3-ss2007-3-avltree.png]]
	*Löschen aus AVL-Baum
	~~<br>~~		*Löschen von 10 aus dem folgenden AVL-Baum:
			[[Bild:Info3-ss2007-3-avltree.png]]


	'''Rot/Schwarz-Bäume'''		'''Rot/Schwarz-Bäume'''
	*Einfügen in RS-Baum		*Einfügen von '9' in den folgenden Rot/Schwarz-Baum:
			[[Bild:Info3-ss2007-3-rbtree.png]]


	*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes: int getBlackHeight(Node root)		*Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes: int getBlackHeight(Node root)
	** Rot-Schwarz-Baum als gültig vorausgesetzt.		** Rot-Schwarz-Baum als gültig vorausgesetzt.

TomyLobo: /* Aufgabe 2: HashTables (7 Punkte) */

2007-07-30T13:53:40Z

Aufgabe 2: HashTables (7 Punkte)

← Nächstältere Version		Version vom 30. Juli 2007, 13:53 Uhr
Zeile 14:		Zeile 14:
	*Hashfunktion: h(k) = k mod 4		*Hashfunktion: h(k) = k mod 4
	*Kollisonsauflösung"double hashing" a(k) = k+2		*Kollisonsauflösung"double hashing" a(k) = k+2
	~~<br>~~
	Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.		Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.

	(A,5) (B,11) (C,9) (D,14)		(A,5) (B,11) (C,9) (D,14)

	A -> 1		A -> 1

	B -> 3		B -> 3
	C -> 1, 3, 1 , 3 .. (kann nicht eingefügt werden)
			C -> 1, 3, 1 , 3 .. (kann nicht eingefügt werden) - Unsinn, bitte korrigieren [[Benutzer:TomyLobo\|TomyLobo]]

	D -> 2		D -> 2

	0 blieb leer.		0 blieb leer.
	~~<br>~~
	Andere Lösung:		Andere Lösung:
	A -> 1		A -> 1

TomyLobo: Punkte bei Klausureinsicht mitgeloggt, die stimmen jetzt so :)

2007-07-30T13:51:25Z

Punkte bei Klausureinsicht mitgeloggt, die stimmen jetzt so :)

← Nächstältere Version		Version vom 30. Juli 2007, 13:51 Uhr
Zeile 1:		Zeile 1:
	== Aufgabe 1: Multiple Choice (~~10(?)~~ Punkte) ==		== Aufgabe 1: Multiple Choice (7 Punkte) ==

	Kreuzen Sie jeweils wahr bzw. falsch an:		Kreuzen Sie jeweils wahr bzw. falsch an:
Zeile 9:		Zeile 9:
	<br>		<br>

	== Aufgabe 2: HashTables (~~>=5~~ Punkte) ==		== Aufgabe 2: HashTables (7 Punkte) ==

	Hashtabelle der Größe 4.		Hashtabelle der Größe 4.
Zeile 32:		Zeile 32:
	<br>		<br>

	== Aufgabe 3: Suchbäume (~~>=10~~ Punkte) ==		== Aufgabe 3: Suchbäume (11 Punkte) ==
	'''AVL-Bäume'''		'''AVL-Bäume'''
	*Einfügen in AVL-Baum		*Einfügen in AVL-Baum
Zeile 54:		Zeile 54:
	<br>		<br>

	== Aufgabe 4: Graphen (~~>=9~~ Punkte) ==		== Aufgabe 4: Graphen (10 Punkte) ==
	a) Baue eine Adjazenzmatrix zu folgendem Graphen:		a) Baue eine Adjazenzmatrix zu folgendem Graphen:

Zeile 73:		Zeile 73:
	[[Bild:Info3-ss2007-4e.png]]		[[Bild:Info3-ss2007-4e.png]]

	== Aufgabe 5: Übungsorganisation (~~>=8~~ Punkte) ==		== Aufgabe 5: Übungsorganisation (4 Punkte) ==
	Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.		Es herrscht grosser Andrang bei der Sprechstunde. Keiner der wartenden Studierenden erinnert sich an die genaue Ankunftsreihenfolge. Einige erinnern sich jedoch noch an die Leute die bereits warteten. Es soll eine ungefähre Ankunftsreihenfolge bestimmt werden.

Zeile 100:		Zeile 100:
	Ablauf:		Ablauf:

	== Aufgabe 6: Dynamisches Programmieren (=4 Punkte) ==		== Aufgabe 6: Dynamisches Programmieren (5 Punkte) ==

	[[Bild:Info3-ss2007-6.png]]		[[Bild:Info3-ss2007-6.png]]
Zeile 114:		Zeile 114:
	O( .... )		O( .... )

	== Aufgabe 7: Geld wechseln (=6 Punkte) ==		== Aufgabe 7: Geld wechseln (6 Punkte) ==
	Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.		Gegeben ist ein Betrag, welcher durch möglichst wenige Geldstücke der Grössen { 200, 100, 50, 20, 10, 5, 2, 1 } dargestellt werden werden soll.