Algorithmen und Datenstrukturen 3. Semester

Menge von Werten und zugeordneten Operationen, die unabhängig von ihrer Implementierung spezifiziert sind.

Vorteile:

- größere Verständlichkeit durch Abstraktion

- Austauschbarkeit der Implementierungen

- Wiederverwendbarkeit

Name

Schnittstelle (Operation 1, Operation 2, ...)

Invariante: relevante, stets (während der Durchführung der Operation darf sie kurz verletzt werden) geltende Eigenschaft, z.B. Sortiertheit der Elemente

- Erzeugung (eines leeren Exemplars)

- Sondierende Operationen (Sondierung des Zustands, ohne ihn zu verändern)

- Verändernde Operationen

- Erschaffende Operationen (Erschaffung eines weiteren Exemplars aus einem oder mehreren bestehenden Exemplaren)

- Zerstörung (Speicherfreigabe)

Vorbedingung: Eigenschaft, die vor Ausführung der Operation gelten muss

Nachbedingung: Eigenschaft, die nach Ausführung der Operation zugesichert wird

Zustand einer Datenstruktur: zur Beschreibung der Wirkung einer Operation

- Linare Datenstrukturen: Arrays, einfach und doppelt verkettete Listen

- Graphen: als Adjazenzmatrizen oder -listen

- Bäume: Binärbäume, n-äre Bäume

- Sequenz von n Elementen des gleichen Datentyps

- Ablage in zusammenhängenden Hauptspeicherbereichen

- Zugriff auf Elemente über Index

- Hauptvorteil: Elementzugriff in konstanter Zeit

- Hauptnachteil: feste Größe

- Folge von beliebig vielen Listenelementen bestehend aus Datenfeld und Next-Zeiger

- Ablage der Elemente verteilt im Hauptspeicher

- Zugriff auf Liste erfolgt über Head-Zeiger

- Listenende durch leeren Next-Zeiger (null) markiert

- Hauptvorteil: flexibles Wachsen (oder Schrumpfen)

- Hauptnachteil: größerer Speicherbedarf durch Zeiger, langsamer

- wie einfach verkettete Liste, zusätzlich noch Zeiger auf vorheriges Listenelement

- Prev-Zeiger des ersten Elementes ist null

- Hauptvorteil: teilweise effizientere Operationen als einfach verkettete Liste

- Hauptnachteil: noch größerer Speicherbedarf als einfach verkettete Liste

informell: Punkte (Knoten) in der Ebene, die durch Liniensegmente (Kanten) verbunden sein können.

formell: Graph G (V,E) mit V= {v₁, v₂, ... , v_n} als nicht-leere, endliche Menge von Knoten und E= {e₁, e₂, ... , e_n} als endliche Menge von Kanten der Form (v_i, v_j)

ungerichtete Kanten = Linien, kein Unterschied zwischen Kante (u,v) und (v,u) - u und v sind benachbart (adjazent)

gerichtete Kanten = Pfeile, Unterschied zwischen (u,v) und (v,u) - für (u,v) ist v adjezent zu u

Schleife: Kante von einem Knoten auf sich selbst, nach Definition erlaubt

Mehrfachkanten: mehrere Kanten zwischen denselben Knoten, nach Definition nicht erlaubt, falls benötigt --> Erweiterung zu Multigraphen

vollständiger Graph: alle erlaubten Kanten vorhanden

dichter Graph: nur wenige fehlende Kanten

lichter Graph: nur wenige Kanten vorhanden

- boolesche n x n Matrix

- Wert an (i,j) besagt, ob Kante von i nach j existiert

- jeder Knoten besitzt eine verkettete Liste

- Listenelemente sind die zum Knoten adjazenten Knoten

- Zuordnung von Zahlenwerten zu den Kanten

- Werte repräsentieren eine Größe des Anwendungsbereiches (z.B. Dauer)

- Übernahme der Werte in die Adjazenz-Liste oder -Matrix

- Pfad: Folge von adjazenten Knoten

- einfacher Pfad: jeder Knoten taucht nur einmal auf

- Pfadlänge: ungewichtet = Anzahl der Kanten im Pfad, gewichtet = Summe der Kantengewichte

stark zusammenhängend: alle Knotenpaare sind verbunden

schwach zusammenhängend: zugrundeliegender ungerichteter Graph ist verbunden

Maximalgroße zusammenhängende Teilgraphen des Graphen

Zyklus: Pfad von einem Knoten zu sich selbst

- positive Pfadlänge

- keine Kante wird mehrmals durchlaufen

Ein Baum ist ein ungerichteter, zusammenhängender, zyklenfreier Graph.

- Auszeichnung eines Knotens als Wurzel

- Vorteile: Pfadrichtung zur Wurzel weg oder hin; eindeutige, einfache Pfade zwischen Wurzel und allen anderen Knoten

Vorgänger: alle Knoten auf dem Pfad von v zur Wurzel

Nachfolger: alle Knoten (außer v), deren Pfade zur Wurzel den Knoten v enthalten

direkter Vorgänger: der erste Knoten auf dem Pfad zur Wurzel

direkte Nachfolger: alle Knoten, die v als Elternknoten besitzen

Geschwisterknoten: alle Knoten mit demselben Elternknoten wie v

Blätter: Knoten ohne Nachfolger

Tiefe eines Knotens: Länge des einfachen Pfades von v zur Wurzel

Höhe des Baumes: Länge des längsten einfachen Pfades von der Wurzel zu einem Blatt

Ebene i des Baumes: alle Knoten, bei denen die Länge des einfachen Pfades von der Wurzel zu ihnen den Wert i besitzt

Grad eines Knotens: Anzahl der direkten Nachfolger von v

Grad n eines Baumes: maximaler Grad aller Knoten eines Baumes

- sortierter Binärbaum (Wurzelbaum mit dem Grad 2)

- Wert aller linken Nachfolger <= Wert des Knotens

- Wert aller rechten Nachfolger > Wert des Knotens

- Korrektheit

- Laufzeiteffizienz

- Speicherplatzeffizienz

- Optimalität

Wie oft wird die Basisoperation des Algorithmus ausgeführt?

Basisoperation: Operation, die am stärksten zu der Laufzeit des Algorithmus beiträgt (Ausführungsanzahl von Eingabegröße abhängig)

Laufzeit T in Abhängigkeit von Eingabegröße n: T(n) ≈ Ausführzeit Basisoperation * Ausführungsanzahl C(n)

NICHT der Durchschnitt aus best und worst case!

Annahmen über die Beschaffenheit und Wahrscheinlichkeit von "typischen" Eingaben notwendig

Anzahl zusätzlich benötigter Speicherplätze

Ansatz, um konstante Faktoren und Besonderheiten bei kleinen Eingabegrößen ausblenden zu können.

Groß-O-Funktion von g(n): Klasse der Funktionen f(n), die nicht schneller als g(n) wachsen.

Groß-Theta-Funktion von g(n): Klasse der Funktionen f(n), die gleich schnell wie g(n) wachsen

Groß-Omega-Funktion von g(n): Klasse der Funktionen f(n), die mindestens so schnell wie g(n) wachsen

Falls lim f(n) = unendlich und lim g(n) = unendlich sowie f´(n) und g´(n) existieren, dann gilt:

lim (f(n)/g(n)) = lim (f´(n)/g´(n))

Formel zur Abschätzung der Fakultät

n! ≈ \(\sqrt{2 \pi n} ( \frac n e)^n\)

Jede Exponentialfunktion beschränkt jedes Polynom: n^k = O(rⁿ)

Jedes (nicht-konstante) Polynom beschränkt jede Logarithmus-Funktion: log_r n = O(n^k)

Die Wurzelfunktion ist linear beschränkt: \(\sqrt{n}\) = O(n)

f₁(n) = O(g(n)) und f₂(n) = O(h(n))

Summenformel: f₁(n) + f₂(n) = O( max(g(n), h(n)) )

Produktregel: f₁(n) * f₂(n) = O(g(n)*h(n))

O(1) = konstant

O(log n) = logarithmisch

O(n) = linear

O(n * log n) = überlogarithmisch

O(n²) = quadratisch

O(n³) = kubisch

O(kⁿ) = exponentiell

O(n!) = faktoriell