Algorithmen & Datenstrukturen

- Es gibt Referenzen auf das erste (-> head) und das letzte (-> tail) Element in der Liste
- Jedes Element kennt seinen direkten Vorgänger und Nachfolger

(siehe Bild)

Da wir keinen direkten Zugriff haben (sondern nur sequenziell) beträgt der Aufwand für die Suche eines Elementes in einer Liste grundsätzlich O(n).
- Unabhängig davon ob sortiert oder unsortiert.
- Unabhängig davon ob einfach oder doppelt verkettet.

Ja, die Suche lässt sich bei sortierten Listen mit zusätzlichen Hilfsmitteln (-> Skiplisten) beschleunigen.

Damit wird ebenfalls O(log n) möglich

Einfach verkettete Liste:

Da wir mit dem Head eine Referenz auf das erste Element haben, können neue Element am Anfang einfach und schnell eingefügt werden. Der Aufwand beträgt: O(1)

Bei doppelt verketteter Liste:

Analog kann zusätzlich auch am Ende der Liste (tail) mit Aufwand O(1) eingefügt bzw. angehängt werden.

Wir müssen sequenziell die richtige Position (B) suchen und ein neues Element einfügen, das Verschieben der restlichen Elemente entfällt hingegen! Der Aufwand ist trotzdem: O(n)

Aufwand für einfach und doppelt verkettete Liste identisch

Wir müssen sequenziell das gewünschte Element suchen und es aus der Liste entfernen. Auch hier ist kein Nachrücken von Elementen notwendig. Aufwand (bedingt durch Suche): O(n)

Aufwand ist für einfach und doppelt verkettet Liste identisch

Eine Klasse repräsentiert die Liste selber
- Enthält die Referenz auf das erste Element (head).
- Hilfsattribute z.B. für Anzahl enthaltene Elemente.
- Methoden für die verschiedenen Operationen

Eine zweite Klasse repräsentiert die Elemente und wird häufig als Knoten, Element oder Node bezeichnet.
- Enthält je nach Listentyp (einfach/doppelt) ein oder zwei Referenzen auf den Vorgänger bzw. den Nachfolger.
- Enthält Attribut(e) für die eigentlichen, enthaltenen Daten

Bei der Implementation mit Java kann das Datenattribut generisch sein und somit für beliebige Typen parametrisiert werden

Da jeder Node (Element) eine Referenz auf den Nachfolger (next) hält, resultiert eine rekursive Beziehung auf den selben Typ.

- Modell enthält einen Zyklus

Je eine auf seinen unmittelbaren Vorgänger (prev) und seinen Nachfolger (next)

Der Hauptvorteil von Listen ist, dass sie dynamisch sind:

Sie können eine beliebige Datenmenge aufnehmen, belegen selber aber keinen «festen» Platz, sondern wachsen und schrumpfen mit der Datenmenge mit.

- prädestiniert für (sehr) grosse, stark variierende Datenmengen

- Der Aufwand für das reine Einfügen in eine Liste ist an jeder beliebigen Position (sofern man diese bereits gefunden hat!) konstant (und schnell)

- Listen sind als Datenstrukturen objektorientiert implementiert, unterstützen Generics, und können dank der vorhandenen Interfaces je nach Anwendungsfall in spezifischen Implementationen eingesetzt / ausgetauscht werden

Der Stack ist eine Datenstruktur, der die Element als «Stapel» speichert:
- push(E e): Neue Elemente werden immer oben auf den Stapel abgelegt.
- E pop(): Es kann jeweils nur das oberste Element entnommen werden

LIFO - Last In First Out

Tellerstapel

- Datenablage bei Funktionsaufrufen
- Umkehren der Reihenfolge

(siehe Bild)

(siehe Bild)

(siehe Bild)

Wir haben also die Wahl!
(Nebenbei: Array-Variante ist auch dynamisch implementiert!)

- Berechnung des grössten gemeinsamen Teilers (ggT) für zwei beliebige natürliche Zahlen.
- Zeichnen der Verbindungslinie, welche zwei Punkte verbindet.
- Sortierung von zufällig vorliegenden ganze Zahlen.
- Finden des kürzesten Weges zwischen zwei Knoten in einem zusammenhängenden Graphen.
- Entscheiden, ob es sich bei einer vorliegenden natürlichen Zahl um eine Primzahl handelt.
- Berechnung des Integrals bei vorliegenden Funktionswerten in einem bestimmten Bereich.
- Finden einer Lösung in einem vorgegebenen Lösungsraum.

- schrittweises Verfahren
- ausführbare Schritte 
- eindeutiger nächster Schritt (determiniert)
- endet nach endlich vielen Schritten (terminiert)

- arbeitet schrittweise, gemäss Programm

- Anweisung für Anweisung, jede Anweisung korrespondiert mit einem ausführbaren Befehl

- arbeitet präzise und schnell

- Algorithmentheorie: Guter Lösungsalgorithmus für bestimmte Problemstellung?

- Komplexitätstheorie: Ressourcenverbrauch von Rechenzeit und Speicherbedarf?

- Berechenbarkeitstheorie: Was ist mit einer Maschine grundsätzlich lösbar bzw. nicht lösbar?

Eine Datenstruktur ist ein Konzept zur Speicherung und Organisation von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung möglichst effizient zu ermöglichen. Datenstrukturen sind daher insbesondere auch durch die Operationen charakterisiert, welche Zugriff und Verwaltung realisieren.

Beispiele: 

Array: direkter Zugriff (+), fixe Grösse (-)
Liste: flexible Grösse (+), sequentieller Zugriff (-)

Bei vielen Algorithmen hängt der Ressourcenbedarf, d.h. sowohl die benötigte Laufzeit als auch der Speicherbedarf, von der Verwendung geeigneter Datenstrukturen ab.

Algorithmen operieren auf Datenstrukturen und Datenstrukturen bedingen spezifische Algorithmen. Beides ist untrennbar miteinander verbunden!

- Adäquat für kleine Probleme? Adäquat für grosse Probleme?
- Selber entwickeln oder aus Bibliothek wählen?
- Einfach zu verstehen, zu implementieren, zu warten oder schwierig?
- Schneller Algorithmus mit grossem Speicherbedarf oder umgekehrt?

Extrembeispiel: Ist n eine Primzahl, ja/nein?
- Prüfen, ob n durch 2, 3, 4, 5, 6, … , sqrt(n) ganzzahlig teilbar. Wenig Speicher, lange Rechenzeit
- Alle Primzahlen 2, 3, 5, 7, 11, … im Voraus in einer Tabelle abspeichern. Viel Speicher, schnell (natürlich kann man dies praktisch nur für eine endliche Anzahl Primzahlen tun)

Ermittlung des grössten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen A und B:

(siehe Bild)

(siehe Bild)

(siehe Bild)

1. Beispiel (ohne Modulo): weniger optimiert
2. Beispiel (mit Modulo): optimiert

(siehe Bild)

- Alle Implementierungen basieren auf Euklid.
- unterschiedliche Ansätze: Schleifen vs. Rekursion
- "Abkürzungen": Modulo-Operation anstelle x-mal A-B
- unterschiedliche Anzahl Schleifendurchläufe
- Ausführungsgeschwindigkeit
- unterschiedliche Anzahl Methodenaufrufe
- unterschiedlicher Speicherbedarf
- Alle Implementierungen liefern die gleichen Resultate (gemäss Testing).
- Alle Implementierungen sind gleichwertig.

Dies bedeutet, dass es kein Java-Programm geben kann, das den Quellcode von zwei Implementationen einliest und feststellt, ob sie gleichwertige Algorithmen repräsentieren oder nicht!

- Komplexität (auch Aufwand oder Kosten) eines Algorithmus: 
Ressourcenbedarf = f (Eingabedaten). D.h. «Wie hängt der Ressourcenbedarf von den Eingabedaten ab?»

- Ressourcenbedarf: 
Rechenzeit -> Zeitkomplexität, Speicherbedarf -> Speicherkomplexität

- Eingabedaten: 
Grösse der Datenmenge (z.B. 100 vs. 1'000'000'000 zu sortierende Elemente), Grösse eines Datenwertes (z.B. 10! vs. 1'000'000'000!)

- Bleibt der Ressourcenbedarf gleich, wenn wir den ggT von zwei sehr grossen Zahlenwerten berechnen wollen?

- Verdoppelt oder vervierfacht sich der Ressourcenbedarf für das Sortieren der doppelten Datenmenge?

Der exakte / absolute Ressourcenbedarf!

-  Z.B., die ggT-Berechnung von 1’000’000’489 und 9’123’000’124 auf dem Computer XY mit der Konfiguration Z dauert 0.42 Sek.

- Vgl., solche Rechenzeiten sind für jeden Computer anders. Möchte man die Rechenzeit reduzieren, so lässt sich jederzeit ein schnellerer Computer kaufen! (bessere Hardware)

(siehe Bild)

(siehe Bild)

Die Big-O-Notation (landau’sches Symbol) bringt zum Ausdruck, dass eine Funktion f(n) höchstens so schnell wächst wie eine andere Funktion g(n). g(n) ist die obere Schranke für f(n).