Tutorium Algo:

anchored to [[111.00_anchor]]

Overview:

Session 03 - [Date:2023-11-08]:

Wiederholung von Bäumen:

es wurden Bäume wiederholt.

Die Vollständigkeitseigenschaften können nur bei Binärbäumen bezeichnet werden, da man hier genau weiß, wie viele kinder ein Knoten haben kann. –> Anderweitig kann keine Vollständigkeit beschrieben werden, weil wir nicht wissen, ob wir alle Kinder von $n$ -vielen wirklich befüllt haben.

Heaps: Heaps müssen wir zuvor entsprechend aufbauen –> entweder Max oder small heap.

Heaps haben wir jetzt mit $O (n lo g n)$ gebaut. Man kann sie aber auch in $O (n)$ bauen.

Dafür betrachten wir einen Binärbaum. Dafür haben wir unter Betrachtung aller Level / Schichten $n = 0 \sum H 2^{n} (H - h)$ –> pro Schicht müssen wir maximal diese Menge durchlaufen.

Wir können diesen Term weiter vereinfachen: $h = 0 \sum H 2^{h + 1} (H - h) - h = 0 \sum H 2^{h} (H - h) = 2^{1} + 2^{2} + \dots + 2^{n} = O (n)$

Session 06 - [Date:2023-11-29]:

Wir haben Floyd-Warshall nochmals betrachten. Dabei schauen wir uns imemr zu den vorhandenen Wellen die nächsten Knoten, die nahe liegen an, und bauen so nach und nach die kürzesten Pfade von einem Punkt zum nächsten.

Beispiel Graph mit Beispielsadjazenzmatrix:

	a	b	c	d
a	0	1	$\infty$	3
b	$\infty$	0	$\infty$	$\infty$
c	-1	0	0	2
d	1	2	2	0

| | | | | |

WIr iterieren das Ganze 3 mal. WIr starten immer in der Diagonalen und schauen dann in Form von der gewählten Spalte und Reihe an, was sich verändern kann / bzw wie sich die Distanz anpassen kann. Nach jeder Iteration werden wir dann zu der nächsten diagonalen Ebene übergehen und hier entsprechend schauen, ob wir einen besseren Weg zu einem Knoten konstruieren kann

[!Important] Intuitiv gesagt Wir möchten mit jeder Iteration mehr oder wenniger schauen, ob wir von einem Knoten, den wir zum Zeitpunkt gewählt haben, zu einem anderen schneller traversieren können. Intuitiv würden wir hier also

BSP :

	a	b	c
a	0	1	3
b	2	0	7
c	$\infty$	$\infty$	0

Ist unser Ausgangszustand

iteratino: Gibt es von A zu dem Knoten der oben steht (also b/c) einen kürzeren Weg ? Wir betrachten also etwa, ob wir von a nach c besser kommen, als mit dem derzeitigen weg von $a \to c$ Hier können wir jetzt schauen, dass man von b nach c auch über a und dann c kommt. Das ist kürzer, als der vorherige Weg.

Wir schauen uns also an, ob wir die Werte Schritt für Schritt verkürzen können.

Ein Wert ist immer die Addtion der Zelle rechts und über ihr ( oder wenn wir ganz oben sind, von oben und rechts) ( wenn man es betrachtet, sieht man halt, dass dieser Pfad sich daraus bilden lässt).

Im Beispiel können wir etwa $c \to a$ berechnen, indem wir schauen, ob $ba + c b$ kleiner / günstiger ist.

Diesem Schema folgen wir dann auf der ganzen Diagonale –> Dabei ist jeder Schritt auf dieser Diagonale gleich einer Iteration des Algorithmus

	a	b	c
a	0	1	3
b	2	0	7
c	$\infty$	$\infty$	0

Übungsblatt 6:

1a: Laufzeit bei 1a schränkt stark ein! 2b: Korrektheitsbeweis –> kann man in ein / zwei Sätzen lösen.

2d: Angeben, wie man es machen kann: -> Entweder guter Text oder PseudoCode

Session 7 | 06.12.2023

Korrektheitsbeweise und generelle Beweise:

-> Wichtig eine gewisse Struktur aufzubauen Also angeben, um welchen Beweis es sich handeln soll ( etwas Widerspruch etc) –> Am Ende muss ein Beweis die Personen, die es lesen, überzeugen, damit ist die formalisierung auf hoher Ebene vielleicht nicht ganz wichtig //

Es wurde noch Gruskal / Prim angewandt

Prim –> Dijkstra, aber nicht minimalstes Kantengewicht (plus minialste Distanz), sondern nur

Betrachtung Union-Find

auch in [[111.28_Graphen_MST_Union_Find]] referenziert.

Wir haben jetzt zwei