Datenstrukturen und Algorithmen

nach dem ersten Teilen der Folge: noch n/2 Elemente
nach dem zweiten Schritt: n/4 Elemente
nach dem dritten Schritt: n/8 Elemente

\(1 = \frac{n}{2^i} \rightarrow 2^i=n \rightarrow \log_2(2^i)=\log_2n \rightarrow i=\log_2n\)

• Datenstruktur mit beschränktem Zugriff
• 3 Methoden
• push: legt das Objekt als obersts Element auf dem Stack ab
• pop: nimmt das oberste Element vom Stack und gibt es zurück
• top (bzw. peek): gibt das oberste Element des Stacks zurück ohne es zu entfernen
• Außerdem: isEmpty: liefert true, wenn keine Element auf dem Stack liegen, andernfalls false

• FIFO-Prinzip
• Einfache Datenstruktur mit beschränktem Zugriff mit 3 Methoden
• enter (bzw. enqueue): fügt das Objekt zur Warteschlange hinzu
• leave (bzw. dequeue): nimmt das "älteste" Element aus der Warteschlange heraus und gibt es zurück
• front (bzw. peek): liefert das "älteste" Element aus der Warteschlange, ohne es zu entfernen
• Außerdem: isEmpty: liefert true, wenn kein Element und false falls Elemente in der Warteschlange

• Array muss mit einer festen Größe intialisiert werden (wenn die Kapazität erschöpft, dann neues größeres Array erstellen und Umkopieren der Elemente)
• Zeiger auf die "Spitze des Stacks" notwendig

Gilt für Stack und Queue:

• void addFirst(Object obj): fügt das Objekt obj als erstes Eleemnt in die Liste ein
• Object getFirst(): liefert das erste Element der Liste
• Object removeFirst(): entfern das erste Element der Liste udn gibt es gleichzeitig als Ergebnis zurück
• void addLast(Object obj): hängt das Objekt obj als letztes Element an die Liste an
• Object getLast(): liefert das letzt Element der Liste
• Object removeLast(): entfernt das letzte Element der Liste und gibt es gleichzeitig als Ergebnis zurück

\(\begin{matrix} \underline{Umsetzung} & \underline{Operation} & \underline{Komplexit \ddot a t} \\ \textbf{ArrayList} & \\ & addFirst & \mathcal{O}(1)\\ \ & getFirst & \mathcal{O}(1)\\ & removeFirst & \mathcal{O}(1)\\ \textbf{Linked List} \\ & addFirst & \mathcal{O}(n) \\ & getFirst & \mathcal{O}(n)\\ & removeFirst & \mathcal{O}(n)\\ \textbf{DoubleLinkedList} \\ & addFirst & \mathcal{O}(1) \\ & getFirst & \mathcal{O}(1) \\ & removeFirst & \mathcal{O}(1)\\ \end{matrix}\)

Der Speicherplatzbedarf des Arrays ist vorgegeben durch die Größe des Arrays und nicht durch die Anzahl der Elemente.  Operationen für Queue und Stack sind effizient mit doppelt verketteter Liste umzusetzen.

• boolean hasNext() prüft, ob noch weitere Elemente in der Kollektion verfügbar sind
• Object next() liefert das aktuelle Element zurück und setzt den internen Zeiger des Iterators auf das nächste Element
• void remove() erlaubt es, das zuletzt von next() gelieferte Element zu löschen
• Implementiert als Interface

Ein Sortierverfahren heißt stabil, wenn es die relative Reihenfolge gleicher Schlüssel beibehält.

Ansatz: Suche das größte Element und setze es an das Ende der Folge: fahre dann mit der um 1 kleineren Liste fort. 

\( Eingabe: \ zu \ sortierende\ Folge \ F \ der \ L \ddot a nge\ n \\ p := n; \\ \textbf{while} \ p > 0 \ \textbf{do} \\ \ \ \ \ \ \ g := Index\ des\ größten\ Elementes\ aus\ F \\ \ \ \ \ \ \ im\ Bereich\ 1…p; \\ \ \ \ \ \ \ Vertausche\ Werte\ von\ F[p]\ und\ F[g]; \\ \ \ \ \ \ \ p := p − 1 \\ \textbf{od} \)

1. Starte mit der ersten Karte des Stapels einen neuen Stapel.

2. Nimm jeweils nächste Karte des Originalstapels: Füge diese an der richtigen Stelle in den neuen Stapel ein. 

\(Eingabe: \ zu\ sortierende\ Folge\ F\ der \ L \ddot a nge\ n \\ \textbf{for}\ i := 1\ \textbf{to}\ n-1\ \textbf{do} \\ m := F[i]; \\ /* \ zu\ merkendes\ Element\ */ \\ j := i; \\ \textbf{while}\ j > 0 \ \textbf{do} \\ \textbf{if} \ F[ j − 1] > m \ \textbf{then} \\ /* Verschiebe\ F[ j − 1] \ nach\ rechts */ \\ F[ j] := F[ j − 1]; \\ j := j − 1 \\ \textbf{else} \\ Verlasse\ innere\ Schleife \\ \textbf{fi;} \\ F[ j] := m /* j \ zeigt \ auf \ Einf \ddot u geposition\ */ \\ \textbf{od;} \\ \textbf{od;} \\\)

Ein Iterator ist eine Art Mischung aus Zeiger und Datenstrom, das bei einer ArrayList oder einer LinkedList Verwendung findet. Der Zugriff erfolgt sequentiell, d.h. ein Iterator kann nicht zurückspringen. Ein Iterator-Objekt wird mittels der Methode iterator() erzeugt. Dessen Methode hasNext() liefert true, solange der Iterator noch nicht das Ende der Collection erreicht hat. Mit next() greift man auf das jeweils nächste Element zu. 

Generics sind parametrisierte Datentypen, die dem Programmier eine Typsicherheit bieten und als Platzhalter an Stelle eines konreten Datentypen dienen können. Sie werden mit spitzen Klammern eingeführt: Objetc<Generics> object. Generics selbst können nochmal typisiert werden (mit weiteren spitzen Klammern im Generics Codeteil).

Bester Fall: \(\mathcal{O}(n)\) (linear), weil ein Durchlauf \(n-1\) Durchgänge und Best Case nur bei sortierten Reiehenfolgen
schlechtester Fall: \(\frac{n \cdot (n-1)}{2} \approx \frac{n^2}{2} = \mathcal{O}(n^2)\) Liste ist im worst case falsch rum sortiert, deswegen muss \(n-1\) durchgelaufen werden und \(n-1\) und Rückwegfaktor von \(n-1\)
Durchschnitt (erfolgreiche Suche): \(\frac{n^2}{4} = \mathcal{O}(n^2)\), unsortiert und Einfügeposition irgendwo in der MItte, d.h. \(n-1\) Durchlauf und \(\frac{n-1}{2}\) Rückweg. 

Es werden immer jeweils zwei benachbarte Elemente vertauscht, wenn sie nicht in der richtigen Reihenfolge sind. Die Folge wird mehrmals sequenziell durchlaufen bis alle Elemente sortiert sind.

Eingabe: zu sortierende Folge F der Länge n 

\(\textbf{do} \\ \ \ \ \ \textbf{for}\ i := 0 \ \textbf{to}\ n – 2\ \textbf{do} \\ \ \ \ \ \ \ \ \ \ \textbf{if}\ F[i] > F[i + 1]\ \textbf{then}\ \\ \ \ \ \ \ \ \ \ \ \ \ Vertausche\ Werte\ von\ F[i]\ und\ F[i + 1] \\ \ \ \ \ \ \ \ \ \ \textbf{fi}\\ \ \ \ \ \textbf{od}\\ Until\ keine\ Vertauschung\ mehr\ aufgetreten \)

 Bester Fall: \(n\)  
  Durchschnittlicher Fall: normal:  \(n^2\)  optimiert:  \(\frac{n^2}{2}\)
Schlechtester Fall:  normal: \(n^2\)   optimiert:  \(\frac{n^2}{2}\)
 

Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die sortierten kleinen Listen werden dann im Reißverschlussverfahren zu größeren Listen zusammengefügt (engl. (to) merge), bis wieder eine sortierte Gesamtliste erreicht ist.

  Eingabe: eine zu sortierende Folge F

  Ausgabe: eine sortierte Folge F_S 

\(\textbf{if} \ F \ einelementig \ \textbf{then} \\ \ \ \ \ \ \textbf{return} \ F \\ \textbf{else} \\ Teile \ F \ in \ F_1 \ und \ F_2 ; \\ \ \ \ \ \ F_1 := MergeSort (F_1 ); \\ \ \ \ \ \ F_2 := MergeSort (F_2 ); \\ \ \ \ \ \ \textbf{return} \ Merge (F_1 , F_2 ) \\ \textbf{fi} \)

Weiter:

\(F := leere \ Folge; \\ \textbf{while} \ F_1 \ oder \ F_2 \ nicht \ leer \ \textbf{do} \\ \ \ \ \ \ Entferne \ das \ kleinere \ der \ Anfangselemente \\ \ \ \ \ \ aus \ F_1 \ bzw. \ F_2 ; \\ \ \ \ \ \ F \ddot u ge\ dieses\ Element\ an\ F\ an \\ \textbf{od;} \\ F \ddot u ge\ die\ verbliebene\ nichtleere\ Folge\ F_1\ oder \\ \ \ \ \ F_2 \ an\ F\ an; \\ \textbf{return} \ F \)

Aus einer unsortierten Folge wird ein beliebiges so genanntes Pivot-Element gewählt. Die unsortierte Folge wird von links sequenziell durchsucht auf Elemente die größer oder gleich dem Pivot-Element sind und nochmal von rechts auf Element die kleiner dem Pivot-Element sind. Erfüllen die Element die Bedingungen werde sie in eine größer-gleich und kleiner-gleich Liste aufgeteilt, in denen wiederrum jweils zwei Pivot Elemente gewählt werden. Sind nur noch 1-elementige Teilliste vorhanden, werden die Teillisten wieder zusammengefügt, in dem jeweils das erste Element der Teilliste mit Elementen der anderne auf Sortierung untersucht werden.  

 Eingabe: eine zu sortierende Folge F, 
  die untere und obere Grenze u, o 

\(\textbf{if} \ o > u \ \textbf{then} \\ \ \ \ \ Bestimme\ Position\ p\ des\ Pivot-Elements; \\ \ \ \ \ pn := Zerlege(F, u, o, p); \\ \ \ \ \ QuickSort (F, u, pn-1); \ /* pn\ ist\ neue\ Pivot-Position\ */ \\ \ \ \ \ QuickSort (F, pn+1, o) \\ \textbf{fi} \)

Der Zerlege-Algorithmus:

Eingabe:  zu zerlegende Folge F, untere und obere Grenze u, o,  
  Position p des Pivot-Elements 
Ausgabe:  neue Positionen pn des Pivot-Elements 

\(pn := u; \\ pv := F[p]; \\ Tausche\ F[p]\ und\ F[o];\ /*\ Pivot-Element\ nach\ rechts\ */ \\ \textbf{for}\ i := u\ \textbf{to}\ o – 1\ \textbf{do} \\ \ \ \ \ \textbf{if}\ F[i]\ ≤ \ pv\ \textbf{then} \\ \ \ \ \ \ \ \ Tausche\ F[pn]\ und\ F[i]; \\ \ \ \ \ \ \ \ pn := pn + 1; \\ \ \ \ \ \textbf{fi} \\ \textbf{od;} \\ Tausche \ F[o] \ und \ F[pn];\ /* Pivot-Element\ zurück */ \\ \textbf{return} \ pn\\ \)

Die O-Notation ist die asymptotische obere Schränke für eine Aufwandsfunktion. 
Mathemetatisch: \(f(n) / g(n)\) ist für genügend große \(n\) durch eine Konstante \(c\) beschränkt, d.h.

\(f \ w \ddot a chst \ asymptototisch \ nicht \ schneller \ als \ g\)

\(f(n)= \mathcal{O}(g(n)):\Leftrightarrow \exists c,n_0 \ \forall n \geq n_0: f(n) \leq c \cdot g(n)\)

• Multiplikative Konstanten können weggelassen werden
• Basis des Logarithmus ist unerheblich, da Basiswechsel Multiplikation von Konstanten entspräche 
• Beschränkung auf höchsten Exponenten 

\(\begin{matrix} \underline{Komplexit \ddot a tsklasse} & \underline{Aufwand} & \\ \mathcal{O}(1) & konstant\\ \mathcal{O}(\log n) & logarithmisch\\ \ \mathcal{O}(n) & linear\\ \mathcal{O}(n \cdot \log n) & loglinear\\ \mathcal{O}(n^2) & quadratisch\\ \mathcal{O}(n^k) f \ddot u r \ k>1& polynomiell\\ \mathcal{O}(2^n) & exponentiell \\ \end{matrix}\)

\(\begin{matrix} \underline{Sortierverfahren} & \underline{Bester Fall} & \underline{Mittlerer Fall} & \underline{Schlechtester Fall} \\ \textbf{SelectionSort} & \mathcal{O}(n^2) & \mathcal{O}(n^2) & \mathcal{O}(n^2) \\ \textbf{InsertionSort} & \mathcal{O}(n) & \mathcal{O}(n^2) & \mathcal{O}(n^2) \\ \textbf{BubbleSort} & \mathcal{O}(n) & \mathcal{O}(n^2) & \mathcal{O}(n^2) \\ \textbf{MergeSort} & \mathcal{O}(n ⋅ \log n) & \mathcal{O}(n ⋅ \log n) & \mathcal{O}(n ⋅ \log n) \\ \textbf{QuickSort} & \mathcal{O}(n ⋅ \log n) & \mathcal{O}(n ⋅ \log n) & \mathcal{O}(n^2) \\ \end{matrix} \)

Laufzeit := max. Laufzeit der inneren Anweisung * Anzahl der Iterationen

Beispiel:
for i:= to n do
     a[i]:=0;
od

hat Komplexität n * O(1)= O(n)

Laufzeit : = Laufzeit der inneren Anweisung * Produkt der Größen aller Schleifen

Beispiel:

for i:= 1 to n do
     for j:= 1 to n do
         k:=k+1;
     od
od

hat Komplexität n * n * O(1) = O(n²)
 

Sequenzen werden addiert.

Laufzeit := Aufwand für Text + max(Aufwand für A₁, Aufwand für A₂)

Beispie.

if x< 100 then
      y := x;
else
     for i := 1 to n do
         if x > 100 then y := a[i] fi
     od
fi

hat Komplexität von O(n), da if Abfrage O(1)+max(y=x ist O(1), for..od O(n))=O(1)+O(n)=O(n)

\(1.\ f(n)=\mathcal{O}(f(n)) \\ 2. \ c ⋅ \mathcal{O}(f(n)) = \mathcal{O}(f(n)), \ c \ ist \ Konstante \\ 3.\ \mathcal{O}(f(n)) + \mathcal{O}(f(n)) = \mathcal{O}(f(n)) \\ 4.\ \mathcal{O}(f(n)) + \mathcal{O}(g(n)) = \mathcal{O}(max(f(n),g(n))) \\ 5. \ \mathcal{O}(\mathcal{O}(f(n))) = \mathcal{O}(f(n)) \\ 6.\ \mathcal{O}(f(n)) ⋅ \mathcal{O}(g(n)) = \mathcal{O}(f(n) ⋅ g(n)) \\ 7.\ \mathcal{O}(f(n) ⋅ g(n)) = f(n) ⋅ \mathcal{O}(g(n)) \)

Ein Baum besteht aus einer Menge von Knoten (engl. node) und einer Menge von Kanten (engl. edge) mit besonderen Eigenschaften:

• Jeder Baum besitzt einen ausgezeichneten Knoten genannt Wurzel (engl. root).
• Jeder Knoten (außer Wurzel) ist genau durch eine Kante mit seinem Elternknoten (auch Vaterknoten, direkter Vorgänger, engl. parent node) verbunden.
• Ein Knotne ohne Kinder heißt Blatt (engl. leaf), alle anderen Knoten bezeichnet man als Innere Knoten (eng. inner node)
• Die Länge des Pfades von der Wurzel zu einem Knoten wird als dessen Niveau bezeichnet.

Ein Baum, bei dem jeder Knoten höchstens zwei Kindknoten hat, heißt Binärbaum. Man spricht dabei vom linken und rechten Knd.

Ein Binärbaum heißt voll, wenn jeder Knoten entweder 0 (Blätter) oder 2 (innere Knote) Kinder hat. Ein voller Binäerbaum heißt vollständig, wenn alle Blätter auf derselben Ebene liegen.