ALD

Wie ist ein Problem zu lösen

Haben keine Pfeile und sind symetrisch

In einem gerichteten Graphen haben die Kanten eine Richtung und sind durch Pfeile gekennzeichnet. Wenn es eine gerichtete Kante von Knoten A zu Knoten B gibt, bedeutet das, dass A mit B in Verbindung steht, aber B nicht unbedingt mit A verbunden ist

verices v

Eine teil der Knoten und kanten in einem Obergraph

Spezielle version in der beide Knoten der Kante bekannt ist

mussen die kanten nicht zwischen bekannten knoten verlaufen

Ist eine Menge an Knoten(verices/Nodes) die mittels Kanten(edges) miteinander verbunden werden

p_last zeigz dabei als nächstes Element auf p_head unt damit auf entsteht eine art kreis von Zeigern

Datenstruktur wo eine liste ist wo jedes Element als bucket bezeichnet wird. der bucket wird durch einen Hashfunktion ausgewählt bei der es zu kollision kommen kann die durch eine ander datenstruktur oder double hashing gelöst werden kann

Ermlglicht schnelles finden von daten

ein versuch Kollision zu behandeln indem mit einer weiteren Funktion ein alternativer bucket errechnet wird die zweite funktion ist die schrittweite beim überlauf fängt man wieder mit dem ersten bucket an

Schlusselsuche durch Berechnung der Array-Indizes!

keine überlauf list sondern veruchen eine ausweich adresse zu finden

Erkärung für Insertion sort

1. Wir sagen der anfang der liste ist der sortierte bereich der von z.b. i abgegrenzt wird

2. i bewgt sich mit jedem schleifendurchlauf 1 schritt näher richtung schleifen ende

3. dabei wird überprüft ob i immer kleiner ist als der rechte nachbar

4. ist das nicht der fall wird der nachbar an die stelle im sortierten bereich platziert wo die vorherhige Zahl kleiner und die nachfolgende größer ist

procedure countingSort(arr: sequence of integers, k: integer)

let cnt be an array of size k initialized with all elements as 0

let n be the size of arr

let output be an array of size n

// Count the occurrences of each element in the input array

for i := 0 to n-1 do

cnt[arr[i]] := cnt[arr[i]] + 1

// Compute the cumulative sum of the count array

for i := 1 to k-1 do

cnt[i] := cnt[i] + cnt[i-1]

// Place the elements in the correct position in the output array

for j := n-1 downto 0 do

output[cnt[arr[j]] - 1] := arr[j]

cnt[arr[j]] := cnt[arr[j]] - 1

// Copy the sorted elements from the output array back to the input array

for i := 0 to n-1 do

arr[i] := output[i]

end procedure

procedure heapify(arr: sequence of integers, n: integer, i: integer)

largest := i

left := 2 * i + 1

right := 2 * i + 2

// Finde das größte Element unter den Wurzel-, linken und rechten Kindknoten

if left < n and arr[left] > arr[largest]

largest := left

if right < n and arr[right] > arr[largest]

largest := right

// Wenn das größte Element nicht die Wurzel ist, tausche es mit der Wurzel

if largest != i

swap(arr[i], arr[largest])

// Wiederhole den Vorgang rekursiv für den betroffenen Teilbaum

heapify(arr, n, largest)

procedure heapSort(arr: sequence of integers)

n := length(arr)

// Erstelle einen Max-Heap aus dem Eingabearray

for i := n / 2 - 1 downto 0

heapify(arr, n, i)

// Sortiere das Array, indem das größte Element immer an den Anfang verschoben wird

for i := n - 1 downto 1

swap(arr[0], arr[i])

heapify(arr, i, 0)

procedure heapify(arr: sequence of integers, n: integer, i: integer)

largest := i

left := 2 * i + 1

right := 2 * i + 2

// Finde das größte Element unter den Wurzel-, linken und rechten Kindknoten

if left < n and arr[left] > arr[largest]

largest := left

if right < n and arr[right] > arr[largest]

largest := right

// Wenn das größte Element nicht die Wurzel ist, tausche es mit der Wurzel

if largest != i

swap(arr[i], arr[largest])

// Wiederhole den Vorgang rekursiv für den betroffenen Teilbaum

heapify(arr, n, largest)

O

Untere schranke

Ω(n) muss kleiner sein als f(n) oft ansehbar durch die exponente

Stimmte wenn es die ober und untere schranke darstellt

Die Laufzeit

Θ(g) stimmt wenn groß o und Omega stimm

idealisiertes Modell (RAM: Random Access Machine)

• festgelegter Befehlssatz (Assembler-¨ahnlich)

• abzählbar unendlich viele Speicherzellen ⇒ Laufzeit: Anzahl ausgefuhrter RAM-Befehle

• ⇒ Speicherbedarf: Anzahl benötigter Speicherzellen

  charakteristische Parameter ermitteln

• Sortieren: Schlusselvergleiche, Vertauschungen ¨

• Arithmetik: Additionen, Multiplikationen

Korrektheit

Laufzeit

Speicherplatz

auch

Kommunikationszeit

Güte

bezeichnet die größte, ganze Zahl k, die kleiner oder gleich x ist. Die Zeichen ⌊⌋ werden untere Gauß-Klammern genannt.

Beispiele: ⌊8, 2⌋ = 8, ⌊6, 99⌋ = 6, ⌊−7, 3⌋ = −8

⌈x⌉ bezeichnet die kleinste, ganze Zahl k, die gr¨oßer oder gleich x ist. Die Zeichen ⌈⌉ werden entsprechend als obere Gauß-Klammern bezeichnet.

Beispiele: ⌈8, 2⌉ = 9, ⌈6, 01⌉ = 7, ⌈−9, 6⌉ = −9

Womit kann das Problem gelöst werden

(Abstrakter Datentyp)

Ein abstrakter Datentyp wird definiert durch einen Wertebereich, also einer Menge von Objekten, und darauf definierten Operationen. Die Menge der Operationen nennt man die Schnittstelle des Datentyps.

int double char graphen liste array Bäume

Heap

Damit wir die richtigen schneller finden

Divide the problem into subproblems.

Conquer the subproblems by solving them recursively.

Combine subproblem solutions.

Hierbei steht T(n) für die gesuchte Laufzeitfunktion, während a und b Konstanten sind. Ferner bezeichnet f(n) eine von T(n) unabhängige und nicht negative Funktion. Damit das Master-Theorem angewendet werden kann, müssen für die beiden Konstanten die Bedingungen a≥1 und b>1 erfüllt sein.

Interpretation der Rekursion für T(n):

a  = Anzahl der Unterprobleme in der Rekursion

1/b = Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird

f(n)= Kosten (Aufwand, Nebenkosten), die durch die Division des Problems und die Kombination der Teillösungen entstehen

Jeder Schritt wird nur aufgrund der ” lokal verfügbaren“ Information durchgeführt. ¨

Es wird aus allen möglichen ” Fortsetzungen einer Teillösung“ diejenige ausgewählt, die momentan den besten Erfolg bringt. → Es werden also nicht verschiedene Kombinationen von Teillösungen getestet, sondern nur eine einzige ausgewählt. Diese Lösung ist ggf. nicht optimal

Berechnete Lösungen in Tabelle abspeichern

Alle bereits berechneten Teillösungen speichern (Bottom UP)

Aus den Teillösungen wird die Gesamtlösung zusammengesetzt, indem alle Kombinationen von Teillösungen betrachtet werden und die optimale Lösung ausgewählt wird

fugt Element x in den Stack D ein

top(D) liefert das zuletzt eingefugte Element des Stacks D

entfernt das zuletzt eingefugte Element aus dem Stack ¨ D

Ist eine Liste wo die Elemente mit Zeigern aufeinander zeigen so das jedes element an einer belibiegen stelle im speicher

head zeigz auf das erste element

tail auf das Ende

Einfach verkettet

zeigt auf das nächste element

Doppelt verkettet

Elemente zeigen auf das vorherhige und nachfolgende element

liefert die Größe des Stacks D als Anzahl gespeicherter Objekte

Ein Datentyp nach dem LIFO verfahren arbeitet Last in first Out

Man bekommt immer nur das, was man zuletzt hereingelegt hat.

erzeugt eine leere Queue (First-In, First-Out)

fugt Element x in die Queue D ein

liefert zuerst eingefugtes Element von D

entfernt zuerst eingefugtes Element aus D

fugt das Element ¨ x vor dem Element an Position p in die Folge

tail()

head

vor und zurück travers bar

nur von head zu tail

Knoten mit einem Wert und link und recht einem knoten haben

Zig Zag

rechts links drehen von knoten

Post-Order

Pre Order

Level Order

In Order

1. Besuchen des Wurzelknotens

2. Preorder-Traversierung des linken Teilbaums

3. Preorder-Traversierung des rechten Teilbaums

1. Postorder-Traversierung des linken Teilbaums

2. Postorder-Traversierung des rechten Teilbaums

3. Besuchen des Wurzelknotens

1. Inorder-Traversierung des linken Teilbaums

2. Besuchen des Wurzelknotens

3. Inorder-Traversierung des rechten Teilbaums

Binäre Suchbäume sind links-rechts-geordnete binäre Bäume, d.h. der linke und der rechte Nachfolger sind unterscheidbar

1. Besuchen des Wurzelknotens

2. Durchlaufe jede weitere Ebene von links nach rechts

Die tiefe aller bläter untscheidet sich max um 1

1+2+3+4+5+6+7+8+9+10

1*2*3*4*5*n

Jeder schlüssel wird mittels umstrukturierung richtung wurzel bewegt

• Alle Bl¨atter befinden sich in gleicher Tiefe.

• Alle inneren Knoten außer der Wurzel haben mindestens ⌈m/2⌉ Kinder. In einem nicht leeren Baum hat die Wurzel mindestens 2 Kinder.

• Jeder innere Knoten hat h¨ochstens m Kinder. Ein Knoten mit k Kindern speichert k − 1 Schlusselwerte. ¨

• Alle Schlusselwerte eines Knotens sind aufsteigend sortiert. ¨

• Seien k1, . . . , ks die Schlussel eines inneren Knotens. Dann gibt es die Zeiger ¨ z0, z1, . . . , zs auf die Kinder und es gilt: z0 zeigt auf einen Teilbaum mit Werten kleiner als k1. zi fur ¨ i = 1, . . . ,s − 1 zeigt auf einen Teilbaum mit Werten gr¨oßer als ki und kleiner als ki+1. zs zeigt auf einen Teilbaum mit Werten gr¨oßer als ks .

Spezieller baum wo die Kinder größer oder kleiner sind als die wurzel

Ein Min-Heap hingegen hat die Eigenschaft, dass der Wert des Elternknotens immer kleiner oder gleich den Werten seiner Kinderknoten ist. Das bedeutet, dass das kleinste Element im Heap sich immer an der Wurzel befindet.

Ein Max-Heap hat die Eigenschaft, dass der Wert des Elternknotens immer größer oder gleich den Werten seiner Kinderknoten ist. Das bedeutet, dass das größte Element im Heap sich immer an der Wurzel (der obersten Ebene) des Baums befindet.