Gedächtnisprotokoll AD08-1 - Versionsgeschichte

1steenfa: Bot: Kosmetische Änderungen

2012-06-08T16:05:04Z

Bot: Kosmetische Änderungen

← Nächstältere Version		Version vom 8. Juni 2012, 16:05 Uhr
Zeile 12:		Zeile 12:
	Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)		Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)

	Finden Sie die geschlossene Form für folgende Rekurenzgleichung: <math>T(\sqrt{(N)})+1</math> (oder so ähnlich)<br>		Finden Sie die geschlossene Form für folgende Rekurenzgleichung: <math>T(\sqrt{(N)})+1</math> (oder so ähnlich)<br />
	Sie können annehmen dass <math>n \in 2^{2^i}</math> mit <math>i \in \mathbb{N}</math> ist.		Sie können annehmen dass <math>n \in 2^{2^i}</math> mit <math>i \in \mathbb{N}</math> ist.

2008-07-15T17:49:03Z

sort

← Nächstältere Version		Version vom 15. Juli 2008, 17:49 Uhr
Zeile 70:		Zeile 70:
	* Laufzeit?		* Laufzeit?

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

2008-02-21T11:54:26Z

Hashing: +math-tag

← Nächstältere Version		Version vom 21. Februar 2008, 11:54 Uhr
Zeile 31:		Zeile 31:

	== Hashing ==		== Hashing ==
	Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an.		Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion <math>h(k,i) = h_1(k) + i * h_2(k)</math> mit <math>h_1(k) = k \mod m</math> und <math>k_2 = 1 + k \mod (m-1)</math>. Geben Sie die Sondierungsfolge an.

	== Bäume ==		== Bäume ==

2008-02-21T11:53:16Z

asymptotische Laufzeiten: +math-tag

← Nächstältere Version		Version vom 21. Februar 2008, 11:53 Uhr
Zeile 12:		Zeile 12:
	Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)		Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)

	Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)<br>		Finden Sie die geschlossene Form für folgende Rekurenzgleichung: <math>T(\sqrt{(N)})+1</math> (oder so ähnlich)<br>
	Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.		Sie können annehmen dass <math>n \in 2^{2^i}</math> mit <math>i \in \mathbb{N}</math> ist.

	Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)		Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)

	Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).		Zeigen Sie anhand der Definition des O-Kalküls: <math>f(n) = O(g(n))</math>. (Natürlich für konkrete f und g).

	== Suchen ==		== Suchen ==

2008-02-18T19:00:57Z

Bäume

← Nächstältere Version		Version vom 18. Februar 2008, 19:00 Uhr
Zeile 39:		Zeile 39:

	Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n))		Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n))

			Gegeben: Ein Heap. Entfernen Sie das grösste Element (Heap-Extract-Max) und geben Sie den Heap nach der Operation an.

	== Graphen ==		== Graphen ==

2008-02-18T18:58:33Z

Graphen

@@ Zeile 47: / Zeile 47: @@
 * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?
 * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.
 == Dynamische Programmierung ==

2008-02-18T18:54:08Z

Suchen

← Nächstältere Version		Version vom 18. Februar 2008, 18:54 Uhr
Zeile 20:		Zeile 20:

	== Suchen ==		== Suchen ==
	Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen		Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit dem bekannten Sortieralgorithmen Insertion-, Selection-, Bubble- und Quicksort.

	Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?		Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?
Zeile 26:		Zeile 26:
	Quicksort		Quicksort

	~~Bubble-Sort an Zusatzbedingung anpassen~~: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. ~~Quicksort war~~ gegeben.		Annahme:Jedes Element steht maximal k Plätze von seinem richtigen entfernt
			* Zeigen Sie, dass eine Vertauschung von <nowiki>A[j] und A[j+1] mit A[j] > A[j+1]</nowiki> diese Eigenschaft nicht zerstört.
			* Passen Sie Bubble-Sort an die Zusatzbedingung an. (Bubble-Sort gegeben)

	== Hashing ==		== Hashing ==

2008-02-18T18:50:30Z

Hashing

← Nächstältere Version		Version vom 18. Februar 2008, 18:50 Uhr
Zeile 27:		Zeile 27:

	Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.		Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.

			== Hashing ==
			Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an.

	== Bäume ==		== Bäume ==

2008-02-18T18:47:14Z

Bäume

← Nächstältere Version		Version vom 18. Februar 2008, 18:47 Uhr
Zeile 29:		Zeile 29:

	== Bäume ==		== Bäume ==
			Gegeben: 5 Bäume. Entscheiden Sie jeweils ob ein korrekter Rot-Schwarz-Baum vorliegt. Begründen Sie ihre Antwort.

			Geben Sie einen Algortithmus an, der ein Array mit n Zahlen in einem unbalancierten Binärbaum sortiert. Sie können dabei die aus der Vorlesung bekannten Operationen auf Binärbäumen verwenden. Geben Sie die asymptotischen Best- und Worst-Case-Laufzeiten an.

	Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n))		Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n))

2008-02-18T18:44:08Z

asymptotische Laufzeit

← Nächstältere Version		Version vom 18. Februar 2008, 18:44 Uhr
Zeile 9:		Zeile 9:
	* P/NP		* P/NP

	== ~~O-Kalkül~~ ==		== asymptotische Laufzeiten ==
			Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)

			Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)<br>
			Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.

			Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)

	Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).		Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).