Gedächtnisprotokoll AD11-1 - Versionsgeschichte

92.76.11.94: /* Aufgabe 5 */

2011-02-18T13:27:44Z

Aufgabe 5

← Nächstältere Version		Version vom 18. Februar 2011, 13:27 Uhr
Zeile 56:		Zeile 56:

	d) Mit welchem der folgenden Algorithmen kann man negative Zyklen in einem Graphen finden/erkennen?		d) Mit welchem der folgenden Algorithmen kann man negative Zyklen in einem Graphen finden/erkennen?
	TopoSort, Bellman-Ford, Dijkstra, ~~BFS~~ oder Edmond-Karps? (2P)		BFS, DFS, TopoSort, Bellman-Ford, Dijkstra, oder Edmond-Karps? (2P)

	e) Was sind die Unterschiede und Gemeinsamkeiten zwischen den Algorithmen von Dijkstra, Bellman-Ford und Floyd-Warshall? (6P)		e) Was sind die Unterschiede und Gemeinsamkeiten zwischen den Algorithmen von Dijkstra, Bellman-Ford und Floyd-Warshall? (6P)

92.76.11.43: /* Aufgabe 7 */

2011-02-15T18:57:57Z

Aufgabe 7

← Nächstältere Version		Version vom 15. Februar 2011, 18:57 Uhr
Zeile 70:		Zeile 70:

	== Aufgabe 7 ==		== Aufgabe 7 ==
	~~Gegeben war ein Flussnetzwerk mit einem Fluss~~.		...?

	~~a) Zeichnen Sie das Restnetzwerk~~.

	~~b) Fügen Sie einen Pfad hinzu und zeichnen Sie das nun neue Flussnetzwerk. (es gab nur einen Pfad im Restnetzwerk)~~

	~~Zu beiden Aufgaben waren die Knoten schon gegeben, man musste nur die Kanten sowie den Fluss / die Kapazitäten einzeichnen~~.

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

92.76.11.43: /* Aufgabe 2 */

2011-02-15T18:53:26Z

Aufgabe 2

← Nächstältere Version		Version vom 15. Februar 2011, 18:53 Uhr
Zeile 27:		Zeile 27:
	\end{matrix}\right.</math>		\end{matrix}\right.</math>

	a) Geben Sie die Werte von T(n) an für n = 1,2,3,4		a) Geben Sie die Werte von T(n) an für n = 0, 1, 2, 3, 4

	b) Bringen Sie die Gleichung durch die Substitutionsmethode in eine Darstellung ohne Summenzeichen (geometrische Reihe war im Anhang angegeben)		b) Bringen Sie die Gleichung durch die Substitutionsmethode in eine Darstellung ohne Summenzeichen (geometrische Reihe war im Anhang angegeben, Induktionsbeweis war nicht zu führen)

	c) Hätte man auch das Master-Theorem anwenden können?		c) Hätte man auch das Master-Theorem anwenden können?

92.76.11.43: /* Aufgabe 6 */

2011-02-15T18:52:12Z

Aufgabe 6

← Nächstältere Version		Version vom 15. Februar 2011, 18:52 Uhr
Zeile 63:		Zeile 63:
	a) Wann ist ein Algorithmus stabil? (1P)		a) Wann ist ein Algorithmus stabil? (1P)

	b) Geben Sie die Worst-Case-Laufzeiten an für Quicksort, Bubblesort, Mergesort und Heapsort (6P).		b) Geben Sie die Worst-Case-Laufzeiten bei bester Implementierung an für Quicksort, Bubblesort, Mergesort und Heapsort (6P).

	c) Was ist der Unterschied zwischen einem Stack und einer Queue? (2P)		c) Was ist der Unterschied zwischen einem Stack und einer Queue? (2P)

	d) Kommentieren Sie folgende Aussage: "Algorithmen auf Bäumen ~~sind viel~~ schneller als auf Arrays." (2P)		d) Kommentieren Sie folgende Aussage: "Algorithmen sind auf Bäumen oft schneller als auf Arrays." (2P)

	== Aufgabe 7 ==		== Aufgabe 7 ==

92.76.11.43: /* Aufgabe 7 */

2011-02-15T18:50:34Z

Aufgabe 7

← Nächstältere Version		Version vom 15. Februar 2011, 18:50 Uhr
Zeile 71:		Zeile 71:
	== Aufgabe 7 ==		== Aufgabe 7 ==
	Gegeben war ein Flussnetzwerk mit einem Fluss.		Gegeben war ein Flussnetzwerk mit einem Fluss.

	a) Zeichnen Sie das Restnetzwerk.		a) Zeichnen Sie das Restnetzwerk.

	b) Fügen Sie einen Pfad hinzu und zeichnen Sie das nun neue Flussnetzwerk. (es gab nur einen Pfad im Restnetzwerk)		b) Fügen Sie einen Pfad hinzu und zeichnen Sie das nun neue Flussnetzwerk. (es gab nur einen Pfad im Restnetzwerk)

	Zu beiden Aufgaben waren die Knoten schon gegeben, man musste nur die Kanten sowie den Fluss / die Kapazitäten einzeichnen.		Zu beiden Aufgaben waren die Knoten schon gegeben, man musste nur die Kanten sowie den Fluss / die Kapazitäten einzeichnen.

92.76.11.43: /* Aufgabe 7 */

2011-02-15T18:50:01Z

Aufgabe 7

← Nächstältere Version		Version vom 15. Februar 2011, 18:50 Uhr
Zeile 70:		Zeile 70:

	== Aufgabe 7 ==		== Aufgabe 7 ==
	...?		Gegeben war ein Flussnetzwerk mit einem Fluss.
			a) Zeichnen Sie das Restnetzwerk.
			b) Fügen Sie einen Pfad hinzu und zeichnen Sie das nun neue Flussnetzwerk. (es gab nur einen Pfad im Restnetzwerk)
			Zu beiden Aufgaben waren die Knoten schon gegeben, man musste nur die Kanten sowie den Fluss / die Kapazitäten einzeichnen.

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

92.76.11.43: /* Aufgabe 9 */

2011-02-15T18:47:08Z

Aufgabe 9

← Nächstältere Version		Version vom 15. Februar 2011, 18:47 Uhr
Zeile 94:		Zeile 94:
	1. Hamiltonkreis-Problem HC: Eingabe ungerichteter Graph. Gibt es einen Hamiltonkreis?		1. Hamiltonkreis-Problem HC: Eingabe ungerichteter Graph. Gibt es einen Hamiltonkreis?

	2. "Kreis"-Problem Gk: Eingabe ungerichteter Graph mit gewichteten Kanten und einem <math>k \in N</math>. Gibt es einen Kreis, dessen Kantengewicht-Summe über k liegt?		2. "Kreis"-Problem Gk: Eingabe ungerichteter Graph mit gewichteten Kanten und einem <math>k \in N</math>. Gibt es einen einfachen Kreis, dessen Kantengewicht-Summe über k liegt?

	Das "Kreis"-Problem sei in NP. Zum Nachweis der NP-vollständigkeit reduzieren Sie HC auf Gk in Polynomialzeit.		Das "Kreis"-Problem sei in NP. Zum Nachweis der NP-vollständigkeit reduzieren Sie HC auf Gk in Polynomialzeit.

	[[Kategorie:Gedaechtnisprotokoll\|AD11-1]]		[[Kategorie:Gedaechtnisprotokoll\|AD11-1]]

Tee: Die Seite wurde neu angelegt: Klausur zu Algorithmen & Datenstrukturen, WS 10/11, 1. Termin, Dienstag, 15.02.2011

 Es gab insgesamt 2 Varianten der Klausur, 100 Punkte, 9 Aufgaben und 120 Minut...

2011-02-15T16:45:38Z

Die Seite wurde neu angelegt: Klausur zu Algorithmen & Datenstrukturen, WS 10/11, 1. Termin, Dienstag, 15.02.2011 <pre> Es gab insgesamt 2 Varianten der Klausur, 100 Punkte, 9 Aufgaben und 120 Minut...

Neue Seite

Klausur zu Algorithmen & Datenstrukturen, WS 10/11, 1. Termin, Dienstag, 15.02.2011
<pre>
Es gab insgesamt 2 Varianten der Klausur, 100 Punkte, 9 Aufgaben und 120 Minuten Zeit.
Kann gut sein, dass die Reihenfolge der Aufgaben etwas anders war. Die Punkte sind auch eher eine Abschätzung.
</pre>

== Aufgabe 1 ==
Bei folgenden Fragen ist jeweils Ja/Nein anzukreuzen (1P) und zu begründen (2-3P).

a) <math>f(n) = \left\{\begin{matrix} n^{4} + 2^{7} \;\;mit\; n < 3^{10} \\
n^{3} + 2^{8} \;\;mit\; n \geq 3^{10}
\end{matrix}\right .</math>

Ist <math>f(n) \in O(n^3)</math>?

b) Gilt <math>g \in \Theta(f) </math> genau dann, wenn <math>g \in o(f) </math> und <math>g \in \omega(f) </math> gilt?

c) Ist <math>o(f) \subseteq O(f) ?</math>

d) Ist <math>ln(n) \in O(\sqrt{n}) ? </math>
== Aufgabe 2 ==
Gegeben folgende Rekkurenzgleichung:

<math>T(n) = \left\{\begin{matrix} 0 \;\;\;\;\;\; n = 0 \\
3T(n-1) + 2 \;\;\;\;\;\; n > 0
\end{matrix}\right.</math>

a) Geben Sie die Werte von T(n) an für n = 1,2,3,4

b) Bringen Sie die Gleichung durch die Substitutionsmethode in eine Darstellung ohne Summenzeichen (geometrische Reihe war im Anhang angegeben)

c) Hätte man auch das Master-Theorem anwenden können?

== Aufgabe 3 ==

Gegeben waren 2 Heaps (A und B) in graphischer Darstellung.

a) Geben Sie A in Array-Darstellung an.

b) Führen Sie die Operation ExtractMax an A aus und zeichnen Sie das Resultat.

c) Führen Sie an B die Operation IncreaseKey aus [es war ein Blatt, dessen Wert erhöht wurde] und zeichnen Sie das Resultat.

== Aufgabe 4 ==
a) Suchbaum gegeben. Fügen Sie die 19 ein [war ein Blatt] und löschen Sie die 25 [hatte 2 Kinder].

b) Warum braucht man Rot-Schwarz-Bäume?

== Aufgabe 5 ==
a) Wenden Sie Kruskals Algorithmus an und bestimmen sie einen MST (ähnlich zur Probeklausur; 5P)

b) Gegeben war ein gerichteter Graph. Geben sie mittels DFS eine topologische Sortierung des Graphen an. (2P)

c) Gegeben war ein Flussnetzwerk. Man musste wie in einer Iteration zunächst das Restnetzwerk zeichen, darin einen Erweiterungspfad finden und daneben eine weitere Zeichnung des neuen Flussnetzwerks machen (5P).

d) Mit welchem der folgenden Algorithmen kann man negative Zyklen in einem Graphen finden/erkennen?
TopoSort, Bellman-Ford, Dijkstra, BFS oder Edmond-Karps? (2P)

e) Was sind die Unterschiede und Gemeinsamkeiten zwischen den Algorithmen von Dijkstra, Bellman-Ford und Floyd-Warshall? (6P)

== Aufgabe 6 ==
a) Wann ist ein Algorithmus stabil? (1P)

b) Geben Sie die Worst-Case-Laufzeiten an für Quicksort, Bubblesort, Mergesort und Heapsort (6P).

c) Was ist der Unterschied zwischen einem Stack und einer Queue? (2P)

d) Kommentieren Sie folgende Aussage: "Algorithmen auf Bäumen sind viel schneller als auf Arrays." (2P)

== Aufgabe 7 ==
...?

== Aufgabe 8 ==
Wieder einige Fragen zum Ankreuzen, manchmal mit Begründung.

a) Gehen Sie im Folgenden immer davon aus, dass P != NP.
* Ist <math>P \subseteq NP? </math>
* Ist <math>P \subseteq coNP? </math>
* Ist ...?

b) Folgt aus P = NP auch coP = coNP? (Mit Begründung, 2P)

c) Kann man ein Problem aus P immer auf ein NP-vollständiges Problem reduzieren? (Mit Begründung; 3P)

d) Sind alle Probleme in NP entscheidbar? Was ist mit den Problemen in coNP? (Mit Begründung; 4P)

== Aufgabe 9 ==

a) Angenommen P != NP. Ist folgendes Problem dann NP-schwierig: Gegeben ein Flussnetzwerk und eine natürliche Zahl k. Gibt es einen Schnitt mit einer niedrigeren Kapazität als k? (4P)

b) Polynomialzeitreduktion (5P). Gegeben:

1. Hamiltonkreis-Problem HC: Eingabe ungerichteter Graph. Gibt es einen Hamiltonkreis?

2. "Kreis"-Problem Gk: Eingabe ungerichteter Graph mit gewichteten Kanten und einem <math>k \in N</math>. Gibt es einen Kreis, dessen Kantengewicht-Summe über k liegt?

Das "Kreis"-Problem sei in NP. Zum Nachweis der NP-vollständigkeit reduzieren Sie HC auf Gk in Polynomialzeit.

[[Kategorie:Gedaechtnisprotokoll|AD11-1]]