Algorithmen & Datenstrukturen

- Ein Algorithmus ist ein präzise festgelegtes Verfahren zur Lösung eines Problems; genauer gesagt von einer Problem-Klasse beinhaltend (unendlich) viele gleichartige Probleme. 

- Etwas salopp: Algorithmus = Lösungsverfahren (Rezept, Anleitung) 

- Probleme bzw. Problem-Klassen , die mit Algorithmen gelöst werden können, heissen (berechenbar)

- 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)