ProgrammingWiki - Letzte Änderungen [de]

AuK/Minimaler Spannbaum SS12

2012-05-20T21:30:34Z

Steinerbaumproblem:

← Nächstältere Version		Version vom 20. Mai 2012, 21:30 Uhr
Zeile 377:		Zeile 377:

	==== Jakob Steiner ====		==== Jakob Steiner ====
		+	[[Bild:JakobSteiner.jpg\|thumb\|right\|165px\|Jakob Steiner 1796 – 1863]]
		+	Jakob Steiner war ein Schweizer Mathematiker und arbeitete vor allem in der Geometrie.

	=== Touren des Handelsreisenden ===		=== Touren des Handelsreisenden ===

Datei:JakobSteiner.jpg

2012-05-20T21:27:45Z

hat eine neue Version von „[[Datei:JakobSteiner.jpg]]“ hochgeladen {{Information |Beschreibung = Jakob Steiner |Quelle = Hanns Peter Holl: Jeremias Gotthelf. Zürich/München 1988, S. 33 |Urheber = |Datum = |Genehmigung = |Andere Versionen = |Anmerkungen = }} == Lizenz == {{Bild-PD-alt}}

Datei:JakobSteiner.jpg

2012-05-20T21:27:11Z

hat „[[Datei:JakobSteiner.jpg]]“ hochgeladen {{Information |Beschreibung = Jakob Steiner |Quelle = Hanns Peter Holl: Jeremias Gotthelf. Zürich/München 1988, S. 33 |Urheber = |Datum = |Genehmigung = |Andere Versionen = |Anmerkungen = }} == Lizenz == {{Bild-PD-alt}}

AuK/Minimaler Spannbaum SS12

2012-05-20T21:20:34Z

Steinerbaumproblem:

← Nächstältere Version		Version vom 20. Mai 2012, 21:20 Uhr
(Der Versionsvergleich bezieht 6 dazwischenliegende Versionen mit ein.)
Zeile 100:		Zeile 100:
	Sei $C$ ein Zyklus in $G$, $e$ eine Kante aus $C$ mit maximalem Gewicht und $T$ ein Spannbaum der $e$ enthält.		Sei $C$ ein Zyklus in $G$, $e$ eine Kante aus $C$ mit maximalem Gewicht und $T$ ein Spannbaum der $e$ enthält.
	$Tu$ und $Tv$ seien Teilbäume aus $T \setminus e$ und $e'$ eine Kante aus $C$ welche ebenfalls $Tu$ und $Tv$ verbindet. Dann existiert ein Spannbaum mit geringerem Gewicht als $T$, indem man $e$ aus dem Spannbaum entfernt und $e'$ hinzufügt.		$Tu$ und $Tv$ seien Teilbäume aus $T \setminus e$ und $e'$ eine Kante aus $C$ welche ebenfalls $Tu$ und $Tv$ verbindet. Dann existiert ein Spannbaum mit geringerem Gewicht als $T$, indem man $e$ aus dem Spannbaum entfernt und $e'$ hinzufügt.
		+
		+	=== Kreuzen ===
		+
		+	Wenn einer der Endpunkte einer Kante $(u,v) \in{} E$ in $S$ und der Andere in $V\setminus{}S$ liegt, so kreuzt diese Kante den Schnitt $(S, V\setminus{}S)$.
		+
		+	=== Respektieren ===
		+
		+	Wenn keine Kante von $A$ den Schnitt kreuzt, so respektiert der Schnitt die Kantenmenge $A$.
		+
		+	=== Leichte Kante ===
		+
		+	Eine Kante wird als leichte den Schnitt kreuzende Kante bezeichnet, wenn sie das geringste Gewicht aller den Schnitt kruzenden Kanten hat.
		+
		+	=== Sichere Kante ===
		+
		+	$G=(V,E)$ ist ein ungerichter, zusammenhängender und gewichteter Graph. $A$ ist eine Teilmenge von $E$ und gehört zu einem minimalen Spannbaum von $G$. Weiterhin ist $(S,V\setminus{}S)$ ein Schnitt von $G$ der außerdem $A$ respektiert. Dann ist die Kante $(u,v)$ für A '''sicher''', wenn diese Kante eine leichte den Schnitt $(S, V\setminus{}S)$ kreuzende Kante ist.
		+
		+	=== Korollar ===
		+
		+	Für die Algorithmen von Prim und Kruskal wird Folgendes Korollar verwendet:<br>
		+	Sei $C=(V_{C},E_{C})$ eine Zusammenhangskompenete (ein Baum) des Waldes $G_{A}=(V,A)$. Die Kante $(u,v)$ ist für A sicher, wenn $(u,v)$ ein leichte Kante ist, die $C$ mit einer anderen Zusammenhangskomponente von $G_{A}$ verbindet.

	== Algorithmen zum Bilden minimaler Spannbäume ==		== Algorithmen zum Bilden minimaler Spannbäume ==
Zeile 108:		Zeile 129:
	==== Idee ====		==== Idee ====
	$A$ ist eine Kantenmenge und wird vom Algorithmus verarbeitet. Dabei ist $A$ vor jeder Iteration eine Teilmenge eines minimalen Spannbaums. Während der Laufzeit des Algorithmus wird in jedem Schritt eine Kante $(u,v)$ bestimmt, sodass auch $A\cup{}{(u,v)}$ eine Teilmenge eines minimalen Spannbaums ist.		$A$ ist eine Kantenmenge und wird vom Algorithmus verarbeitet. Dabei ist $A$ vor jeder Iteration eine Teilmenge eines minimalen Spannbaums. Während der Laufzeit des Algorithmus wird in jedem Schritt eine Kante $(u,v)$ bestimmt, sodass auch $A\cup{}{(u,v)}$ eine Teilmenge eines minimalen Spannbaums ist.
-	$A$ muss dabei immer azyklisch sein, damit wenn der Algorithmus terminiert $A$ ein Spannbaum ist. Solange der Algorithmus ausgeführt wird, ist der Graph $G_{A}=(V,A)$ ein Wald. Die Zusammenhangskomponenten des Waldes sind Bäume. Diese Bäume können auch nur aus einem einzigsten Knoten bestehen. Dies ist zum Beispiel zu Beginn der Fall. Zu diesem Zeitpunkt gibt es $\|V\|$ Bäume. Die ''while''-Schleife wird $\|V\|-1$ mal ausgeführt, da ein Spannbaum aus $Knoten - 1$ Kanten besteht. Nach jedem Schleifendurchlauf verringert sich die Anzahl der Bäume im Wald um eins. Sobald der Wald aus nur noch einem Baum besteht terminiert der Algorithmus.	+	$A$ muss dabei immer azyklisch sein, damit wenn der Algorithmus terminiert $A$ ein Spannbaum ist. Solange der Algorithmus ausgeführt wird, ist der Graph $G_{A}=(V,A)$ ein Wald. Die Zusammenhangskomponenten des Waldes sind Bäume. Diese Bäume können auch nur aus einem einzigsten Knoten bestehen. Dies ist zum Beispiel zu Beginn der Fall. Zu diesem Zeitpunkt gibt es $\|V\|$ Bäume. Die ''while''-Schleife wird $\|V\|-1$ mal ausgeführt, da ein Spannbaum aus $Knoten - 1 Kanten$ besteht. Nach jedem Schleifendurchlauf verringert sich die Anzahl der Bäume im Wald um eins. Sobald der Wald aus nur noch einem Baum besteht terminiert der Algorithmus.

	==== Pseudocode ====		==== Pseudocode ====
Zeile 265:		Zeile 286:
	==== Pseudocode ====		==== Pseudocode ====
	Der Folgende Pseudocode soll die Scheme-Prozedur veranschaulichen. Da diese ohne Seiteneffekte arbeitet wird bei jeder Iteration die Menge $S$ und $E'$ neu bestimmt. Die Prozedur '''verwendeteKnoten''' erstellt die Menge $S$ und die Prozedur '''moeglicheKanten''' erstellt die Menge $E'$. Als letztes sucht die Prozedur '''kuerztKante''' die Kante mit den minimalen Kosten. Dise wird dann dem MST hinzugefügt.		Der Folgende Pseudocode soll die Scheme-Prozedur veranschaulichen. Da diese ohne Seiteneffekte arbeitet wird bei jeder Iteration die Menge $S$ und $E'$ neu bestimmt. Die Prozedur '''verwendeteKnoten''' erstellt die Menge $S$ und die Prozedur '''moeglicheKanten''' erstellt die Menge $E'$. Als letztes sucht die Prozedur '''kuerztKante''' die Kante mit den minimalen Kosten. Dise wird dann dem MST hinzugefügt.
		+	<br>
		+	'''Anmerkung'''
		+	Der folgende Algorithmus ist keine effiziente Implementierung. Dies liegt hauptsächlich daran, dass diese Prozdur Seiteneffektfrei sein soll. Desweiteren soll dies zeigen, dass minimale Spannbäume nur mit Listen und ohne Seiteneffekte erstellt werden können.<br>
		+	Am schnellsten läuft der Algorithmus mit Fibonacci-Heaps.

	prim($V$,$E$,$ls$)		prim($V$,$E$,$ls$)
Zeile 347:		Zeile 372:

	=== Steinerbaumproblem ===		=== Steinerbaumproblem ===
		+
		+	Ein Steinerbaum ist ein minimaler Spannbaum eines Teilgraphen von $G$, dabei werden die Knoten $V$ eingeschränkt. Auf unser Beispiel mit den Fähren auf den Kanarischen Inseln angewendet:<br>
		+	Einige Inseln sind zu unrentabel, da niemand die besuchen möchte. Nun ist der Steinerbaum, der minimale Spannbaum unseres neuen Problems.
		+
		+	==== Jakob Steiner ====

	=== Touren des Handelsreisenden ===		=== Touren des Handelsreisenden ===

AuK/Minimaler Spannbaum SS12

2012-05-20T15:44:16Z

Idee:

← Nächstältere Version		Version vom 20. Mai 2012, 15:44 Uhr
(Der Versionsvergleich bezieht 4 dazwischenliegende Versionen mit ein.)
Zeile 125:		Zeile 125:

	=== Algorithmus von Kruskal ===		=== Algorithmus von Kruskal ===
		+
		+	[[Bild:Chlorophyllkid_Kruskal.jpg\|thumb\|right\|390px\|Joseph Kruskal (1928-2010)]]
		+	==== Joseph Bernard Kruskal ====
		+
		+	Er war ein US-amerikanischer Mathematiker und Statistiker.
		+	Er hat an der Universität von Chicago und der Princeton Universität studiert, wo er 1954 mit der Dissertation Theory of Well-Quasi-Ordering unter Roger Lyndon und Paul Erdős promoviert wurde. <br>
		+
		+	Von Ihm stammt der nach ihm benannte Algorithmus zum Bilden minimaler Spannbäume von 1956.
		+

	==== Idee ====		==== Idee ====
Zeile 142:		Zeile 151:

	==== FIND-UNION-Methode ====		==== FIND-UNION-Methode ====
		+	Der Algorithmus von Kruskal führt zwei Operationen aus: Er testet ob sich 2 verschiedene Knoten im selben Teilbaum befinden oder nicht und verbindet 2 Teilbäume miteinander. <br>
		+	Man nennt diese Operationen FIND und UNION.
		+
		+	'''Die FIND-Operation''' <br>
		+	Hier wird die kleinste Kante aus $E$ genommen und geprüft ob ihre beiden Enden sich im selben Teilbaum befinden oder nicht. Ist dies der Fall ist die Kante unnütz, da das hinzufügen lediglich einen Kreis oder Zyklus im Baum erschaffen würde. <br>
		+	Befinden sich jedoch beide Enden in verschiedenen Teilbäumen so kann man die Kante zum Baum hinzufügen ohne einen Kreis zu erzeugen.
		+
		+	''Wie erkennt man ob sich beide Enden im selben Teilbaum befinden?''
		+
		+	Dafür gibt es eine einfache Lösung. Man übergibt den Knoten bei ihrer Initialisierung eine Variable, die sogenannte ''LEADER''- oder ''PARENT''-Variable. Am Anfang initialisiert sich jeder Knoten selbst als sein LEADER, sodass die Frage nach dem LEADER immer den Knoten selbst zurückgibt.
		+
		+	'''Die UNION-OPERATION''' <br>

	==== Pseudocode ====		==== Pseudocode ====
Zeile 239:		Zeile 260:
	==== Idee ====		==== Idee ====
	Bei jeder Iteration ist $S$ die Menge der bereits zum minimalen Spannbaum hinzugefügten Knoten und der '''Schnitt''' $E'$ ist die Menge der Kanten die genau einen Endpunkt in $S$ haben. In jeder Wiederholung wird eine Kante minimalen Gewichts dem Baum hinzugefügt. Die größte Herausforderung ist es die Kante effizient zu finden.		Bei jeder Iteration ist $S$ die Menge der bereits zum minimalen Spannbaum hinzugefügten Knoten und der '''Schnitt''' $E'$ ist die Menge der Kanten die genau einen Endpunkt in $S$ haben. In jeder Wiederholung wird eine Kante minimalen Gewichts dem Baum hinzugefügt. Die größte Herausforderung ist es die Kante effizient zu finden.
		+
		+	'''Verständnis-Aufgabe:''' [http://students.ceid.upatras.gr/~papagel/project/prim.htm Applet Prim-Algorithmus]

	==== Pseudocode ====		==== Pseudocode ====

Datei:Chlorophyllkid Kruskal.jpg

2012-05-20T10:49:14Z

hat „[[Datei:Chlorophyllkid Kruskal.jpg]]“ hochgeladen {{Information |Beschreibung = Joseph Kruskal |Quelle = http://three-mode.leidenuniv.nl/people/html/kruskal.htm |Urheber = |Datum = |Genehmigung = |Andere Versionen = |Anmerkungen = }} == Lizenz == {{Bild-CC-by-sa/3.0/de}}{{Bild-CC-by-sa/3.0}

AuK/Minimaler Spannbaum SS12

2012-05-20T10:45:38Z

Zyklus:

← Nächstältere Version		Version vom 20. Mai 2012, 10:45 Uhr
(Der Versionsvergleich bezieht 7 dazwischenliegende Versionen mit ein.)
Zeile 83:		Zeile 83:
	=== Schnitt ===		=== Schnitt ===

-	[[Bild:Chlorophyllkid_Schnitt.png\|thumb\|390px\|right\|~~Beispiel~~]]	+	[[Bild:Chlorophyllkid_Schnitt.png\|thumb\|390px\|right\|Cut-Property]]
	Ein ''Schnitt'' in einem verbundenen Graphen ist eine Teilmenge $E'$ von Kanten, so dass $G \setminus E'$ nicht verbunden ist.		Ein ''Schnitt'' in einem verbundenen Graphen ist eine Teilmenge $E'$ von Kanten, so dass $G \setminus E'$ nicht verbunden ist.

-	'''Schnitteigenschaft:''' Sei $E'$ ein Schnitt und $e$ eine Kante mit minimalen Kosten in $E'$. Dann gibt es einen Spannbaum $T$ von $G$ der $e$ enthält. Außerdem, wenn $T'$ in einem minimalen Spannbaum vorkommt und $T'$ keine Kante von $E'$ enthält, dann ist $T' \cup {e}$ in einigen minimalen Spannbäumen enthalten.	+	'''Schnitteigenschaft:''' (engl. Cut-Property) <br>
		+	Sei $E'$ ein Schnitt und $e$ eine Kante mit minimalen Kosten in $E'$. Dann gibt es einen Spannbaum $T$ von $G$ der $e$ enthält. Außerdem, wenn $T'$ in einem minimalen Spannbaum vorkommt und $T'$ keine Kante von $E'$ enthält, dann ist $T' \cup {e}$ in einigen minimalen Spannbäumen enthalten.

	'''Beispiel:'''		'''Beispiel:'''
Zeile 93:		Zeile 94:
	=== Zyklus ===		=== Zyklus ===

-	~~For any cycle~~ C in ~~the graph~~, ~~if the weight of an edge~~ e of C ~~is larger than the weights of other edges of C, then this edge cannot belong to an MST. Assuming the contrary, i.~~e. ~~that~~ e ~~belongs to an MST T1, then deleting~~ e ~~will break T1 into two subtrees with the two ends of e in different subtrees~~. ~~The remainder of C reconnects the subtrees~~, ~~hence there is an edge f of C with ends in different subtrees, i.~~e~~., it reconnects the subtrees into a tree T2 with weight less than that of T1, because the weight of f is less than the weight of~~ e.	+	[[Bild:Chlorophyllkid_Zyklus.png\|thumb\|390px\|right\|Cycle-Property]]
		+	Ein ''Zyklus'' in einem verbundenen Graphen ist eine Möglichkeit 2 Teilbäume über verschiedene Kanten zu verbinden.
		+
		+	'''Zykleneigeschaft:''' (engl. Cycle-Property) <br>
		+	Sei $C$ ein Zyklus in $G$, $e$ eine Kante aus $C$ mit maximalem Gewicht und $T$ ein Spannbaum der $e$ enthält.
		+	$Tu$ und $Tv$ seien Teilbäume aus $T \setminus e$ und $e'$ eine Kante aus $C$ welche ebenfalls $Tu$ und $Tv$ verbindet. Dann existiert ein Spannbaum mit geringerem Gewicht als $T$, indem man $e$ aus dem Spannbaum entfernt und $e'$ hinzufügt.

	== Algorithmen zum Bilden minimaler Spannbäume ==		== Algorithmen zum Bilden minimaler Spannbäume ==
Zeile 132:		Zeile 138:
	Dieses Verfahren nenn man auch die '''FIND'''-'''UNION'''-Methode.		Dieses Verfahren nenn man auch die '''FIND'''-'''UNION'''-Methode.

-	~~==== Pseudocode ====~~	+	'''Verständnis-Aufgabe:'''
		+	[http://students.ceid.upatras.gr/~papagel/project/kruskal.htm Applet Kruskal-Algorithmus]

-	~~Aus der Idee lassen sich nun folgende Pseudocodes entwickeln:~~	+	==== FIND-UNION-Methode ====
		+
		+	==== Pseudocode ====

-	~~<table>~~	+	Aus der Idee lässt sich nun folgender Pseudocode entwickeln:
-	~~<tr> <td>~~	+
-	~~:'''Iterativ''':~~	+
-	~~Spannbaum T = null;~~	+
-	~~<b>for</b> alle v aus V[G]~~	+
-	~~Knoten(v);~~	+
-	~~Leader(v) = v;~~	+
-	~~<b>for</b> alle (u,v) aus E[G]~~	+
-	~~<b>if</b> ( Leader(u) != Leader(v) )~~	+
-	~~Leader(u) = v;~~	+
-	~~T = T + (u,v);~~	+
-	~~<b>return</b> T;~~	+
-	~~</td><td></td><td>~~	+
-	~~:'''Rekursiv'''~~:	+

-	~~</td></tr></table>~~	+	T $\leftarrow$ {}
		+	'''for''' alle v aus V[G]
		+	v = Knoten(v);
		+	'''while''' E[G] $\neq$ {}
		+	Nimm die kleinste Kante aus E[G].
		+	'''if''' (Leader(u) $\neq$ Leader(v))
		+	'''then''' Füge die Kante (u,v) dem Baum T hinzu.
		+	'''else''' Nimm die nächst kleinere Kante aus E[G].
		+	'''end while'''
		+	'''return''' T;

	==== Implementierung ====		==== Implementierung ====
Zeile 186:		Zeile 191:
	(else (error 'knoten% "~s is not applicble to ~s " messagename args))))]		(else (error 'knoten% "~s is not applicble to ~s " messagename args))))]
	[else (error 'knoten% "doesn't understand ~s" messagename)]))))))))		[else (error 'knoten% "doesn't understand ~s" messagename)]))))))))
		+	(define UNION cons)
	</code>		</code>

Zeile 218:		Zeile 224:
	[(FIND (caar kante)) ((eval ((eval (cdaar kante)) 'get-leader!)) 'set-leader! `(,(eval (caaar kante)) 'get-leader!))		[(FIND (caar kante)) ((eval ((eval (cdaar kante)) 'get-leader!)) 'set-leader! `(,(eval (caaar kante)) 'get-leader!))
	((eval (cdaar kante)) 'set-leader! `(,(eval (caaar kante)) 'get-leader!))		((eval (cdaar kante)) 'set-leader! `(,(eval (caaar kante)) 'get-leader!))
-	(~~cons~~ (car kante) (MST (cdr kante)))]	+	(UNION (car kante) (MST (cdr kante)))]
	[else (MST (cdr kante))]))])		[else (MST (cdr kante))]))])
	(MST kanten)))))		(MST kanten)))))

Datei:Chlorophyllkid Zyklus.png

2012-05-20T09:11:31Z

hat „[[Datei:Chlorophyllkid Zyklus.png]]“ hochgeladen {{Information |Beschreibung = Erklärung: Zykleneigenschaft |Quelle = Minimal Spanning Trees |Urheber = |Datum = |Genehmigung = |Andere Versionen = |Anmerkungen = }} == Lizenz == {{Bild-frei}}

AuK/Minimaler Spannbaum SS12

2012-05-20T08:48:38Z

Zyklus:

← Nächstältere Version		Version vom 20. Mai 2012, 08:48 Uhr
(Der Versionsvergleich bezieht 2 dazwischenliegende Versionen mit ein.)
Zeile 79:		Zeile 79:
	Die Gesamtstrecke der Fähr-Verbindung beträgt $341$km</popup>		Die Gesamtstrecke der Fähr-Verbindung beträgt $341$km</popup>

-	== ~~Überschrift für Definitionen~~, ~~Theorem~~ und ~~Korollar~~ ==	+	== Grundbegriffe Schnitt und Zyklus ==
		+
		+	=== Schnitt ===
		+
		+	[[Bild:Chlorophyllkid_Schnitt.png\|thumb\|390px\|right\|Beispiel]]
		+	Ein ''Schnitt'' in einem verbundenen Graphen ist eine Teilmenge $E'$ von Kanten, so dass $G \setminus E'$ nicht verbunden ist.
		+
		+	'''Schnitteigenschaft:''' Sei $E'$ ein Schnitt und $e$ eine Kante mit minimalen Kosten in $E'$. Dann gibt es einen Spannbaum $T$ von $G$ der $e$ enthält. Außerdem, wenn $T'$ in einem minimalen Spannbaum vorkommt und $T'$ keine Kante von $E'$ enthält, dann ist $T' \cup {e}$ in einigen minimalen Spannbäumen enthalten.
		+
		+	'''Beispiel:'''
		+	$e$ ist die billigste Kante im Schnitt $E'$ und $p$ ist ein Pfad im MST, der die Endpunkte von $e$ $(u, v)$ verbinden soll. Man kann also die Kante $e'$ aus dem Spannbaum entfernen und durch $e$ ersetzen, sodass immer noch die Baumeigenschaft gilt.
		+
		+	=== Zyklus ===
		+
		+	For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of other edges of C, then this edge cannot belong to an MST. Assuming the contrary, i.e. that e belongs to an MST T1, then deleting e will break T1 into two subtrees with the two ends of e in different subtrees. The remainder of C reconnects the subtrees, hence there is an edge f of C with ends in different subtrees, i.e., it reconnects the subtrees into a tree T2 with weight less than that of T1, because the weight of f is less than the weight of e.

	== Algorithmen zum Bilden minimaler Spannbäume ==		== Algorithmen zum Bilden minimaler Spannbäume ==

Datei:Chlorophyllkid Schnitt.png

2012-05-20T08:26:33Z

hat „[[Datei:Chlorophyllkid Schnitt.png]]“ hochgeladen {{Information |Beschreibung = Erklärung: Schnitteigenschaft |Quelle = Minimal Spanning Trees |Urheber = |Datum = |Genehmigung = |Andere Versionen = |Anmerkungen = }} == Lizenz == {{Bild-CC-by-sa/3.0/de}}{{Bild-CC-by-sa/3.0}}{{Bild-GFDL-Neu}

AuK/Minimaler Spannbaum SS12

2012-05-17T12:58:31Z

Algorithmus von Prim:

← Nächstältere Version		Version vom 17. Mai 2012, 12:58 Uhr
(Der Versionsvergleich bezieht 2 dazwischenliegende Versionen mit ein.)
Zeile 1:		Zeile 1:
	<language>Scheme</language>		<language>Scheme</language>
-	~~== Wozu? ==~~
	Minimale Spannbäume (englisch: ''Minimal Spanning Tree'', Abkürzung: '''MST''') können zum lösen vieler Probleme genutzt werden. Ein Problem, dass man mit MST lösen kann ist z.B., dass verbinden mehrerer Inseln mit Brücken. Man möchte, dass alle Inseln miteinander verbunden sind und die Brücken minimale Länge haben und damit minimale Kosten entstehen. Dabei sollen die Inseln so verbunden werden, dass man alle Inseln über die Brücken berreisen kann und keine redundanten Brücken entstehen. Redundante Brücken sind Brücken mit der man eine Insel erreicht, die man auch über einen anderen ggf. längeren Weg hätte erreichen können. Längerer Weg heißt in diesem Fall, dass man über (eine) andere Brücke(n) reisen muss um die Insel zu erreichen.		Minimale Spannbäume (englisch: ''Minimal Spanning Tree'', Abkürzung: '''MST''') können zum lösen vieler Probleme genutzt werden. Ein Problem, dass man mit MST lösen kann ist z.B., dass verbinden mehrerer Inseln mit Brücken. Man möchte, dass alle Inseln miteinander verbunden sind und die Brücken minimale Länge haben und damit minimale Kosten entstehen. Dabei sollen die Inseln so verbunden werden, dass man alle Inseln über die Brücken berreisen kann und keine redundanten Brücken entstehen. Redundante Brücken sind Brücken mit der man eine Insel erreicht, die man auch über einen anderen ggf. längeren Weg hätte erreichen können. Längerer Weg heißt in diesem Fall, dass man über (eine) andere Brücke(n) reisen muss um die Insel zu erreichen.

Zeile 7:		Zeile 6:
	== Spannbäume ==		== Spannbäume ==
	[[Bild:Muessigd_Spannbaum.png\|miniatur\|Spannbaum]]		[[Bild:Muessigd_Spannbaum.png\|miniatur\|Spannbaum]]
-	Im Folgenden soll eine Einführung in die Begriffe und Grundvorraussetzungen für MST gegeben werden. Die Begriffe werden dabei anhand des Beispiels ~~aus dem Punkt [[AuK/Minimaler_Spannbaum_SS12#Wozu.3F\|Wozu?]]~~ erklärt. <br/>	+	Im Folgenden soll eine Einführung in die Begriffe und Grundvorraussetzungen für MST gegeben werden. Die Begriffe werden dabei anhand des obigen Beispiels erklärt. <br/>
	Im allgemeinen hat man $n$-Knoten die man zu einem Spannbaum verbinden möchte. Wir haben also $n$-Inseln die miteinander verbunden werden sollen. Dazu benötigt man immer $n-1$ Kanten (Brücken). <br/>		Im allgemeinen hat man $n$-Knoten die man zu einem Spannbaum verbinden möchte. Wir haben also $n$-Inseln die miteinander verbunden werden sollen. Dazu benötigt man immer $n-1$ Kanten (Brücken). <br/>
	Man geht immer von einem zusammenhängenden, gewichteten und ungerichteten Graphen $G=(V,E)$ aus. $V$ ist die Menge der Knoten und $E$ ist die Menge der möglichen Verbindungen zwischen allen Parren von Knoten. In unserem Beispiel also alle möglichen Brücken. Jede Kante $(u,v)\in E$ besitzt ein Gewicht $w(u,v)$ (deshalb gewichtet), dass die Länge (auch Kosten gennant) angibt. Ein Graph $G$ ist ungerichtet, wenn die Kanten des Graphen keine Pfeile sondern Striche sind. Das heißt also, dass es innerhalb des Graphen keine Einschränkung der Wege gibt. Ein ungerichteter Graph heißt zusammenhängend, wenn es zu je zwei belliebigen Knoten $u$ und $v$ einen ungerichteten Weg gibt mit $u$ als Startknoten und $v$ als Endknoten.<br/>		Man geht immer von einem zusammenhängenden, gewichteten und ungerichteten Graphen $G=(V,E)$ aus. $V$ ist die Menge der Knoten und $E$ ist die Menge der möglichen Verbindungen zwischen allen Parren von Knoten. In unserem Beispiel also alle möglichen Brücken. Jede Kante $(u,v)\in E$ besitzt ein Gewicht $w(u,v)$ (deshalb gewichtet), dass die Länge (auch Kosten gennant) angibt. Ein Graph $G$ ist ungerichtet, wenn die Kanten des Graphen keine Pfeile sondern Striche sind. Das heißt also, dass es innerhalb des Graphen keine Einschränkung der Wege gibt. Ein ungerichteter Graph heißt zusammenhängend, wenn es zu je zwei belliebigen Knoten $u$ und $v$ einen ungerichteten Weg gibt mit $u$ als Startknoten und $v$ als Endknoten.<br/>
Zeile 104:		Zeile 103:


-	~~----~~

	=== Algorithmus von Kruskal ===		=== Algorithmus von Kruskal ===
Zeile 215:		Zeile 213:

	<run id="4fb23af8e79fc">(gewicht (kruskal))</run>		<run id="4fb23af8e79fc">(gewicht (kruskal))</run>
-	~~----~~

	=== Algorithmus von Prim ===		=== Algorithmus von Prim ===
	[[Bild:Muessigd_Prim.gif\|thumb\|390px\|right\|Algorithmus von Prim Animation]]		[[Bild:Muessigd_Prim.gif\|thumb\|390px\|right\|Algorithmus von Prim Animation]]
		+	Der Jarnik-Prim-Algorithmus für minimale Spannbäume ist dem Dijkstra Algorithmus für kürzeste Wege sehr ähnlich. Beginnend bei einem zufälligen Startknoten $s$, wächst der Baum zu einem minimalen Spannbaum durch das hinzufügen eines Knoten nach dem anderen.
	==== Idee ====		==== Idee ====
		+	Bei jeder Iteration ist $S$ die Menge der bereits zum minimalen Spannbaum hinzugefügten Knoten und der '''Schnitt''' $E'$ ist die Menge der Kanten die genau einen Endpunkt in $S$ haben. In jeder Wiederholung wird eine Kante minimalen Gewichts dem Baum hinzugefügt. Die größte Herausforderung ist es die Kante effizient zu finden.

	==== Pseudocode ====		==== Pseudocode ====
		+	Der Folgende Pseudocode soll die Scheme-Prozedur veranschaulichen. Da diese ohne Seiteneffekte arbeitet wird bei jeder Iteration die Menge $S$ und $E'$ neu bestimmt. Die Prozedur '''verwendeteKnoten''' erstellt die Menge $S$ und die Prozedur '''moeglicheKanten''' erstellt die Menge $E'$. Als letztes sucht die Prozedur '''kuerztKante''' die Kante mit den minimalen Kosten. Dise wird dann dem MST hinzugefügt.
		+
	prim($V$,$E$,$ls$)		prim($V$,$E$,$ls$)
	'''if''' length($V$) $-$ $1$ == length($ls$)		'''if''' length($V$) $-$ $1$ == length($ls$)

BuK/IIm11/BuK-KA-RAM-Programm

2012-05-16T17:31:29Z

Die Seite wurde neu angelegt: „=Registermaschine= Geben Sie mind. ein RAM-Programm zur Berechnung der Funktion $w : \N \mapsto \N$ mit $w(n) = \left\lfloor \sqrt{n} \right\rfloor$ an.“

Neue Seite

=Registermaschine=

Geben Sie mind. ein RAM-Programm zur Berechnung der Funktion $w : \N \mapsto \N$ mit $w(n) = \left\lfloor \sqrt{n} \right\rfloor$ an.

BuK/IIm11/BuK-Übung08

2012-05-16T17:23:32Z

Neue Seite

==Semantik: $\alpha$-Regel (Felix Nitsche, Stefan Lüttke)==
* Wenden Sie für (($\lambda$ x. ( $\lambda$ y. ((x y)))(y w)) vor der $\beta$-Reduktion die $\alpha$-Konvention an.

==Semantik: $\eta$-Regel (Daniel Tasche, Jens Heider)==
* Vereinfachen Sie den Racket-Ausdruck ($\lambda$(z)(($\lambda$(x)($*$ 3 x)) z)).

==Reduktion (Raik Bieniek, Max Wielsch)==
* Reduzieren Sie (($\lambda$(x)(x x))($\lambda$(x) x)) und (($\lambda$(x)(x x))($\lambda$(x)(x x)))
* Zeigen Sie, dass für Y := ($\lambda$ f. (($\lambda$ x. (f (x x)))($\lambda$ x. (f (x x))))) gilt: (Y g) = (g (Y g))

==Reduktionsreihenfolge (Ingo Körner, Christof Ochmann)==
* Zeigen Sie dass es von der Reduktionsreihenfolge abhängen kann, ob die für (($\lambda$ y. z)(($\lambda$ x. (x x))($\lambda$ x. (x x)))) existierende Normalform z gefunden wird oder nicht.
* Verwenden Sie zur Berechnung von (($\lambda$x. ((x d)(($\lambda$ y. (x y)) a))) b) unterschiedliche Reduktionsreihenfolgen.

==Boolesche Werte (Stefan Scheumann, Robert Rosenberger)==
Berechnen Sie <tt>if true e1 e2 = e1</tt>.

==Curryzierung (Ronald Krause, Tobias Salzmann)==
Currizieren Sie f(x, y, z) = x + y + z

==Registermaschine(Ronald Krause, Tobias Salzmann)==
Führen Sie folgendes Programmbeispiel per Hand aus.

BuK/IIm11

2012-05-16T12:33:50Z

Aufgabenübersicht:

← Nächstältere Version		Version vom 16. Mai 2012, 12:33 Uhr
Zeile 22:		Zeile 22:
	\|-		\|-
	\|\|[[BuK/IIm11/BuK-Übung07\|Gödelisierung]] \|\| Gödelisierung \|\| Stefan Scheumann, Robert Rosenberger \|\| [[BuK/IIm11/BuK-KA-MU \|MU-Rätsel]] \|\|		\|\|[[BuK/IIm11/BuK-Übung07\|Gödelisierung]] \|\| Gödelisierung \|\| Stefan Scheumann, Robert Rosenberger \|\| [[BuK/IIm11/BuK-KA-MU \|MU-Rätsel]] \|\|
		+	\|-
		+	\|\|[[BuK/IIm11/BuK-Übung08\|Lambda-Kalkül]] \|\| Lambda-Kalkül \|\| Tobias Salzmann, Ronald Krause \|\| [[BuK/IIm11/BuK-KA-RAM-Programm \|RAM-Programm]] \|\|
	\|-		\|-
	\|}		\|}

AuK/Minimaler Spannbaum SS12

2012-05-16T11:49:01Z

Algorithmus von Sibeyn:

← Nächstältere Version		Version vom 16. Mai 2012, 11:49 Uhr
Zeile 297:		Zeile 297:

	== Algorithmus von Sibeyn ==		== Algorithmus von Sibeyn ==
-
-	~~----~~

	== Anwendungen ==		== Anwendungen ==

AuK/Durchläufe durch Graphen SS12

2012-05-16T11:34:34Z

CPP:

← Nächstältere Version		Version vom 16. Mai 2012, 11:34 Uhr
Zeile 1.784:		Zeile 1.784:
	Inhalt des Problems ist die Frage nach dem besten Weg um Briefe zuzustellen. Jede Straße wird hierbei als Kante und jede Straßenkreuzung als Knoten in einem Straßennetzwerk(Graph) modelliert. Der Postbote muss nun jede Straße(Kante) ''genau einmal'' ablaufen, um alle Adressaten zu erreichen und dennoch nicht zu viel zu laufen.<br>		Inhalt des Problems ist die Frage nach dem besten Weg um Briefe zuzustellen. Jede Straße wird hierbei als Kante und jede Straßenkreuzung als Knoten in einem Straßennetzwerk(Graph) modelliert. Der Postbote muss nun jede Straße(Kante) ''genau einmal'' ablaufen, um alle Adressaten zu erreichen und dennoch nicht zu viel zu laufen.<br>

-	Damit kann man das CPP lösen, ~~wenn~~ man einen Eulerkreis findet.<br>	+	Damit kann man das CPP lösen, indem man einen Eulerkreis findet.<br>

	Leider sind reale Straßennetze nicht immer eulersch, das Thema soll hier jedoch nicht weiter vertieft werden.		Leider sind reale Straßennetze nicht immer eulersch, das Thema soll hier jedoch nicht weiter vertieft werden.

Datei:Croxeldyffic Bfs01.gif

2012-05-16T11:32:17Z

hat eine neue Version von „[[Datei:Croxeldyffic Bfs01.gif]]“ hochgeladen {{Information |Beschreibung = Breitensuche an G1 |Quelle = selbst erstellt |Urheber = ~~~ |Datum = |Genehmigung = |Andere Versionen = |Anmerkungen = }} == Lizenz == {{Bild-frei}}

AuK/Minimaler Spannbaum SS12

2012-05-16T10:24:40Z

Algorithmus von Sibeyn:

← Nächstältere Version		Version vom 16. Mai 2012, 10:24 Uhr
(Der Versionsvergleich bezieht 2 dazwischenliegende Versionen mit ein.)
Zeile 226:		Zeile 226:
	'''then return''' $ls$		'''then return''' $ls$
	'''else'''		'''else'''
-	'''if''' $ls$ == $0$	+	'''if''' $ls$ == $null$
	'''then''' $ls$ $\leftarrow{}$ kuerztKante(erstesElement($V$))		'''then''' $ls$ $\leftarrow{}$ kuerztKante(erstesElement($V$))
	'''else''' $vls$ $\leftarrow{}$ verwendeteKnoten($ls$)		'''else''' $vls$ $\leftarrow{}$ verwendeteKnoten($ls$)
	$mls$ $\leftarrow{}$ moeglicheKanten($vls$)		$mls$ $\leftarrow{}$ moeglicheKanten($vls$)
-	$ls$ $\leftarrow{}$ $ls + $kuerztKante($mls$)	+	$ls$ $\leftarrow{}$ $ls +$ kuerztKante($mls$)
	prim($V$,$E$,$ls$)		prim($V$,$E$,$ls$)

Zeile 296:		Zeile 296:
	<run id="4fb23af8e7a8b">(gewicht (prim '()))</run>		<run id="4fb23af8e7a8b">(gewicht (prim '()))</run>

-	=== Algorithmus von Sibeyn ===	+	== Algorithmus von Sibeyn ==

	----		----
-

	== Anwendungen ==		== Anwendungen ==

Datei:Muessigd Spannbaumkrusk.png

2012-05-16T09:53:16Z

hat eine neue Version von „[[Datei:Muessigd Spannbaumkrusk.png]]“ hochgeladen