Gedächtnisprotokoll AD09-1 - Versionsgeschichte

1steenfa: Bot: Kosmetische Änderungen

2012-06-08T16:05:14Z

Bot: Kosmetische Änderungen

← Nächstältere Version		Version vom 8. Juni 2012, 16:05 Uhr
Zeile 8:		Zeile 8:
	* <math>2^{n+3} \in O( 2^{n-3} )</math>		* <math>2^{n+3} \in O( 2^{n-3} )</math>
	* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>		* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>
	* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten?		* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten?
	* Gilt <math>o(n^2) \cap O(n^2) = \emptyset</math> ?		* Gilt <math>o(n^2) \cap O(n^2) = \emptyset</math> ?
	* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>?		* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>?
Zeile 75:		Zeile 75:
	[[Bild:avl.png]]		[[Bild:avl.png]]

	[[Kategorie: Gedaechtnisprotokoll\|AD]]		[[Kategorie:Gedaechtnisprotokoll\|AD]]

2009-02-19T16:02:55Z

Kurskal

← Nächstältere Version		Version vom 19. Februar 2009, 16:02 Uhr
Zeile 53:		Zeile 53:
	''Gegeben ist ein Graph''		''Gegeben ist ein Graph''
	* Bestimmen sie den minimalen Spannbaum und tragen sie in die Tabelle ein, wann sie welche Kante zum Spannbaum hinzugefügt haben, und welche ausgelassen wurden.		* Bestimmen sie den minimalen Spannbaum und tragen sie in die Tabelle ein, wann sie welche Kante zum Spannbaum hinzugefügt haben, und welche ausgelassen wurden.
			* Mit welcher Datenstruktur würden sie Kruskal implementieren, ohne groß Laufzeit zu verschenken?

	=== Aufgabe 8 ===		=== Aufgabe 8 ===

2009-02-19T16:01:30Z

Suchbäume

← Nächstältere Version		Version vom 19. Februar 2009, 16:01 Uhr
Zeile 26:		Zeile 26:

	=== Suchbäume ===		=== Suchbäume ===
			* Wenn sie in einem Suchbaum alle Elemente aufsteigend ausgeben wollen, in welcher Reihenfolge müssen sie dann suchen? Ankreuzmöglichkeiten: preorder inorder postorder
			* Anzahl innerer Knoten eines Binärbaums der Höhe h

			a) wenn der Baum minimal
			b) wenn der Baum maximal
			ist. Jeweils eine geschlossene Form(d.h. ohne Summenzeichen) angeben und begründen!
	* Kann ein Rot-Schwarz-Baum ein AVL-Baum sein?		* Kann ein Rot-Schwarz-Baum ein AVL-Baum sein?
	* Zeichnen sie alle binären Suchbäume der Menge {1,2,3}.		* Zeichnen sie alle binären Suchbäume der Menge {1,2,3}.
	* Ist jeder Suchbaum eine spezielle Form des Heaps?		* Ist jeder Suchbaum eine spezielle Form des Heaps?


	=== Aufgabe 6 ===		=== Aufgabe 6 ===

2009-02-19T15:58:59Z

Aufagbe 2

← Nächstältere Version		Version vom 19. Februar 2009, 15:58 Uhr
Zeile 16:		Zeile 16:
	* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.		* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.
	* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?		* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?
	* Gilt <math>7^{\log_2(n)} \in \Theta(n^3)</math>

	=== NP ===		=== NP ===

2009-02-19T15:58:22Z

O-Notation

← Nächstältere Version		Version vom 19. Februar 2009, 15:58 Uhr
Zeile 8:		Zeile 8:
	* <math>2^{n+3} \in O( 2^{n-3} )</math>		* <math>2^{n+3} \in O( 2^{n-3} )</math>
	* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>		* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>
	* ~~schlechteste Laufzeit von QuickSort ist~~ <math>n\~~cdot log~~(n)</math>		* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten?
	* ~~Wenn f~~ <math>\in O(g)</math> ~~gilt, dann kann~~ <math>g \in \~~Omega~~(f)</math> ~~nicht gelten~~		* Gilt <math>o(n^2) \cap O(n^2) = \emptyset</math> ?
	* <math>~~o(f)~~ \~~cap O~~(f) ~~= \emptyset~~</math>		* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>?
			* Ist folgende Behauptung richtig? Schlechteste Laufzeit von QuickSort ist <math>n\cdot log(n)</math>

	=== Aufagbe 2 ===		=== Aufagbe 2 ===

2009-02-13T10:00:41Z

O-Notation: Teilaufgabe mit QuickSort hinzufügen

← Nächstältere Version		Version vom 13. Februar 2009, 10:00 Uhr
Zeile 8:		Zeile 8:
	* <math>2^{n+3} \in O( 2^{n-3} )</math>		* <math>2^{n+3} \in O( 2^{n-3} )</math>
	* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>		* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>
			* schlechteste Laufzeit von QuickSort ist <math>n\cdot log(n)</math>
	* Wenn f <math>\in O(g)</math> gilt, dann kann <math>g \in \Omega(f)</math> nicht gelten		* Wenn f <math>\in O(g)</math> gilt, dann kann <math>g \in \Omega(f)</math> nicht gelten
	* <math>o(f) \cap O(f) = \emptyset</math>		* <math>o(f) \cap O(f) = \emptyset</math>


	=== Aufagbe 2 ===		=== Aufagbe 2 ===

2009-02-12T18:57:40Z

← Nächstältere Version		Version vom 12. Februar 2009, 18:57 Uhr
Zeile 68:		Zeile 68:
	* Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann.		* Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann.
	* ''Gegeben ist ein verletzer AVL-Baum''. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren.		* ''Gegeben ist ein verletzer AVL-Baum''. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren.
			[[Bild:avl.png]]

	[[Kategorie: Gedaechtnisprotokoll\|AD]]		[[Kategorie: Gedaechtnisprotokoll\|AD]]

2009-02-12T18:44:21Z

← Nächstältere Version		Version vom 12. Februar 2009, 18:44 Uhr
Zeile 1:		Zeile 1:
	Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten).		Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten) und es gab 100Punkte.
			Die Klausur war eine gute Mischung aus Multiple-Choice-Fragen und Anwendungsaufgaben. Wenn man das Tutorium bei Frank Heitmann besucht hatte, war es gut möglich die Klausur zu bestehen.

	Gliederung muss nicht unbedingt korrekt sein.		Gliederung muss nicht unbedingt korrekt sein.

2009-02-12T18:40:22Z

Rekurrenzgleichung

← Nächstältere Version		Version vom 12. Februar 2009, 18:40 Uhr
Zeile 22:		Zeile 22:

	=== Rekurrenzgleichung ===		=== Rekurrenzgleichung ===
	* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. ~~Finden~~ sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.		* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. Trages Sie die ersten 5 Werte in eine Tabelle ein, finden sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.


	=== Suchbäume ===		=== Suchbäume ===

2009-02-12T15:16:04Z

Aufagbe 2: Formel korrigiert (n in Potenz)

← Nächstältere Version		Version vom 12. Februar 2009, 15:16 Uhr
Zeile 14:		Zeile 14:
	* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.		* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.
	* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?		* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?
	* Gilt <math>n^{\log_2(7)} \in \Theta(n^3)</math>		* Gilt <math>7^{\log_2(n)} \in \Theta(n^3)</math>


	=== NP ===		=== NP ===