Überblick

Mitarbeiter

Prof. Dr. Stefan Bosse, Praktische Informatik (Vorlesung und Übung)

Verteilte Künstliche Intelligenz & Sensornetzwerke

Betriebssysteme & Virtualisierung

Technische Systeme

WiMi Lucas Böltz (Übung)

Formale Methoden und Theoretische Informatik

HiWi Valerie Simon, Lynx Petry Pacheco (Übung)

Aufbau der Veranstaltung

Vorlesungen

Mittwoch 10-12 Uhr (Hauptstrang, Grundlagen)

Donnerstag 12-14 Uhr (Besondere Themen, wie z.B. Numerik)

Übungen

Dienstags 14-16 Uhr

Donnerstags 14-16 Uhr

Freitags 10-12 Uhr

Übungsformat

Notebooks: Alle Übungen sind digital und werden im Web Browser bearbeitet (lokal, ggfs. off-line). Die Inhalte einer Übungseinheit werden als Datei im JSON Format gespeichert und hochgeladen.

Leistungskriterien

Übungen

Bearbeitung der Übungseinheiten in Einzelarbeit (in Gruppe)

Abgabe eines Übungszettels in digitaler Form als Gruppe

Klausur

Inhalte

Einführung in Komplexität und Effizienz, Grundlagen

Numerische Algorithmen

Abstrakte Datentypen

Arrays und Tabellen

Datenbanken und Datenorgansation

Sortierverfahren

Warteschlange und Stapelspeicher

Listen

Bäume

Graphen

Einführung in Algorithmen und Datenstrukturen

Algorithmen

Datenstrukturen

Laufzeit und Komplexität

                                             ――――┐
┌――――――――――┐                                     │
│Problem   │   ┌―――――――――――――┐   ┌――――――――――┐    │
├――――――――――┼――▶│Algorithmus A├――▶│Programm A│    │
│Aufgabe   │   └―――――――――――――┘   └――――――――――┘    │ Programmier-
└――――――――――┘   ┌―――――――――――――┐   ┌――――――――――┐    │ sprachen
      ┌――――――――┤Algorithmus B├――▶│Programm B│    │
      │        └――――――┬――――――┘   └―――――┬――――┘    │
┌―――――┴――――┐          │     Messen?    │         │
│Daten-    │          ▼                ▼     ――――┘
│struktur 1│   ┌――――――――――――――――――――――――――――┐
└――――――――――┘   │  Komplexität / Effizienz ? │
┌――――――――――┐   └――――――――――――――――――――――――――――┘
│Daten-    │
│struktur 2│
└――――――――――┘

Literatur

Algorithmen und Datenstrukturen&br;Thomas Ottman&br;Peter Widmayer&br;Spektrum Verlag

Algorithmen und Datenstrukturen&br;Eine Einführung in Java&br;Gunter Saake, Kai Uwe Sattler&br;dpunkt Verlag

Historischer Überblick: Algorithmen

300 v. Chr.

Euklids Algorithmus zur Bestimmung des ggT (beschrieben im 7. Buch der Elemente), also des größten gemeinsamen Teilers, mit dem etwa ggT(300, 200) = 100 sehr effizient berechnet werden kann, ist die erste Beschreibung eines Verfahrens, das modernen Kriterien für Algorithmen gerecht wird.

800 n. Chr.

Der persisch-arabische Mathematiker Muhammed ibn Musa abu Djafar alChoresmi (oft auch als »al Chworesmi« oder »al Charismi« geschrieben) veröffentlicht eine Aufgabensammlung für Kaufleute und Testamentsvollstrecker, die später ins Lateinische als Liber Algorithmi übersetzt wird.

Das Wort Algorithmus ist ein Kunstwort aus dem Namen dieses Mathematikers und dem griechischen »arithmos« für Zahl.

1574

Adam Rieses Rechenbuch verbreitet mathematische Algorithmen in Deutschland.

1614

Die ersten Logarithmentafeln werden algorithmisch berechnet – ohne Computer dauerte dies 30 Jahre!

1703

Binäre Zahlensysteme werden von Leibnitz eingeführt. Diese Zahlensysteme bilden die Grundlage der internen Verarbeitung in modernen Computern.

1815

Augusta Ada Lovelace, die erste »Computer-Pionierin«, wird geboren. Sie entwickelt schon früh Konstruktionspläne für verschiedenartige Maschinen, wird Assistentin von Babbage und entwirft Programme für dessen erste Rechenmaschinen.

1822

Charles Babbage entwickelt die sogenannte Difference Engine, die in einer verbesserten Version 1833 fertiggestellt wird. Später entwickelt er auch die Analytical Engine, die bereits die wichtigsten Komponenten eines Computers umfasst, aber niemals vollendet wird.

1931

Gödels Unvollständigkeitssatz beendet den Traum vieler damaliger Mathematiker, die gesamte Beweisführung aller Sätze in der Mathematik mit algorithmisch konstruierten Beweisen durchzuführen.

1936

Die Church’sche These vereinheitlicht die Welt der Sprachen zur Notation von Algorithmen, indem für viele der damaligen Notationen die gleiche Ausdrucksfähigkeit postuliert wird.

danach

Mit der Realisierung der ersten Computer erfolgte natürlich der Ausbau der Algorithmentheorie zu einem eigenen Wissenschaftsgebiet.

Auch für den Bereich der Datenstrukturen können lang zurückreichende Wurzeln gefunden werden, etwa das Indexierungssystem historischer Bibliotheken.

Praktische Eigenschaften von Algorithmen

Bausteine für Algorithmen

Die Basiselemente sind die elementaren Operationen, die ausgeführt werden.

Das Hintereinanderausführen von Schritten bezeichnet man als sequenzielle Ausführung.

Die parallele Ausführung hingegen bedeutet das gleichzeitige Ausführen von Schritten.

Eine bedingten Ausführung ist ein Schritt, der nur ausgeführt wird, wenn eine bestimmte Bedingung erfüllt wird.

Die Schleife ist eine Wiederholung von Anweisungen, bis eine vorgegebene Endbedingung erfüllt wird ⇒ Terminierungskriterium!

Konzept des Unterprogramms: Funktionen und Funktionsrekursion.

Daten! Rekursion gibt es bei Funktionen und Daten!

Algorithmen verarbeiten Daten. Daten müssen wie Algorithmen strukturiert werden. Daher der Name dieser Veranstaltung.

Formale Beschreibung von Algorithmen

Ein Algorithmus beschreibt eine Abbildung:

image-placeholder
(2-1)

mit

E

Menge der zulässigen Eingabedaten.

A

Menge der Ausgabedaten.

Aber: Nicht jede Abbildung f: E → A lässt sich durch einen Algorithmus realisieren (Berechenbarkeit!)

Formale Eigenschaften von Algorithmen

Welche formalen Eigenschaften von Algorithmen werden studiert?

Die wichtigste formale Eigenschaft eines Algorithmus ist zweifellos dessen Korrektheit!

Dazu muss gezeigt werden, dass der Algorithmus die jeweils gestellte Aufgabe richtig löst.

Aber kann die Korrektheit (d.h. Fehlerfreiheit) eines Algorithmus oder besser dessen Implementierung mit einer Programmiersprache überhaupt bewiesen werden? Uff.

Die zweite wichtige formale Eigenschaft eines Algorithmus ist dessen Effizienz.

Da sieht es hier schon besser aus. Effizienz ist messbar, Korrektheit nicht.

Wir müssen zwischen Algorithmen (also Berechungsvorschriften) und deren Implementierung mit einer Programmiersprache unterscheiden. Welche Programmiersprachen und Programmiermodelle?

Programmiersprachen und Programmiermodelle

Algorithmen werden mit Programmiersprachen implementiert (Handwerkzeug)

Es gibt verschiedene Programmiermodelle und Klassen:

Funktionaler Programmierung (mathematisch, zustandslos, z.B. Haskell, ML, LISP, OCAML)

Prozedurale und imperative Programmierung (C, ggfs. JavaScript, Fortran)

Objektorientierte Programmierung (Java, ggf, JavaScript und Python)

Deklarative (deduktive) und logische Programmierung (Prolog)

Laufzeit und Komplexität

Die Laufzeit ist messbar, die Rechenkomplexität nur bestimmbar/ableitbar!

Annahme: Einheitsoperations (Addition, Wertzuweisung usw.)

Rechenkomplexität ist spezifisch für einen Algorithmus, nicht für eine Programmierung (da Laufzeit)

Rechnekomplexität bedingt auch eine Speicherkomplexität!

Speicherkomplexität meist einfacher abzuschätzen; aber

Nur statischer Datenspeicher lässt sich direkt aus den Ein- und Augabedaten ableiten

Dynamischer Speicherbedarf z.B. bei Funktionsaufrufen ist gesondert und dezidiert zu berechnen

Beispiel statischer und dynamischer Speichebedarf

D=[1,2,3,4,5,6,7,8,9,10] // N=10, |A|=10*B
sum=0
// Fall 1
for(i=0;i<D.length;i++) sum+=D[i]
// Fall 2
function dosum(i) {
  if (i>0) D[i]+dosum(i-1);
  return D[0]
}
sum=dosum(D.length-1)

Wo liegen die Unterschiede in Fall 1 und 2 beim Speicherbedarf bezogen auf N?

Fall 1

Rechenzeit (in Einheitsoperationen) ist N*k

Speicherbedarf (in Einheitszellen) ist N+k

Fall 2

Rechenzeit (in Einheitsoperationen) ist N*k

Speicherbedarf (in Einheitszellen) ist N+N*k

Messbarkeit von Effizienz

Nochmal wichtigste Eiegenschaften eines Algorithmus: Korrektheit und Effizienz

Man könnte beides durch Implementation des Algorithmus in einer konkreten Programmiersprache auf einem konkreten Rechner für eine Menge repräsentativ gewählter Eingaben messen.

Solche experimentell ermittelten Meßergebnisse lassen sich aber nicht oder nur schwer auf andere Implementationen und andere Rechner übertragen und sind nicht vollständig, sondern immer exemplarisch.

Nicht Test (oder Simulation) mit Nachweis von Korrektheit verwechseln! Das gibt nur Frust bei den Kunden und endlose Rückrufaktionen....

Man kann häufig dasselbe Problem durchaus mit verschiedenen Algorithmen lösen.

Das Ziel ist, den für ein Problem besten Algorithmus zu finden und zu implementieren.

Das verlangt insbesondere eine möglichst optimale Nutzung der Ressourcen Speicherplatz und Rechenzeit.

Beispiel: Ein von Jon Bentley behandeltes Problem

Gegeben sei eine Folge X von N ganzen Zahlen in einem Array. Gesucht ist die maximale Summe aller Elemente in einer zusammenhängenden Teilfolge. Sie wird als maximale Teilsumme bezeichnet, jede solche Folge als maximale Teilfolge.

───────────────────────────────────────────────
1    2    3    4    5    6    7    8    9    10    Index
───────────────────────────────────────────────
31   -41  59   26   -53  58   97  -93   -23  84   Zahlen
───────────────────────────────────────────────

Beispiel 2-1. Für die Eingabefolge X[1::10] ist die Summe der Teilfolge X[3::7] mit Wert 187 die Lösung des Problems.

Naives Verfahren (Vollständige Schleifeniteration)

maxtsumme = 0
for (u=0;u<N;u++) {
  for (o=u;o<N;o++) {
    // bestimme die Summe der Elemente in der Teilfolge X [ u : : o ]
    Summe = 0;
    for (i=u; i<=o;i++) Summe = Summe + X[i];
    // bestimme den größeren der beiden Werte Summe und maxtsumme
    maxtsumme = max (Summe, maxtsumme)
  }
}

Algorithmus 2-1. Naives Verfahren für die Suche nach der größten Teilsumme

Anzahl der Einheitsoperationen:

image-placeholder
(2-2)

/ide

size

Divide-and-Conquer (Zerlegung)

Jetzt folgen wir dem Divide-and-conquer-Prinzip (DaC) zur Lösung des Maximum-Subarray-Problems. Die Anwendbarkeit dieses Prinzips ergibt sich aus folgender Überlegung:

Wird eine gegebene Folge in der Mitte geteilt, so liegt die maximale Teilfolge entweder

ganz in einem der beiden Teile

oder sie umfaßt die Trennstelle, liegt also teils im linken und teils im rechten Teil.

Im letzteren Fall gilt für das in einem Teil liegende Stück der maximalen Teilfolge:

Die Summe der Elemente ist maximal unter allen zusammenhängenden Teilfolgen in diesem Teil, die das Randelement an der Trennstelle enthalten.

Warum Divide-and-Conquer?

DaC basiert auf Rekursion und rekursive Zerlegung eines Problems in kleine (elementare) Probleme.

Wir wollen die maximale Summe von Elementen, die das linke bzw. das rechte Randelement einer Folge von Elementen enthält, kurz das linke bzw. rechte Randmaximum nennen.

Das linke Randmaximum lmax für eine Folge X[l] ... X[r] ganzer Zahlen kann man in ungefähr (r-l) Schritten (also linear) wie folgt bestimmen:

lmax = 0
summe = 0
for (i=l;i<=r;i++) {
  summe = summe + X[i]
  lmax = max (lmax,summe)
}

Algorithmus 2-2.

Entsprechend kann man auch das rechte Randmaximum rmax für eine Folge ganzer Zahlen in einer Anzahl von Schritten bestimmen, die linear mit der Anzahl der Folgenelemente wächst.

function maxtsum (X) {
 // f liefert eine maximale Teilsumme der Folge X ganzer Zahlen g
  if (length(X)==1) {
    a=X[0]
    if (a > 0) result = a
    else result = 0
  } else {
   // Divide:
   // teile X in eine linke und eine rechte Teilfolge A und B annähernd gleicher Größe;
   j = floor(length(X)/2)
   A = slice(X,[0,j]); B=slice(X,[j+1,length(X)-1])
   // Conquer:
   maxtinA = maxtsum (A)
   maxtinB = maxtsum (B)
   // bestimme das rechte Randmaximum rmax ( A ) der linken Teilfolge A;
   // bestimme das linke Randmaximum lmax ( B ) der  rechten Teilfolge B;
   // Merge:
   result = max(maxtinA, maxtinB, rmax(A) + lmax (B))
  }
  return result
}

Algorithmus 2-3. Der gesamte DaC Algorithmus zur Suche der maximalen Teilsumme

Bezeichnet nun T(N) die Anzahl der Schritte, die erforderlich ist, um den Algorithmus maxtsum für eine Folge der Länge N auszuführen, so gilt offenbar folgende Rekursionsformel:

image-placeholder
(2-3)

Man erhält dann für die Größenordnung der Berechungen (also maxtsum Aufrufe) folgende asymptotische Näherung:

image-placeholder
(2-4)

Das ist schon viel besser als die Laufzeit des naiven Verfahrens.

Aber ist es bereits das bestmögliche Verfahren? Nein — denn die Anwendung eines weiteren algorithmischen Lösungsprinzips, des Scan-line-Prinzips, liefert uns ein noch besseres Verfahren.

Scan-line Verfahren (Abtastung)

Wir haben eine aufsteigend sortierte, lineare Folge von Inspektionsstellen (oder: Ereignispunkten), die Positionen 1...N der Eingabefolge.

Wir durchlaufen die Eingabe in der durch die Inspektionsstellen vorgegebenen Reihenfolge

Dabei führen wir zugleich eine vom jeweiligen Problem abhängige Information mit,

eine dynamisch veränderliche, d.h. an jeder Inspektionsstelle gegebenenfalls zu korrigierende Information.

Hier: die maximale Summe bisMax einer Teilfolge im gesamten bisher inspizierten Anfangsstück und das an der Inspektionsstelle endende rechte Randmaximum ScanMax des bisher inspizierten Anfangsstücks

Abbildung 2-1. Prinzip des aufsteigenden Scan-line Verfahrens mit den bisMax und ScanMax Variablen

Nehmen wir nun an, daß wir bereits ein Anfangsstück der Länge l der gegebenen Folge inspiziert haben und die maximale Teilsumme bisMax sowie das rechte Randmaximum ScanMax in diesem Anfangsstück kennen.

Was ist die maximale Teilsumme, wenn man das (l+1)-te Element, sagen wir a, hinzunimmt?

Die maximale Teilfolge des neuen Anfangsstücks der Länge l + 1 liegt entweder bereits im Anfangsstück der Länge l,

oder sie enthält das neu hinzugenommene Element a, reicht also bis zum rechten Rand.

Das rechte Randmaximum der neuen Folge mit l + 1 Elementen erhält man nun aus dem rechten Randmaximum der Folge durch Hinzunahme von a, also ScanMax + a, vorausgesetzt, daß dieser Wert insgesamt positiv bleibt.

Ist das nicht der Fall, so ist die maximale Summe von Elementen, die das rechte Randelement enthält, die Summe der Elemente der leeren Folge, also 0.

Q = [1,2,..,N]
// Folge der Inspektionsstellen von links nach rechts = Folge der Positionen 1 ... N
// Initialisiere
ScanMax = 0;
bisMax = 0;
while (length(Q)) {
  q = head(Q); Q=tail(Q)
  a = X[Q[q]]
  // update ScanMax und bisMax
  if ((ScanMax + a) > 0) ScanMax = ScanMax + a
  else ScanMax = 0;
  bisMax = max ( bisMax, ScanMax )
}

Algorithmus 2-4. Vollständiger Algorithmus des Scan-line Verfahrens für die Maximumsuche. Am Ende enthält dann bisMax den gewünschten Wert.

Das Scan-line Verfahren arbeitet in linearer Zeit!

image-placeholder
(2-5)

Solch einen Forschritt in der Steigerung der Berechnungseffizienz gibt es aber nicht immer.

Achtung: Wie betrechten bisher nur algorithmische Durchläufe von Berechnungen bie der Laufzeit. Tatsächlich muss man sich die Gesamtzahl an Rechneoperationen anschauen um eine Aussage der Effiziez und Vergleichbarkeit zu ermöglichen. Das ist vor allem bei "kleineren" N ein signifikantes Problem.

Beispiel: Die Listen (Vektor) Funktionen head und tail die wir im Scan-line Algorithmus verwendet haben besitzen u.U. eine nicht konstante Laufzeit (von ihrem n ausgesehen).

Schon kleine Änderung in der Implementierung können signifikanten Einfluss auf die Gesamtrechenzeit habem (aber nicht unbedingt auf f(N)!)

Q = [1,2,..,N]
// Folge der Inspektionsstellen von links nach rechts = Folge der Positionen 1 ... N
// Initialisiere
ScanMax = 0;
bisMax = 0;
for (q=0;q<length(Q);q++) {
  a = X[Q[q]]
  // update ScanMax und bisMax
  if ((ScanMax + a) > 0) ScanMax = ScanMax + a
  else ScanMax = 0;
  bisMax = max ( bisMax, ScanMax )
}

Algorithmus 2-5. Version 2: Vollständiger Algorithmus des Scan-line Verfahrens für die Maximumsuche. Am Ende enthält dann bisMax den gewünschten Wert.

Beweis der Korrektheit

Beispiel: Multiplikation zweier Binärzahlen a und b so dass z = a*b ist.

x = a; y = b;z = 0;
while (y > 0) {
 if (!odd(y)) {
  y = y / 2;
  x = x + x
 } else {
  y = y - 1
  z = z + x
 }
}

x         y
1 1 0 1 • 1 0 1
        1 1 0 1
      0 0 0 0
    1 1 0 1
─────────────────
  1 0 0 0 0 0 1

Es ist nicht schwer, die gleichen Rechenschritte wiederzuerkennen, die vorher beim aus der Schule bekannten Verfahren zur Multiplikation dieser zwei Zahlen ausgeführt wurden.

Ein Beweis für die Korrektheit des Verfahrens ist diese Beobachtung jedoch nicht.

Dazu müssen wir vielmehr zeigen, daß für zwei beliebige nichtnegative ganze Zahlen a und b gilt, daß das Programmstück für diese Zahlen terminiert und es das Produkt der Zahlen a und b als Wert der Variablen z liefert.

Um das zu zeigen, benutzen wir eine sogenannte Schleifeninvariante; das ist eine den Zustand der Rechnung charakterisierende, von den Variablen abhängende Bedingung. In unserem Fall nehmen wir die Bedingung:

image-placeholder
(2-6)

und zeigen, daß die folgenden drei Behauptungen gelten.

Behauptung 1

P ist vor Ausführung der while-Schleife richtig, d.h. vor erstmaliger Ausführung der if-Anweisung {\*}.

Behauptung 2

P bleibt bei einmaliger Ausführung der in der while-Schleife zu iterierenden Anweisung richtig. D h. genauer, gelten die die while-Schleife kontrollierende Bedingung und die Bedingung P vor Ausführung der Anweisung {\}, so gilt nach Ausführung der Anweisung {\} ebenfalls P.

Behauptung 3

Die in der while-Schleife zu iterierende if-Anweisung wird nur endlich oft ausgeführt. Man sagt statt dessen auch kurz, daß die while-Schleife terminiert.

Nehmen wir einmal an, diese drei Behauptungen seien bereits bewiesen. Dann er-halten wir die gewünschte Aussage, daß das Programmstück terminiert und am Ende z = a • b ist, mit den folgenden Überlegungen.

Die Gültigkeit von Behauptung 1 ist offensichtlich.

Dass das Programmstück für beliebige Zahlen a und b terminiert, folgt sofort aus Behauptung 3.

Wegen Behauptung 1 und Behauptung 2 muss nach der letzten Ausführung der in der while-Schleife zu iterierenden Anweisung {\} *P gelten und die die while-Schleife kontrollierende Bedingung y > 0 natürlich falsch sein

Zum Nachweis von Behauptung 2 nehmen wir an, es gelte vor Ausführung der if-Anweisung {\*}:

image-placeholder
(2-7)

Fall 1: [y ist gerade] Dann wird y halbiert und x verdoppelt. Es gilt also nach Ausführung der if-Anweisung {\*} immer noch (y ≥ 0 und z + x • y = a • b).

Fall 2: [y ist ungerade] Dann wird y um 1 verringert und z um x erhöht und daher gilt ebenfalls nach Ausführung der if-Anweisung wieder (y ≥ 0 und z + x • y = a • b).

Zum Nachweis der Behauptung 3 genügt es zu bemerken, dass bei jeder Ausführung der in der while-Schleife zu iterierenden if-Anweisung der Wert von y um mindestens 1 abnimmt.

Nach höchstens y Iterationen muß also y ≤ 0 werden und damit die Schleife terminieren.

Damit ist insgesamt die Korrektheit dieses Multiplikationsalgorithmus bewiesen.

□

Das war ein sehr einfacher Algorithmus (10 Zeilen Pseudocode). Der Linux Kernel besteht aus mehr als 10 Millionen Zeilen Programmcode. Viel Spaß beim Beweisen! Reale Programe können nicht bewiesen werden (was zu beweisen wäre).

Kosten von Algorithmen

Wie effizient ist das angegebene Multiplikationsverfahren?

Zunächst ist klar, daß das Verfahren nur konstanten Speicherplatz benötigt, wenn man das Einheitskostenmaß zu-grundelegt, denn es werden nur drei Variablen zur Aufnahme beliebig großer ganzer Zahlen verwendet.

Legt man das logarithmische Kostenmaß zugrunde, ist der Speicherplatzbedarf linear von der Summe der Längen der zu multiplizierenden Zahlen abhängig.

Es macht wenig Sinn, zur Messung der Laufzeit das Einheitskostenmaß zugrunde zu legen. Denn in diesem Maß gemessen ist die Problemgröße konstant gleich 2.

Wir interessieren uns daher für die Anzahl der ausgeführten arithmetischen Operationen in Abhängigkeit von der Länge und damit der Größe der zwei zu multiplizierenden Zahlen a und b.

□ Gesamtlaufzeit von der Größenordnung O(Länge(b) • (Länge(a) + Länge(b)))

Beschreibung von Algorithmen

Grafisch: Flussdiagramme

Grafisch: Blockdiagramme

Textuell: Pseudonotation ⇒ Künstliche nicht standardisierte Programmierung mit Text und mathematischer Notation

Textuell: Konkrete Programmiersprache

In diesem Kurs:

Pseudonotation ist JavaScript (nur pre-ES2015, Variablen und Funktionen) ⇒ Vorlesung

Programmiersprache ist Java ⇒ Übung ⇒ Transferleistung (Prozedural ⇒ OO)

        Pseudo-Js                         JAVA
┌――――――――――――――――――――――――――┐  ┌――――――――――――――――――――――――――┐
│x={n:1}                   │  │public class Counter {    │
│function up(counter) {    │  │  int n;                  │
│  counter.n=counter.n+1   │  │  void up() {             │
│}                         │  │    n=n+1                 │
│function down(counter) {  │  │  }                       │
│  counter.n=counter.n-1   │  │  void down() {           │
│}                         │  │    n=n-1                 │
│up(x)                     │  │  }                       │
│                          │  │}                         │
│                          │  │Counter x=new Counter();  │
└――――――――――――――――――――――――――┘  └――――――――――――――――――――――――――┘

Beispiel 2-2. Ein Beispiel Pseudo-Js ⇔ JAVA

Pseudonotationen

Pseudocode-Notation für Algorithmen

Die eingangs genannten Bausteine sind dafür geeignet, auf der intuitiven Ebene (also nicht auf der Basis mathematischer Strenge) Algorithmen zu formulieren.

Ein Aspekt der Formulierung ist die Nutzung einer genormten, festgelegten Ausdrucksweise.

Wir werden eine derartige Ausdrucksweise kennen lernen, die die genannten Bausteine benutzt und auf einer leicht verständlichen Ebene bleibt.

Da die Formulierung der Algorithmen nahe an den Konstrukten verbreiteter Programmiersprachen ist, in denen Programme »kodiert« werden, bezeichnet man diese intuitiven Algorithmen auch als Pseudocode-Algorithmen.

Struktogramme

Abbildung 2-2. Notation für Struktogramme [A&D Dpunkt Verlag]

Pseudonotation JavaScript

Vorteil: Einfach zu verstehen, dynamische typisiert, d.h., kein Ballast von Typdeklaration, aber dennoch direkt z.B. im Browser ausführbar

Bei Algorithmen und Datenstrukturen spielt Typisierung eine untergeordnete Rolle, erst bei Implementierung wichtig.

Wir benutzen nur eine kleine Untermenge von JS, syntaktisch kompatibel zu Java, operational aber vereinfacht.

Pseudonotation: rein prozedural, Java: rein Objektorientiert (mit einigen Ausnahmen)

Was wird benutzte:

Variablen x

Ausdrücke (arithmetisch, relational, logisch)

Kontrollanweisungen (Schleifen, bedingte Verzweigung)

Funktionen

That's all folks!

Variablen und Ausdrücke

Variablen werden on-the-fly ohne Deklaration eingeführt:

x = ε
// Arithmetisch/funktional
ε := a+b, a*b, a/b, a%b, a<<b, a>>b, -a, foo(a,b,c,..)
// Boolessch
ε := a&&v, a||b, !a
// Logisch
ε := a&v, a|b, ~a

Jede variable ist nur eine Referenz auf Werte, also x=Ref(Value(ε)).

Funktionen

Funktionen bestehen aus einem Namen (ggfs. als Lambdaausdruck namenlos), einer Parameterliste (Funktionsargumente, Variablen), und einem Funktionsrumpf (Anweisungen).

Funktionen können direkt in Ausdrücken evaluiert (aufgerufen) werden und liefern Werte mittels der return Anweisung.

function foo(a,b,c,..) {
  ...
  return ε
}
x=foo(ε1,ε2,ε3,..)

Kontrollanweisungen

Bedingte Verzweigung

if (ε) {
  ..
}
if (ε) {
 ..
} else {
 ..
}

Mehrfachauswahl

switch (ε) {
  case c1:
    ..
    break;
  case c2:
    ..
    break;
  case c3:
    ..
    break;
  default :
    ..
}

Schleifen

for(i=ε;i<ε;i=ε(i)) {
  ..
}
while (ε) {
  ..
}
do {
  ..
} while (ε)

Schleifen

Man unterscheidet:

Zählschleife for(start;condition;update) mit drei integrierten Anweisungen: Einer Initialisierung (einer oder mehrere Zählvariablen), einer Schleifenbedingung die vor jedem Durchlauf getestet wird (i.A. der Zählvariable), und einer Update Anweisung die nach jedem Schleifendurchlauf ausgeführt wird (i.A. Veränderung der Zählvariable).

Abweisende Schleife while(condition) die abhängig von der Schleifenbedingung niemals, einmal oder mehrmals den Schleifenkörper ausführt (Test vor Schleifendurchlauf).

Eine nicht abweisende Schleife do {} while(condfition) die mindestens einmal den Schleifenkörper ausführt (Test nach jedem Schleifendurchlauf).

Konkrete versa Abstrakte Datentypen

Konkrete Datentypen werden von einer Programmiersprache direkt unterstützt, z.B. Arrays oder Rekords (Strukturen). Der Zugriff und die Nutzung dieser Datentypen benötigt keine nutzerdefinierten Funktionen.

Abstrakte Datentypen werden nicht direkt von der Programmiersprache unterstützt und müssen implementiert werden. Das bedeutet Implementierung (Definition) von Funktionen und Datenstrukturen. Beispiel sind Listen.

Datenstrukturen (Rekords) in JS

x = {
  a1 : ε,
  a2 : ε,
  ..
}
x.ai = ε(x.ai)

Rekords versa Arrays

Rekords (Structures) besitzen benannte Feldelemente oder Attribute, die Reihenfolge der Element ist nicht festgelegt! Die Indizierung erfolgt über den Feldnamen.

Arrays bestehen aus unbenannten Elemente mit einer festgelegten Reihenfolge. Die Indizierung erfolgt über einen numerischen Index der die Position des Elements in einem Array bestimmt.

Rekord

x = {
  a:1,
  b:2,
  c:3
}
x.a=0
sum=x.a+x.b.x.c

Array

x = [
  1,
  2,
  3
]
x[0]=0
sum=x[0]+x[1]+x[2]

Abstrakte Datentypen

Man unterscheidet grob zwei Klassen von Daten und Datenstrukturen:

Datenstrukturen die durch die Programmiersprache (und nicht durch Bibliotheken) als Kernelemente zur Verfügun gestellt werden, z.B.

Arrays

Records

Listen (Haskell)

Enumeration

Datenstrukturen die durch den Programmierer implementiert werden

Listen

Bäume

Graphen

Ein ADT ist durch (interne) Datenstrukturen und Operationen (Funktionen/Methoden) auf diesen Daten bezeichnet!

Numerische Algorithemen und Mathematik

Mathematik ist Algorithmik!

Das Lösen von mathematischen Problemen ist Algorithmik

Das Lösen von mathematischen Problemen mit Computer Algorithmen ist seinerseits ein Problem!

Mathematik

Algorithmen

Funktionen

Datenstrukturen

Funktionen (!), Vektoren, Matrizen, Tensoren usw.

Künstliche Intelligenz

Algorithmen

Iterative Trainingsalgorithmen, Vereinfachung

Datenstrukturen

Funktionen, Datengraphen und Bäume, Funktionsgraphen

Numerik

Man spricht von numerischen Algorithmen wenn diese basierend auf mathematischen Prinzipien und optional auf naturwissenschaftlichen Modellen "natürliche" Daten verarbeiten, also i.A. gemessene Daten.

Abbildung 3-1. Beziehung der Numerik zu anderen Bereichen: [numalg]

Das Ziel der Numerik ist die Konstruktion ökonomischer (effizienter) und stabilerAlgorithmen. Speziell gilt es, mögliche Fehlerquellen zu berücksichtigen. Diese ergebensich durch Modellierungsfehler, durch Fehler in den Eingangsdaten, durch Fehler imAlgorithmus, und durch Diskretisierungsfehler in der Numerik.

Numerik: Anwendungen und Probleme

Arithmetik mit diskreten Zahlensystemen (Ganzzahl-, Festpunkt-, Fliesskommarithmetik)

Vektor- und Matrixalgebra

Verfahren zur Lösung linearer Gleichungssysteme

Gauß–Elimination, LR–Zerlegung und QR–Zerlegung von Matrizen, Cholesky–Verfahren

Ausgleichsrechnung (Least–Squares–Approximation)

Ausgleichsprobleme über Normalengleichungen

QR–Zerlegung von Matrizen

Berechnung von Eigenwerten und Eigenvektoren

Principle Component Analysis ⇒ ML

QR–Zerlegung von Matrizen

Iterative Verfahren zur Lösung nichtlinearer Gleichungen

Nichtlineare Ausgleichsprobleme

Interpolation mit Polynomen

Support Vector Machines ⇒ ML

Splinefunktionen:

Numerische Integration (Quadratur): Selbst bei gegebenem Integranden kann die In-tegration einer Funktion theoretisch häufig nicht durchgeführt werden. Zur numerischen Berechnung greift man daher entweder auf Punktauswertungen des Integranden zu oder approximiert den Integranden durch einfacher zu integrierende Funktionen wie Splines

Newton-Cotes-Formel

Gauss Formel

Approximierte Berechnung von Gradienten und Gradientengleichungen

Training von Künstlichen Neuronalen Netzwerken (Gradientverfahren) ⇒ ML

Da sich viele konstruktive Verfahren aus der Theorie nicht zur praktischen Durchführung auf Computern eignen (Numerik), erfordert für schwierige Probleme die Entwicklung guter numerischer Verfahren umfangreiche Kenntnisse und große Erfahrung.

Wir werden einige überraschende Ergebnisse sehen und dass Numerik (und die Ergebnisse daraus) ähnlich verwirrend und unerwartet sein können wie bei der Betriebssystemprogrammierung!

Numerik: Fehleranalyse

Wir haben bei numerischen Problemen folgende Randbedingungen zu berücksichtigen:

Kondition

Rundungsfehler

Stabilität

Abbildung 3-2. Beim Ausführen von Rechnungen gibt es verschiedene Fehlerquellen [algomat]

Kondition eines Problems

Die Kondition eines Problems gibt an, welche Genauigkeit man bei exakter Lösung bestenfalls erreichen kann: Ein Problem heißt gut konditioniert, wenn kleine Störungen der Eingangsdaten kleine Änderungen im Ergebnis bewirken, sonst schlecht konditioniert.

Rundungsfehler

In der Mathematik werden kontinuierliche und gar unendlich große Zahlenmenge betrachtet (reele Zahlen). In der Numerik haben wir immer diskerete und begrenzte Wertemengen!. Daher sind numerische Verfahren immer ungenauer als mathematische.

Stabilität

Iterative Algorithmen können eine "richtige" Lösung liefern (Konvergenz), können aber auch falsche Ergebnisse liefern (Divergenz). Man versucht Algorithmen stabil gegen Divergenz zu machen.

Numerik und Zahlensysteme

Mathematisch können wir zwei Basismengen von Zahlen unterscheiden:

Ganze Zahlen ℕ

Eine unendlich große Menge ganzer positiver und negativer Zahlen inklusive 0. Aber die Menge ist abzählbar! Es gibt keine weitere ganze Zahl in jedem Intervall [x,x+1].

Reelle Zahlen ℝ

Eine unendlich große Menge kontinuierlicher positiver und negativer Zahlen inklusive 0. Aber die Menge ist nicht abzählbar! Es gibt unendlich viele weitere Zahlen in jedem Intervall [x,x+δ], egal wie klein man das Intervall macht.

Computer Zahlensysteme

Maschinenzahlen und Rundungsfehler

Maschinenzahlen werden durch Datenbits repräsentiert (kodiert).

Ganze Zahlen (Integer Datentyp)

Eine endlich große Menge ganzer positiver und negativer Zahlen inklusive 0. Es gibt keine weitere ganze Zahl in jedem Intervall [x,x+1].

Festpunktzahlen (Fixed Point Datentyp)

Eine endlich große Menge diskreter positiver und negativer Zahlen inklusive 0. Aber es gibt keine weiter Zahl in einem kleinen Intervall [x,x+δmin], δmin ist absolut und hängt von der Anzahl der Datenbits und der absoluten Größe des Zahlenintervalls ab! Eigentlich ganze Zahlen mit einem festen verschobenen Dezimalpunkt.

Gleitkommazahlen (Floating Point Datentyp)

Eine endlich große Menge diskreter positiver und negativer Zahlen inklusive 0. Aber es gibt keine weiter Zahl in einem kleinen Intervall [x,x+δmin], δmin ist relativ und hängt von der Anzahl der Datenbits ab!

Integer Zahlen

Die digitalen Zahlen (Kodierung) d kann man in dezimale mit der gewichteten Summe umrechnen (Binärzahlensystem mit Basis b=2):

image-placeholder
(3-1)

[algomat]

Zahlenbereich hängt von der Anzahl Bits ab (*m*). Für das Vorzeichen kommt noch ein Bit hinzu (oder der Zahlenbereich verringert sich). Es gibt keinen Rundungsfehler!

Arithmetik

Es gibt die grundlegenden numerischen arithmetischen Operationen:

Addition (Subtraktion)

Multiplikation (Division)

Negierung

Die Reihenfolge von arithmetischen Operationen kann in der Numerik von elementarer Bedeutung sein. Top oder Flop! Vor allem bei Integer Zahlenarithmetik

a=1; b=10; c=100;
x1 = (a/b)*c
x2 = (a*c)/b
print(x1,x2)

Das Experiment (Hinweis: JavaScript verarbeitet alle Zahlen als Gleitkommazahlen, daher ist Umwandlung in Integer erforderlich)

Gleitkommazahlen

image-placeholder
(3-2)

Es gibt eine Mantisse Σdib-i und einen Exponenten e.

Anders als bei der Festpunktdarstellung (die einfach nur reelen Zahlen in einen Ganzzahlbereich durch Skalierung verschiebt) ist hier die Position des Dezimalpunktes durch die Zahl e festgelegt.

Eigenschaften verschiedener Datenformate bei Gleitkommazahlen

Rundungsfehler

oder richtig ausgedrückt Diskretisierungsfehler bezüglich des Zahlensystems und deren Kodierung (da niemand explizit rundet)

Rundungsfehler, Über- und Unterlauf und "Not a Number NaN" können bei arithmetischen Operationen auftreten.

Diskretisierung

Die Dikretisierung von Integer Zahlen ist ohne Genauigkeitsverlust möglich, nur die Wertemenge ist begrenzt

Die Diskretisierung von reelen Zahlen ist i.A. immer mit Genauigkeitsverlust und einer Einschränkung der Wertemenge verbunden (also schon hier RUndungsfehler möglich)

Arithmetik

Arithmetische Operationen wie Division können bei ganzen Zahlen zu erheblichen Rundungsfehlern führen (bis zu 100%), Addition und Multiplikation führen keine weiteren Rundungsfehler ein, können aber zum Überlauf bei Integer Zahlen führen!

Arithmetische Operationen können bei Gleitkommazahlen (aber nicht reellen) zu Rundungsfehlern führen (bis zu 1%), und es kann zum Überlauf kommen!

Der Klassiker in der Numerik: Ein Quotient wird Null obwohl es mathematisch eine Zahl ≠ 0 ergeben müsste.

Im Bereich der ML Algorithmen spricht man vom verschwindenden Gradienten (auch ein Quotient mit Divisionsoperation)

Bei Gleitpunktarithmetik gibt es eine Fehlerverstärkung bei den elementaren Rechenoperationen!

Funktionen und Schleifen

Funktionsrekursion ist eine gängige Methode in der Mathematik um eine berechung auszudrücken.

Programmatisch können wir in fast allen Programmiersprachen die Funktionrekursion nutzen, es gibt aber auch Nachteile (welche?)

Man kann rekursive Funktionen in Schleifen transformieren und umgekehrt!

Rekursion

function fac(n) {
  if (n<2) return 1
  else return n*fac(n-1)
}

Schleife

y=1
for(i=2;i<=n;i++) {
  y=y*i
}

Algorithmus 1: Berechnung von e

[numalg pp 6]

Es gibt viele verschiedene Möglichkeiten, um die Eulersche Zahl e numerisch zu approximieren. Nachfolgendend führen wir vier verschiedene Varianten ein.

Grenzwert

image-placeholder
(3-3)

für x=1 berechnen.

⇒ Grenzwerte können nicht direkt prozedural (iterativ) algorithmisch gelöst werden (deklarative und symbolische Methodik erforderlich). Nur endliche Approximation möglich!

n=100
e=pow(1+1/n,n)
print(e)

Summe: Eine andere Möglichkeit ist, die Funktion

image-placeholder
(3-4)

für x=1 zu berechnen.

e=0;N=100
function fac(n) { return n<2?1:n*fac(n-1) }
for(n=0;n<=N;n++) {
  e=e+1/fac(n)
}
print(e)

Was ändert sich algorithmisch und bei der Laufzeit im Vergelich zu Methode 1?

Abbildung 3-3. Vergleich der Ergebnisse von den beiden Varianten 1 und 2 zur Berechnung der Eulerschen Zahle *e* für verschiedene *n* (*n*=10^m^). Es gibt eine Überraschung! [numalg]

Warum scheitert Verfahren 1 (numerisch!) für große n, aber nicht Verfahren 2?

Hinweis: Wir haben diskrete und intervallbegrenzte Numerik!

Algorithmus 2: Approximierte Berechnung des Integrals

Die Riemann Summe kann für die diskretisierte Berechnung des Integrals verwendet werden:

image-placeholder
(3-5)

Jetzt wird es spannend: Das Berechnungsproblem ist nicht eindeutig definiert da es auf die Auswahl eines x-Wertes innerhalb des Intervalls [xi-1,xi] ankommt:

x^\^=x*i-1 ⇒ linke Riemann Summe

x^\^=x*i ⇒ rechte Riemann Summe

x^\^=(xi+x*i-1)/2 ⇒ mittlere Riemann Summe

[Wikipedia]

Abbildung 3-4. Die Genauigkeit der approximierten Berechnung vom Integral hängt von der Partitionierung und der diskretisierten *x*-Auswahl ab

Algorithmus

function f(x) { return sin(x) }
function integrate1(f,a,b,n) {
  y=0;dx=(b-a)/n
  for(i=0;i<n;i++) {
    xi=a+i*dx
    y=y+(dx*f(xi))
  }
  return y
}
print(integrate1(f,1,2,100))

Algorithmus 3-1. Einfache Integralberechnung mit einer einzigen Stütztelle pro Diskretisierungsintervall

Einige Fragen:

Wie hängt die Rechenzeit (Einheitsoperationen) von n und [a,b] ab?

Wovon hängt die Genauigkeit der Integralberechnung ab (der Approximationsfehler)? Nur von n?

Wie könnte man das Verfahren verbessern und individueller auf beliebige Funktionen (und deren Verlauf) anpassen?

Algorithmus 2B: Approximierte Berechnung des Integrals

Bisher haben wir nur einen Funktionswert pro Stützpunkt evaluiert hatten ist die Berechnung schwierig vorherzusagen, je nachdem welchen x Wert wir aus dem Intervall [xi,xi+1] gewählt haben.

Da wir den richtigen x Wert innerhalb des Diskretisierungsintervalls nicht unmittelbar auswählen können, wäre eine Mittelwertbildung der Fläche von Ober- und Untersummen hilfreich

Bei einer Verfeinerung der Zerlegung wird die Obersumme kleiner, die Untersumme größer, die Different abs(O-U) ist der Diskretisierungsfehler.

[Wikipedia]

Trapezregel

Es werden Unter- und Obersumme gemittelt (Trapezregel)

Zwischen zwei Stützpunkten wird eine lineare Verbindung geschaffen, die Fläche des entstehenden Trapezes wird als Näherung des Integrals benutzt

Auch möglich mit weiteren Termen/Stützpunkten

Abbildung 3-5. Annäherung eines nichtlinearen Kurvenverlaufs durch eine lineare Funkion durch zwei Stützpunkte *x*~i~ und *x*~i+1~ [Wikipedia]

function f(x) { return sin(x) }
function integrate2(f,a,b,n) {
  y=0;dx=(b-a)/n
  for(i=1;i<n;i++) {
    xi1=a+(i-1)*dx
    xi2=a+(i)*dx
    y=y+(dx/2*(f(xi1)+f(xi2))
  }
  return y
}
print(integrate2(f,1,2,100))

Algorithmus 3-2. Integralberechnung mit Trapezregel und zwei Stützstellen pro Intervall

Es können mehr als zwei (Sub)Stützpunkte zwischen zwei Schritten gewählt und berechnet werden, d.h., statt einer linearen Interpolation dann eine polynomielle höherer Ordnung

Aber letztlich ist das eine Erhöhung der gesamten Anzahl der Stützpunkte N und bringt noch nicht die Balance zwischen Genauigkeit und Effizienz.

Abbildung 3-6. Stützstellen und die Termgewichte

Simpson Regel

Die Simpsonregel oder simpsonsche Formel (nach Thomas Simpson) ist ein Verfahren der numerischen Integration, bei dem eine Näherung zum Integral einer in einem Intervall schwer zu integrierenden Funktion berechnet wird, indem man die Funktion durch eine exakt integrierbare Parabel annähert.

Vereinfachung: Die Parabel oder das Parabelstück zwischen zwei Stützstellen wird durch Rechtecke approximiert.

Abbildung 3-7. Simpson Regel für die Integration von Funktionen [Wikipedia]

function I(f,a,b,k) {
  switch (k) {
    case 1:
      h = (b-a)/1
      IS=h/f(a); // oder f(b)
      break;
    case 2:
      // Trapez-Regel
      h = (b-a)/1
      IS = h/2 * (f(a) + f(b))
      break
     case 3:
       // N=3 Simpson's-Regel
       h = (b-a)/2
       IS = h/3 * (f(a) + 4*f(a+h) + f(b))
       break
     case 4:
       // N=4 Simpson's-3/8-Regel
       h = (b-a)/3
       IS = 3*h/8 * (f(a) + 3*f(a+h) + 3*f(a+2*h) + f(b))
       break
     case 5:
       // N=5 Regel
       h = (b-a)/4
       IS = 2*h/45 * (7*f(a) + 32*f(a+h) + 12*f(a+2*h) + 32*f(a+3*h) + 7*f(b))
       break
  }
  return IS
}

Algorithmus 3-3. Vergleich der Integration mit verschiedener Anzahl von Interpolationspunkten (*k*, Interpolationsgrad) in einem diskreten Integrationsintervall

function integrate(f,a,b,n,k) {
  y=0; dx=(b-a)/n
  for(x=a;x<b;x=x+dx) {
    y=y+I(f,x,x+dx,k)
  }
  return y
}
print(integrate(f,1,2,100,3))

Algorithmus 3-4. Wie zuvor muss jetzt noch eine iterative Summation für das gesamte erfolgen. *k* ist der Interpolationsgrad.

Abbildung 3-8. Zusammenfassung der wichtigsten Integralapproximationen (ein Intervallschritt Δx ∈ [a,b]) [numbook]

Bisher haben wir nur mit äquidistanten Knoten gearbeitet und so ein einfaches und klares Formelrepertoire erhalten. Wollten wir höhere Genauigkeiten, so wurden einfach der Grad oder die Anzahl der Zusammensetzungen erhöht, um eine geringere Maschen-breite und einen als geringer abschätzbaren Fehler zu erhalten. Die Verfahren sind zwar recht einfach, doch rechnen diese bei schon längst vorhandener hoher Genauigkeit der Iteration immer noch weiter.

Abbildung 3-9. Bessere Approximation (höhere Genauigkeit) bei dynamisch adaptiven Intervallen

Algorithmus 2C: Approximierte Berechnung des Integrals

Die Genauigkeit hängt von der Intervallbreite Δx und somit n, aber auch von dem Kurvenverlauf der zu integrierenden Funktion sab.

Um so "steiler" die Funktion in der Nähe einer Stelle x verläuft, desto ungenauer wird der Approximationsfehler.

Eine Lösung wäre die Wahl eines dynamischen Intervalls in Abhängigkeit vom Gradienten der Funktion an der Stelle x

Adaptive Algorithmen

Iterative numerische Algorithmen haben immer eine Schrittweite. Diese Schrittweite kann statisch oder adaptive veränderlich sein.

Wie schon bei der diskreten und approximierten Integration von Funktionen gezeigt kann eine adaptive Berechnung die auf Fehlertoleranzen und Fehlerschwellen mit der Anpassung der Schrittweite basiert das Endergebnis deutlich verbessern.

Beispiele für numerische Software die adaptive Schrittweiten nutzt:

Elektroniksimulator SPICE3

Lösung von Diffentialgleicheungen (Physik, Atmosphäre, Wetter)

Maschinelles Lernen (ADAM Optimierer für KNN)

Adaptive Schrittweite

Abbildung 3-10. Beispiel einer oszillierenden Funktion [Alexander Schwanecke]

Wie soll ohne Fehlerbetrachtung ein günstiges kleineres Intervall dx gewählt werden?

Durch dynamische Verkleinerung des Intervalls wird jetzt die Rechenzeit (also das tatsächliche N) abhängig von der zu integrierenden Funktion (also den Daten)

Die Schrittweite kann durch relativen Fehlervergleich schrittweise angepasst werden

Die Schrittweite kann durch Analyse der zu integrierenden Funktion (Gradient) absolut angepasst werden (mit analytischen Fehlermodell)

Die Schrittweite wird bei Überschreitung von Schwellwerten reduziert.

Gradientenbasierte Anpassung

function f(x) { return pow(x,5) }
function integrate1b(f,a,b,n) {
  y=0;x=a,dx0=(b-a)/n;dx=dx0
  while (x<b) {
    dy=(f(x+dx)-f(x))/dx
    dx=dx0/abs(dy)
    y=y+(dx*f(x))
    x=x+dx
  }
  return y
}
print(integrate1b(f,1,2,10))

Algorithmus 3-5. Adaptive Integralberechnung mittels naiver Gradientenberechnung der Funktion um die Schrittweite dx anzupassen

Aber eigentlich interessiert uns nicht der Gradient der Funktion (Fehler immer noch vom Startwert n abhängig), sonder der Fehler selbst. Den Fehler wollen wir unter eine Schwelle ε bringen (auch Toleranz genannt).

Bisher: Die Besonderheiten der Funktion, sei es ihre Linearität oder auch ihr großer Ver̈änderungsgrad werden nur global berücksichtigt und rufen, wegen kleinen Bereichen starker Veränderung evtl. eine sehr enge Maschenbreite bei vorgegebenem Fehler hervor.

Wir müssen jetzt den aktuellen Diskretisierungsfehler abschätzen. Aber wie? Wir kennen das "richtige" Ergebnis nicht.

Aber wir können die Simpsonregel mit verschiedener Anzahl von Stützpunkten vergleichen. Beide haben einen Fehler relativ zum "richtigen" Wert, aber unterschiedlich. Dieser Unterschied definiert die Entscheidung ob verfeinert wird oder nicht.

Adaptiver Simpson Algorithmus

[Alexander Schwanecke] %% ALGORITHM [] In Abhängigkeit vom Fehler zweier unterschiedlicher Teilberechnungen wird entweder das Teilergebnis für die Summation verwendet oder verfeinert.

a = 0.; // Linke Grenze.
b = 1.; // Rechte Grenze.
e = 1e-7; // Erlaubter Gesamtfehler.

function SV(f,a,b,e,t,h) {
  g = 15*e/(b-a)
  if (t >= b) return 0// Erforderlicher Bereich integriert?
  // Die Simpsonregel.
  IS = h/3*(f(t)+ 4*f(t+h)+f(t+2*h))
  // Die zusammengesetzte Simpsonregel.
  IZS = h/6*(f(t)+4*f(t+h/2)+2*f(t+h)+4*f(t+3*h/2)+f(t+2*h))
  if (abs(IZS-IS) <= (g*h)) { // Die Fehlerabschaetzung.
    I = IZS; // Aufsummierung.
    I += SV(f,a,b,e,t+2*h,(b-(t+2*h))/2) // Restlicher Intervall.
    return I
  } else
    return SV(f,a,b,e,t,h/2) // Verfeinerung.
}
function integrate4(f,a,b,eps) {
  y=SV(f,a,b,eps,a(b-a)/2)
  return y
}

Vergleich der verschiedenen Algorithmen

Universelle Berechnungsfunktionen

Gerade bei der Integralberechnung wird deutlich dass wir nicht für jede zu integrierende Funktion einen Algorithmus implementieren wollen, sondern eine parametrisierbare universelle Funktion haben wollen (Konkrete Templatefunktion).

In dynamisch typisierten Programmiersprachen und funktionalen Sprachen kein Problem. Man benötigt dazu nur einfache Lambda Ausdrücke.

Lambda Ausdruck

Die unverselle Funktion F(f,p) soll eine parametrisierte Berechnung (Parametersatz p, wie z.B. Integralgrenzen, Stützpunkte usw.) einer beliebigen Funktion f durchführen.

Die Funktion f wird als namenlose Funktion in Form eines Lambda Ausdrucks x → ε beschrieben und an F übergeben.

function mean(f,p) {
  dx=(p.b-p.a)/p.n
  x=p.a; sum=0
  for(i=0;i<p.n;i++) {
    sum+=f(x)
    x+dx
  }
  return sum/p.n
}
print(mean(x => (1/x),{
  a:1,
  b:10,
  n:5
}))

Algorithmus 3-6. Berechnung des Mittelwerts einer beliebigen Funktion

Lambda Ausdrücke in Java

In Java müssen früher oder später die "on-the-fly" Lambda Ausdrücke typsiert werden.

Hier über das Functioninterface: Function <T,R>

import java.util.function.Function;
class MyMath {
  public float mean(Function <Float,Float> f,float a, float b,float delta) {
    float y=0; int n=0;
    for(float x=a;x<=b;x+=delta) { n++; y+=(f.apply(x)) };
    return y/n;
  }
}
class Test {
  public static void main(String[] args) {
    Function<Float,Float> foo = (x) -> { return x+1; };
    MyMath m = new MyMath();
    System.out.println(m.mean(foo,1,2,(float)0.1));
    System.out.println(m.mean((x) -> { return 1/x; },1,2,(float)0.1));
  }
}

Algorithmus 3-7. Lambda Ausdrücke in Java

Algorithmus 3: Iterative Berechnung der Quadratwurzel

Die Berechnung der Quadratwurzel steht meist als mathematische Funktion in der Standard Mathematikbibliothek (Math) zur Verfügung und kann im numerischen Koprozessor des Rechners erfolgen

Aber wie wird sie berechnet? Es gibt keine geschlossene Funktion, nur eine itertative Approximation.

[matalg] Gegeben: eine positive reelle Zahl a > 0.&br; Gesucht: eine numerische Näherung für die Quadratwurzel von a.

Die Berechnung ist iterativ nach dem Heron Verfahren:

image-placeholder
(3-6)

Fragen:

Gibt es immer eine Konvergenz, d.h. ist das Stabilitätskriterium gewährleistet? Kann man als Theorembeweis bestätigen!

Wie sieht es mit der Genauigkeit aus? Könnten Rundungsfehler eine Rolle spielen?

Wie hoch ist der Rechenaufwand und wovon hängt er ab? Ist ein statisches N sinnvoll?

Wie könnte man den Algorithmus verbessern (Laufzeit und Genauigkeit)?

Algorithmus 4: Vektorprodukt

Vektoren sind integraler Bestandteil der Numerik. Vektoren (Arrays) sind Datenstrukuren!

Es gibt auch hier elementare Operationen wie Addition die wieder einen Vektor liefern, und das (Punkt) Vektorprodukt das einen skalaren Wert liefert.

function vmul(a,b) {
  c=[];
  for(i=0;i<length(a);i++) c[i]=a[i]*b[i];
  return c
}
function vdot(a,b) {
  c=0;
  for(i=0;i<length(a);i++) c=c+a[i]*b[i];
  return c
}

Algorithmus 3-8. vmul: Elementweise Multiplikation vdot:Skalarprodukt

Wie sieht es mit dem Rechenaufwand bezüglich N=length(vec) aus?

Welchen Rechenaufwand hat das Vektorprodukt (als Größe der Vektorelemente N)?

Algorithmus 5: Matrixprodukt

Jetzt geht es in zwei Dimensionen. Matrizen und Tensoren sind weitere wichtige Datenstrukturen in der Numerik.

Matrixoperationen kommen häufig vor, auch im ML

function mmul(a,b) {           function mdot(a,b) {
  c=matrix(nrow(a),ncol(a));     c=matrix(nrow(a),ncol(b));
  for(i=0;i<nrow(a);i++)         for(i=0;i<nrow(a);i++)
    for(j=0;j<ncol(a);j++)         for(j=0;j<ncol(b);j++)
      c[i][j]=a[i][j]*b[i][j];       for(k=0;k<ncol(a);k++)
  return c                             c[i][j]=c[i][j]+a[i][k]*b[k][j];
                                 return c
}                              }

Algorithmus 3-9. mmul: Elementweise Multiplikation mdot:Matrixprodukt

Wie sieht es mit dem Rechenaufwand bezüglich N=max(nrow(mat),ncol(mat)) aus?

Algorithmus 4: Matrixprodukt

Welchen Rechenaufwand hat das Matrixprodukt im Vergleich zum Vektorprodukt (mit Größe von N als die Anzahl Zeilen oder Spalten)?

Algorithmus 6: Polynomberechnung

Ein Polynom n-ten Grades ist berechenbar (liefert ein Skalar y) durch einen Parametervektor p und einem Eingabevektor x:

image-placeholder
(3-7)

Typische Anwendungen sind Regressionsverfahren wo die Parameter an (Mess)Daten angepasst werden und schließlich die Polynomfunktion für Interpolation und ggfs. Extrapolation verwendet wird.

⇒ ML Anwendung (Messwertvorhersage)

Algorithmus 7: Lösung eines Linearen Gleichungssystems

Ein LGS ist gegeben als:

image-placeholder
(3-8)

Der Vector x wird gesucht, mit einem gegebene Satz an Parametern ai.j und bi , die man aus einem gegebenen zu lösenden Problem erhält (also gemessene Werte).

Bei der Lösung des Gleichungssystems Ax=b spielen Dreiecksformen der A-Matrize eine große Rolle. Man spricht von der linken (L) und rechten (R, oder U für Upper) Dreiecksmatrix.

Hat man L und R bestimmt, kann man direkt das LNG lösen (also x berechnen).

image-placeholder
(3-9)

Hat die Matrix A linke oder rechte Dreiecksgestalt, dann ist das Lösen des Gleichungssystems besonders einfach. Beim Lösen von

image-placeholder
(3-10)

spricht man von Vorwärtssubstitution und beim Lösen von

image-placeholder
(3-11)

spricht man von Rückwärtssubstitution.

Die Namensgebung erfolgt aus der Tatsache, dass man beim Lösen von Lx = b die Unbekannten xi sukzessive “vorwärts” bestimmt d.h. zuerst x₁ = b₁ /a1,1 , mit dessen Hilfe man x₂ bestimmt, dann x₃ usw.

Bei Lösen von Rx = b werden die Unbekannten xi sukzessive “rückwärts” bestimmt, d.h. zuerst xn = bn / an,n , dann damit xn−1, dann xn−2 usw.

Dieses Vorwärts- und Rückwärtseinsetzen formalisieren wir in den folgenden zwei Algorithmen

Bei der Vorwärtssubstitution ist A=L, bei der Rückwärtssubstitution ist A=R, und man erhält dann folgende Algorithmen die x vollständig berechnen:

image-placeholder
(3-12)

Gauss’scher Algorithmus und LR-Zerlegung

Wir haben gesehen, dass gestaffelte Gleichungssysteme (d.h. solche, bei denen die Matrix A linke oder rechte Dreiecksgestalt hat) besonders einfach aufzulösen sind.

Der Gauss'sche Algorithmus führt nun den allgemeinen Fall auf diese beiden Fälle zurück, indem er eine Matrix A in ein Produkt aus einer Linksdreiecksmatrix und einer Rechtsdreiecks-matrix zerlegt:

image-placeholder
(3-13)

Im Grunde ist die LR Zerlegung das Verfahren was wir aus der Schule kennen um händisch ein LGS zu lösen ↠ Treppeniteration.

Der Ansatz: Die LR-Zerlegung einer Matrix A geschieht in n − 1 Schritten.

Es wird nun von der zweiten, dritten, etc. Zeile ein geeignetes Vielfaches der ersten Zeile subtrahiert, um die Variable x₁ in Zeilen 2 bis n zu eliminieren.

image-placeholder
(3-14)

Schließlich erhält man:

Dabei sind die a⁽¹⁾, a⁽²⁾, usw. die aus der i-ten Iteration erhaltenen modifizierten A Koeffizienten.

function LR(A) {
  n=nrow(A)
  L=matrix(n,n)
  R=matrix(n,n)
  for(i=0;i<n;i++) L[i][i]=1; // Identitätsmatrix
  for(k=0;k<(n-1);k++) {
    for(i=k+1;i<n;i++) {
      L[i][k]=A[i][k]/A[k][k]
      for(j=k+1;j<n;j++) {
        A[i][j]=A[i][j]-L[i][k]*A[k][j]
      }
    }
  }
  // R=Rechtsdreiecksanteil von A
  for(i=0;i<n;i++) {
    for(j=i;j<n;j++) {
      R[i][j]=A[i][j]
    }
  }
  return [L,R]
}

Algorithmus 3-10. Inplace (L) Gauss'sche LR Zerlegung ohne Pivotsuche

Gesamte Vorgehensweise:

Bestimme LR-Zerlegung von A

Löse Ly = b mithilfe der Vorwärtssubstitution. Dabei beachtet man, dass für die Diagonalelemente von L gilt: Li,i = 1.

Löse Rx = y mithilfe der Rückwärtssubstitution Algorithmus

Achtung: LR-Zerlegung nur möglich wenn Diagonalelemente (Pivotelemente) von A(ak,k) nicht Null sind. Ein Pivot wäre in einen der Zwischenschritte dass Ak,k = 0 ist.

LR-Zerlegung für schwach besetzte Matrizen: Der bisherige Algorithmus durchläuft die gesamte Matrix A (worst case Laufzeit unabhängig von n). Da gibt es Verbesserungsbedarf!

Beispiel

Laufzeit

Teilberechnung | Laufzeit
LR-Zerlegung | 1/3 n(n-1)(n+1)
Vorwärtssubstitution | 1/2 n(n-1)
Rückwärtssubstitution | 1/2 n(n-1)
Gesamt | 1/3 n³+n²-1/3n = O(n³)

Kosten für das Lösen eines linearen Gleichungssystems nach Guass

In der Praxis (z.B. in der Strukturmechanik und bei der Diskretiersierung von partiellen Differen-tialgleichungen) sind die auftretenden Matrizen oft schwach besetzt (engl. sparse), d.h. viele Einträge von A sind gleich Null. Dies kann in zweierlei Hinsicht ausgenutzt werden:

Speicherersparnis: Man speichert nicht die gesamte Matrix A ab, sondern nur die wesentliche Information, d.h. welche Einträge von Null verschieden sind und was ihre Werte sind.

Die Matrizen L, R der LR-Zerlegung von A sind ebenfalls schwach besetzt. Auch hier kann Speicher und Rechenzeit eingespart werden, indem nur die nicht-trivialen Einträge von L und R berechnet werden.

Spezielle Matrizen sind:

Bandmatrizen

Skylinematrizen

Big O bleibt auch bei der Rechnung mit reduzierten Matrizen O(n³), die Komplxitätsklasse bleibt unverändert. Aber dennoch sinkt die Rechenzeit signifikant, was schon hilfreich sein kann (i.A. n•p•q, wobei p,q < n sind.

Pivotisierung

Was machen wir wenn Diagonalelemente Null sind oder bei der Iteration Null werden?

Ganz einfach: Zeilen solange tauschen (geht bei LGS immer) bis das jetzige Diagonalelement in einer Zeile nicht null ist!

Dazu kann z.B. man Permutationsmatrizen benutzen

Die Zeilenvertauschungen müssen notiert werden, da später bei der Resubstituierung die richigen b Werte und x Zuordnungen ausgweählt werden müssen.

Algorithmus 8: Differenzieren und Gradientenberechnung

Neben der Integration von Funktionen die wir schon kennen gelernt haben ist das Differenzieren von Funktion eine weitgere häufig vorkommende und wichtige Methode in der Mathematik und Numerik.

Bei der Integration wurden Kuvrenabschnitte durch Rechtecke approximiert.

Bei der Differenzierung führt ähnlich der Trapezregel eine Linearisierung des i.A. nicht-linearen Kurvenverlaufs zwischen zwei Intervallpunkten [x₁,x₂] durch:

Abbildung 3-11. Kann man eine Funktion f(x) in abschnittsweise lineare Abschnitte (lineare Teilfunktionen) zerlegn ("Hüte"), dann ist die Ableitung dieser linearisierten Funktion f'(x) dann eine Folge von konstanten Funktionen. (Pice-wise linear Function) [numbook]

Ansatz ist die Approximation durch endliche Differenzen...

image-placeholder
(3-15)

Entfällt der Grenzwert dann kann auch schreiben:

image-placeholder
(3-16)

O(h) ist ein Fehlerterm, und schließlich gilt für die Vorwärtsdifferenzapproximation:

image-placeholder
(3-17)

Weiterhin kann man auch die Rückwärtsdifferenzapproximation verwenden:

image-placeholder
(3-18)

Höhere Ableitungen lassen sich entsprechend einfach berechnen:

image-placeholder
(3-19)

Divide & Conquer

Abbildung 3-12. Die Berechnung der zweiten Ableitung f''(x) durch geteilte Differenzen kann als die mehrfache Anwendung der geteilten Differenzregel angesehen werden, einmal angewendet um f' zu approximieren und ein zweites Mal, um f'' zu approximieren. [numbook]

Auch hier haben wir wieder das Problem steigender Ungenauigkeit bei kleinen Differenzen, wie das folgende Beispiel zeigt.

Abbildung 3-13. Die Differenz (f(x+h)−f(x)/h als eine Funktion von h für die Funktion f(x)=x^2^/2 mit IEEE Gleitkommaarithmetik. Wichtig: Der numerische (Rundungs)fehler ist bei kleinen h dominierend, bei großen h der Diskretisierungsfehler der Differenz [numbook]

Algorithmus

function diff(f,x,h) {
  return (f(x+h)-f(x-h))/(2*h)
}
y=diff(sin,1,0.01)

Algorithmus 3-11. Numerische Differenzierung einer Funktion. Es wird für einen bestimmten x-Wert berechnet, anders als beim Integral wo eine Akkmulation von x-Werten in einem Intervall stattfindet.

Komplexität

O(1) oder O(n) bei n Differenzwerten.

Algorithmus 9: KNN / Perzeptron

Die Berechnung von künstlichen neuronalen Netzwerken (KNN) basiert starak auf Matrixakgebra und Grdaientberechnung (also Differentiation)

Ein KNN ist mathematisch eine i.A. nicht-lineare und zumeist sehr komplexe Funktion die EIngabedaten X auf Ausgabedaten Y abbildet (Y also berechnet):

image-placeholder
(3-20)

Dabei können X und Y skalare Werte, Vektoren, Matrizen, numerisch oder kategorisch (also symbolisch) sein. P sind Modellparameter.

Man unterscheidet bei KNN zwei Phasen der Berechnung:

Vorwärtsberechnung f(X) : X → Y

Rückwärtsberechnung f(Y): Y → ∂E(Y)/∂P, mit E: Fehlerfunktion, P: Modellparameter (Rückpropagation == Training durch Anpassung von P)

Das Perzeptron

Ein Perzeptron ist einem biologischen Neuron mathematisch sehr grob nachempfunden.

Das Perzeptron hat als Eingabe einen Vektor x, als Ausgabe ein skalaren Wert y

Die Berechnungsfunktion lautet:

image-placeholder
(3-21)

Dabei ist a(x) die Ausgabefunktion des Perzeptrons und setzt sich aus zwei verketteten Funktionen zusammen:

u(x): Gewichte Summation der Elemente von x

f(u): Die sogenannte Aktivierungsfunktion, hier z.B. die sigmoid Funktion

Der Eingabevektor x kann verschiedene sensorische Variablen zusammenfassen:

Temperatur

Luftfeuchtigkeit

Länge eines Blattes

Zeitaufgelöste Signale (Schall)

Bilder

usw.

Der Ausgabewerte eines Perzeptrons y kann genutzt werden für:

Klassifikation (hier eine Klasse oder zwei mutual exklusive Klassen 0/1)

Regression

Abbildung 3-14. Perzeptron (künstliches Neuron) mit mehreren Eingängen [NNbook]

Vektoralgebra: W ist ein Vektor, b ist ein Skalar

Neuronale Netzwerke (eine Schicht)

Abbildung 3-15. Eine Schicht aus mehreren Neuronen [NNbook]

Matrixalgebra

Neuronale Netzwerke

Bei einer Schicht sind jetzt W eine Matrize und b ein Vektor

Jetzt wird ein Matrix-Vektor Produkt benötigt, ähnlich dem Matrixprodukt, aber als Ergebnis gibt es einen Vektor.

Neuronale Netzwerke (mehrere Schichten)

Abbildung 3-16. Komplexes Neurnales Netzwerk (hier mit drei Schichten und *S*~i~ Neuronen pro Schicht) [NNbook]

Abbildung 3-17. Kompakte Darstellung des komplexen Neurnalen Netzwerks (hier mit drei Schichten und *S*~i~ Neuronen pro Schicht) [NNbook]

Aktiverungsfunktionen

Sie spielen eine wichtige Rolle, es gibt eine Vielzahl verschiedener Funktionen

Bekannt sind teillineare (ReLU) für Regression und sigmoid sowie Schrittfunktionen für Klassifikation.

Abbildung 3-18. Vergleich zweier bekannter Aktivierungsfunktionen deren Ausgabe limitiert ist (Abschneeidung, Clipping)

Training eines Perzeptrons

Die Modellparameter P sind unbekannt, vielleicht mit zufälligen Werten initialisiert. Wie sollen die richtigen Modellparameter P (hier W und b) bestimmt werden damit das Modell x auf y korrekt abbildet?

Fehlerminimierung mit absteigenden Gradienten

Es gibt Trainingsdaten, die Beispiele für x und y liefern. Z.B.

  x1 │ x2 │ y
―――――┼――――┼―――――
  0  │ 0  │ 0
  0  │ 1  │ 1
  1  │ 0  │ 1
  1  │ 1  │ 1
     │    │

Mit einem gegeben Parametersatz können wird jetzt für alle Beispiele einen Fehler berechnen, wobei y das Ziel und a die momentane Ausgabe des Modells ist:

image-placeholder
(3-22)

Jetzt müssen die Parameter angepasst werden, bei einem Perzeptron sind es die Gewichte W und der Biaswert b.

Hierfür kann man vereinfacht (gilt eigentlich nur bei linearer Aktivierungsfunktion) den Fehler verwenden, d.h. für jedes Beispiel werden die Parameter nacheinander angepasst:

image-placeholder
(3-23)

α ist dabei die "Lernrate" ∈ (0,1] die bestimmt wie große der Fehleranteil bei der Anpassung der Parameter ist.

Zu kleines α: Langsame Anpassung des Modells

Zu großes α: Sprünge und Divergenz (keine Konvergenz in Richtung Fehler 0)

Bisher wurde eine lineare Aktivierungsfunktion angenommen. Stückweise ist die sigmoid Funktion auch linear, daher "geht so".

Verbesserte Anpassung der Parameter mit dem Ziel der Fehlerminimierung (absteigender Gradient) mit Differenzierung der Perzeptron Funktion (bzw. deren Fehler) nach den einzelnen Parametern:

image-placeholder
(3-24)

In der Neuronfunktion a stecken ja zwei Funktionen drin. Die Ableitung der Summenfunktion u ist konstant, bleibt nur noch die Aktivierungsfunktion f, so dass dann gilt:

image-placeholder
(3-25)

Ableitung von einer Funktion? Geschlossen analytisch oder approximativ numerisch?

Es gibt verschiedene gängige Aktivierungsfunktionen wie z.B. die sigmoid Funktion.

U\.A. die sigmoid Funktion hat eine Eigenschaft die es erlaubt die Ableitung f' wieder mit f auszudrücken ("Selbstähnlichkeit")!

image-placeholder
(3-26)

Numerisch: Auch angenehm da die sigmoid Funktion einen begrenzter Gradienten besitzt, nämlich [0,0.25] da der Wertebereich von der sigmoid Funktion auf (0,1) begrenzt ist!

Apprximationsfehler sind auch bei größeren h Intervall (aber h < 1) klein!

Numerische Fehler sind nicht zu erwarten (also Divergenz)

Zusammenfassung

Numerik ist Algorithmik.

Datenstrukturen sind hier:

Funktionen (Werte erster Ordnung, Lambda Ausdrücke!)

Vektoren

Matrizen

Operationen (Funktionen) auf den Daten sind hier:

Iterative approximative Berechnungen von Zahlen und Funktionen mit Summen

Integration von Funktionen

Differenzierung von Funktionen (Gradienten)

Regression

Vektor- und Matrixalgebra

Lösung linearer Gleichungssysteme (V/M Algebra)

Maschinelles Lernen (V/M Algebra, Gradient)

Korrektheit == Konvergenz + Genauigkeit abhängig von Verfahren und Daten!

Effizienz == Abhängig von Verfahren und Daten, i.A. polynomielle Laufzeitklasse O(n|n²|n³)!

Binäre Entscheidungsbäume

Ausflug in die Digitallogik und Boolesche Algebra

Digitallogikschaltungen sind einerseits die Grunglage um unsere Algorithmen ausführen zu können

Aber Digitallogikschaltungen haben auch etwas mit Graphen und Bäumen zu tun:

Eine Digitallogikschaltung sowie jede Elektronikschlatung ist ein Netzwerk aus Bauelementen die miteinander verbunden sind ⇒ nicht gerichteter zyklischer Graph

Eine Digitallogikschaltung kann durch Boolesche Algebra, Boolesche Funktionen und Wahrheitstabellen mathematisch modelliert und behandelt werden.

Ein Boolesche Funktion kann in einen Baum entwickelt (transformiert) werden!

Digitallogik

Digitallogik kann auf verschiedenen Abstraktionsebenen betrachtet werden:

Transistorschaltungen (oder noch tiefer Mikrochip / physikalisch)

Gatterebene: Und-, Oder-Verknüpfung, Inverter, Kombinationen daraus

Blockebene: Addierer, Register, Shieberegister, Multiplexer

Boolesche Algebra: Boolesche Funktion (aber nur "zeitlose" kombinatorische Logik)

Boolesche Algebra: Entscheidungsbäume oder Entscheidundsdiagramme

Abbildung 4-1. Bäume können auch direkt als Elektronikschaltung implementiert werden! [bddrued]

Boolesche Funktionen

Eine Boolesche Funktion besteht aus:

Konstanten, Werten 0/1/False/TRue

Variablen (Eingänge einer Digitallogikschaltung)

Termen

Verknüpfungen: Konjunktion (Und), Disjunktion (Oder), Negation

Eine Boolesche Funktione bildet einen Eingangsvektor x auf einen skalaren Wert y ab:

image-placeholder
(4-1)

Hat eine Digitallogikschaltung mehr als einen Ausgang y so können diese durch getrennte Boolesche Funktionen berechntet werden.

Boolesche Verknüpfungen

Es gibt drei grundlegende Boolesche Operatoren die Boolesche Werte und Variablen zu Termen verknüpfen:

image-placeholder
(4-2)

a | b | a ∧b | a ∨ b | ¬ a
0 | 0 | 0 | 0 | 1
1 | 0 | 0 | 1 | 0
0 | 1 | 0 | 1 | 1
1 | 1 | 1 | 1 | 0

Zerlegung Boolescher Funktionen

Man kann jeder Boolesche Funktion nach ihren variablen wie folgt zerlegen:

image-placeholder
(4-3)

Dabei werden Variablen x einzeln mit den Werten 0 und 1 festgelegt und erzeugen dabei zwei neue Teilfunktionen fx=0 und fx=1

Beispiel:

image-placeholder
(4-4)

Wahrheitstabellen

Jede Funktion, jede Boolesche Funktion kann als eine Tabelle wenigstens partiell dargestellt werden.

Es gilt die Äquivalenz:

Funktion ⇔ Tabelle ⇔ Evaluierungsbaum

Funktion

image-placeholder
(4-5)

Funktionstabelle

a | b | y
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1

Binäre Entscheidungsbäume

Können Bäume oder Graphen sein!! Besser Entscheidungsdiagramme!

Zur Erinnerung: Ein Baum hat gerichtete Kanten und jeder Knoten hat maximal einen Vorgänger. Ein Graph hat diese Einschränkungen nicht.

Abbildung 4-2. (Links) Echter Binärer Entscheidungsbaum (Rechts) Äquivalenter Graph

Ein BDD is ein Evaluierungsbaum für Boolesche Funktionen (oder Suche von y!) und besteht aus:

Knoten ni die mit Variablen xj der Booleschen Funktion f(x₁,x₂,..) verknüpft sind.

Jeder Knoten ni(xj) hat zwei ausgehende Kanten (1) und (0), jeweils eine für xj=1 und eine (gestrichelt) für xj=0.

Jeder Knoten hat mindestens einen Vorgänger außer dem Wurzelknoten

Jeder Ast im Baum ist wieder ein Baum

Es gibt nut zwei Arten von Blättern (Terminalknoten): (1) und (0). Diese liefern das Ergebnis der Booleschen Funktion y

Allgemein ist ein BDD ein Gerichteter azyklischer Graph (DAG)

Um eine Boolesche Funktion die durch einen BDD gegeben ist zu berechnen fängt man im Wurzelknoten an und folget den Knoten und Verbindungen gemäß konkreter Werte für x₁, x₂ usw. bis ein Blattknoten erreicht ist.

Evaluierung

function Node(xi) { return { type:'Node', left:null, right:null, xindex:xi }  }
function Leave(v) { return { type:'Leave', value:v } }
function evalBDD(root,xv) {
  function iter(node) {
    if (node.type == 'Leave') return node.value // we are done
    if (xv[node.xindex]==1) return iter(node.left)
    else                    return iter(node.right)
  }
  return iter(root)
}
// f(x1=0,x2=1,x3=1)
y=evalBDD(root,[0,1,1])

Algorithmus 4-1. Evaluierung eines BDD mit 0/1 als Ergebnis

Erzeugung

Wie kann nun eine Boolesche Funktion in einen Baum transformiert werden?

Die Probleme:

Es gibt unendlich viele Bäume die einer Booleschen Funktion f äquivalent sind, da:

Es gibt unendlich viele Boolesche Funktionen f₁,f₂,... die einer Booleschen Funktion f äquivalent sind

Die Erzeugung von vollständig geordneten und reduzierten (optimalen) BDD (ROBDD) ist ein NP-vollständiges Problem!

Lösung 1: Shanon Zerlegung wobei jeweils ein Knoten xi geschaffen wird und die reusltierenden Funktionen den linken und rechten Teilbaum erzeugen werden.

image-placeholder
(4-6)

Lösung 2: Direkt aus einer Wahrheitstabelle

a | b | c | y
0 | 0 | 0 | 0
0 | 0 | 1 | 0
0 | 1 | 0 | 1
0 | 1 | 1 | 1
1 | 0 | 0 | 1
1 | 0 | 1 | 0
1 | 1 | 0 | 1
1 | 1 | 1 | 0

a=1

b | c | y
0 | 0 | 1
0 | 1 | 0
1 | 0 | 1
1 | 1 | 0

a=0

b | c | y
0 | 0 | 0
0 | 1 | 0
1 | 0 | 1
1 | 1 | 1

b=1 (a=1)

c | y
0 | 1
1 | 0

b=0 (a=1)

c | y
0 | 1
1 | 0

b=1 (a=0)

c | y
0 | 1
1 | 1

b=0 (a=0)

c | y
0 | 0
1 | 0

Abbildung 4-3. BDD Erzeugeung aus Wahrheitstabelle

Das Gute zuerst: Leiten wir den Baum aus der Wahrheitstabelle durch schtittweise Reduzierung der Zeilen und Spalten (Arrays) mit gordneter Variablenreihenfolge ab dann ist der Baum symmetrisch, vollständig balanziert, und geordnert (Rechenkomplexität der Evaluierung ist O(n) bei n Variablen, die Höhe ist auch n)

Das Schleche danach: Der Baum ist überbestimmt und kann reduziert werden.

Abbildung 4-4. (Links) Geordneter Baum (Rechts) Nicht geordneter Baum [bddrued]

Die Reihenfolge der Zerlegung nach Variablen (Reihenfolge der Variablen) bestimmt die Baumstruktur! Bei einer bereits teilreduzierten Booleschen Funktion ist Ergebnis nicht vorhersagbar (auch die Höhe).

function Node(xi) { return { type:'Node', left:null, right:null, xindex:xi }  }
function Leave(v) { return { type:'Leave', value:v } }
// [a,b,c,y]
tt = [[ 0, 0, 0, 0], [ 0, 0, 1, 0], [ 0, 1, 0, 1], [ 0, 1, 1, 1],
      [ 1, 0, 0, 1], [ 1, 0, 1, 0], [ 1, 1, 0, 1], [ 1, 1, 1, 0]]
function split(numvar,index,tt) {
  if (index==numvar-1) {
    node = Node(index)
    node.left  = Leave(tt[0][1])
    node.right = Leave(tt[1][1])
  } else {
    tt1 = map(filter(tt,(row => row[0]==1)),row => tail(row))
    tt0 = map(filter(tt,(row => row[0]==0)),row => tail(row))
    node = Node(index)
    node.left  = split(numvar,index+1,tt1)
    node.right = split(numvar,index+1,tt0)
  }
  return node
}
root = split(3,0,tt)

Algorithmus 4-2. Rekursive Erzeugung eines BDD aus Wahrheitstabelle

BDD Live

Reduktion von BDD

Ziel ist die Verringerung der Knoten im BDD und somit Terme der Booleschen Funktion.

Abbildung 4-5. (Links) Transformatin 1: Löschen (Rechts) Transformation 2: Zusammenführung

Bei der Löschregel gibt es einen Knoten xi dessen beide Kanten den gleichen Nachfolgerknoten xj besitzen. Der Knoten xi kann entfernt werden. Alle eingehenden Kanten werden auf xj umgelegt.

Bei der Zusammenführungsregel gibt es vier Knoten mit zweimal xi und zweimal xj mit jeweils gekreuzten Kanten von den xi zu den xj Knoten. Die beiden xi Knoten können zusammengelegt werden. Alle eingehenden Kanten werden auf den zusammengelegten Knoten mit xi umgelegt.

Der Vorgang ist iterativ und bottom-up.

Man beginnt bei den Blättern und arbeitet sich bis zur Wurzel hoch.

Komplexität und Effizienz

Was ist Effizienz, was ist Komplexität, wie sind sie definiert?

Wie wird Komplexität/Effizienz berechnet?

Wie wird Komplexität/Effizienz gemessen?

Was ist praktisch relevant?

Einstieg

Für die algorithmische Lösung eines gegebenen Problems ist es unerlässlich, dass der gefundene Algorithmus das Problem korrekt löst. Darüber hinaus ist es natürlich wünschenswert, dass er dies mit möglichst geringem Aufwand tut. Manchmal ist dies auch unerlässlich – etwa beim automatischen Abschalten eines Kernkraftwerkes im Falle einer Havarie.

Die Theorie der Komplexität von Algorithmen beschäftigt sich damit, gegebene Algorithmen hinsichtlich ihres Aufwandes abzuschätzen und – darüber hinaus – für gegebene Problemklassen zu bestimmen, mit welchem Mindestaufwand Probleme dieser Klasse gelöst werden können.

Wir haben bereits Beispiele aus der Numerik kennen gelernt, wo unterschiedliche Algorithmen das gleiche Problem mit unterschiedlicher Effizienz lösen. Das Ergebnis war (fast) immer gleich (aber in der Numerik nicht selbstverständlich).

AuD dpunkt 7.3 Komplexität

Ein Beispiel: Suche in linearen Arrays

Die Bestimmung des Aufwandes wollen wir zunächst an einem einfachen Beispiel verdeutlichen: der sequenziellen Suche in Folgen. Gegeben seien hierzu

i=IndexOf(b ∈ {a₁,..., an})

eine Zahl n ≥ 0,

n Zahlen A=a₁,..., an, die alle verschieden sind,

eine Zahl b.

Gesucht wird der Index i = 1, 2,..., n, so dass b = ai ist, sofern ein solcher Index existiert. Sonst soll i = -1 ausgegeben werden.

Ein Beispiel: Suche in linearen Listen

Eine sehr einfache Lösung (Implementierung) dieses Suchproblems ist die folgende (wobei standardmäßig an+1 = 0 gesetzt sei) und mit i=0 als programmatischen Startindex:

a=[1,2,5,6,7]
b=5

i=0
n=length(a)
while (i<n && b != a[i]) {
  i=i+1
}
if (i==n) i=-1; // nicht gefunden

Algorithmus 5-1. Suche in linearer Array Liste

Am Ende hat i den gesuchten Ausgabewert (oder -1 wenn nicht gefunden).

Analyse

Der Aufwand der Suche, d.h. die Anzahl der Schritte, hängt von der Eingabe ab, d.h. von n, A=a₁,..., an und b. Es gilt:

Bei erfolgreicher Suche, wenn b = ai ist, werden S = i Schritte benötigt.

Bei erfolgloser Suche werden S = n + 1 Schritte benötigt.

Die erste Aussage hängt noch von zu vielen Parametern ab, um aufschlussreich zu sein. Man ist bemüht, globalere Aussagen zu finden, die nur von einer einfachen Größe abhängen. Hier bietet sich die Länge n der Eingabeliste an und man beschränkt sich auf Fragen der Art:

Wie groß ist S für ein gegebenes n im schlechtesten Fall?

Wie groß ist S für ein gegebenes n im Mittel?

Wir analysieren nun den Fall der erfolgreichen Suche:

Im schlechtesten Fall wird b erst im letzten Schritt gefunden, d.h. b = an. Also gilt: S = n im schlechtesten Fall.

Um eine mittlere Anzahl von Schritten zu berechnen, muss man Annahmen über die Häufigkeit machen, mit der – bei wiederholter Verwendung des Algorithmus mit verschiedenen Eingaben – b an erster, zweiter, …, letzter Stelle gefunden wird.

Wird b häufiger am Anfang der Liste gefunden, so ist die mittlere Anzahl von Suchschritten sicherlich kleiner, als wenn b häufiger am Ende der Liste gefunden wird.

Als einfaches Beispiel nehmen wir die Gleichverteilung an. Läuft der Algorithmus N-mal, N ≫ 1, so wird b gleich häufig an erster, zweiter,.., letzter Stelle gefunden, also jeweils N/n-mal.

Dann werden für alle N Suchvorgänge insgesamt M Schritte benötigt, im Mittel S=M/N:

image-placeholder
(5-1)

Also im Mittel bei Gleichverteilung:

image-placeholder
(5-2)

Unser Algorithmus ist für das gestellte Problem keineswegs der schnellste, sondern eher einer der langsameren. Es gibt Algorithmen, die die Suche in Listen (oder Tabellen) mit n Einträgen unter speziellen Voraussetzungen i.W. mit einer konstanten, nicht von n abhängigen Anzahl von Schritten lösen!

Die besten Suchverfahren für direkten Zugriff, die auch Ordnung der Schlüssel zulassen, benötigen eine logarithmische Anzahl von Schritten, d.h. S = a · log2(b · n) + c, wobei a, b, c Konstanten sind.

Asymptotische Analyse

Meist geht es bei der Analyse der Komplexität von Algorithmen bzw. Problemklassen darum, als Maß für den Aufwand eine Funktion F(n) zu finden.

F(n) = a bedeutet: Bei einem Problem der Größe n ist der Aufwand a.

Die Problemgröße n bezeichnet dabei in der Regel ein Maß für den Umfang einer Eingabe, z.B. die Anzahl der Elemente in einer Eingabeliste oder die Größe eines bestimmten Eingabewertes.

Der Aufwand a ist in der Regel ein grobes Maß für die Rechenzeit, jedoch ist auch der benötigte Speicherplatz zuweilen Gegenstand der Analyse.

Die Rechenzeit wird meist dadurch abgeschätzt, dass man zählt, wie häufig eine bestimmte Art von Operation ausgeführt wird, z.B. Speicherzugriffe, arithmetische Operationen.

Auf diese Weise erhält man ein maschinenunabhängiges Maß für die Rechenzeit, die mit einer abstrakten Maschine maschinenunabhängig bestimmt werden kann ⇒ Continuum VM in Java2JS!

Die Aufwandsfunktion F lässt sich in den wenigsten Fällen exakt bestimmen. Vorherrschende Analysemethoden sind wie bereits eingeführt:

Abschätzungen des Aufwandes im schlechtesten Fall

Abschätzungen des Aufwandes im Mittel

Abschätzungen des Aufwandes im besten Fall (Business best hope)

Selbst hierfür lassen sich im Allgemeinen keine exakten Angaben machen. Man beschränkt sich dann auf approximiertes Rechnen in Größenordnungen.

Rechnen in Größenordnungen

Das folgende Beispiel illustriert die Schwierigkeit von exakten Analysen, insbesondere bei Abschätzungen im Mittel, bereits in recht einfachen Fällen.

Gegeben: n ≥ 0, A={a₁,.., an, ai ∊ ℕ}

Gesucht: Der Index i der (ersten) größten Zahl

a=[5,2,1,7,6]

n=length(a)
amax=a[0],imax=0
for (i=1;i<n;i++) {
  if (amax<a[i]) { amax=a[i]; imax=i }
}

Algorithmus 5-2. Maximumssuche in linearer Array Liste

Analyse: Wie oft wird die Anweisung {\} im Mittel ausgeführt, abhängig von *n? (Worst case wäre n-1, best case 1).

Diese gesuchte mittlere Anzahl sei Tn. Offenbar gilt: 1 ≤ Tn ≤ n.

Beobachtung: {\} wird genau dann ausgeführt, wenn *ai das größte der Elemente {a₁,.., ai} ist.

Annahme (Gleichverteilung): Für jedes i = 1,.., n hat jedes der Elemente a₁,..,an die gleiche Chance, das größte zu sein.

Das heißt, dass bei N Durchläufen durch den Algorithmus, N ≫ 1, insgesamt N/n-mal die Anweisung {\} ausgeführt wird für *i = 1,..,n. Das heißt:

imax := 1 wird N-mal, d.h. immer, ausgeführt

imax := 2 wird N/2-mal ausgeführt

etc.

Die gesamte Ausführungszeit ist dann N*Tn:

image-placeholder
(5-3)

Hn ist die harmonische Zahl mit der Näherung Hn≈ln(n)+γ

Da der Aufwand schon vom Ansatz her ohnehin nur grob abgeschätzt werden kann, macht eine Feinheit wie +γ im obigen Beispiel nicht viel Sinn. Interessant ist lediglich, dass Tn logarithmisch von n abhängt, nicht so sehr, wie dieser Zusammenhang im Detail aussieht.

Man schreibt dafür die O-Notation mit der weiteren Approximation ln(n)≈log(n):

image-placeholder
(5-4)

D.h. Tn ist von der Ordnung log n, wobei multiplikative und additive Konstanten sowie die Basis des Logarithmus unspezifiziert bleiben.

Die O-Notation

Die O-Notation lässt sich mathematisch exakt definieren. Seien f, g : ℕ → ℕ Funktionen, dann gilt:

image-placeholder
(5-5)

Was bedeutet diese Relation?

Das heißt, dass f(n)/g(n) für genügend große n > n₀ durch eine Konstante c beschränkt ist. Anschaulich bedeutet dies, dass f nicht stärker wächst als g.

Diese Begriffsbildung wendet man bei der Analyse von Algorithmen an, um Aufwandsfunktionen f durch Angabe einer einfachen Vergleichsfunktion g abzuschätzen, so dass f(n) = O(g(n)) gilt, also das Wachstum von f durch das von g beschränkt ist (Oberschranke).

Eigentlich ist die Angabe f = O(g) im mathematischen Sinn nicht exakt. Vielmehr müsste man f ∊ O(g) schreiben, um auszudrücken, dass f zur Klasse der Funktionen gehört, deren Wachstum asymptotisch durch das Wachstum von g beschränkt ist. Die Schreibweise mit dem »=« hat sich allerdings allgemein eingebürgert, so dass wir sie auch verwenden.

Abbildung 5-1. Asymptotische obere Schranke: O-Notation [addp]

Da die O(g)-Notation eine obere Grenze für eine Klasse von Funktionen definiert, kann die Funktion g jeweils vereinfacht werden, indem konstante Faktoren weggelassen werden sowie nur der höchste Exponent berücksichtigt wird.

Beispiele:

image-placeholder
(5-6)

Diese Ungleichung wird für n ≥ n₀ erfüllt, wenn man beispielsweise c = 2 und n₀ = 1 einsetzt (erster Fall).

Für kleine n kann es aber signifikante Abweichungen geben (siehe Übungsaufgaben) von der tatsächlichen Rechenzeit geben!

Warum?

Komplexitätsklassen

Aufwand | Klasse
O(1) | Konstanter Aufwand (unabhängig von n)
O(log n) | Logarithmischer Aufwand
O(n) | Linearer Aufwand
O(n log n) | Linearer Aufwand
O(n²) | Quadratischer Aufwand
O(n³) | Kubischer Aufwand
O(nk) | Polynomieller Aufwand für k ≥ 0
O(kn) | Exponentieller Aufwand

Typische Komplexitätsklassen aufsteigend sortiert

Abbildung 5-2. Wachstum für ausgewählte Komplexitätsklassen [addp]

Die Polynomiellen Klassen sind auch noch für großes n mit "schnelleren" Rechnern (z.B. durch Parallelisierung) in akzeptabler Zeit lösbar, wo hingegen exponentielle Laufzeit auch nicht mehr durch schnellere Rechner oder Parallelisierung lösbar sind.

Recht illustrativ ist es auch, sich vor Augen zu führen, welche Größenordnung ein Problem haben kann, wenn man die Zeit durch eine maximale Dauer T begrenzt. Wir nehmen dazu an, dass ein Schritt des Aufwandes genau eine Mikrosekunde (1 µs) dauert. G sei dabei das größte lösbare Problem in der Zeit T. Den Aufwand g(n) = log n lassen wir weg, da man hier praktisch unbegrenzt große Probleme in vernünftiger Zeit bearbeiten kann.

Abbildung 5-3. Zeitaufwand für einige Problemgrößen [addp]

Problemklassen

Aufwand | Problem
O(1) | Einfache Suchverfahren mit Hash Tabellen
O(log n) | Allgemeine Suchverfahren für Tabellen (Baum-Suchverfahren)
O(n) | sequenzielle Suche, Suche in Texten, syntaktische Analyse von Programmen, einfache Vektoroperationen
O(n log n) | Sortieren, Suche
O(n²) | einige dynamische Optimierungsverfahren (z.B. optimale Suchbäume), Multiplikation Matrix-Vektor (einfach)
O(n³) | Matrizen-Multiplikation (einfach)
O(2n) | viele Optimierungsprobleme (z.B. optimale Schaltwerke), automatisches Beweisen (im Prädikatenkalkül 1. Stufe)

Typische Problemklassen

NP versa P-vollständig

P-vollständig Gruppe

Der Algorithmus löst maximal in polynomieller Laufzeit (aber beliebiger Polynomgrad)

NP

Der Algorithmus löst maximal in exponentieller Laufzeit (aber beliebige Basis), eventuell auch in P Laufzeit.

Offensichtlich gehört jedes Problem aus P auch NP an, d.h., es gilt P ⊆ NP.

Es gibt eine Reihe von Problemen, von denen man weiß, dass sie NP angehören, aber nicht, ob sie auch P angehören.

Das bedeutet, dass sie mithilfe eines nichtdeterministischen Algorithmus gelöst werden können, aber es noch nicht gelungen ist, einen effizienten deterministischen Algorithmus zu finden.

Es ist – streng genommen – ein offenes Problem, ob sich die exponentiellen Probleme nicht doch mit polynomialem Aufwand lösen lassen, d.h., ob P=NP gilt. Es wäre jedoch eine große Überraschung, wenn sich dies herausstellen sollte. Man kann allerdings beweisen, dass es eine Klasse von verwandten Problemen aus NP gibt, die folgende Eigenschaft aufweisen: Falls eines dieser Probleme in polynomialer Zeit mit einem deterministischen Algorithmus gelöst werden könnte, so ist dies für alle Probleme aus NP möglich (demzufolge wäre P=NP). Man bezeichnet Probleme mit dieser Eigenschaft als NP-vollständig. Ein bekanntes Problem aus dieser Klasse ist das Problem des Handlungsreisenden.

Aber:

Diese Annahmen und Aussagen gelten nur für "handelsübliche" Rechnermodelle, also der Turing- oder Registermaschine (von-Neumann Rechner). Wie sich das bei völlig andersartigen Rechnermodellen (z.B. Quantencomputer) entwickelt ist noch unklar.

Analyse von Algorithmen

Wie kann nun die Laufzeitkomplexität eines Algorithmus bestimmt werden? Die Probleme einer exakten Analyse haben wir bereits diskutiert. Die Bestimmung der Größenordnung ist dagegen wesentlich einfacher, da sich hierfür einige einfache Regeln angeben lassen:

Zählschleifen

for(i=a;i<b;i=i+c) { * }

Definition 5-1. Laufzeit := max. Laufzeit der inneren Anweisung · Anzahl der Iterationen (b-a)/c

Geschachtelte Zählschleifen

for(i=a1;i<b1;i=i+c1) for(j=a2;j<b2;j=j+c2) { * }

Definition 5-2. Laufzeit := max. Laufzeit der inneren Anweisung · Produkt der Durchläufe aller Schleifen, d.h. Π~i~(b~i~-a~i~)/c~i~

Nacheinanderausführung

for(i=a;i<b;i=i+c) { * } ; for(j=a2;j<b2;j=j+c2) { * }

Definition 5-3. Bei einer Sequenz von Anweisungen werden die Laufzeiten zunächst addiert. Da konstante Faktoren weggelassen werden können und nur die jeweils höchsten Exponenten berücksichtigt werden, wird für die Gesamtlaufzeit nur die maximale Laufzeitkomponente verwendet.

Bedingte Verzweigungen

if (cond) { A1 } else { A2 }

Definition 5-4. Laufzeit := Aufwand für Test + max(Aufwand für A1, Aufwand für A2)

Funktionsaufrufe (Rekursion)

function foo(x) { return terminatecond(x)?C:F(foo(G(x))) }

Definition 5-5. Laufzeit := max. Laufzeit der inneren Anweisung · Anzahl der Iterationen

Landau Symbole

But wait, there is more...

Abbildung 5-4. Es gibt neben der O-Notation noch weitere Funktionen die unterschiedliche Schranken definieren [Wikipedia]

Little versa Big O

Big-O- und Little-O-Notationen haben sehr ähnliche Definitionen, und ihr Unterschied liegt darin, wie streng sie in Bezug auf die von ihnen dargestellte Obergrenze sind.

Big O

Engerer Abstand zwischen f und g

image-placeholder
(5-7)

Little o

Großzügigerer Abstand zwischen f und g

image-placeholder
(5-8)

Datenbanken

Datenstrukturen

Algorithmen

Anwendungen

Motivation

Datenbanken sind eine wichtige "Anwendung" für Algorithmen und Datenstrukturen.

Viele Algorithmen und Datenstrukturen aus dem Kurs finden sich in Datenbankprogrammen wieder

Extern sichtbar für die Datenorganisation durch/über die Nutzer

Intern unsichtbar aber elementar wichtig für die extern sichtbare Datenorganisation

Eine Datenbank zentralisiert Datenspeicherung und Datenorganisation (wenn auch DBs selbst verteilt sein können)!

Abbildung 6-1. Links: Mehrere Anwendungen verwalten ihre Daten selbst in Dateien. Rechts: Die Daten aller Anwendungen werden in einer gemeinsamen Datenbank von einem Datenbankmanagement-System verwaltet.

Die wichtigsten Vorteile von Datenbankmanagement-Systemen im Vergleich zu einer dateiorientierten Strategie sind:

Die Daten werden in der Regel unabhängig von den Anwendungen gespeichert, die diese verwenden.

Die Daten sollten damit möglichst unabhängig von der verwendeten Programmiersprache sein, da sich diese im Laufe der Zeit eventuell ändert.

Die Anwendung kann durch eine neuere Software mit größerer Operationalität und Performant ersetzt oder ergänzt werden, dieselben Daten können aber langfristig weiter verwendet werden.

Die Daten werden in der Regel nur einmal zentral verwaltet und nicht redundant an mehreren unabhängigen Stellen. Damit sinkt das Risiko von Inkonsistenzen (mehrere unterschiedlich geänderte Kopien derselben Daten). Zusätzlich wird dadurch weniger Speicherplatz benötigt.

Die Daten werden nicht nur persistent gespeichert, das Datenbankmanagement-System (DBMS) sorgt für die Konsistenz der Daten, auch wenn die Anwendung mitten in einer Operation abstürzt. Auch wenn die Datenbank zerstört ist, kann sie mithilfe von Backup und Recovery wieder hergestellt werden.

Das DBMS ermöglicht, dass viele Anwendungen bzw. Benutzer quasi gleichzeitig lesend und auch schreibend zugreifen können. Hierzu werden Konzepte wie Transaktionen angeboten.

Das DBMS kontrolliert die Zugriffe auf die Daten und sorgt dafür, dass definiert werden kann, welcher Nutzer bzw. welche Anwendung welche Daten ansehen oder ändern darf.

DBMS: Datenbankmanagement-System, die Softwareschnittstelle und das Ausführungsprogramm

Die Programmierung der Anwendungen wird vereinfacht, da das DBMS das Anlegen, Ändern, Löschen und Suchen von Daten implementiert und optimiert. Die Implementierung der Operationen ist nicht festgelegt und kann geändert werden (z.B. Bäume statt Listen verwenden)

Über die Sektoren der Festplatte und die Speicherseiten des Betriebssystems zerbrechen sich jetzt die Entwickler des Herstellers des DBMS den Kopf. Die Benutzer und Entwickler der Anwendungen kennen nur eine konzeptuelle Sicht auf die Daten in Form von Knoten eines Graphen, von Zeilen in Tabellen oder von Schlüssel-Wert-Paaren.

Daten und Datenstrukturen

je nach Datenbankmodell können verschiedene Daten und Datenstrukturen gespeichert und verarbeitet werden:

Name / Wert-Paare dienen dazu Daten wiederzufinden. Dazu müssen diese eindeutig identifizierbar sein. Im einfachsten Fall ist das ein eindeutiger Name (wie die Pfad- und Dateinamen in einem Dateisystem). Das kann auch ein aus den Daten selbst berechneter Hash-Wert sein. Damit wäre jede Entität bzw. jedes Objekt jeweils ein Wert. Als identifizierender Name kann eventuell eines der Attribute verwendet werden.

Die Tabelle ist eine sehr häufige Darstellungsform von Daten, besonders im Bereich betriebswirtschaftlicher Anwendungen. Aus einem Entitätstyp bzw. einer Klasse wird im einfachsten Fall eine Tabelle. Aus jedem Attribut wird eine Spalte. Objekte bzw. Entitäten sind jeweils die Zeilen. Tabellen sind die Grundlage der relationalen Datenbankmanagement-Systeme.

Die Baumstruktur: Von einer Wurzel aus sind die anderen Knoten erreichbar. Aus einem Entitätstyp bzw. einer Klasse wird eine Menge von Bäumen. Ein Objekt bzw. eine Entität wird als Baum dargestellt werden: Jedes Attribut ist ein innerer Knoten oder ein Blatt. Baumstrukturen bieten verbesserte Sucheigenschaften.

Ein Gerichteter Graph: Wenn die Objekte bzw. Entitäten sich untereinander häufig referenzieren, kann dies gut als gerichteter Graph dargestellt werden mit den Objekten bzw. Entitäten als Knoten und den jeweiligen Referenzen als (annotierte) Kanten.

Zeitreihe und zeitabhängige Daten: Ein Sensor misst eine physikalische Größe, zu speichern sind Zeitpunkt und Messwert. Das wäre ein Objekt bzw. eine Entität. Eventuell kommen noch Metadaten dazu wie die Geoposition und die physikalische Einheit in der der Sensor misst. Regelmäßiges Messen erzeugt so eine Zeitreihe.

(Text) Dokumente: (Internet-) Anwendungen erzeugen teilweise große Mengen von mehr oder weniger strukturierten Textdokumenten, auch die Log-Ausgaben zählen dazu. Damit wäre ein Textdokument, z. B. ein Text über einen Mitarbeiter ein Objekt bzw. die Entität. Möglicherweise gibt es dazu eine Klasse, die Strukturvorgaben an das Dokument macht.

Abbildung 6-2. Überblick über verschiedene Möglichkeiten Daten darzustellen. a) als Menge von Name-Wert Paaren, b) als Tabelle oder in mehreren Tabellen, c) als Zeitreihe, d) als Menge von Bäumen, e) als ungerichteten oder gerichteten annotierten Graphen oder f) als Menge von (Text-) Dokumenten

Zugriffsmuster auf gespeicherte Daten

Was sind nun Kriterien zur Wahl einer bestimmten Repräsentation der Daten als Baum, Graph oder Tabelle?

Darstellung als Tabellen

Ein Entitätstype besteht aus einer Klasse mit Attributen

Im einfachsten Fall wird aus jedem Entitätstyp eine Tabelle modelliert

Die Attribute werden jeweils zu Spalten. Ein identifizierendes Attribut ist dabei der Primärschlüssel der Tabelle.

Beispiel 6-1. Entity-Relationship-Modell der Relationen Mitarbeiter und Abteilung

Die Beziehung zwischen Mitarbeiter und Abteilung ist 1 zu N,

ein Mitarbeiter ist genau in einer Abteilung und in einer Abteilung können beliebig viele Mitarbeiter sein.

Dies wird über einen Fremdschlüssel dargestellt, die Tabelle Mitarbeiter hat eine Spalte mit Abt. Nr. Werten, diese sind Primärschlüssel in der Abteilung-Tabelle.

Dies war ein Beispiel für die Übersetzung eine logischen Datenmodells in Form eine ER-Modells bzw. Klassenmodells auf ein physisches Datenmodell in Form von Tabellen.

Abbildung 6-3. Abbildung des ER-Modells auf Tabellen und auf eine Baumstruktur [kap16db]

Relationale Datenbankmanagement-Systeme

Das relationale Datenbankmodell und darauf aufbauende relationale Datenbankmanagement-Systeme (RDBMS) gehen auf eine in 1970 veröffentlichte Arbeit von E. F. Codd zurück.

Codd legte damit das mathematische Fundament in Form der relationalen Algebra

Unter einer Relation versteht man im Zusammenhang mit dem relationalen Datenmodell eine logische Zusammenfassung von Informationen in einer Form, die in etwa einer Tabelle vergleichbar ist.

Gemeint ist auch eine Relation im mathematischen Sinne, also eine Menge von Tupeln.

Zur eindeutigen Identifikation aller Zeilen der Relation sollte diese einen Primärschlüssel (Pri-mary Key) besitzen (vorhandenes Attribut oder erzeugte Nummer ID).

Um den Zugriff zu beschleunigen, kann man neben dem Primärschlüssel weitere eindeutige Schlüssel einführen, sog. Zweitschlüssel (Secondary Keys).

Relationen

Abbildung 6-4. Die Relation Mitarbeiter hat vier Attribute (Namen PersonalNr , Name , Gehalt und AbteilungsNr) drei Zeilen (also insgesamt drei 4-Tupel). Die Relation Abteilung hat drei Attribute (AbteilungsNr , Name und Standort) sowie vier Zeilen (also insgesamt fünf 3-Tupel). Die (Primär)Schlüssel der beiden Tabellen sind jeweils für jede Zeile eindeutig: PersonalNr ist Schlüssel der Relation Mitarbeiter und AbteilungsNr ist Schlüssel von Abteilung.

Beziehungen (Relationships)

Relationen und ihre Tupel bzw. Tabellen und ihre Zeilen können nicht isoliert betrachtet werden.

Relationen können also in Beziehung zu einander stehen, wie dies schon in den ER-Modellen in Form der Beziehungen (Relationships) zwischen den Entitäten zum Ausdruck kommt. Abhängig von den Kardinalitäten unterscheidet man:

1:1 Beziehungen ⇒ Zu einem Tupel gehört genau ein anderes Tupel.

1:N Beziehung ⇒ Zu einem Tupel gehört mindestens ein (≥ 1) anderes Tupel.

M:N Beziehung ⇒ Zu einem Tupel gehören beliebig viele (≥ 0) andere Tupel umgekehrt gilt dasselbe.

Relationale Algebra

Eine Algebra besteht aus einer Grundmenge und einer Menge von Operationen, die auf dieser Grundmenge definiert sind und deren Ergebnisse wieder in der Grundmenge liegen.

In unserem Fall ist die Grundmenge die Menge aller Relationen (Tabellen), die Operationen bilden eine oder mehrere Relationen wieder auf Relationen ab und können flexibel miteinander verknüpft werden.

Die relationale Algebra legt ein mathematisches Fundament für relationale DBMS.

Eine Datenbank-anfrage kann mathematisch vergleichsweise einfach modelliert werden.

Mithilfe der Operationen der Algebra kann diese dann z. B. durch Rechenregeln in eine andere Anfrage umgeformt werden, die dasselbe Ergebnis liefert aber effizienter ausgeführt werden kann.

Selektion σ

Mit der Selektion σ werden aus einer Relation entsprechend einer Bedingung (Prädikat) ein oder mehrere Tupel herausgegriffen.

Abbildung 6-5. Anwendung der Selektion auf die Relation Mitarbeiter

Projektion π

Mit der Projektion π können Attribute Attri (in einer Tabelle wären das Spalten) aus einer Relation herausgegriffen werden.

Abbildung 6-6. Anwendung der Projektion auf die Relation Mitarbeiter

Kartesisches Produkt (Kreuzprodukt ×)

Mit dem (kartesischen) Produkt × wird analog zum kartesischen Produkt zweier Mengen das Produkt zweier Relationen gebildet. Die resultierende Relation Rel 1 × Rel 2 enthält dann sämtliche Kombinationen, die sich aus den Tupeln der beiden Relationen bilden lassen.

Abbildung 6-7. Aus den Relationen Rel 1 und Rel 2 entsteht durch Rel 1 × Rel 2 eine neue Relation

Vereinigung (Union, ∪)

Die Operation Vereinigung ∪ (Union) vereinigt zwei Relationen Rel 1 und Rel 2 zu einer Relation Rel 1 ∪ Rel 2 , in der alle Tupel der ersten Relation und der zweiten Relation enthalten sind. In beiden Relationen enthaltene Tupel erscheinen im Ergebnis nur einmal. Diese Operation ist nur ausführbar, wenn die Anzahl der Attribute in den beiden zu verknüpfenden Relationen gleich sind und wenn die Attribute miteinander kompatibel sind

Abbildung 6-8. Aus den Relationen Abteilungen A und Abteilungen B entsteht die rechts abgebildete Relation durch Abteilungen A ∪ Abteilungen B

Mengendurchschnitt (Intersection, ∩)

Durch die Operation Mengendurchschnitt ∩ (Intersection) wird aus zwei Relationen Rel 1 und Rel 2 als Ergebnis eine Relation Rel 1 ∩ Rel 2 gebildet, die nur diejenigen Tupel enthält, die sowohl in der ersten Relation als auch in der zweiten Relation enthalten sind. Diese Operation ist nur ausführbar, wenn die beiden Relationen in dem oben bei der Operation Union erläuterten Sinne union-kompatibel sind.

Abbildung 6-9. Aus den Relationen Abteilungen A und Abteilungen B entsteht die rechts abgebildete Relation durch Abteilungen A ∩ Abteilungen B

Mengendifferenz (Difference, −)

Durch die Operation Differenz (Difference) wird aus zwei Relationen Rel 1 und Rel 2 als Ergebnis eine Relation Rel 1 − Rel 2 gebildet, die nur diejenigen Tupel enthält, die in der ersten Relation enthalten sind, in der zweiten Relation jedoch nicht. Diese Operation ist nur ausführbar, wenn die beiden Relationen union-kompatibel sind.

Abbildung 6-10. Aus den Relationen Abteilungen A und Abteilungen B entsteht durch Abteilungen A − Abteilungen B die rechts abgebildete Relation

Division ÷

Es wird die Division einer Relation Rel 1 durch eine Relation Rel 2 bezüglich eines Attributes A aus Rel 1 betrachtet, wobei Rel 2 ebenfalls ein Attribut mit demselben Wertebereich enthalten muss wie das bei der Division verwendete Attribut A. Aus der Ergebnisrelation wird zunächstdas Attribut A gelöscht. Sodann verbleiben in der Ergebnis-Relation Rel 1 ÷ Rel 2 nur diejenigen Tupel, für die irgendein Attribut der Relation Rel 1 alle Werte von Relation Rel 2 enthält.

Abbildung 6-11. In der Relation Rel 1 gibt es nur einen Wert für Attribut 1.1, der mit allen Werten von Attribut 2.1 aus Rel 2 vorkommt: Tupel sind (2, A) und (2, B), der Wert ist damit 2. Dieser Wert findet sich in der Ergebnisrelation

Verbund (Join, )

Bei der Operation Join (Verbund) wird in dessen allgemeinster Form zunächst das Produkt × zweier Relationen gebildet, danach über eine Selektion mit der Verknüpfung zweier Attribute aus je einer der Relationen eine Anzahl von Zeilen herausgegriffen und schließlich über eine Projektion eine Reihe von Attributen ausgewählt. Vorausgesetzt wird dabei, dass die beiden im Join verwendeten Attribute denselben Wertebereich haben.

Umbenennung β

Um vollständig mit Relationen rechnen zu können, fehlt noch eine Operation zur Umbenennung von Spalten. Diese wird mit β bezeichnet.

Die Datenbanksprache SQL

Mit SQL (Structured Query Language) steht eine Sprache zur Verfügung, mit der alle Funktionen auf relationalen Datenbanken ausgeführt werden können. Eine Basis von SQL ist die im vorangegangenen Abschnitt eingeführte Relationenalgebra.

SQL ist eine deklarative Sprache

Der wesentliche Unterschied zwischen Sprachen wie Java oder C und SQL liegt in der Art und Weise wie Anweisungen formuliert werden. In SQL-Anweisungen wird nicht beschrieben wie ein Datenbankzugriff zu erfolgen hat (algorithmisch, prozedural), es wird vielmehr beschrieben, was der Anwender beabsichtigt (deklarativ).

Wenn ein DBMS eine SQL-Anweisung ausführt, muss daher eine Umsetzung in prozedurale Anweisungen erfolgen, da nur solche durch einen Computer ausführbar sind.

Dies kann geschehen durch Umwandlung von SQL-Ausdrücken in Ausdrücke der relationalen Algebra, die dann ihrerseits in einer Sprache wie C unter Verwendung von Konzepten wie B-Bäumen oder Hashing ausgeführt werden können.

SQL basiert zwar auf der relationalen Algebra, besteht aber keineswegs nur aus einfachen Zuordnungen von SQL-Anweisungen zu den Operationen der relationalen Algebra.

Auch wurden die mathematisch geprägten Ausdrücke der relationalen Algebra durch eher umgangssprachliche Formulierungen ersetzt und die Operationen durch Schlüsselworte der Sprache SQL:

Relation → Tabelle, Tupel → Satz oder Zeile und Attribut → Spalte.

SQL-Anweisungen lassen sich zwei wesentlichen Gruppen zuordnen:

DDL (Data Definition Language)

DML (Data Manipulation Language), sowie noch die

DCL (Data Contol Language) zur Wahrung der Datenintegrität.

Zusammenstellung der wichtigsten SQL-Anweisungen der DDL

Zusammenstellung der wichtigsten SQL-Datentypen

Zusammenstellung der DML Anweisungen in SQL

Erzeugen einer Tabelle

Es muss ein Schema angegeben werden dass die Spalten definiert (Name, Typ, weitere Attribute)

Zu jeder Spalte der Datenbank wird ein Name und ein Wertebereich (Datentyp) angegeben. SQL gibt ein eigenes Typsystem vor.

CREATE TABLE Mitarbeiter (
  PersonalNr int primary key,
  Name varchar(100) not null,
  Gehalt int,
  AbteilungsNr int,
  foreign key (AbteilungsNr) references Abteilungen (AbteilungsNr)
);

Definition 6-1. Erzeugung einer nicht existierenden Tabelle "Mitarbeiter"

Einfügen, Ändern und Löschen von Daten

Um Daten in eine Tabelle einzufügen, zu ändern oder zu löschen bietet SQL die drei Anweisungen INSERT , UPDATE und DELETE an. Diese Anweisungen zählen wie das Suchen zur Data Manipulation Language (DML) innerhalb von SQL.

INSERT INTO Mitarbeiter VALUES (104, ’Beneken’, 38000, 5);
INSERT INTO Mitarbeiter (PersonalNr, Name, Abteilung) VALUES (106, ’Schmidt’, 5);

Definition 6-2. Einfügen von Zeilen in die Tabelle "Mitarbeiter"

Suchen mit SELECT

SELECT <Liste von Spalten evtl. mit Berechnungen>
  FROM <Liste mit Tabellen und Sichten>
   [WHERE <Bedingung>]

Definition 6-3. SELECT -Anweisung oder auch SELECT-FROM-WHERE -Anweisung (SFW).

Die nach der SELECT -Anweisung spezifiziert die Spaltennamen (Attribute) einer Tabelle oder mehrerer Tabellen.

Die Ergebnistabelle umfasst genau diese genannten Spalten. Dies ist vergleichbar mit der Projektion π aus der relationalen Algebra. Erlaubt ist auch ein Stern (*), der für alle Attribute steht.

Der Name der Spalte in der Ergebnistabelle kann dabei angepasst werden (SELECT PersonalNr AS Nummer FROM ... ).

Weiterhin können die Werte in den Spalten auch berechnet sein, etwa durch Zusammenfassung von mehreren Werten der Ergebniszeilen, dazu werden Funktionen wie min , max , sum , avg oder count verwendet.

Nach dem Schlüsselwort FROM folgt ein Tabellenname oder eine Liste von Tabellennamen. Wenn keine weiteren Bedingungen hinter WHERE spezifiziert sind, wird das kartesische Produkt (×) aller angegebenen Tabellen gebildet.

Die Zeilen in der Ergebnistabelle werden mit WHERE eingeschränkt: Eine Bedingung liefert für die Zeilen, die in das Ergebnis übernommen werden sollen true und für alle anderen false . In der relationalen Algebra ist dies die Selektion σ Bedingung .

SELECT Name, Gehalt
 FROM Mitarbeiter
  WHERE AbteilungsNr = 3 AND Gehalt > 80000

Beispiel 6-2. Beispiel einer selektiven und konditionalen Suchanweisung

Ein Datenbank Dateisystem

Ein Dateisystem ist i.A. ein hierarchischer Baum (oder Graph)

Verzeichnisse sind Knoten für weitere Teilbäume (Verzeichnisse) oder Dateien

Dateien sind Blätter

Verzeichnisse werden durch / getrennt

Ein Pfad beginnend beim Wurzelknoten / ist eine Referenz zu einem Verzeichnis oder einer Datei.

Naive DB Implementierung

Jedes Verzeichnis ist eine Tabelle

Eine Zeile besteht aus einem Namen und Inhalt

Der Inhalt kann ein Verweis auf eine tiefere folgende Verzeichnistabelle oder der Inhalt einer Datei sein.

CREATE TABLE FolderNNN (
  Name char,
  Type int,
  Site int,
  Date datetime,
  Content char
);

Beispiel 6-3. Type=1: Verzeichnis, Type=2 (Text): Datei, NNN = Fortlaufende Nummerierung 001, 002, ..

CREATE TABLE Folder000 (Name char, Type int, Size int,
                        Date datetime, Content char);
INSERT INTO Folder000 values
  ("foo",  2 , 11 , "Today" ,     "Hello World"),
  ("foo2", 2 , 3  , "Yesterday" , "Joe"),
  ("dir1", 1 , 0  , "1.1.1970" ,  "Folder001");
CREATE TABLE Folder001 (Name char, Type int, Size int,
                        Date datetime, Content char);
INSERT INTO Folder001 values
  ("foo",  2 , 4  , "Today" ,     "End."),

Beispiel 6-4. Ein einfaches Dateisystem

Wie kann man nun aber Pfade auflösen und an die Inhalte von Dateien gelangen oder tiefere Verzeichnisse lesen (listen)?

Rekursive SQL Queries

Man kann einen solchen Dateisystempfad nur rekursiv mit Variablen über mehrere Tabellen hinweg auflösen und das Ergebnis ermitteln.

SQL bietet rekursive Statements

Beispiel Stammbaum

CREATE TABLE family(
  name TEXT PRIMARY KEY,
  mom TEXT REFERENCES family,
  dad TEXT REFERENCES family,
  born DATETIME,
  died DATETIME -- NULL if still alive
  -- other content
);

Beispiel 6-5. Beispiel Stammbaum

WITH RECURSIVE
  parent_of(name, parent) AS
    (SELECT name, mom FROM family UNION SELECT name, dad FROM family),
  ancestor_of_alice(name) AS
    (SELECT parent FROM parent_of WHERE name='Alice'
     UNION ALL
     SELECT parent FROM parent_of JOIN ancestor_of_alice USING(name))
SELECT family.name FROM ancestor_of_alice, family
 WHERE ancestor_of_alice.name=family.name
   AND died IS NULL
 ORDER BY born;

Beispiel 6-6. Rekursive Stammbaumiteration

Algorithmenparadigmen

Unter einem Paradigma versteht man unter anderem in der Wissenschaftstheorie ein »Denkmuster, welches das wissenschaftliche Weltbild einer Zeit prägt« – ein Algorithmenparadigma sollte daher ein Denkmuster darstellen, das die Formulierung und den Entwurf von Algorithmen und damit letztendlich von Programmiersprachen grundlegend prägt.

Es gibt aber keine einheitliche Auffassung über die Anzahl existierender Algorithmenparadigmen und deren Abgrenzung.

Algorithmen

Ein Algorithmenparadigma legt die Denkmuster fest, die einer Beschreibung eines Algorithmus zugrunde liegen.

Ein Algorithmus ist eine Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-)Schritte.

Es gibt zwei grundlegende Arten, Schritte von Algorithmen zu notieren (schießloich die Programmierklassen):

Applikative Algorithmen sind eine Verallgemeinerung der Funktionsauswertung mathematisch notierter Funktionen.

In ihnen spielt Rekursion eine wesentliche Rolle.

Imperative Algorithmen basieren auf einem einfachen Maschinenmodell mit gespeicherten und änderbaren Werten.

Hier werden primär Schleifen und Alternativen als Kontrollbausteine eingesetzt.

In der Informatik werden weitere Paradigmen diskutiert: logisch, objektorientiert, agentenorientiert, parallel.

Applikative Algorithmen

Die Idee applikativer Algorithmen besteht darin, eine Definition zusammengesetzter Funktionen durch Terme mit Unbestimmten vorzunehmen. Eine einfache Funktionsdefinition in diesem Sinne kann wie folgt mathematisch notiert werden:

image-placeholder
(7-1)

Streng genommen erfüllt die Funktionsdefinition erst zusammen mit einem Auswertungsalgorithmus für Terme unsere Anforderungen an eine Algorithmensprache – erst die Termauswertung legt die Reihenfolge der atomar auszuführenden Berechnungsschritte fest.

Applikative Algortihmen entsprechen den funktionalen Programmiersprachen und bestehen aus:

Termen als Ausdrücke für die Berechnung

Termen mit Unbestimmten

Funktionsdefinitione

Funktionsauswertung

Terme

Gegeben sind im Folgenden zwei (unendliche, abzählbare) Mengen von Symbolen (als »Unbestimmte« bezeichnet):

    x, y, z, … vom Typ int
    q, p, r, … vom Typ bool

Wir müssen nun die Definition von Termen auf Terme mit Unbestimmten erweitern.

Die int-Werte …, − 2, −1, 0, 1, … sind elementare nicht weiter zerlegbar int-Terme.

Sind t, u int-Terme, so sind auch (t + u), (t − u), (t · u), (t ÷ u), sign(t), abs(t) int-Terme.

Ist b ein bool-Term und sind t, u int-Terme, so ist auch if b then t else u fi ein int-Term.

Nur die durch diese Regeln gebildeten Zeichenketten sind int-Terme.

Definition von int-Termen und Regelwerk zur Berechnung

Ein Term mit Unbestimmten wird analog zu Termen ohne Unbestimmte gebildet.

x, x − 2, 2x + 1, (x + 1)(y − 1)

Definition 7-1. Terme vom Typ int mit Unbestimmten

p, p ∧ true, (p ∨ true) = ⇒ (q ∨ false)

Definition 7-2. Terme vom Typ bool

Termkomposition

Komplexeren Berechnungen kann man durch Zusammensetzen von Grundoperationen durchführen

image-placeholder
(7-2)

Bei der Termbildung dienen Klammern und Prioritäten zur Festlegung der Auswertungsreihenfolge

Für Algorithmensprachen gibt es eine weitere Art von Termen , die in normaler Arithmetik nicht eingesetzt werden (oder doch?).

Bedingte Terme erlauben – analog dem Auswahloperator in der Pseudocode-Notation – die Auswahl zwischen zwei Alternativen basierend auf dem Test eines Prädikats. Notiert wird ein bedingter Term wie folgt:

if b then t else u fi

Funktionsdefinition

Basierend auf der erweiterten Termdefinition, können wir nun eine Notation für die Funktionsdefinitionen festlegen.

Sind v₁, …, vn Unbestimmte vom Typ τ₁, …, τn (bool oder int) und ist t(v₁, …, vn) ein Term, so heißt

image-placeholder
(7-3)

eine Funktionsdefinition der Funktion f vom Typ τ. τ ist dabei der Typ des Terms t(v1, …, vn).

Funktionsdefinitionen

f heißt Funktionsname,

die v₁, …, vn heißen formale Parameter und

der Term t(v₁, …, vn) heißt Funktionsausdruck.

foo(a,b) = a+b

Funktionen

Jede Funktion ist also bestimmt durch:

Einen Namen (oder ohne Name: Lambda Ausdruck)

Formalen Parametern

Funktionsausdruck (Funktionskörper)

Einer Eingabemenge 𝔼 von Werten

Einer Ausgabemenge 𝔸 von Werten

Einer Relation r: 𝔼 → 𝔸

Auswertung von Funktionen

Definierte Funktionen können mit konkreten Werten aufgerufen und ausgewertet werden.

Eine Funktionsdefinition definiert eine Funktion mit der folgenden Signatur:

image-placeholder
(7-4)

Sind nun a₁, .., an Werte vom Typ τ₁, .., τn, so ersetzt man bei der Auswertung von f(a₁, .., an) im definierenden Term jedes Vorkommen der Unbestimmten vi durch den Wert ai und wertet dann den entstehenden Term t(a₁, .., an) aus.

Die konkreten Werte a₁, …, an heißen aktuelle Parameter.

Den Ausdruck f(a₁, …, an) bezeichnen wir als Funktionsaufruf.

Funktionale Komposition

Terme sind Ausdrücke

Aufrufe definierter Funktionen sind auch Terme

Terme können also Funktionsaufrufe enthalten

Argumente von Funktionen können wiederum Funktionsaufrufe sein

f(x, y) = if g(x, y) then h(x + y) else h(x − y) fi
g(x, y) = (x = y) ∨ odd(y)
h(x) = j(x + 1) · j(x − 1)
j(x) = 2x − 3

Das grundlegende Programmierparadigma von funktionalen Sprachen (Haskell, OCaML)

Eine Funktionsdefinition f heißt rekursiv, wenn direkt (oder indirekt über andere Funktionen) ein Funktionsaufruf f(..) in ihrer Definition auftritt.

Abbildung 7-1. Funktionsauswertung; obwohl scheinbar mehrschrittig wird die Berechnung nur durch Datenabhängigkeiten "gesteuert". Es findet eine schrittweise Termreduktion durch Einsetzen und Zusammenfassen sowie Berechnung mit grundlegenden Operationen statt. [addp]

Schließlich kann zusammengefasst werden:

Ein applikativer Algorithmus ist eine Liste von Funktionsdefinitionen:

image-placeholder
(7-5)

Die erste Funktion f₁ wird wie beschrieben ausgewertet und ist die Bedeutung (Semantik) des Algorithmus (quasi die main Funktion).

Applikativer Algorithmus

Applikative Algorithmen sind die Grundlage einer Reihe von universellen Programmiersprachen, wie APL, Lisp, Scheme, Haskell oder Scala etc. Diese Programmiersprachen werden als funktionale Programmiersprachen bezeichnet.

Ein applikativer Algorithmus muss nicht für alle Eingabewerte zu einem definierten Ergebnis führen. Das folgende Beispiel verdeutlicht dies.

f(x) = if x = 0 then 0 else f(x − 1) fi

f(−1) → f(−2) → … Auswertung terminiert nicht!

Eine nicht terminierende Berechnung führt als Vereinbarung zum Ergebnis ⊥ für undefiniert. Also gilt:

image-placeholder
(7-6)

Eine (möglicherweise) für einige Eingabewertekombinationen undefinierte Funktion heißt partielle Funktion.

x! = x(x − 1)(x − 2) … 2 · 1 für x > 0
fac(x) = if x = 0 then 1 else x · fac(x − 1) fi

Beispiel 7-1. Beispiel für einen applikativen Algorithmus: Fakultät mit Rekursion

f0 = f1 = 1, fi = fi−1 + fi−2 für i > 0
fib(x) = if (x = 0) ∨ (x = 1) then 1
         else fib(x − 2) + fib (x − 1) fi

Beispiel 7-2. Beispiel für einen applikativen Algorithmus: Fibonacci Zahlen mit Rekursion

f(x) = if x > 100 then x − 10 else f(f(x + 11)) fi
⇔
f(x) = if x > 100 then x − 10 else 91 fi

Beispiel 7-3. Noch ein kurioses Beispiel: Die McCarthys 91 Funktion und zwei Funktionen mit gleicher Ein- und Ausgabemenge und Relation

Imperative Algorithmen

Die imperativen Algorithmen bilden die verbreitetste Art, Algorithmen für Computer zu formulieren, da sie auf einem abstrakten Modell eines üblichen Rechners basieren.

Wir hatten trotzdem zuerst applikative Algorithmen betrachtet, da diese mathematisch einfacher zu formalisieren und zu analysieren sind.

Imperative Algorithmen basieren auf den Konzepten Anweisung und Variable.

Das imperative Paradigma ist sehr nah mit dem intuitiven Algorithmenbegriff verwandt und wird durch viele Programmiersprachen wie C, Pascal, Fortran, COBOL oder auch von Java realisiert.

Variablen

Variablen bilden die Speicherplätze für Werte:

Eine Variable besteht aus einem Namen (z.B. X) und einem veränderlichen Wert. Jeder Variablen ist ein Typ zugeordnet.

Ist t ein Term ohne Unbestimmte und w(t) sein Wert, dann bezeichnet man das Paar X :=t als Wertzuweisung. Ihre Bedeutung ist festgelegt durch:

Nach Ausführung von X:=t gilt: X = w(t).

Vor der Ausführung der ersten Wertzuweisung gilt: X = ⊥ (undefiniert).

Zustände

Die möglichen Zustände eines Rechners werden wie folgt festgelegt:

Ist 𝕏 = {X1, X2, …} eine Menge von Variablen(namen), von denen jede Werte aus der Wertemenge W annehmen kann (alle Variablen vom gleichen Typ), dann ist ein Zustand Z eine partielle Abbildung:

Z : 𝕏 → W (Zuordnung des momentanen Wertes).

Ist Z : 𝕏 → W ein Zustand und wählt man eine Variable X ∊ 𝕏 und einen Wert w vom passenden Typ, so ist der transformierte Zustand durch eine Änderung der Variablen X gegeben, d.h. es findet ein Zustandsübergang Zi → Zi+1 statt!

Mit einer Anweisung α wird ein Zustand Z in einen (anderen) Zustand ⟦α⟧(Z) überführt.

Um Werte, die Variablen als Zwischenergebnisse zugewiesen wurden, später wiederverwenden zu können, muss man Werte aufrufen bzw. auslesen können.

Ausdrücke

Ausdrücke entsprechen im Wesentlichen den Termen einer applikativen Sprache, jedoch stehen an der Stelle von Unbekannten Variablen.

In applikativen (funktionalen) Algorithmen können Unbestimmte wie in einem Gleichungssystem "parallel" im Sinne von bewachten Ausdrücken verwendet werden, d.h. erst ein Term der eine Unbestimmte x verwendet, und dann folgend ein Term der die Unbestimmte berechnet, oder mehrere Terme die die Unbestimmten bestimmen. In imperativen Sprachen gibt es eine strikte Sequenz: Erst berechnen, dann verwenden.

Applikativ                           Imperativ
===============                      =========
y=x-t   fac n | n===1 = 1            a:=1;          fac(n) {
t=a+b         | n > 1 = n *fac(n-1)  b:=2;            if (n<0) then return null;
a=1           | n<1   = ⊥           t:=a+b;           else if (n==1) return 1:
b=2                                  y:=x-t;          else return n*fac(n-1)
                                                    }

Beispiel 7-4. Terme mit Unbestimmten (funktional) und Ausdrücke mit Variablen

Die Auswertung von Termen mit Variablen ist zustandsabhängig. An der Stelle der Variablen wird ihr Wert im gegebenen Zustand gesetzt. Imperative Algorithmen könne Seiteneffekte haben, d.h. dann dass ein Berechnugn mit den gleichen Eingabe- zu verschiedenen Ausgabewerten führt!

Man unterscheidet gebundene und freie Variablen.

Gebundene Variablen sind in Java Klassenvariablen, oder Methoden/Funktionsparameter

Frei Variablen sind solche die außerhalb eines lokalen Kontext definiert und überall verändert werden können!

Schleifen verwenden Variablen die u.U. zuerst gelesen und dann verändert werden (Rückwirkung)

Seiteneffekte und Rückwirkung

Rückwirkung              Seiteneffekt
═══════════              ════════════
x=0                  ┌――▶x=0     ――――――――――――┐
for(i=0;i<10;i++) {  │   function foo(u) {   │
  if (x>5) {  ◀――┐   └―――――if (u>2) x=x+1; ◀―┘
    i=i-1        │         return u-x
  }              │       }
  x=foo(i)   ――――┘
}

Beispiel 7-5. Beispiele für Rückwirkung und Seiteneffekte

Komplexe Anweisungen

Die komplexen Anweisungen imperativer Algorithmen bilden eine Untermenge der intuitiven Algorithmenbausteine.

Die Folge oder Sequenz bildet den ersten Baustein imperativer Algorithmen: Sind α1 und α2 Anweisungen, so ist α1;α2 auch eine Anweisung.

Die Bedeutung der Sequenz ist durch die folgende Zustandstransformation festgelegt:

⟦α1;α2⟧ = ⟦α2⟧(⟦α1⟧(Z))

Die Auswahl oder Selektion bildet den zweiten Baustein: Sind α1 und α2 Anweisungen und B ein boolescher Ausdruck, so ist

if B then α1 else α2 fi

eine Anweisung.

Die letzte und für imperative Algorithmen charakteristische Kontrollstruktur ist die Wiederholung oder Iteration: Ist α eine Anweisung und B ein boolescher Ausdruck, so ist

while B do α od

eine Anweisung. Die Iteration wird wie bei den intuitiven Algorithmen oft als Schleife bezeichnet.

Programme

Ein Programm ℙ bildet eine Eingabe- auf eine Ausgabemenge ab, ist letztlich auch wieder eine Funktion, die aus Anweisungen α besteht die den zustand Z eines Programms durch Änderungen von Variablen verändert.

Zusammenfassung

Kurz gefasst lassen sich imperative Algorithmen wie folgt charakterisieren:

Die Algorithmenausführung besteht aus einer Folge von Basisschritten, genauer von Wertzuweisungen. Diese Folge wird mittels Selektion und Iteration basierend auf booleschen Tests über dem Zustand konstruiert. Jeder Basisschritt definiert eine elementare Transformation des Zustands. Die Semantik des Algorithmus ist durch die Kombination all dieser Zustandstransformationen zu einer Gesamttransformation festgelegt.

Deduktive Algorithmen

Das sogenannte logische Paradigma führt uns zu den deduktiven Algorithmen.

Deduktive Algorithmen basieren auf logischen Aussagen und sind die Grundlage von Programmiersprachen wie PROLOG (für PROgramming in LOGic).

Logische Algorithmen bestehen aus einer Reihe von logischen Aussagen und einem Auswertungsalgorithmus für Anfragen.

Daher sind sie nicht in dem Sinne Algorithmen, wie wir sie bisher betrachtet haben – erst die Kombination der drei Bestandteile, logisches Programm, Auswertungsalgorithmus und konkrete Anfrage, legen eine Berechnungsfolge fest.

Während die meisten sonstigen Programmiersprachen applikative und imperative Elemente mischen, werden aufgrund dieser Unterschiede deduktive Elemente nur in speziellen logischen Programmiersprachen eingesetzt.

%% sudoku.pl
:- use_module(library(clpfd)).

sudoku(Puzzle) :-
    flatten(Puzzle, Tmp), Tmp ins 1..9,
    Rows = Puzzle,
    transpose(Rows, Columns),
    blocks(Rows, Blocks),
    maplist(all_distinct, Rows),
    maplist(all_distinct, Columns),
    maplist(all_distinct, Blocks),
    maplist(label, Rows).

blocks([A,B,C,D,E,F,G,H,I], Blocks) :-
    blocks(A,B,C,Block1), blocks(D,E,F,Block2), blocks(G,H,I,Block3),
    append([Block1, Block2, Block3], Blocks).

blocks([], [], [], []).
blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3], [Block|Blocks]) :-
    Block = [A,B,C,D,E,F,G,H,I],
    blocks(Bs1, Bs2, Bs3, Blocks).

Beispiel 7-6. Sudoko Löser in Prolog mit Randbedingungslöser. That's all folks.

Genetische Algorithmen

Genetische Algorithmen sind durch Prinzipien der Informationsverarbeitung in der Natur inspiriert.

Die DNS kann als Analogon zu einem Programm aufgefasst werden, indem Gene als ein in einem 4-Buchstaben-Alphabet kodiertes Programm interpretiert werden, das den Bauplan etwa eines Tieres (inklusive einiger Aspekte des Verhaltens!) festgelegt.

In der Natur gibt es keine Programmierer, die Fortpflanzung mit der Kombination aus männlichem und weiblichem Erbgut zusammen mit Mutationen verändert das Erbgut; die natürliche Auslese führt zur Ausprägung von Eigenschaften und letztendlich zu neuen Arten.

Durch Auslese driftet der Gen-Pool langfristig in eine Richtung, die besser an die auslesenden Umweltbedingungen angepasst ist.

Umgesetzt in die Denkweise der Informatik, arbeitet ein genetischer Algorithmus wie folgt:

Ein Pool von Phänotypen repräsentiert Individuen, die eine bestimmte Problemklasse (näherungsweise) zu lösen vermögen.

Die Lösungsstrategie jedes Phänotyps ist in seinem Erbgut kodiert (entsprechend den Chromosomen in der Natur). Die Strategie kann beispielsweise als Bitfolge fester Länge dargestellt sein.

Eine Generation von Individuen wird auf Probleme der Problemklasse angesetzt. Einzelne Phänotypen werden betreffend der Qualität der Lösungen (oft Fitness genannt) bewertet.

Erreicht die Fitness eines Phänotyps einen vorgegebenen Schwellwert, kann dieses Programm als Löser für Probleme der Problemklasse eingesetzt werden.

Entspricht noch kein Phänotyp den Anforderungen, so wird eine neue Generation von Phänotypen aus den bisherigen Phänotypen berechnet. Die Fitness der bisherigen Phänotypen bestimmt dabei, inwieweit diese als Elternteil einbezogen werden. Das Erbgut eines Kindes kann durch Kombination des Erbguts zweier Eltern und / oder durch Mutation berechnet werden.

Genetische Algorithmen sind typischerweise einsetzbar für Optimierungsaufgaben, in denen eine sehr gute Näherungslösung, aber nicht notwendigerweise die optimale Lösung gesucht wird (es gibt Probleme, für die die optimale Lösung nicht mit vertretbarem Aufwand berechenbar ist, Komplexitätsklasse NP!).

Initialisiere erste Generation G;

do
  BesteFitness = max { Fitness(x) |x in G };
  if BesteFitness = 0 then break;
  Bestimme G′ aus G als Eltern der neuen Generation G;
  // etwa durch n Turniere aus je k zufällig aus G gewählten x
  G = {};
  for each x in G′ do
    with probability 0.7 do x = mutate(x) od;
     with probability 0.2
       do wähle y aus G′ aus;
       x = crossover(x, y);
       od;
    G = G union { x };
  od;
od;
return Kandidaten x aus G mit Fitness(x) = BesteFitness;

Algorithmus 7-1. Grundprinzip genetischer Algorithmen

Entwurfsprinzipien

Der Entwurf von Algorithmen und damit von Programmen ist eine konstruktive und kreative Tätigkeit, die den Entwerfer immer wieder vor neue Herausforderungen stellt – neben der reinen Funktionalität sind ja auch Fragen der Laufzeitkomplexität und andere, nichtfunktionale Anforderungen zu berücksichtigen.

Die automatische Ableitung eines optimalen Algorithmus aus einer Beschreibung der Anforderungen ist prinzipiell nicht automatisierbar!

ad-dpunkt 8.1

TODO: ad-dpunkt: Greedy (S. 226), DaC (S. 231), Backtracking (S. 234), Dyn. Programmierung (S. 242)

Schrittweise Verfeinerung

Die Vorgehensweise der schrittweisen Verfeinerung basiert auf folgendem Ablauf:

Beginne mit einer kurzen Folge abstrakter Lösungsschritte (d.h. etwa Anweisungen in Pseudocode)

Verfeinere die Anweisungen Schritt für Schritt in detailliertere Anweisungen, zunächst in verfeinerten Pseudocode und letztendlich in konkrete Algorithmenschritte

Fertig, wenn alle Anweisungen in der Zielsprache (z.B. Java) formuliert sind

In der Terminologie der Programmierung entspricht der Verfeinerungsschritt der Formulierung von Algorithmen auf einer abstrakten Stufe, bei der statt ausführbarer Einzelschritte Prozeduraufrufe eingesetzt werden, deren Bedeutung dann durch die Ausprogrammierung der Prozedur konkretisiert wird.

Fakorisierung, d.h. Aufteilung eines Programms oder einer großen Funktion in viele kleine Funktionen ist ebenfalls schrittweise Verfeinering von Algorithmen.

Aber schrittweise Verfeinerung ist Übgergang von abstrakter in konkrete Notation mit einer Programmiersparche.

Es sollte so lange wie möglich während der Verfeinerung eine geeignete Notation (Pseudocode, natürliche Sprache) genutzt werden (so abstrakt wie möglich, so detailliert wie nötig).

Jeder Verfeinerungsschritt ist mit einer Entwurfsentscheidung verbunden, die spätere Eigenschaften des Programms wie Geschwindigkeit oder Speicherplatzbedarf beeinflusst.

Das bedeutet, dass unter Umständen derartige Entscheidungen später revidiert werden müssen.

Zim Beispiel ist dies etwa die Wahl des Sortierverfahrens oder auch die Entscheidung, dass die Eingabe für das Programm eine bereits sortierte Folge sein muss.

Neben dem Ablauf müssen auch die zu verarbeitenden Daten schrittweise verfeinert werden, und auch Datenstrukturen angepasst werden.

Auch Datenstrukturen sowie Klassen können verfeinert (also refaktorisiert) werden.

Einsatz von Algorithmenmustern

Die Idee des Einsatzes von Algorithmenmustern besteht darin, generische algorithmische Muster für bestimmte Problemklassen zu entwickeln und diese dann jeweils an eine konkrete Aufgabe anzupassen.

Man versucht also für eine allgemeine Problemklasse, zum Beispiel das Finden einer kostenoptimalen Lösung in einem großen Lösungsraum (etwa das Finden kürzester Wege), eine Muster-Implementierung zu finden und diese dann an das konkrete Problem anzupassen.

Diese Grundidee kann man auf verschiedene Weise konkretisieren:

Das Lösungsverfahren wird an einem möglichst einfachen Vertreter der Problemklasse vorgeführt und dokumentiert. Der Entwerfer versteht die Problemlösungsstrategie und überträgt diese auf sein Programm.

Eine Bibliothek von Mustern (»Design Pattern«, »best practice«-Strategien) wird genutzt, um einen abstrakten Programmrahmen zu generieren. Die freien Stellen dieses Programmrahmens werden dann problemspezifisch ausgefüllt.

Moderne Programmiersprachen benutzen parametrisierte Algorithmen und Vererbung mit Überschreiben, um Algorithmenmuster als lauffähige Programme zur Verfügung zu stellen und diese dann an ein konkretes Problem anzupassen.

Problemreduzierung durch Rekursion

Rekursive Algorithmen sind ein für die Informatik spezifischer Lösungsansatz, der in den klassischen Ingenieurwissenschaften nicht entwickelt werden konnte – ein mechanisches Bauteil kann physikalisch nicht sich selbst als Bauteil enthalten, während ein Programm sich durchaus selbst aufrufen kann.

Rekursive Programmierung ist daher in der Regel nicht aus dem Alltagswissen ableitbar, sondern muss als Technik erlernt und geübt werden.

Formale Algorithmenmodelle sind auch ohne rekursive Aufrufe bereits berechnungsuniversell.

Man könnte daher meinen, Rekursion als solche ist eigentlich nicht notwendig. Tatsächlich formen Compiler rekursive Programme in nichtrekursiven Maschinencode um (Schleifen).

Allerdings ist das rekursive Anwenden einer Problemlösungsstrategie auf Teilprobleme ein Algorithmenmuster, mit dem man bestimmte Problemklassen einfach realisieren kann.

==== Linear ====          ==== Rekursiv ====

function fac(n) {         function fac(n) {
  y=1                       if (n>1) return n*fac(n-1)
  for(i=2;i≤n;i++) {        else return 1
    y=y*i                 }
  }
  return y
}

Algorithmenmuster: Greedy

Greedy steht hier für gierig. Das Prinzip gieriger Algorithmen ist es, in jedem Teilschritt so viel wie möglich zu erreichen. Wir werden das Prinzip an einem kleinen Beispiel verdeutlichen und danach ein realistisches Problem und dessen »gierige« Lösung behandeln.

Problemklasse, für die sie angewendet werden können:

Gegeben ist eine feste Menge von Eingabewerten.

Es gibt eine Menge von Lösungen, die aus Eingabewerten aufgebaut sind.

Alle Lösungen lassen sich schrittweise aus partiellen Lösungen, beginnend bei der leeren Lösung, durch Hinzunahme von Eingabewerten aufbauen.

Es existiert eine Bewertungsfunktion für partielle und vollständige Lösungen.

Gesucht wird die bzw. eine optimale Lösung bezüglich der Bewertungsfunktion.

Greedy-Algorithmen berechnen nicht für alle derartigen Probleme tatsächlich die optimale Lösung.

Rekursion: Divide-and-conquer

Das bereits mehrfach behandelte Prinzip der Rekursion wendet bei der Lösung eines Problems die Gesamtlösungsstrategie innerhalb der algorithmischen Lösung rekursiv auf ein geändertes Problem an.

Typischerweise erfolgt diese erneute Anwendung des Gesamtverfahrens auf ein vereinfachtes Problem, um eine Terminierung zu garantieren.

Das Prinzip »Divide-and-conquer«, deutsch »Teile und herrsche«, basiert nun darauf, in einem Schritt eine große Aufgabe in mehrere kleinere Aufgaben zu teilen und diese rekursiv zu bearbeiten – also ein klassischer Einsatz des Rekursionsprinzips.

Vorgehensweise:

Zerlege das gegebene Problem in mehrere getrennte Teilprobleme,

löse diese einzeln

und setze die Lösungen des ursprünglichen Problems aus den Teillösungen zusammen.

Wende dieselbe Technik auf jedes der Teilprobleme an, dann auf deren Teilprobleme usw., bis die Teilprobleme klein genug sind, dass man eine Lösung explizit angeben kann.

Strebe an, dass jedes Teilproblem von derselben Art ist wie das ursprüngliche Problem, so dass es mit demselben Algorithmus gelöst werden kann.

function DIVANDCONQ (P: problem) {
  if (P is klein) then
    return f(P) // direkte Berechnung
  else {
    {P1,P2,...,Pk} = split(P)
    R1=DIVANDCONQ ( P1 )
    R2=DIVANDCONQ ( P2 )
    ..
    Rk=DIVANDCONQ ( Pk )
    return merge(R1,R2,...,Rk)
  }
}

Algorithmus 8-1. Grundprinzip DaC

Dieses Muster muss natürlich noch um die Repräsentation und Übergabe der Teillösungen verfeinert werden.

Rekursion: Backtracking

Das Backtracking ist ein weiteres wichtiges Algorithmenmuster für Such- und Optimierungsprobleme. Das Backtracking realisiert eine allgemeine systematische Suchtechnik, die einen vorgegebenen Lösungsraum komplett bearbeitet.

Backtracking basiert auf dem vollständigen Durchlauf eines Lösungsraums, so dass die gesuchte Lösung tatsächlich erreicht wird.

Dabei müssen Konfigurationen betrachtet werden, die jeweils in einem Schritt zu einer neuen Konfiguration erweitert werden können.

Auch muss entscheidbar sein, ob wir eine Lösung (quasi den Käse) auch tatsächlich gefunden haben.

Formal bedeutet es, dass für unsere Problemstellung die folgenden Voraussetzungen gelten müssen:

KF ist die Menge von Konfigurationen K.

K0 ist die Anfangskonfiguration.

Für jede Konfiguration Ki kann die Menge der direkten Erweiterungen Ki,1, .. , Ki,ni bestimmt werden.

Für jede Konfiguration ist entscheidbar, ob sie eine Lösung ist.

Backtracking ist ein rekursives Verfahren, das mit dem Aufruf BACKTRACK(K0), also mit der Anfangskonfiguration, gestartet wird.

function FindeLösung (Stufe, Vektor) {
  1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
     a) wähle einen neuen Teil-Lösungsschritt;
     b) falls Wahl gültig ist:
               I) erweitere Lösungsvektor um Wahl;
              II) falls Lösungsvektor vollständig ist, return true; // Lösung gefunden!
        sonst:
                  falls (FindeLösung(Stufe+1, Vektor)) return true; // Lösung!
                  sonst mache Wahl rückgängig; // Sackgasse (Backtracking)!
  2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!
}

Algorithmus 8-2. Backtracking-Muster

Komplexität

Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit O(zN) und einem Verzweigungsgrad z > 1 eine exponentielle Laufzeit.

Je größer die Suchtiefe N, desto länger dauert die Suche nach einer Lösung. Daher ist das Backtracking primär für Probleme mit einem kleinen Lösungsbaum geeignet.

Es gibt jedoch Methoden, mit welchen die Zeitkomplexität eines Backtracking-Algorithmus verringert werden kann. Diese sind unter anderem:

Heuristiken

Akzeptanz von Näherungslösungen und Fehlertoleranz

Durchschnittliche Eingabemenge

Randomisierung ("Simuliertes Abkühlen")

Dynamische Programmierung

Dynamische Programmierung vereint Aspekte der drei bisher vorgestellten Algorithmenmuster.

Vom Ansatz der Greedy-Algorithmen wird die Wahl optimaler Teillösungen übernommen,

von Divide-and-conquer und Backtracking die rekursive Herangehensweise basierend auf einem Konfigurationsbaum.

Während Divide-and-conquer-Verfahren unabhängige Teilprobleme durch rekursive Aufrufe lösen, werden bei der dynamischen Programmierung abhängige Teilprobleme optimiert gelöst, indem mehrfach auftretende Teilprobleme nur einmal gelöst werden.

Der Anwendungsbereich der dynamischen Programmierung sind Optimierungsprobleme analog zu Greedy-Algorithmen – mit dynamischer Programmierung werden aber insbesondere Probleme bearbeitet, bei denen die Greedy-Vorgehensweise nicht zu optimalen Lösungen führt.

Endliche Zustandsautomaten

Logik

Mathematik

Graphen

Tabellen

Automaten (die Maschine)

https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/ti_7_4_ger_web.html

Schaltnetze und Schaltwerke

Ohne Rückkopplung (Schaltnetz)

Werte an den Ausgängen sind nur abhängig von den Eingängen

Solche Schaltungen verhalten sich immer gleich (sind zustandslos) und sind durch ihre Schaltfunktion eindeutig beschrieben

Es ist jedoch nicht möglich, etwas zu speichern

Mit Rückkopplung (Schaltwerk)

Werte an den Ausgängen sind abhängig von den Eingängen und den vorherigen Ausgangswerten

Das Zeitverhalten muss genau betrachtet werden

Die vorherigen Ausgangswerte können als Zustand der Gatter interpretiert werden. Abhängig vom Zustand verhalten sich die Gatter anders (zustandsabhängige Schaltfunktion)

Es wird möglich, Zustände zu speichern

Schaltwerke

Ein Schaltwerk kann auch als eine Kombination aus einem Schaltnetz und einem Zustandsspeicher dargestellt werden

Die Ausgabe eines Schaltwerks kann abhängig vom aktuellen Zustand sein

Abhängig von den Eingangswerten kann sich der Zustand eines Schaltwerks ändern

Zur Beschreibung der zustandsabhängigen Schaltfunktion können endliche Automaten verwendet werden

Endliche Automaten

Ein endlicher Automat (engl. Finite State Machine, FSM) ist definiert durch

eine endliche Menge A von Eingabesymbolen ai∈A (Alphabet)

eine endliche Menge S von Zuständen si∈S

einen Anfangszustand s0∈S

eine Zustandsübergangsfunktion δ:S×A→S

Des Weiteren kann er umfassen

eine endliche Menge B von Ausgabesymbolen bi∈B

eine Ausgabefunktion λ:S×A→B

Bei deterministischen Automaten erfolgen die Zustandsübergänge deterministisch (nicht zufällig)

Endliche Automaten können durch Zustandsübergangsgraphen dargestellt werden

Zustandsübergangsgraphen

In einem Zustandsübergangsgraphen wird jeder Zustand si∈S als ein Kreis dargestellt

Die möglichen Zustandsübergänge werden mit Pfeilen gekennzeichnet

Jeder Pfeil wird mit dem zugehörigen Eingabesymbol am∈A beschriftet, für das dieser Zustandsübergang auftritt

Außerdem (abgetrennt durch einen "/") kann jeweils das Ausgabesymbol oder eine Aktion bn∈B angegeben werden

Abbildung 9-1. Ein Zustandsübergang vom Zustand *s*~i~ nach *s*~j~ durch eine Bedingung, hier das Vorliegen eines Eingabesymbols *a*, mit der Aktion der Ausgabe eines Symbols *b*.

Beispiel: Ampelschaltung

Es soll eine Schaltung für eine Fußgängerampelanlage erstellt werden. Es wird dabei die Ampel, die den Autoverkehr regelt, betrachtet (nicht die Fußgängerampel)

Die Ampel reagiert auf das Drücken eines Ampelknopfs durch einen Fußgänger:

a0 = 0 bedeutet der Ampelknopf wurde nicht gedrückt

a1 = 1 bedeutet der Ampelknopf wurde gedrückt

Im Anfangszustand s0∈S ist die Ampel grün

Wurde der Ampelknopf gedrückt, soll die Ampel zunächst auf gelb und dann auf rot schalten

Es wird weiterhin davon ausgegangen, dass das durch den Ampelknopf gesteuerte Eingabesymbol automatisch, nachdem der Fußgänger genug Zeit hatte die Straße zu überqueren, von a1 nach a0 wechselt

Die Ampel soll dann zunächst gelb-rot zeigen und schließlich wieder grün

Menge der Eingabesymbole A={a0,a1} binär kodiert mit {0,1}

Menge der Zustände S={s0,s1,s2,s3}

Menge der Ausgabesymbole B={b0,b1,b2,b3} binär kodiert mit y2y1y0 zu {001,010,110,100}

Es gibt |S|⋅|A|=4⋅2=8 mögliche Zustandsübergänge

Abbildung 9-2. Beispiel Ampelschaltung: (Links) Zustandsübergangsgraph (Rechts) Die Ausgabe der Zustände

Mealy und Moore-Automaten

Moore-Automaten

Bei einem Moore-Automaten ist die Ausgabefunktion λ:S→B nur vom aktuellen Zustand abhängig

Mealy-Automaten

Bei einem Mealy-Automaten ist die Ausgabefunktion λ:S×A→B vom aktuellen Zustand und der Eingabe abhängig

[https://unstop.com/blog/difference-between-mealy-and-moore-machine]

Vom Zustandsübergangsgraphen zum Automaten

Der Zustandsübergangsgraph der Ampelschaltung soll in ein Schaltwerk umgesetzt werden

Zur Erstellung des Schaltwerks kann die Ausgabefunktion, die Übergangsfunktion und der Zustandsspeicher separat betrachtet werden

Für gewünschte Ausgabe- und Übergangsfunktion kann direkt aus dem Zustandsübergangsgraphen abgelesen und als Wahrheitstafel dargestellt werden

Zur Minimierung der Schaltlogik (Boolesche Algebra) können anschließend z.B. BDD verwendet werden

Handelt es sich bei Ampelbeispiel um einen Moore- oder Mealy-Automaten?

Antwort: Moore-Automat, da die Ausgabefunktion nur abhängig vom aktuellen Zustand ist.

Funktionen und Tabellen für das Schaltwerk

image-placeholder
(9-1)

Abbildung 9-3. Ausgabefunktion als Wahrheitstabelle

Übergangsfunktion

Es gibt neben einem Schaltnetz, also der Zustandsübergangsfunktion, einen Zustandsspeicher, hier q=(q₀,q₁) mit den Dateneingängen d=(d₀,d₁).

Abbildung 9-4. (Links) Zustandsübergangsgraph (Rechts) Zustandsübergangstabelle mit d~1~=q~0~

Aus der Zustandsübergangstabelle kann die Übergangsfunktion berechnet werden und z.B. mit BDD Verfahten verinfacht werden.

Normalformen von Booleschen Funktionen können direkt aus der Tabelle (automatisch) abgeleitet werden.

image-placeholder
(9-2)

Vom Zustandsübergangsgraphen zum Schaltwerk

Abbildung 9-5. Die Maschinen mit Digitallogik (Kombinatorische und sequenzielle Logik)

Graphen und Graphenalgorithmen

Abbildung 10-1. Warum der ICE im Dörfchen Oberau hält - aber nicht in Koblenz

Grundlagen der Graphen

Der ungerichtete Graph der voherigen Abbildung zeigt einen vereinfachten Ausschnitt aus dem deutschen Bahnnetz (ICE Trassen).

An den Kanten sind die Entfernungen in Kilometern angegeben.

Es handelt sich also um einen gewichteten Graphen.

Der Graph ist zusammenhängend, aber nicht vollständig und nicht eben (also eben Deutsche Bahn)

Vertiefende Literatur

[1] H. Ernst, J. Schmidt, and G. Beneken, Grundkurs Informatik. Springer, 2023.

Auch die bereits behandelten Bäume sind ein Spezialfall von Graphen. Tatsächlich handelt es sich bei Graphen um eine der wichtigsten Datenstrukturen in der Programmierung, die in vielen Anwendungsgebieten zum Einsatz kommen.

Ein Graph besteht grob aus mit Kanten verbundenen Knoten.

Unterschiede gibt es in der Art der Kanten sowie in der Realisierung der Kanten und Knoten in einer Datenstruktur, die sich auf die Effizienz der unterschiedlichen Graphenfunktionen auswirkt.

Grundlagen der Graphen

Graphen können realen Umgebungen abbilden und abstrahieren

Abbildung 10-2. Das Königsberger Brückenproblem. Oben eine Skizze der Innenstadt von Königsberg im 18. Jahrhundert. Unten eine Repräsentation als Graph, wobei die Stadtteile als Knoten und die Brücken als Kanten dargestellt sind

Taxonomie der Graphen

Arten von Graphen

Graphen werden als eine durch Kanten verbundene Menge von Knoten definiert. Wir werden insbesondere die folgenden drei Klassen von Graphen näher betrachten:

Bei ungerichteten Graphen wird angegeben, welcher Knoten mit welchem verbunden ist, ohne dass eine Richtung vorgegeben wird. Ist allgemein von Graphen ohne nähere Einschränkung die Rede, sind in der Regel ungerichtete Graphen gemeint. Typische Anwendungen von ungerichteten Graphen sind die Modellierung von Straßenverbindungen (ohne Einbahnstraßen!), der Nachbarschaft von Gegenständen oder eines Telefonnetzes.

Gerichtete Graphen unterscheiden sich von den ungerichteten dadurch, dass Kanten eine Richtung haben. Auch können zwei Knoten nun durch zwei Kanten (d.h. in jeder Richtung eine) verbunden sein.

Typische Beispiele sind Modelle von Förderanlagen, der Kontrollfluss in Programmen oder auch Petri-Netze (Abluafdiagramme mit Tokens).

Ein wichtiger Spezialfall sind gerichtete azyklische Graphen, die oft kurz als DAG für englisch directed acyclic graph bezeichnet werden. In einem DAG gibt es keinen geschlossenen Rundweg entlang der gerichteten Kanten.

Beispiele sind die Vorfahrenbeziehung in Stammbäumen und die Vererbung in Programmiersprachen. Ein DAG ist natürlich als Datenstruktur ein normaler gerichteter Graph; relevant ist hier allerdings der möglichst effiziente Test auf Zyklenfreiheit.

Die Bestandteile von Graphen können mit zusätzlichen Attributen versehen werden, etwa der Länge einer Kante bei der Modellierung eines Straßennetzes. Derartige Graphen werden als gewichtete Graphen bezeichnet.

Ungerichtete Graphen

Die Definition von (ungerichteten) Graphen erfolgt in Form eines Zweiertupels G = (V, E). Ein Graph besteht aus

einer endlichen Menge V von Knoten (V für englisch vertices) und

einer Menge E von Kanten (E für englisch edges).

Jedes e ∊ E ist dabei eine zweielementige Teilmenge der Knotenmenge V.

Ungerichteter Graph

Diese Definition lässt also keine Schleifen, d.h. Kanten von einem Knoten zu sich selbst, und auch keine mehrfachen Kanten zwischen zwei Knoten (Parallelkanten) zu. Möglich ist auch eine erweiterte Definition, in der jedes e ∊ E eine ein- oder zweielementige Teilmenge darstellt.

Als Beispiel für diese Formalisierung von Graphen betrachten wir den Graph Gu:

image-placeholder
(10-1)

Abbildung 10-3. Biespiel Ungerichteter Graph mit obiger Knoten- und Kantenmenge

Gerichtete Graphen

Die Definition von gerichteten Graphen erfolgt analog zu den allgemeinen Graphen durch ein Zweitupel G = (V, E) mit

V, einer endlichen Menge von Knoten, und

E, einer Menge von Kanten.

Gerichteter Graph

Allerdings ist jedes e ∊ E nun ein Tupel (a, b) mit a, b ∊ V. Diese Definition lässt Schleifen (a, a) zu.

Als Beispiel für diese Definition gerichteter Graphen betrachten wir den Graph Gg aus Abbildung 16–2:

image-placeholder
(10-2)

Abbildung 10-4. Biespiel Gerichteter Graph mit obiger Knoten- und Kantenmenge

Zustandsautomaten (z.B. Mikroprozessoren oder Kontrollpfade von Logiksystemen) bestehen aus einer endlichen Menge von Zuständen und Übergängen zwischen Zuständen.

Zustandsautomaten kommen in fast allen Programmen vor. Beispiele sind auch Lexer und Parser.

Der Lexer zerlegt einen zusammenhängenden Text in einzelne Tokens (Symbole). Dazu benötigt er eine Sprachstruktur mit Mustern, z.B. ein Muster für die Addition add := expression + expression, und expression spaltet weiter auf (Baumstrukturen!!), z.B. expression := Number | Variable | expression

Der Parser setzt nach einem bestimmten Ablauf die Tokens zu Graphenstrukturen zusammen.

function parse(text) {
  state = {
    instring  : 0,
    incomment : 0,
    last      : '',
    buffer    : ''
  }
  while (next=nexttoken) {
    if (state.incomment) {
      if (next!=NL) continue;
      else state.incomment=0;
    } else if (state.instring==1) {
      if (next!='"') { state.buffer+=next; continue }
    }
    switch (next) {
      case '"':
        state.instring++; if (state.instring==2) { processString(state.buffer); state.instring=0 }
        break;
      case '/': if (state.last=='/') state.incomment++; break;
    }
    state.last=next
  }
}

Beispiel 10-1. Der programmatische Ablauf eines endlichen Zustandsautomaten kann durch eine Zustandsübergangstabelle und als Graph repräsentiert (abstrahiert) werden. Hier sind die Zustände aber im Programmkode "verborgen"

Gewichtete Graphen

Gewichtete Graphen besitzen zusätzlich zu den bisherigen Graphenbestandteilen noch Kantengewichte. Kantengewichte sind den Kanten zugeordnete Gewichtswerte, etwa natürliche Zahlen oder int- oder real-Werte. Ein gewichteter Graph kann nun für natürliche Zahlen als Kantengewichte durch G = (V, E, γ) mit

image-placeholder
(10-3)

definiert werden.

Gewichtete Graphen werfen einige neue Fragestellungen auf, so etwa die Suche nach kürzesten Wegen, dem maximalem Fluss durch einen Graphen oder die Konstruktion minimaler aufspannender Bäume.

Abbildung 10-5. Beispiel eines gewichteten, gerichteten Graphen. Natürlich gibt es auch gewichtete, ungerichtete Graphen, etwa um Entfernungen in Verkehrsnetzen zu modellieren.

Beispiel: Kommunikationsnetzwerk wie das Internet. Die Kanten werden mit Geschwindigkeits- und Durchsatzmetriken annotiert und ermöglichen die Fundung einer optimal schnellen Verbidnung.

Abbildung 10-6. Beispiel für ein Graph eines Rechnernetzwerkes mit unterschiedlichen Übertragungsgeschwindigkeiten (Bandbreite). Der Pfad A-B-D ist langsamer als der Pfad A-C-D, obwohl die gleiche Anzahl von Knoten entlang der Pfade liegen.

Eigenschaften von Graphen

Knotengrad, der für einen gegebenen Knoten i die Anzahl der verbundenen Knoten bezeichnet.

Bei gerichteten Graphen kann noch zwischen Ausgangsgrad (die Anzahl der ausgehenden Kanten) und Eingangsgrad (die Anzahl der eingehenden Kanten) unterschieden werden.

Pfade: Es existiert ein Pfad zwischen zwei Knoten u und v wenn ein Knoten v von einem Knoten u aus erreichbar ist, und eine Kantenfolge von u nach v existiert. Der Pfad kann uni- oder bidrektional sein.

Realisierung von Graphen

Eine Datenstruktur für Graphen kann unterschiedlich aufgebaut werden. Die Realisierungen unterscheiden sich dabei im Platzbedarf gespeicherter Graphen sowie in der Komplexität der erwähnten Basisoperationen.

Knoten- und Kantenlisten

Eine sehr einfache (und historisch daher als erste verwendete) Speicherung von Graphen erfolgt als eine Liste von Zahlen, etwa in einem Array, einer sequenziellen Datei oder als verkettete Liste.

Diese Liste von Zahlen dient als Kodierung des Graphen, wobei die Knoten von 1 bis n = |V| durchnummeriert werden.

Kanten können dann beispielsweise als Paare von Knotenzahlen dargestellt werden.

Die Realisierung durch Kantenlisten baut eine Zahlenfolge wie folgt auf (Kodierung!):

Das erste Element definiert die Knotenanzahl, das zweite die Kantenanzahl und der Rest der Zahlenfolge definiert die Liste der Kanten, die jeweils als zwei Zahlen notiert werden.

Beispiel:

image-placeholder
(10-4)

wird in Listen (Arrays) kodiert als:

Kantenliste :=
[6, 11, 1, 2, 1, 3, 3, 1, 4, 1, 3, 4, 3, 6, 5, 3, 5, 5, 6, 5, 6, 2, 6, 4]
Knotenliste :=
[6, 11, 2, 2, 3, 0, 3, 1, 4, 6, 1, 1, 2, 3, 5, 3, 2, 4, 5]

Die Teilfolge 2, 2, 3 beginnend an der dritten Position in dieser Zahlenfolge bedeutet beispielsweise »Knoten 1 hat Ausgangsgrad 2 und herausgehende Kanten zu den Knoten 2 und 3«.

Man sieht bereits an diesem Beispiel, dass für Graphen mit vielen Kanten Knotenlisten weniger Speicherbedarf als Kantenlisten benötigen. Genauer benötigen Kantenlisten 2 + 2 · |E| Zahlen und Knotenlisten 2 + |V| + |E| Zahlen.

Adjazenzmatrix

Insbesondere bei sehr vielen Kanten ist eine Speicherung der Verbindungen als n × n-Matrix sinnvoll. Der Wert n entspricht dabei der Knotenanzahl |V|. Eine derartige Matrix wird als Adjazenzmatrix bezeichnet.

Ein typisches Beispiel aus der Digitallogik und Rechnerarchitektur: Der Crossbar Switch!

Die Adjazenzmatrix ist ähnlich einer Zustandsübergangstabelle einer FSM. Sie kann für gerichtete Graphen direkt erstellt werden.

Die Idee der Adjazenzmatrix lässt sich direkt auf ungerichtete Graphen übertragen, wobei dann eigentlich nur die eine Hälfte der Matrix gespeichert werden muss, da sich die andere Hälfte durch Spiegelung ergibt.

Beim Vergleich des Speicherbedarfs muss man nun beachten, dass die Matrixelemente boolesche Werte sind, die im Gegensatz zu Zahlwerten nur ein Bit benötigen.

Es lassen sich zyklische wie azyklische Graphen darstellen

Die folgende Adjazenzmatrix stellt den gerichteten Graphen Gg und ungerichteten Gu dar:

image-placeholder
(10-5)

Auch gewichtete Graphen können auf die gleiche Art mit Matrizen beschrieben (und progarmmiert) werden.

Abbildung 10-7. Speicherung eines Graphen als Adjazenzmatrix *A* und Bewertungsmatrix *B* die die Gewichte vermerkt. [Grundkurs Informatik]

Für bewertete Graphen kann das Konzept beibehalten werden, wenn anstelle der Nullen und Einsen die Bewertung eingetragen wird. Man spricht dann auch von einer Bewertungsmatrix B.

Mit Matrizen können wir direkt rechnen:

Wege zwischen Knoten

Man kann nun fragen, wie man über direkte Verbindungen hinaus längere Wege zwischen zwei Knoten finden kann. Eine Methode ist die Bildung von Potenzen Am der Adjazenzmatrix. Die Komponenten der Matrix Am geben dann die Anzahl der Wege der Länge m vom i-ten zum k-ten Knoten an. Die Komponenten der Matrix A² berechnet man nach der Regel „Zeile mal Spalte“ als Skalarprodukte der Zeilen- und Spaltenvektoren der Matrix A mit n × n Elementen:

image-placeholder
(10-6)

Die obige Formel liefert also die Anzahl der Wege der Länge 2 vom Knoten i zum Knoten k.

Beispiel: (a₃₂)²=0, (a₁₄)²=2 bedeutet es gibt also keinen Weg der Länge 2 vom dritten zum zweiten Knoten, also von C nach B, aber zweiWege der Länge 2 von A nach D, nämlich A → B → D und A → C → D. Man kann dies direkt am Skalarprodukt ablesen: es ergibt sich genau dann ein Beitrag, wenn die entsprechende Kante existiert. Die Zählung der Indizes beginnt dabei mit 1.

Die Erreichbarkeitsmatrix

Will man wissen, ob unabhängig von der Länge des Weges überhaupt ein Weg von einem Knoten zu einem anderen existiert, so addiert man alle n Potenzen der Adjazenzmatrix und erhält die Erreichbarkeitsmatrix oder Wegematrix:

image-placeholder
(10-7)

Die Einträge eik von E geben also an, auf wie vielen verschiedenen Wegen ein Knoten von einem anderen Knoten aus erreichbar ist, ohne dass dazwischen liegende Knoten mehrfach besucht werden.

In der Definition von E sind einige Varianten gebräuchlich. Ist man beispielsweise nur an der Existenz eines Weges interessiert, so setzt man eik = 1, wenn der ursprüngliche Eintrag eik > 0 war, sonst bleibt der Eintrag 0 erhalten. Man hat dann also wieder eine effizient speicherbare binäre Matrix.

Abbildung 10-8. Bestimmung der Erreichbarkeitsmatrix an einem Beispiel. Die Potenzen der Matrix A ergebn sich aus dem Matrixprodukt! [Grundkurs Informatik]

Enthält eine ganze Spalte der Erreichbarkeitsmatrix nur die Einträge 0, so kann dieser Knoten von keinem anderen Knoten aus erreicht werden. Sind alle Einträge einer Zeile 0, so kann von dem entsprechenden Knoten aus kein andere Knoten erreicht werden.

Kürzeste und längste Wege

Weiter mit den Adjazenzmatrizen ...

Bei einem gewichteten Graphen kann man anstelle der Anzahl der Wege auch eine Summe von Gewichten längs der Kanten des Weges eintragen und diese als Weglängen interpretieren.

Dies kann etwa das Minimum der Summe der Gewichte sein, wenn man den kürzesten Weg zwischen je zwei Kanten bestimmen möchte, oder auch das Maximum der Summe der Gewichte, wenn der längste Weg gesucht ist.

Der Eintrag 0 bedeutet dabei nach wie vor, dass kein Weg vorhanden ist.

Abbildung 10-9. Berechnung der kürzesten und längsten Wege

Der Floyd-Warshall-Algorithmus

 1: Nummeriere die Knoten des Graphen von 1 bis n durch und
 2: trage die Längen der Wege von Knoten i zu Knoten j in die
 3: Erreichbarkeitsmatrix e(i,j) ein. Existiert kein solcher
 4: direkter Weg, trage ein Symol für „unendlich“ ein (Infinity).
 5:
 6: Wiederhole für k := 1 bis n
 7:   Wiederhole für i := 1 bis n
 8:    Wiederhole für j := 1 bis n
 9:     Wenn e(i,k) + e(k,j) < e(i,j) dann
10:       Setze e(i,j) := e(i,k) + e(k,j)
11:       Ersetze die zu e(i,j) gehörende Knotenliste durch die Knotenliste, die durch
12:       Verbinden der zu e(i,k) und zu e(k,j) gehörenden Knotenlisten entsteht.
13: ENDE

Algorithmus 10-1. Floyd-Warshall-Algorithmus zum Auffinden kürzester Wege in einem Graphen

Längste Pfade

Das Problem des längsten Pfades ist NP-schwer oder NP-vollständig, abhängig von zusätzlichen Randbedingungen. Eine einfache Modifikation des Floyd-Warshall- oder Dijkstra-Algorithmus wird nicht funktionieren.

Wenn jeder Knoten immer wieder besucht werden kann gibt es unendlich viele unendlich lange Pfade

https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Topologisches Sortieren

Linearisierung eines Graphens (nur DAG), d.h. Einordnung der Knoten in eine Liste mit einer Ordnung unter der Bedingung:

dass für jede gerichtete Kante (u,v) vom Knoten u zum Knoten v dann u in der Reihenfolge vor v steht.

Topologisches Sortieren = Scheduling Problem

5, 7, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)

3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)

3, 5, 7, 8, 11, 2, 10, 9 (lexicographic by incoming neighbors)

5, 7, 3, 8, 11, 2, 10, 9 (fewest edges first)

7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)

5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)

3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)

Graphen als dynamische Datenstrukturen

Die bisherigen Graphendarstellungen waren statische Realisierungen, da eigentlich keine dynamischen Erweiterungen im Sinne verketteter Listen vorgesehen waren (obwohl etwa Knotenlisten natürlich auch als verkettete Liste realisiert werden können).

Es gibt nun eine Reihe von Möglichkeiten, Graphen als dynamische Datenstrukturen zu realisieren.

Eine nahe liegende Variante ist es, wie bei einem Baum die Knoten als Elemente einer dynamischen Struktur aufzufassen und die Kanten als Verzeigerung zu realisieren. Dies bildet direkt die Graphenstruktur ab und resultiert in einer komplex verzeigerten Struktur mit vielen Zyklen (und damit Fehlermöglichkeiten bei der Programmierung).

Wir werden uns eine andere Realisierung anschauen, die auch als Adjazenzliste bezeichnet wird. Ein Graph wird dabei durch |V| +1 verkettete Listen realisiert. Die Basisstruktur bildet die Liste aller Knoten. Für jeden Knoten wird eine Liste der Nachfolger entlang gerichteter Kanten abgespeichert, so dass man für n = |V| und m = |E| insgesamt image Listenelemente erhält.

Abbildung 10-10. Graph als dynamische Datenstruktur

Verkettete Speicherung eines Graphen

Forward-Star Datenstruktur

Eine sehr platzeffiziente Möglichkeit zum Speichern von Graphen ist der Forward Star. Dabei wird zunächst jedem der n Knoten ein Index zugewiesen.

Nun werden in einem als Knotenliste bezeichneten Array K Verweise auf Positionen in einem zweiten Array, die Nachfolgerliste N, eingetragen.

Diese enthält, beginnend mit dem ersten Nachfolger von Knoten 1 der Reihe nach alle Nachfolger von Knoten 1, sofern dieser überhaupt einen hat.

Danach kommen alle Nachfolger von Koten 2 usw. Die Nachfolgerliste enthält somit genau einen Eintrag für jede der m Kanten.

Die in der Knotenliste eingetragenen Verweise Ki geben die Position an, an der in der Nachfolgerliste die zugehörigen Nachfolger beginnen.

Abbildung 10-11. Repräsentation eines Graphen als Forward Star

Abbildung 10-12. Der Graph wird direkt als verzeigerte Datenstruktur abgebildet. Jeder Knoten hat eine Nachfolgerliste. Algortihmen auf diese Datenstruktur anzuwenden ist wegen Zyklen gefährlich und aufwendig Zyklen zu erkennen.

Vergleich und Komplexität

Alle vorgestellten Realisierungsvarianten sind äquivalent; jede Darstellung kann also in jede andere ohne Informationsverlust transformiert werden. Im Wesentlichen erfordert dies das Auslesen der einen Darstellung und anschließend das Erzeugen der jeweils anderen Darstellung.

Abbildung 10-13. Vergleich der Komplexität. Hierbei gilt n = |V| und m = |E|. [addp]

Komplexität der Berechnung der Erreichbarkeitsmatrix

Die Komplexität für die Berechnung der Erreichbarkeitsmatrix eines Graphen mit n Knoten durch Summierung der ersten n Potenzen der Adjazenzmatrix ist von der Ordnung O(n⁴), also polynomial mit einem recht hohen Exponenten. Dies ergibt sich, da n − 1 Matrixmultiplikationen auszuführen sind, wobei die Komplexität der Multiplikation zweier n × n Matrizen von der Ordnung O(n³) ist.

Der Floyd-Warshall-Algorithmus hat die Komplexität O(n³), was sich aus den drei ineinander geschachtelten Schleigen mit n Durchläufen sofort ertgit.

Das Löschen eines Knotens löscht auch zugehörige Kanten, so dass hier der Aufwand in allen Varianten unvermutet hoch ist. Zu den einzelnen Varianten sind einige Bemerkungen angebracht:

Bei Kantenlisten ist sowohl das Einfügen von Kanten (Anhängen zweier Zahlen) und von Knoten (Erhöhung der ersten Zahl um 1) besonders günstig, falls das Anhängen von Zahlen nicht zum Umkopieren eines Feldes führt. Das Löschen von Kanten kann das Zusammenschieben in einer Liste bedeuten; das Löschen von Knoten eine erneute Durchnummerierung der Knoten.

Bei Knotenlisten ist insbesondere das Einfügen von Knoten (Erhöhung der ersten Zahl und Anhängen einer 0) günstig.

In der Matrixdarstellung ist insbesondere das Manipulieren von Kanten eine sehr effizient ausführbare Operation. Der Aufwand bei Knoteneinfügung hängt von der Realisierung der Matrix ab, hier wurde von einem Kopieren der Matrix in eine größere Matrix ausgegangen.

Bei der Realisierung als Adjazenzliste ergibt sich unterschiedlicher Aufwand, je nachdem ob die Knotenliste als Feld (mit Direktzugriff) oder als verkettete Liste (mit sequenziellem Durchlauf) realisiert wird.

Durchsuchen von Graphen

Das systematische Durchsuchen eines Graphen ist durchaus keine triviale Aufgabe.

Da es sich um einen wichtigen Teilaspekt vieler Anwendungen handelt, werden gibt es einige Algorithmen zum Durchsuchen von Graphen.

Verwendet werden solche Verfahren beispielsweise um einen Weg von einem gegebenen Startknoten zu einem Zielknoten zu finden, der ggf. bestimmten Kriterien genügen soll (wie: gefunden werden soll der kürzest mögliche Weg).

Tiefensuche

Bei der Tiefensuche (Depth First Search) in einem Graphen besucht man von einem Startknoten k ausgehend dessen nächsten noch nicht besuchten Nachfolger, d.h. den als nächsten in der zu k gehörenden Nachfolgerliste befindlichen Knoten und setzt dort die Suche rekursiv fort. Gerät man dabei in eine Sackgasse, so muss der Weg bis zum ersten Knoten zurückverfolgt werden, von dem aus eine alternative Wahl möglich ist (Backtracking).

Breitensuche

Bei der Breitensuche (Breadth First Search) besucht man von einem Knoten ausgehend zuerst alle direkten Nachfolger, d. h. die in der zugehörigen Kantenliste enthaltenen Knoten, bevor deren noch nicht besuchte Nachfolger besucht werden. Auch bei der Breitensuche müssen Knoten als schon bearbeitet markiert werden können, wozu wie schon bei der Tiefensuche der Eintrag „Status“ verwendet wird. Anstelle eines Stapels wird bei der Breitensuche ein Puffer (Warteschlange, FIFO) für die temporäre Speicherung benötigt.

A∗-Algorithmus

Problematisch bei der uniformen Kosten Suche ist, dass zur Bestimmung kürzester Wege der zu expandierende Knoten nur auf Basis der schon entstandenen Kosten ab dem Startknoten ausgewählt wird, in der Annahme, dass es besser ist zunächst die Wege mit aktuell geringen Kosten weiter zu betrachten.

Solche Wege können aber kurz sein und in die falsche Richtung gehen, d. h. weg vom Ziel.

Das Verfahren bemerkt dies erst, wenn andere Wege, die näher am Ziel sind, wieder besser bewertet werden. Man bezeichnet solche Suchverfahren als uninformierte Suche, weil sie keine Informationen darüber haben, wie nahe sie während der Suche dem Ziel schon gekommen sind (ohne den Weg zum Ziel tatsächlich zu berechnen).

Der A∗ -Algorithmus kombiniert die besten Aspekte zweier anderer Algorithmen:

Dijkstra-Algorithmus: Dieser Algorithmus findet den kürzesten Weg zu allen Knoten von einem einzigen Quellknoten.

Greedy Best-First-Suche: Dieser Algorithmus untersucht den Knoten, der dem Ziel am nächsten zu sein scheint, basierend auf einer heuristischen Funktion.

A∗ findet immer eine Lösung, sofern diese existiert. Das Verfahren ist optimal-effizient.

Es lässt sich zeigen, dass kein anderer Algorithmus existiert, der bei der Suche weniger Knoten expandiert, wenn die Bedingungen für die heuristische Funktion eingehalten werden.

Deswegen ist A∗ das Standardverfahren für alle Anwendungen, bei denen kürzeste Wege gesucht werden müssen, so z.B. bei der Routenplanung in Navigationsgeräten oder der Wegplanung in Computerspielen.

Die Zeitkomplexität von A∗ ist exponentiell in der Länge des kürzesten Pfads zum Ziel.

Das Hauptproblem in der Praxis ist jedoch der (ebenfalls exponentielle) Speicherverbrauch, da alle Knoten im Speicher gehalten werden müssen.

Schlüsselkonzepte in der A∗-Suche

[https://www.datacamp.com/tutorial/a-star-algorithm]

Die Effizienz des A∗ -Algorithmus beruht auf seiner intelligenten Bewertung von Pfaden unter Verwendung von drei Schlüsselkomponenten: g(n), h(n) und f(n). Diese Komponenten arbeiten zusammen, um den Suchprozess auf die vielversprechendsten Pfade zu lenken.

Abbildung 10-14. A∗ Kostenfunktionen: Pfadkosten g, heuristische Funktion h

function A_Star(start, goal) {
    // Initialize open and closed lists
    openList = [start]          // Nodes to be evaluated
    closedList = []             // Nodes already evaluated
    // Initialize node properties
    start.g = 0                 // Cost from start to start is 0
    start.h = heuristic(start, goal)  // Estimate to goal
    start.f = start.g + start.h       // Total estimated cost
    start.parent = null               // For path reconstruction
    while openList is not empty:
        // Get node with lowest f value - implement using a priority queue
        // for faster retrieval of the best node
        current = node in openList with lowest f value
        // Check if we've reached the goal
        if current = goal:
            return reconstruct_path(current)
        // Move current node from open to closed list
        remove current from openList
        add current to closedList
        // Check all neighboring nodes
        for each neighbor of current:
            if neighbor in closedList:
                continue  // Skip already evaluated nodes
            // Calculate tentative g score
            tentative_g = current.g + distance(current, neighbor)
            if neighbor not in openList:
                add neighbor to openList
            else if tentative_g >= neighbor.g:
                continue  // This path is not better
            // This path is the best so far
            neighbor.parent = current
            neighbor.g = tentative_g
            neighbor.h = heuristic(neighbor, goal)
            neighbor.f = neighbor.g + neighbor.h
    return failure  // No path exists
}

Algorithmus 10-2. A∗-Algorithmus

A∗-Algorithmus

Was ist wichtig?

Es werden Listen geführt um noch nicht und breits besuchte Knoten zu merken

Initialisierungsphase

Der Algorithmus beginnt mit der Erstellung von zwei wesentlichen Listen:

Die offene Liste beginnt nur mit dem Startknoten

Die geschlossene Liste beginnt leer

Jeder Knoten speichert vier kritische Informationen:

g: Die tatsächlichen Kosten vom Startknoten

h: Die geschätzten Kosten für das Ziel

f: Die Summe von g und h

parent: Verweis auf den vorherigen Knoten (für Pfadrekonstruktion)

Hauptschleife

Der Kern von A∗ ist seine Hauptschleife, die fortgesetzt wird, bis entweder:

Das Ziel ist erreicht (Erfolg)

Die offene Liste wird leer (Fehler - es existiert kein Pfad)

Während jeder Iteration wird der Algorithmus:

Wählt den vielversprechendsten Knoten (niedrigster f-Wert) aus der offenen Liste aus

Verschiebt es in die geschlossene Liste

Untersucht alle benachbarten Knoten

Nachbarbewertung

Für jeden Nachbarn der Algorithmus:

Überspringt Knoten, die sich bereits in der geschlossenen Liste befinden

Berechnet einen vorläufigen G-Wert

Aktualisiert Knotenwerte, wenn ein besserer Pfad gefunden wird

Fügt der offenen Liste neue Knoten hinzu

Wegrekonstruktion

Sobald das Ziel erreicht ist, arbeitet der Algorithmus rückwärts durch die übergeordneten Referenzen, um den optimalen Pfad vom Start zum Ziel zu konstruieren.

Diese systematische Vorgehensweise stellt sicher, dass A* immer den optimalen Weg findet, wenn:

Die heuristische Funktion ist zulässig (niemals überschätzt)

Zwischen dem Start- und dem Zielknoten existiert tatsächlich ein Pfad

Tabellen

Überblick in die Einführung einfachster Abstrakter Datentypen mit Tabellen:

Lineare Arrays als Datenstrukturen

Der Stapelspeicher (LIFO)

Die Warteschlange (FIFO)

Die Hashtabelle

Lineare Arrays

Ein Array ist eine Tabelle mit einer Spalte und n Zeilen.

Ein Array ist eine monosortige lineare Folge von Werten und somit Speicherzellen.

Jede Speicherzelle hat den gleichen Datentpy, z.B. skalare Werte wie Ganzzahlen, aber acuh Datenstrukturen

Die Größe des Arrays ist fest (n)

Jede Zelle eines Arrays wird über einen eindeutigen Index adressiert, i.A. immer mit 0 beginnend (erstes Element) bis n-1 (letztes Element):

image-placeholder
(11-1)

Operationen

Elementare (eingbaute) Operationen:

Lesen eines Elements T[index]

Schreiben eines Elements T[index]=ε

RAM Modell: freier Indexzugriff in beliebiger Reihenfolge!

Abstrakte Operationen:

Suche: Suche den Index eines Elementwertes

Sortieren: Sortieren der Werte in einer definierten Reihenfolge

usw.

Es gibt beliebig viele Operationen die man auf Tabllen anwenden und implementieren kann. Suche und Sortierung (kommt noch) sind die wichtigsten.

Linear Arrays = Mathematische Vektoren

Numerik

Vektorarithmetik

Schlüssel-Wert Paare

Der Index einer Tabelle ist ein Schlüssel zur Erlangung eines Werts. So könnte man numerischen Indexwerten eine Zecihenkette zuordnen.

T=['Zero','One','Two']
print(T[0])

Beispiel 11-1. Schlüssel-Wert Paare für Lookup-Tabellen

Der große Vorteil: "Suchzeit", d.h. Abbildung eines Schlüssels (Index) auf einen Wert geschieht in konstanter Laufzeit O(1)!

Der große Nachteil: Die Schlüsselfolge ist fest vorgegeben und startet bei 0. Bei dünn besetzten Schlüsselmengen bräuchte man dünnbesetzte riesig Tabellen!

Daher werden noch kompaktere Hashtabellen eingeführt.

Lineare Tabellen verwenden eine lineare Suchfunktion für Schlüssel, i.A. i=H(k)=k

Hashtabellen verwenden eine "andere" Suchfunktion H(k) die beliebige Schlüsselverteilungen (theoretisch) auf einen Index i abbilden.

          ┌――――┐ 0                       ┌――――┐
k=0 ――――▶ │ a  │   ――――▶ a  k=10――――▶H(k)│ a  │ ――――▶ a
          ├――――┤ 1                       ├――――┤
k=1 ――――▶ │ b  │   ――――▶ b               │ f  │
          ├――――┤ 2                       ├――――┤
          │ c  │            k=2 ――――▶H(k)│ e  │ ――――▶ e
          ├――――┤ 3                       ├――――┤
          │ d  │                         │ d  │
          ├――――┤ 4                       ├――――┤
          │ e  │                         │ b  │
          ├――――┤ 5                       ├――――┤
          │ f  │                         │ b  │
          │    │                         └――――┘
          │    │
          └――――┘

Definition 11-1. Lineare versa Hashtabellen als Suchtabellen (Look-up tables)

Der Stapelspeicher

Ein Kellerspeicher oder auch Stapelspeicher alias Stack genannt ist eine lineare Tabelle (Array), aber

Es gibt aber keine freie Indizierung (kein RAM Modell)

Er implementiert aber Operationen mit einer Last-In First-Out Reigenfolge

Nur abstrakte Operationen:

Push: Lege einen neuen Wert auf den Stapel ab (Last-In)

Pop: Holt den obersten Wert vom Stapel (Last-Out)

type Stack(T)
operators
  empty : → Stack
  new : n → Stack(n)
  push : Stack × T → Stack
  pop : Stack → T
  top : Stack → T
  is_empty : Stack → Bool
  is_full : Stack → Bool
axioms ∀s : Stack, ∀x : T
  pop (push (s, x)) = x
  top (push (s, x)) = x
  is_empty (empty) = true
  is_empty (push (s, x)) = false
  is_full (empty) = false
  is_full (n*push (s, x)) = true

Definition 11-2. ADT-Spezifikation eines Stacks

LIFO Prinzip: (Last-In-First-Out-Speicher): Beim Auslesen eines Elementes wird das jeweils zuletzt gespeicherte Element zuerst ausgelesen, danach das vorletzte etc. Der Kellerspeicher wird daher auch als Stapel bezeichnet: Elemente werden sozusagen übereinander gestapelt und dann wieder in umgekehrter Reihenfolge vom Stapel genommen.

Die Operation push packt ein Element des Parametertyps T auf den Stapel, pop entfernt das oberste Element.

Mittels top kann man sich das oberste Element anschauen (ohne es zu entfernen).

All diese Operationen sind als Funktionen mit einem (ersten) Parameter vom Typ Stack (genauer natürlich Stack(T)!) als Eingabe definiert.

empty erzeugt einen leeren neuen Stapel, is_empty testet auf leeren Stack.

Abbildung 11-1. Verdeutlichung des Stack-Prinzips [addp]

Eine besondere Behandlung erfordert noch der Fall, dass versucht wird, ein Element vom leeren Stack zu lesen oder wenn es zu einem Überlauf des Stacks kommt.

Dies kann über eine Ausnahme (Exception, Signal) des Typs StackException signalisiert werden, die beim Aufruf der Methoden pop, push und top auftreten kann.

Der Datentyp der Datenelemente kann beliebig sein:

Numerische Werte

Zeichenketten

Datenstrukturen

Statisch typisierte Programmiersprachen erfordern entweder ein virtuelles Template oder für jeden Datensatztyp eine eigene Implementierung. Dynamisch typisierte und teils auch funktionale Sprachen haben dieses Problem nicht.

Algorithmik

Algorithmisch brauchen wir wieder eine Indexabbildungsfunktion, die jetzt aber parameterlos und zustandsbehaftet wird (d.h. zum Stapelobjekt gehört).

Am einfachsten ist sowohl beim LIFO als noch beim folgenden FIFO Speicher die Einführung zweier Indexzeiger:

TOP: Zeigt auf das nächste freie Element in der lienaren Tabelle

BOTTOM: Zeigt auf das letzte belegte Element

Man kann hier aber einfach nur einen Zeiger verwenden:

SP: Der Stackzeiger der auf das nächste freie Element zeigt und (SP-1) welches auf den obersten letzten Wert des Stapels verweist.

function Stack(N) {
  return {SP:0,N:N,T:Array(N)}
}
function push(S,x) {
  if (full(S)) throw "Full";
  S
S.SP
=x;
  S.SP++;
}
function pop(S) {
  if (empty(S)) throw "Empty";
  x=S
S.SP-1
;
  S.SP--;
  return x
}
function full(S) { return S.SP==S.N } function empty(S) { return S.SP==0 }

Algorithmus 11-1. Implementierung der Stackoperationen

Die Komplexitätsklasse der Push und Pop Operationen liegt weiterhin bei konstanten O(1)!

Applikationen

Hardware: Fast jeder Mikroprozessor hat einen Hardware Stack (also in Register-Transfer Logik implementierten Stack)

Auf dem Stack werden temporäre variablen ablegt (für Berechnungen)

Auf dem Stack werden Funktionsrahmen beim Aufruf von von Funktionen abgelegt

Die Stack Maschine

Ein einfacher Prozessor mit 0-Operandenbefehlen

Alle Operationen laufen über einen (oder mehrere) Stacks

FORTH ist ein bekanntes Stackprozessor Systeme (Hardware+Software)

Aber auch WebAssembly (Browser) und Postscript (und PDF) Interpreter sind Stackmaschinen

Der Stackprozessor

Es gibt twei Stacks: Einen Daten- und einen Instruktions Stack D und C

Es gibt zwei Arten von Operationen:

Literale die eine Wert auf dem Stack ablegen (und C → D bewirken)

Unäre und binäre Arithmetische Operationen die ihre Operanden vom D-Stack holen und das Ergebnis auch dort wieder ablegen

Wir benötigen noch eine weitere Stack Operation nth die den n-obersten Werte (n>0) vom Stapel liest:

function nth(S,n) { return S
S.SP-n
 } // n > 0

Jetzt müssen wir Befehle für unsere einfache Numerik VM definieren:

function LITERAL(x) { return x /*number*/ }
function ADD() { return '+' }
function END() { return '.' }

Auf dem Stack sind Daten und Code abgelegt. Code ist ein String, Daten ein numerischer Wert. That's all folks.

Wir brauchen nun einen Stackprozessor der das Programm vom Stack abarbeitet:

function run() {
  next=pop(C)
  while (next!='.') {
    switch (next) {
      case '+':
        a=pop(D); b=pop(D)
        push(D,a+b)
        break;
      default:
        if (typeof next=='number') push(D,next);
        else throw "EEXEC"
    }
    next=pop(C);
  }
}

Jetzt folgt der Stack und ein kleines Beispielsprogramm:

C=Stack(10)
D=Stack(10)

// Programm
push(C,END())
push(C,ADD())
push(C,LITERAL(3))
push(C,LITERAL(2))

run(C);
print(pop(D))

Jetzt wollen wir noch die Subtraktion hinzufügen. Bei der Addition ist die Reihenfolge der Operanden nicht relevant, bei der Subtraktion schon.

Was sollen wir machen wenn die Operanden auf dem Stack in der falschen Reihenfolge liegen? Wir könnten eine swap Operation einführen!

function SUB() { return '-' }
function SWAP() { return '%' }
function run() {
  ...
    case '-': a=pop(D);b=pop(D);push(D,a-b); break;
    case '%': a=pop(D);b=pop(D);push(D,a);push(D,b); break;
  ...

Die Warteschlange

Um die Prinzipien der Spezifikation von parametrisierten Datenstrukturen zu vertiefen, betrachten wir kurz eine weitere Datenstruktur, nämlich die Warteschlange oder englisch Queue.

Eine Queue realisiert das sogenannte FIFO-Prinzip, also einen First-In-First-Out-Speicher.

Das FIFO-Prinzip modelliert eine Warteschlange, bei der man sich hinten anstellt: »Wer zuerst kommt, mahlt zuerst«.

Es gibt wieder zwei wesentliche Operationen, die zwar auf einer Tabelle operieren, aber ebenfalls wie beim Stack keine explizite Indizierung der Tabelle benörigen (daher auch kein RAM Modell):

enter: Schreibt einen neuen Wert in die Queue

leave: List einen alten Wert aus der Queue

type Queue(T)
operators
  empty : → Queue
  new : n → Queue(n)
  enter : Queue × T → Queue
  leave : Queue → T
  bottom : Queue → T
  top : Queue → T
  is_empty : Queue → Bool
  is_full : Queue → Bool

axioms ∀q : Queue, ∀x, y : T
  leave (enter (empty, x)) = empty
  leave (enter (enter(q, x), y)) =
  enter (leave (enter(q, x)), y)
  top (enter (empty, x)) = x
  top (enter (enter(q, x), y)) =
  top (enter (q, x))
  is_empty (empty) = true
  is_empty (enter(q, x)) = false
  is_full (empty) = false
  is_full (enter(q, x)) = false
  is_full (n * enter(q, x)) = true

Definition 11-3. Die Spezifikation einer Queue sieht auf den ersten Blick sehr ähnlich zu der eines Stacks aus, obwohl das Verarbeitungsprinzip komplett entgegengesetzt ist

Bezüglich Spezifikation: Im Unterschied zum Stack kann jetzt bei leave und bei front nicht der jeweilig letzte gespeicherte Parameter bearbeitet werden. Stattdessen ist es nötig, durch rekursiv aufgebaute Gleichungen sich bis zum jeweils »innersten« Wert des Queue-Terms vorzuarbeiten.

Abbildung 11-2. Verdeutlichung des Queue-Prinzips [addp]

Anwendungen

Warteschlangen werden ebenfalls in vielfältiger Weise in Softwaresystemen eingesetzt, da sie das Abarbeiten von Aufträgen in Eingangsreihenfolge realisieren können:

so etwa zur Prozessverwaltung in Betriebssystemen (FIFO Scheduling),

zur Speicherverwaltung,

für Warteschlangen bei Druckaufträgen,

für Nachrichtenpuffer in der Kommunikationssoftware etc.

Abbildung 11-3. Beispiel: Einsatz einer Queue im Nachrichtenmuliplexing (Multi-Queue System) [https://mungfali.com/explore/FIFO-Method-Diagram]

Algorithmik

Das erste Element befindet sich immer auf der Position 0. Dies hat zur Folge, dass nach jedem Herausnehmen eines Elementes alle verbliebenen Elemente nach links verschoben werden müssten, was natürlich eine eher ungeeignete Variante darstellt.

Wir brauchen jetzt tatsächlich zwei Zeiger um eine Queue mit einer linearen Tabelle zu implementieren:

HEAD: Zeigt auf das nächste freie Element (davor das jüngste)

BOTTOM: Zeigt auf das erste (älteste) Element in der Warteschlange

Die zeiger werden bei enter und leave nur inkrementoiert:

enter: HEAD++

leave: BOTTOM++

Abbildung 11-4. Simulierter Ringpuffer mit zwei umlaufenden Zeigern. O: Start; A,B,C: Zustand nach enter/leave Operationen

Es wird ein zyklischer Ringpuffer durch die Modulo-Operation erzeugt: H%N, B%N mit N als Anzahl der Speicherzellen.

Den Füllstand einer Queue über die beiden Zeigen zu bestimmen (empty, full) ist nicht eindeutig. Gleichheit von HEAD und BOTTOM liegt bei Leere und vollständiger Füllung vor! Daher wird ein Zähler verwendet (oder es dürfen nur N-1 Feldelemente befüllt werden).

function Queue(N)   { return { H:0,B:0,T:Array(N), N:N, n:0 } }
function enter(Q,x) { Q
Q.H
=x; Q.H=(Q.H+1) % Q.N; Q.n++; }
function leave(Q,x) { x=Q
Q.B
; Q.B=(Q.B+1) % Q.N; Q.n--; return x}
function empty(Q)   { return Q.n==0 }
function full(Q)    { return Q.n==Q.N }
function bottom(Q)  { return Q.n>0 && Q
Q.B
 }
function top(Q)     { return Q.n>0 && Q
abs((Q.H-1)%Q.N)
 }

Algorithmus 11-2. Queue Operationen

Ein Problem der hier vorgestellten Implementierung ist die Größenbeschränkung des Feldes. So werden nur so lange Elemente eingefügt, bis die Kapazität des Feldes erschöpft ist. Ein Ausweg wäre das Erzeugen eines neuen, größeren Feldes und das Umkopieren der Elemente aus dem alten Feld. Dennoch haben Felder durchaus vorteilhafte Eigenschaften, wie etwa den günstigen Platzverbrauch (keine zusätzlichen »Verwaltungsinformationen«) oder die kompakte und dadurch Cache-freundliche Organisation der Daten.

Die Zeitkomplexität ist konstant und beträgt O(1) für alle Operationen.

Der Speicherplatzbedarf wird dagegen durch das Anlegen eines Feldes einer vorgegebenen Größe N verursacht und ist somit unabhängig von der tatsächlichen Anzahl der Elemente im Stack bzw. in der Queue. Für die Speicherplatzkomplexität kann demnach O(N) angegeben werden.

Hash Tabellen

Das Grundprinzip von Hashverfahren lässt sich mit wenigen Aussagen charakterisieren:

Die Speicherung der Datensätze erfolgt in einem Feld mit Indexwerten von 0 bis N− 1, wobei die einzelnen Positionen oft als »Buckets« bezeichnet werden.

Eine Hashfunktion h bestimmt für ein Element e die Position h(e) im Feld.

Die Funktion h sorgt für eine »gute«, kollisionsfreie bzw. kollisionsarme Verteilung der zu speichernden Elemente.

Da es in der Regel sehr viel mehr möglicherweise zu speichernde Elemente als die N Positionen im Feld gibt und die zu speichernden Elemente vorher unbekannt sind, kann die Funktion nicht allen möglichen Elementen unterschiedliche Positionen zuweisen.

Wird zwei Elementen dieselbe Position zugewiesen, spricht man von einer Kollision. Neben einer möglichst gut streuenden Hashfunktion ist die Behandlung von Kollisionen ein zentrales Merkmal von Hashverfahren.

Parametrisierung eines Problems

Es gibt K mögliche Schlüssel (Schlüsselgröße)

Numerische Schlüssel, z.B. Matrikel- oder Personalnummer

Zeichenketten, z.B. Nachnamen

Quersummen

Zusammengesetzte Datenstrukturen

Es gibt eine maximale Anzahl von möglichen Datensätzen L (Problemgröße)

Es gibt eine feste Größe der Tablle mit N Feldern (Tabellengröße)

Es gibt eine Hashfunktion h(k): k → i, die einen Schlüssel auf einen Index der Tabelle abbildet, so dass k ∈ 𝕂, i ∈ [0,N-1].

Es gibt eine aktuelle Belegung mit α=m/N, wobei m die Anzahl der gespeicherten Schlüssel ohne Überläufer ist.

Hash Funktionen

Man kann sich leicht klar machen, dass bei einem genügend großen Wertevorrat auch immer n Elemente gefunden werden können, die durch h auf dieselbe Position abgebildet werden – ein Hashverfahren kann entarten. Durch eine gute Hashfunktion kann man die Wahrscheinlichkeit einer Entartung verringern, aber nie ganz ausschließen – wohl ein Grund, weshalb viele Programmierer Hashverfahren etwas misstrauisch betrachten und sie trotz ihrer guten Eigenschaften relativ selten einsetzen.

Betriebssysteme verwenden Hashtabellen für einen effiziente Verwaltung von Ressourcen

Komplexität

Einfügen, Löschen, Suche:

Best case: O(1)

Average case: O(1) (≤ O(N))

Worst case: O(N)

Die Anzahl der zum Suchen, Einfügen oder Entfernen eines Schlüssels benötigten Schritte hängt im wesentlichen vom Belegungsfaktor α ab.

Hash Funktionen

Von zentraler Bedeutung für Hashverfahren sind die Hashfunktionen.

Die Hashfunktionen hängen natürlich vom Datentyp der zu speichernden Elemente und der konkreten Anwendung ab (die Mengen von zu speichernden string-Werten können je nach Anwendung sehr unterschiedlich aussehen).

Divisions-Rest-Methode

Für Integerwerte als Suchschlüssel k wird oft als Hashfunktion direkt die Modulo Funktion verwendet:

image-placeholder
(11-2)

Dies funktioniert in der Regel allerdings nur dann gut, wenn N eine (große) Primzahl ist, die nicht nahe an einer großen Zweierpotenz liegt, da sonst unbeabsichtigt besondere algebraische Eigenschaften der eingegebenen Schlüssel eine Gleichverteilung verhindern.

Gerade künstlich erzeugte Suchschlüssel haben oft verborgene algebraische Eigenschaften, die nicht auf den ersten Blick zu erkennen sind, Z.B.

dass das gerne gewählte N = 2i etwa die Eigenschaft »ungerade« erhält,

werden beispielsweise generierte Artikelnummern durch eine der drei Kontrollziffern 1, 3 oder 7 abgeschlossen, würde ein Hashen mit N = 2i die Werte nur auf ungerade Adressen abbilden.

Für andere Datentypen kann eine Rückführung auf Integerwerte erfolgen:

Bei Fließpunktzahlen kann man Mantisse und Exponent addieren.

Bei Strings könnte man deren ASCII/Unicode-Wert oder den einiger Buchstaben davon, eventuell jeweils mit einem Faktor gewichtet, addieren. In einer konkreten Variante werden für einen String s der Länge l aus 1-Byte-Zeichen l (initial) zufällige Elemente ai ∊ {0, …, N − 1} gewählt und der Hashwert wie folgt berechnet:

image-placeholder
(11-3)

Hashfunktionen sollen die Werte natürlich besonders gut »streuen«. Daher ist es oft sinnvoll, eventuell von Besonderheiten der Eingabewerte abhängige Funktionen zu wählen (Buchstaben des Alphabets tauchen in Namen unterschiedlich häufig auf!). Allerdings müssen Hashfunktionen auf jeden Fall effizient berechenbar sein (konstanter Zeitbedarf, auf keinen Fall abhängig von der Anzahl der gespeicherten Werte!).

Das Matrikelnummer-Beispiel zeigt, dass eine schlecht gewählte Hashfunktion die Güte des Verfahrens schnell negativ beeinflussen kann. Die Hashtabelle besteht hierbei aus 100 Buckets, gespeichert werden sollen Studentendatensätze, identifiziert durch die Matrikelnummer MATRNR. Die 6-stellige MATRNR wird fortlaufend vergeben.

Werden die ersten beiden Stellen von MATRNR als Hashwerte ausgewählt, werden die Datensätze eines Jahrgangs alle auf sehr wenige Positionen abgebildet.

Die letzten beiden Stellen von MATRNR hingegen verteilen die Datensätze gleichmäßig auf alle Positionen.

Die von der Hashfunktion zu gegebenen Schlüsseln gelieferten Hashadressen sollten also über dem Adreßbereich gleichverteilt sein, und zwar selbst dann, wenn die Schlüssel aus 𝕂 alles andere als gleichverteilt sind (etwa bei der Vorliebe von Programmierern für Namen wie x, x1, x2, y1, y2, z1, z2).

Die multiplikative Methode

Der gegebene Schlüssel wird mit einer irrationalen Zahl multipliziert; der ganzzahlige Anteil des Resultats wird abgeschnitten. Auf diese Weise erhält man für verschiedene Schlüssel verschiedene Werte zwischen 0 und 1; für Schlüssel 1, 2, 3,.., n sind diese Werte ziemlich gleichmäßig im Intervall [0,1) verstreut

Von allen Zahlen Θ, 0 ≤ Θ ≤ 1, führt der goldene Schnitt zur gleichmäßigsten Verteilung:

image-placeholder
(11-4)

Damit erhalten wir folgende Hashfunktion:

image-placeholder
(11-5)

Insbesondere bilden die Werte h(1), h(2), .. , h(10) für m = 10 gerade eine Permutation der Zahlen 0 , 1 , .. , 9, nämlich 6, 2, 8, 4, 0, 7, 3, 9, 5, 1.

Man kann die Berechnung von h(k) noch beschleunigen, wenn man ganze Zahlen im Rechner als Bruchzahlen mit Dezimalpunkt vor der höchstwertigen Ziffer ansieht, und wenn man für m eine Zweierpotenz wählt; dann läßt sich die Berechnung von h(k) mit einer ganzzahligen Multiplikation und einer (oder zwei) Shift-Operation(en) vornehmen.

Neben diesen beiden Methoden gibt es noch zahlreiche andere, die z.B.

nach einer Transformation des Schlüssels (in ein anderes Zahlensystem oder durch Quadrieren oder durch Falten auf kurze Länge mit Verknüpfen von Teilstücken) einzelne Ziffernpositionen auswählen.

Praxis

Perfektes und universelles Hashing

Ist die Anzahl der zu speichernden Schlüssel nicht größer als die Anzahl der zur Verfügung stehenden Speicherplätze, gilt also für die Teilmenge K der Menge 𝕂 aller möglichen Schlüssel |K| ≤ N, so ist eine kollisionsfreie Speicherung von K immer möglich!

Wenn wir K kennen und K fest bleibt, können wir leicht eine injektive Ab-bildung h : K → { 0,..,N-1} z.B. wie folgt berechnen:

Wir ordnen die Schlüssel in K lexikographisch und bilden jeden Schlüssel auf seine Ordnungsnummer ab.

Wir haben damit eine perfekte Hashfunktion, die Kollisionen gänzlich vermeidet.

Eine solche Situation (K fest und vorher bekannt) liegt z.B. dann vor, wenn den Schlüsselworten einer Programmiersprache feste Plätze in einer Symboltabelle zugeordnet werden sollen.

Dieser Fall ist aber eher die Ausnahme als die Regel.

Im allgemeinen kennen wir K ⊆ 𝕂 nicht und können selbst dann, wenn |K| ≤ N bleibt, nicht sicher sein, daß Kollisionen vermieden werden.

Lum, Yuen und Dodd hatten festgestellt, dass das Divisions-Rest-Verfahren im Durchschnitt die besten Resultate liefert!

Bei der Analyse der Effizienz von Hashverfahren geht es uns in erster Linie um die durchschnittliche Laufzeit für die Operationen Suchen, Einfügen und Entfernen.

Im schlimmsten Fall sind diese Operationen extrem langsam; dieser Fall ist leicht direkt aus der Beschreibung der Verfahren ableitbar.

Wir werden stets zwei Erwartungswerte Cn+ und Cn- angeben, bezogen auf feste Tabellengröße m.

Dabei ist Cn+ der Erwartungswert für die Anzahl der betrachteten Einträge der Hashtabelle bei erfolgreicher Suche, Cn- der Erwartungswert für die Anzahl der betrachteten Einträge der Hashtabelle bei erfolgloser Suche.

Komplexität beim Hashtabellen

Den Werten liegt eine Wahrscheinlichkeitsverteilung (der Schlüssel) zugrunde.

Dem Entfernen eines Datensatzes muß stets eine erfolgreiche Suche vorausgehen; entsprechend ist der Aufwand für das Entfernen gerade Cn+ , wenn der betreffende Eintrag lediglich als entfernt markiert wird.

Dem Einfügen eines Datensatzes muß stets eine erfolglose Suche vorausgehen; entsprechend ist der Einfüge-Aufwand gerade Cn- , wenn der betreffende Datensatz einfach an der ersten gefundenen freien Stelle eingetragen wird.

Umgang mit Kollision und Überläufer

Folgende Verfahren können eingesetzt werden wenn eine Kollision festgestellt wird, d.h. der mit h(k₁) berechnete Platz ist bereits mit einem Schlüssel k₂ mit k₁ ≠ k₂ belegt, d.h. das einzufügende Element wird zum Überläufer

Verkettung der Überläufer mit Listen - man bringt die Überläufer außerhalb der Tabelle unter

Offene hashverfahren - man bringt die Überläufer in der Tabelle woanders unter:

Lineares Sondieren

Quadratisches Sondieren

Double Hashing

Ordered Hashing

Robin-Hood Hashing

Coealesced Hashing

Dynamische Hashverfahren - Hashverfahren für stark wachsende oder schrumpfende Datenbestände

Hashtabellen und Überläufer

Umgang mit Kollision und Überläufer

Folgende Verfahren können eingesetzt werden wenn eine Kollision festgestellt wird, d.h. der mit h(k₁) berechnete Platz ist bereits mit einem Schlüssel k₂ mit k₁ ≠ k₂ belegt, d.h. das einzufügende Element wird zum Überläufer

Verkettung der Überläufer mit Listen - man bringt die Überläufer außerhalb der Tabelle unter

Offene Hashverfahren - man bringt die Überläufer in der Tabelle woanders unter:

Lineares Sondieren

Quadratisches Sondieren

Double Hashing

Ordered Hashing

Robin-Hood Hashing

Coealesced Hashing

Dynamische Hashverfahren - Hashverfahren für stark wachsende oder schrumpfende Datenbestände

Werden zwei Datensätze dem gleichen Bucket zugeteilt, dann spricht man von einer Kollision. Wir benötigen also Methoden um Kollisionen zu behandeln. Die führt zu folgender Idee:

Zusammegefasst gibt es also zwei Lösungsansätze:

Jede Tabellenzelle wird um eine Liste oder Suchbaum erweitert, in denen die kollidierenden Datensätze untergebracht werden.

Oder: Im Fall einer Kollision such man nach einer alternativen Position. Diese Technik nennt man Sondieren.

Verkettung der Überläufer

Sei N = 10 und h(x) = x mod 10. Werden die Datensätze 100, 42, 5, 333, 19, 666, 202, 36 und 2 in eine Hashtabelle eingetragen, so ergibt sich folgende Situation:

Abbildung 12-1. Beispiel für die Kollisionsbehandlung mit linearen Listen

Zwei Methoden können angewendet werden:

Separate Verkettung der Überläufer

Direkte Verkettung der Überläufer

Gegeben sei eine Hashtabelle t der Größe N mit einer Hashfunktion h(k): k -> index ∈ [0,N-1].

Separate Verkettung der Überläufer

Jedes Element der Hashtabelle t ist Anfangselement einer Überlaufkette (verkettete lineare Liste).

Abbildung 12-2. Mix aus Hashtabelleneintrag und Verkettung [Widmayer]

Suchen nach Schlüssel k: Beginne bei t[h(k)] und folge den Verweisen der Überlaufkette, bis entweder k gefunden wurde (erfolgreiche Suche) oder das Ende der Überlaufkette erreicht ist (erfolglose Suche).

Einfügen eines Schlüssels k: Suche nach k; die Suche verläuft erfolglos (sonst wird k nicht eingefügt) und endet am Ende einer Überlaufkette oder bei t[h(k)].

Im letzteren Fall trage k in t[h(k)] ein; sonst erzeuge ein neues Listenelement und hänge es ans Ende der Überlaufkette an.

Entfernen eines Schlüssels k: Suche nach k; die Suche verläuft erfolgreich (sonst kann k nicht entfernt werden).

Steht k in der Hashtabelle, so streiche k dort; falls eine Überlaufkette bei t[h(k)] beginnt, so übertrage das erste Element der Überlaufkette nach t[h(k)] und entferne es aus der Überlaufkette.

Steht k in einem Element der Überlaufkette, so entferne dieses Element aus der Überlaufkette.

Allerdings fällt auf, daß die unterschiedlichen Fälle (Schlüssel in Hashtabelle oder in Überlaufkette, gegebenenfalls Nachziehen des ersten Überläufers in die Hashtabelle beim Entfernen, usw.) einige Abfragen erfordern, die die Laufzeit der Operationen spürbar beeinträchtigen.

Wenn man bereit ist, unter Umständen etwas Speicherplatz zu opfern, so kann man auch einfach alle Datensätze in den Überlaufketten speichern; in der Hashtabelle benötigt man dann nur Zeiger auf den Listenanfang.

Direkte Verkettung der Überläufer

Jedes Element der Hashtaelle ist ein Zeiger auf eine (Überlauf-) Kette. Im wesentlichen handelt es sich hierbei also stets um Operationen in linearen ver-ketteten Listen.

Abbildung 12-3. Vereinfachtes Verfahren: Alle Elemente werden immer in Listen gespeichert. Der Hasheintrag ist nur Referenz auf Liste. [Widmayer]

Suchen nach Schlüssel k: Beginne bei el=↑t[h(k)] und folge den Verweisen der Überlaufkette, bis entweder k gefunden wurde (erfolgreiche Suche) oder das Ende der Überlaufkette erreicht ist (erfolglose Suche).

Einfügen eines Schlüssels k: Suche nach k; die Suche endet erfolglos am Ende einer Überlaufkette (sonst wird k nicht eingefügt). Schaffe ein neues Listenelement und hänge es ans Ende der Überlaufkette an.

Entfernen eines Schlüssels k: Suche nach k; die Suche verläuft erfolgreich (sonst kann k nicht entfernt werden) und endet bei einem Element der Überlaufkette. Entferne dieses Element aus der Überlaufkette.

Die durchschnittliche Anzahl der Einträge in einer Kette ist gerade α = n / m, wenn n Einträge auf m Ketten verteilt sind.

Die Effizienz der erfolglosen Suche läßt sich verbessern, wenn man die Überlaufketten sortiert hält. Dann muß man beim erfolglosen Suchen nicht stets bis zum Listenende suchen, sondern kann im Mittel schon in der Mitte der Liste der Überläufer aufhören (man beachte, daß die erfolglose Suche dann für α ≤ 1 im Mittel schneller ist als die erfolgreiche).

Nach den angegebenen Methoden der direkten und separaten Verkettung der Überläufer ist klar, daß die Effizienz der erfolgreichen Suche auch gleichzeitig die Effizienz der Entferne-Operation ist, und daß das Einfügen gerade so effizient ist wie die erfolglose Suche.

Ein Belegungsfaktor von mehr als 1 ist möglich; d.h., selbst wenn die zu verwaltende Datenmenge mehr als vorgesehen wächst, so arbeitet das Verfahren noch korrekt.

Effizienz

Abbildung 12-4. Effizienz der Verkettung der Überläufer (Anzahl der durchschnittlichen

Die entscheidenden Nachteile der Methoden der Verkettung der Überläufer sind der Speicherplatzbedarf für die Zeiger und die Tatsache, daß selbst dann Platz für Überläufer außerhalb der Hashtabelle benötigt wird, wenn in der Hashtabelle noch viele Plätze frei sind.

Die gesamte Auslastung und Ausnutzung der eigentlichen Hashtabelle kann niedrig sein trotz hoher Gesamtbelegung.

Offene Hashverfahren

Im Unterschied zur Verkettung der Überläufer außerhalb der Hashtabelle versucht man bei offenen Hashverfahren, Überläufer in der Hashtabelle unterzubringen.

Wenn also beim Versuch, den Schlüssel k in die Hashtabelle an Position h(k) einzutragen, fest-gestellt wird, daß t[h(k)] bereits belegt ist, so muß man nach einer festen Regel einen anderen, nicht belegten Platz (eine offene Stelle) finden, an dem man k unterbringen kann.

Da man von vornherein nicht wissen kann, welche Plätze belegt sein werden und welche nicht, definiert man für jeden Schlüssel eine Reihenfolge, in der alle Speicher-plätze, und zwar einer nach dem anderen, betrachtet werden. Sobald ein betrachteter Platz frei ist, wird der Schlüssel dort gespeichert.

Die Folge der zu betrachtenden Spei-cherplätze für einen Schlüssel nennt man die Sondierungsfolge zu diesem Schlüssel.

Die Folge wird i.A. iterativ/rekursiv berechnet.

Die Hauptaufgabe ist nun das Finden eine geeigneten und effizienten Sondierungsfolge und deren Berechnung.

Natürlich ist das Entfernen von Schlüsseln bei all diesen Verfahren problematisch.

Ein bereits in der Hashtabelle vorhandener Schlüssel k1 versperrt ja einem neu einzufügenden Schlüssel k2 im allgemeinen einen Platz, den k2 gemäß seiner Sondierungsfolge betrachtet.

Der neue Schlüssel k2 weicht also auf einen anderen Platz (später in der Sondierungsfolge) aus.

Wird nun k1 entfernt, so kann k2 nicht wiedergefunden werden, weil der leergewordene Platz von k1 in der Sondierungsfolge von k2 vor dem aktuellen Platz von k2 auftritt.

In diesem Fall wird k1 bei den meisten Verfahren dann auch nicht wirklich entfernt, sondern lediglich als entfernt markiert.

Wird ein neuer Schlüssel eingefügt, so wird der Platz von k1 als frei angesehen; wird ein Schlüssel gesucht, so wird der Platz von k1 als belegt angesehen.

Sei s(j,k) eine Funktion von j und k so, daß (h(k)-s(j,k)) mod m für j = 0,1,..,m-1, eine Sondierungsfolge bildet, d.h. eine Permutation aller Hashadressen.

Es sei stets noch mindestens ein Platz in der Hashtabelle frei.

Suchen nach Schlüssel k: Beginne mit Hashadresse i = h (k). Solange k nicht in t[i] gespeichert ist und t[i] nicht frei ist, suche weiter bei i = (h(k)-s(j,k)) mod m, für aufsteigende Werte von j. Falls t[i] belegt ist, wurde k gefunden; sonst war die Suche erfolglos.

Einfügen eines Schlüssels k: Wir nehmen an, daß k nicht schon in t vorkommt (das kann durch eine Suche festgestellt werden). Beginne mit Hashadresse i = h(k). Solange t[i] belegt ist, mache weiter bei i = (h(k)-s(j,k)) mod m, für steigende Werte von j. Trage k bei t[i] ein.

Entfernen eines Schlüssels k: Suche nach Schlüssel k. Verläuft die Suche erfolgreich und ist i die Adresse, an der k gefunden wird, dann markiere t[i] als entfernt; sonst kommt k nicht in t vor und kann auch nicht entfernt werden.

Abbildung 12-5. Prinzip des Sondierens

Lineares Sondieren

image-placeholder
(12-1)

Abbildung 12-6. Effizienz beim linearen Sondieren (α ist Belegungsfaktor)

N=7; H=vector(N,-1)
function hash(k,N) { return k % N }
function probe(H,N,i) {
  i=i-1; n=N-1
  while(n && H[i]!=-1) {
    n--
    i=(i-1) % N
  }
  return n==0?-1:i
}
function search(H,N,k) {
  i=hash(k,N)
  if (H[i]==k) return i;
  i=i-1; n=N-1
  while(n && H[i]!=k && H[i]!=-1) {
    n--
    i=(i-1) % N
  }
  return n==0?-1:i
}
function collision(H,N,k) {
  i=hash(k,N)
  return H[i]!=-1
}

Algorithmus 12-1. Lineares Sondieren

Quadratisches Sondieren

image-placeholder
(12-2)

Abbildung 12-7. Effizienz beim qudratischen Sondieren (α ist Belegungsfaktor)

Double Hashing

Die Effizienz des uniformen Sondierens wird bereits annähernd erreicht, wenn man statt einer polynomiellen Permutation für die Sondierungsfolge eine zweite Hashfunktion verwendet; die gewählte Sondierungsfolge für Schlüssel k ist

image-placeholder
(12-3)

Dabei muß h'(k) so gewählt werden, daß für alle Schlüssel k die Sondierungsfolge eine Permutation der Hashadressen bildet.

Das bedeutet, daß h'(k) ≠ 0 sein muß und m nicht teilen darf.

Wählen wir m als Primzahl, dann gilt dies sicher für jedes h'(k) und für alle k; diese Wahl von m ist ja auch günstig für die Divisions-Rest-Methode bei der Hashfunktion h.

Wählt man h'(k) abhängig von h(k), so werden manche (oder gar alle) Synonyme die gleiche Sondierungsfolge haben; eine gewisse sekundäre Häufung ist die Folge.

Das kann man vermeiden, wenn man h'(k) von h(k) unabhängig wählt.

Vertiefende Literatur

Algorithmen und Datenstrukturen, Thomas Ottmann, Peter Widmayer, s. 169 ff., Kap. 4 hashverfahren

Listen

Im Gegensatz zu Tabellenstrukturen werden hier dynamische Strukturen eingeführt:

Einfach verkettete Listen

Doppelt verkettete Listen

Skip Listen

Basisoperationen auf Listen:

Einfügen

Suchen

Entfernen

Dynamische Strukturen

Die Probleme statischer Datenstrukturen lassen sich durch die Verwendung dynamischer Strukturen umgehen.

Dynamisch bedeutet dabei, dass sie zur Laufzeit »wachsen« oder »schrumpfen« können und sich dadurch an den tatsächlichen Speicherbedarf anpassen lassen, anders als tabellarische Strukturen.

Ein typischer Vertreter einer dynamischen Datenstruktur ist die verkettete Liste.

Eine solche Liste besteht aus einer Menge von Knoten, die untereinander »verzeigert« (referenziert) oder auch »verkettet« sind.

Jeder Knoten besteht damit aus einem Verweis (in Java eine Objektreferenz) auf das eigentliche zu speichernde Element sowie einem Verweis auf das nachfolgende Element.

Im Vergleich zu Tabellen sind Listen nicht für echtzeitfähige Systeme geeignet da ihre Laufzeiten nicht im voraus bestimmbar sind.

Entwurf von Datentypen

Etwas systematischer als heuristisch: Wir haben bisher einige einfache Beispiele für abstrakte Datentypen kennen gelernt und deren Spezifikationen mit Gleichungen angegeben.

Vorgehensweise, mit der man gerade einfache Datentypen gut spezifizieren kann. Hier empfiehlt sich folgende Vorgehensweise:

Die Festlegung der Konstruktorfunktionen legt den Bereich der Basisterme fest, die den später implementierten Werten entsprechen, und sollte daher mit besonderer Sorgfalt erfolgen.

Im Stack-Beispiel benötigt man einen Konstruktor für den leeren Stack und die push-Operation, um alle zu realisierenden Stack-Werte zu definieren.

Eventuell ist es nötig, auch Axiome zur Gleichsetzung von Konstruktortermen einzuführen. Der Set-Datentyp ist ein gutes Beispiel hierfür. 3.Die Definition geeigneter Selektorfunktionen erlaubt den lesenden Zugriff auf die konstruierten Werte, ohne einen neuen Wert zu konstruieren. Typischerweise ist das Ergebnis einer Selektion daher ein Wert eines importierten Datentyps.

Dann müssen die weiteren Operationen festgelegt werden, sozusagen die Manipulatoren der Datenwerte. Manipulatorfunktionen haben als Ergebnistyp den neu spezifizierten Datentyp.

Der letzte Schritt besteht darin, Fehlersituationen abzufangen.

Listen

Ein typischer Vertreter einer dynamischen Datenstruktur ist die verkettete Liste.

Eine solche Liste besteht aus einer Menge von Knoten, die

untereinander »verzeigert« oder auch »verkettet« sind.

Jeder Knoten besteht damit aus einem Verweis (in Java eine Objektreferenz) auf das eigentliche zu speichernde Element sowie einem Verweis auf das nachfolgende Element.

image-placeholder
(13-1)

Listen sind keine Mengen! Listen sind geordnet bzw. haben eine feste Reihenfolge der Knoten, wonhingegen Mengen ungeordnet sind und jede Permutation der Reihenfolge von Knotenelementen möglich und zuässig ist.

Das letzte Element verweist demzufolge auf null. In der Liste selbst muss nur noch der erste Knoten direkt verankert sein, alle anderen Knoten sind durch das Navigieren über die Zeiger erreichbar. Der »Anker« für den Beginn der Liste wird mit head bezeichnet.

Einfach verkettete Listen

Abbildung 13-1. Prinzip der einfach verketteten Liste. Dier Daten werden i.A. separat gespeichert und in der Elementstruktur gibt es nur einen Zeiger auf die Daten. Eine Integatrion der Daten (z.B. ganze Zahlen) ist aber auch möglich. [addp]

ZeigerArrays

Ein Spezialfall von Listen sind Zeigerarrays, wie sie typischerweise in allen dynamisch typisierten Programmiersprachen wie javaScript, Python oder Lua vorkommen.

Arrays sind in dynamische typisierten Programmiersprachen polymorph und mehrsortig, d.h. jedes Element kann einen Wert mit anderen Datentyp besitzen. Es bedarf daher einer getrennten Speicherung von Organisationsstruktur (Tabelle) und Daten.

Abbildung 13-2. Einfache (einelementige) Listen in mehrsortigen Arrays - oder Urform der Bereichslisten

Bei Stack und Queue gab es ein Paar aus (verschiedenen) Operation um Elemente einzufügen und zu entfernen. Diese können auch bei verketteten Listen eingesetzt werden:

addHead(L,x) fügt das Objekt x als erstes Element in die Liste ein.

getFirst(L) liefert das erste Element der Liste.

removeFirst(L) entfernt das erste Element der Liste und gibt es gleichzeitig als Ergebnis zurück.

addLast(L,x) hängt das Objekt x als letztes Element an die Liste an.

getLast(L) liefert das letzte Element der Liste.

removeLast(L) entfernt das letzte Element der Liste und gibt es gleichzeitig als Ergebnis zurück.

Wir haben i.A. Kopf- oder Endlisten oder beides. Das wird durch die Anker bestimmt. Eine Kopfliste hat den head Zeiger, die Endliste den tail Zeiger.

Einfügen und Löschen am Anfange

Abbildung 13-3. Einfügen eines Elements *x* am Anfang ist durch den Anker *head* einfach in O(1) durch Änderung des *head* Zeigers auf *x* möglich. Das gleiche gilt für das Löschen des Kopfelements, ebenfalls nur eine Änderung von *head*.

Einfügen und Löschen am Ende

Abbildung 13-4. Einfügen und Löschen eines Elements *x* am Ende ist durch den Anker *head* nicht möglich. Stattdessen benötigt man das letzte und vorletzte Element beim Löschen, nur durch Suche (Iteration) in O(N) möglich! Auch ein *tail* Anker hilft beim Löschen nicht, beim Einfügen schon!

Die Operationen zur Manipulation des Listenendes sind dagegen etwas komplexer.

Da nur der Listenanfang bekannt ist, muss für das Anhängen eines Elementes zunächst der letzte Knoten (tail) durch Verfolgen der next-Zeiger ermittelt werden.

Dieser ist dadurch gekennzeichnet, dass sein next-Zeiger auf null verweist.

Ist der letzte Knoten gefunden, wird dessen next-Zeiger auf den neu angelegten Knoten mit dem anzuhängenden Element gesetzt

Zum Löschen des letzten Elementes wird dagegen auch der vorletzte Knoten benötigt, da dessen Verweis auf null gesetzt werden muss.

Entsprechend muss der Knoten gesucht werden, dessen Nachfolgerknoten auf null verweist.

Da in jedem Fall die gesamte Liste durchlaufen werden muss, ist der Aufwand abhängig von der Anzahl N der Elemente in der Liste und beträgt für diese Operationen entsprechend O(N).

Komplexität

Operation | Komplexität (head) | Komplexität (head+tail)
addFirst | O(1) | O(1)
getFirst | O(1) | O(1)
removeFirst | O(1) | O(1)
addLast | O(N) | O(1)
getlast | O(N) | O(1)
removeLast | O(N) | O(N)

Der Aufwand aller Listenoperationen für einfach verkettete Listen

Algorithmus und Datenstruktur

L={head:null}                       function addLast(L,x)  {
                                      node=L.head
function Node(data,next) {            while (node.next)
  return { data:data, next:next }       node=node.next
}                                     node.next=Node(x,null)
                                    }
function addFirst(L,x)  {           function getLast(L,x)  {
  node=Node(x,L.head)                 node=L.head
  L.head=node                         while (node.next)
}                                       node=node.next
function getFirst(L)  {               return node.data
  return L.head.data                }
}                                   function removeLast(L,x)  {
function removeFirst(L,x)  {          node=L.head
  if (!L.head) return;                while (node.next && node.next.next)
  first=L.head                          node=node.next
  L.head=L.head.next                  last=node.next
                                      node.next=null
  return first                        return last
}                                   }

Algorithmus 13-1. Einfach verkettete Liste

Doppelt verkettete Listen

Ein Problem der Implementierung der verketteten Liste ist der mit dem Zugriff auf das letzte Element verbundene Aufwand.

Da jeder Knoten nur mit seinem Nachfolger verkettet ist, muss das letzte Element immer erst durch Navigieren vom Listenkopf ausgehend über alle Knoten ermittelt werden.

Zwar könnte man die Liste um einen tail-Zeiger auf das letzte Element ergänzen und so das Einfügen von Elementen am Ende der Liste vereinfachen.

Dies würde beispielsweise die Implementierung der Klasse Queue vereinfachen.

Trotzdem ist beim Löschen des letzten Elementes immer noch das Durchlaufen aller Knoten zum Auffinden des vorletzten Knotens notwendig.

Uns es gibt noch zwei weitere Basisoperationen:

insert(L,x,pos) fügt das Element x an oder hinter pos in der Liste ein.

remove(L,x) entfernt ein beliebiges Element x aus der Liste.

Eine Verbesserung bietet daher die doppelt verkettete Liste, bei der jeder Knoten nicht nur seinen Nachfolger, sondern auch seinen Vorgänger kennt

Es gilt formal:

image-placeholder
(13-2)

Abbildung 13-5. Doppelt verkettete Liste

Für eine doppelt verkettete Liste werden zwei spezielle Knoten, head für den Listenanfang und tail für das Listenende, verwaltet. Durch die Verfügbarkeit des Listenendes und der rückwärts gerichteten Verweise vereinfachen sich die Operationen am Listenende. So kann das letzte Element für die Operation getLast direkt über tail mit konstantem Aufwand O(1) ermittelt werden. Auch beim Anhängen eines Elementes mit addLast kann über tail sofort der bisher letzte Knoten bestimmt werden, dessen next-Zeiger nun auf den neuen Knoten zeigt. Zusätzlich muss noch der prev-Zeiger des neuen Knotens auf den bisherigen letzten Knoten verweisen

Einfach verkettete Listen

Einfügen und Löschen am Anfange und Ende

Abbildung 13-6. Anhängen am Ende einer doppelt verketteten Liste (analog Löschen, am Anfang wie 1 VKL)

Doppelt verkettete Listen

Beim Löschen (removeLast) wird zunächst über den prev-Zeiger des letzten Knotens der vorletzte Knoten bestimmt, dessen next-Zeiger dann auf null gesetzt wird.

Auch für die Operationen addLast und removeLast beträgt der Aufwand daher O(1).

Ebenso einfach ist das Einfügen und Löschen von Elementen in der Mitte der Liste.

Allerdings muss hierzu zunächst die entsprechende Position in der Liste gefunden werden, indem beispielsweise vom Anfang der Liste ausgehend dasjenige Element gesucht wird, vor oder nach dem das neue Element eingefügt werden soll.

Komplexität

Operation | Komplexität (head+tail)
addFirst | O(1)
getFirst | O(1)
removeFirst | O(1)
addLast | O(1)
getlast | O(1)
removeLast | O(1)
insert | O(N)
remove | O(N)

Der Aufwand aller Listenoperationen für deppelt verkettete Listen

Einfach verkettete Listen

Algorithmus und Datenstruktur

L={head:null,tail:null}
function Node(x,prev,next) { return { data:x, prev:prev, next:next }

function addLast(L,x) {                        function insert(L,x,pos) {
  node=Node(x,L.tail,null)                       node=L.head
  if (L.tail) L.tail.next=node                   while(pos && node) {
  L.tail=node                                      node=node.next
  if (!L.head) L.head=L.tail                       pos--
                                                 }
}                                                if (!node) return;
function getLast(L,x) {                          next=node.next;
  return L.tail.data                             node.next=Node(x,node,next)
}                                                if (next) next.prev=node.next
function removeLast(L,x) {                     }
  if (!L.tail) return;                         function remove(L,x) {
  last=L.tail                                    node=L.head
  L.tail.prev.next=null                          while (node.data!==x) node=node.next;
  L.tail=L.tail.prev                             if (!node) return;
  return last.data                                 removed=node;
}                                                node.prev.next=node.next
                                                 if (node.next)
                                                   node.next.prev=node.prev
                                                 return removed.data
                                               }

Algorithmus 13-2. Doppelt verkettete Liste (addHead, getHead, removeHead wie 1 VKL)

Einfügen und Löschen in der Liste

Die universellen insert und remove Operationen arbeiten mit einer Referenzposition. Dafür gibt es verschiedene Möglichkeiten:

Die Indexposition eines Elements in der Liste (Iteration über Index)

Die Daten eines Elements (Suche nach Datengleichheit)

Die Referenz eines Listenelements

Die Suche kann ebenfalls verschiedene Ergebnisse liefern:

Die Indexposition

Die Daten eines Elements

Die Referenz eines Listenelements

Die Einfüge- und Löschoperationen können von O(N) auf O(1) reduziert werden wenn man mit Referenzen auf Listenelementen (also Daten + Orga) arbeitet und diese auch an die insert und remove Funktionen übergibt.

Bereichslisten (Skiplisten)

Ein Nachteil von verketteten Listen gegenüber Feldern ist, dass die binäre Suche nicht einsetzbar ist, da man nicht beliebig »springen« kann. Eine Alternative ist es, mehrere Listen übereinanderzulegen, die dieses Springen ermöglichen. Eine derartige Datenstruktur wird als Skip-Liste bezeichnet.

Abbildung 13-7. Aufbau einer Skip-Liste

Es wird nun aber ein Schlüssel k(x) zu jedem Listenelement (bzw. zu den Daten) benötigt!

Es gibt jeweils einen initialen und einen terminalen Listenknoten, die die Werte −∞ und + ∞ tragen. Grundsätzlich gibt es zwei Möglichkeiten zur Speicherung der Listenelemente auf mehreren Ebenen:

Der Wert wird in separaten Listenelementen auf allen betroffenen Ebenen abgespeichert.

Die Listenelemente werden verschmolzen, so dass Listenelemente mehrere Nachfolger haben können (ja nach abgedeckten Ebenen). Auf diese Weise haben wir in der Abbildung diese Elemente schon zusammengeschoben.

Einfach verkettete listen haben einen, doppelt verk. zwei, und diese Skiplisten bis zu p Nachfolger.

Suche

Man startet in der höchsten Ebene mit dem initialen Knoten. Wenn man einen Knoten ansieht, gibt es drei Möglichkeiten:

Der aktuelle Wert ist der Suchwert. Dann ist man fertig.

Der aktuelle Wert ist kleiner als der Suchwert. Dann wechselt man zum nächsten Knoten derselben Ebene.

Der aktuelle Wert ist größer als der Suchwert. Befinden wir uns auf der Ebene L0, ist der Suchwert nicht gespeichert. Befinden wir uns auf einer höheren Ebene, gehen wir zurück zum letzten Knoten und gehen dann eine Ebene tiefer.

Abbildung 13-8. Suche in einer Skip-Liste

Die bisher gezeigte Liste hat eine statische Struktur mit festen Schrittlängen, die durch das Einfügen und Löschen von Werten zerstört werden würde (etwa wenn die Werte 8 und 9 eingefügt werden).

Allerdings ist der Algorithmus der Suche davon nicht betroffen: Selbst wenn 8 und 9 auf Ebene L0 eingefügt würden, würde die Suche weiterhin funktionieren – jedoch bei der Suche nach der 9 mehrere Schritte auf der untersten Ebenen durchlaufen.

Daher reicht es aus, wenn wir nur eine gute Näherung an feste Schrittlängen haben.

Eine Möglichkeit ist es dabei, neu eingefügte Werte zufällig einer Ebene zuzuweisen, wobei im Mittel die Hälfte der Werte der Ebene L0 zugeordnet wird, ein weiteres Viertel der Ebene L1, ein Achtel dann L2 etc.

Derartige Skip-Listen nennt man randomisiert.

Die zuerst eingeführten Skip-Listen mit Zweierpotenzen als festen Schrittlängen werden zur Abgrenzung von randomisierten Skip-Listen als perfekte Skip-Listen bezeichnet. Sie können insbesondere genutzt werden, wenn die Werte der Skip-Listen nicht mehr geändert oder ergänzt werden.

Algrotihmik

Das Iterator-Konzept

Die Implementierungen der Listen aus den vorigen Abschnitten weist noch ein Manko auf, welches die praktische Verwendbarkeit einschränkt. So ist es oft notwendig, eine Kollektion zu »durchwandern«, d.h. über alle Elemente zu navigieren.

Dieses Navigieren ist zunächst abhängig von der Implementierung: Während beispielsweise ein Feld mittels einer Indexvariablen durchlaufen wird, ist für verkettete Listen das Verfolgen der next-Zeiger der einzelnen Knoten notwendig.

Auch im Hinblick auf die Erhaltung des Prinzips der Kapselung ist daher ein Konzept wünschenswert, das eine einheitliche Behandlung des Navigierens unabhängig von der internen Realisierung unterstützt.

Das ist das Konzept der Iteratoren. Hierbei handelt es sich um Objekte zum Iterieren über Kollektionen.

Ein Iterator verwaltet einen internen Zeiger auf die aktuelle Position in der zugrunde liegenden Datenstruktur.

Auf diese Weise ist es möglich, dass mehrere Iteratoren gleichzeitig auf einer Kollektion arbeiten.

Vier Funktionen von Iteratoren:

hasNext(I) prüft, ob noch weitere Elemente in der Kollektion verfügbar sind. In diesem Fall wird true geliefert. Ist dagegen das Ende erreicht, wird false zurückgegeben.

next(I) liefert das aktuelle Element zurück und setzt den internen Zeiger des Iterators auf das nächste Element.

remove(I) erlaubt es, das zuletzt von next() gelieferte Element zu löschen, wobei pro next-Aufruf nur einmal remove aufgerufen werden darf.

reset(I) setzt den internen Zustand zurück (auf Anfang).

Text Lexer und Parser arbeiten nach dem Iteratorprinzip (hier über Textzeichen oder Texttokens).

Abbildung 13-9. Iterator-Konzept [addp]

Algorithmik

I={iterable:List,next:head(List)}
function next(I) {
  node=I.next
  I.next=node.next
  return node
}

I={iterable:Array,next:0}
function next(I) {
  node=I
I.next
  I.next++
  return node
}

Algorithmus 13-3. Iteratoren

Formale Algorithmenmodelle

ad-dpunkt 6.1

Registermaschine

Als erstes formales Modell betrachten wir die sogenannten Registermaschinen. Registermaschinen befinden sich von der Abstraktion nahe an tatsächlichen Computern und bilden daher quasi eine Art »idealisierte« Version eines Prozessors mit Maschinencode-Steuerung.

Eine Registermaschine als Prozessor führt ein Maschinenprogramm aus, das als durchnummerierte Liste von Einzelschritten vorliegt (dies entspricht tatsächlichen Maschinenprogrammen in Rechnern). Die einzige Kontrollstruktur neben der durch die Nummerierung impliziten Sequenz bilden (bedingte) Sprünge, die es erlauben, an einer beliebigen Stelle des Programms mit der Ausführung weiterzufahren.

Daten werden in einem direkt adressierbaren Speicher gehalten, der eine Abstraktion des bekannten Hauptspeichers darstellt.

Als theoretisches Modell betrachten wir dabei einen beliebig großen, unbeschränkten Speicher. -

Arithmetische Manipulationen werden ausschließlich im Akkumulatorregister des Prozessors ausgeführt.

Diese (maschinennahe) Präzisierung des Algorithmenbegriffs werden wir nun als Registermaschinen exakt definieren. Diese stellen eine relativ simple Abstraktion der programmierbaren Rechner dar, so dass wir in den Bezeichnungen auf vertraute Begriffe der technischen Informatik zurückgreifen.

Eine Registermaschine besteht aus den Registern

B, C0, C1, C2, …, Cn, …

Definition 14-1. Definition einer Registermaschine

und einem Programm.

Das Register B heißt Befehlszähler, C0 heißt Arbeitsregister oder Akkumulator und jedes der Register Cn, n ≥ 1 heißt Speicherregister.

Jedes Register enthält als Wert eine natürliche Zahl. Enthält das Register B die Zahl b und für n ≥ 0 das Register Cn die Zahl cn, so heißt das unendliche Tupel

(b, c0, c1, …, cn, …)

Konfiguration der Registermaschine.

Das Programm ist eine endliche Folge von Befehlen. Durch die Anwendung eines Befehls wird die Konfiguration der Registermaschine geändert.

Befehle bewirken eine Änderung einer Konfiguration (Zustandsänderung ↦ Imperative Algorithmen!)

(b, c0, c1, … cn, …)

in die neue Konfiguration

(b′, c′0, c′1, …, c′n, …),

geschrieben als

(b, c0, c1, … cn, …) ↦ (b′, c′0, c′1, …, c′n, …),

an.

Beispiel 1

LOAD 1 DIV 2 MULT 2 STORE 3 LOAD 1 SUB 3 STORE 3 END

Definition 14-2. Architektur und Aufbau einer Registermaschine

Stehen in den Registern zuerst die Zahlen

b = 1, c0 = 0, c1 = 32, c2 = 5, c3 = 0,

Beispiel 14-1. Ein einfaches Maschinenprogramm für die Registermaschine - eine reine lineare Sequenz

so ergibt sich diese Folge von Konfigurationen

(1, 0, 32, 5, 0, …) ↦ (2, 32, 32, 5, 0, …)
                    ↦ (3, 6, 32, 5, 0, …)
                    ↦ (4, 30, 32, 5, 0, …)
                    ↦ (5, 30, 32, 5, 30, …)
                    ↦ (6, 32, 32, 5, 30, …)
                    ↦ (7, 2, 32, 5, 30, …)
                    ↦ (8, 2, 32, 5, 2, …),

womit der »stoppende« Befehl erreicht wird.

Sind die Inhalte der Register dagegen

b = 1, c0 = 0, c1 = 100, c2 = 20, c3 = 0,

so ergibt sich folgende Folge von Konfigurationen

(1, 0, 100, 20, 0, …)  ↦ (2, 100, 100, 20, 0, …)
                       ↦ (3, 5, 100, 20, 0, …)
                       ↦ (4, 100, 100, 20, 0, …)
                       ↦ (5, 100, 100, 20, 100, …)
                       ↦ (6, 100, 100, 20, 100, …)
                       ↦ (7, 0, 100, 20, 100, …)
                       ↦ (8, 0, 100, 20, 0, …).

Allgemeiner lässt sich Folgendes feststellen. Wir betrachten eine Konfiguration, die durch

b = 1, c0 = 0, c1 = n, c2 = m, c3 = 0

gegeben ist, und nehmen an, dass n = q·m + r mit 0 ≤ r < m gilt, d.h., q = ⌊n/m⌋ ist das ganzzahlige Ergebnis der Division von n durch m und r ist der verbleibende Rest bei dieser Division.

Dann ergibt sich immer die Folge

(1, 0, n, m, 0, …)  ↦ (2, n, n, m, 0, …)
                    ↦ (3, q, n, m, 0, …)
                    ↦ (4, q · m, n, m, 0, …)
                    ↦ (5, q · m, n, m, q · m, …)
                    ↦ (6, n, n, m, q · m, …)
                    ↦ (7, r, n, m, q · m, …)
                    ↦ (8, r, n, m, r, …).

Diese Berechnungsfolge der Registermaschine M1 berechnet also den ganzzahligen Rest der Division zweier natürlicher Zahlen.

Beispiel 2

1. CLOAD 1
2. STORE 3
3. LOAD 2
4. IF c0 = 0 GOTO 12
5. LOAD 3
6. MULT 1
7. STORE 3
8 .LOAD 2
9. CSUB 1
10 .STORE 2
11. GOTO 4
12. END

Beispiel 14-2. Mit Kontrollbefehlen und Verzweigung - jetzt werden die Adressen wichtig!

Stackmaschine

Bisher gabe es eine klassische von-Neumann Rechnerarchitektur bei der Registermaschine. Häufig werden aber Stackmaschinen als Virtuelle Maschinen verwendet.

Meistens gibt es keine reinen Stackmaschinen sondern eine Mischung aus einer Stack- und Registermaschinen.

Registermaschine

Alle Berechnungen laufen über einen Registerspeicher

Stackmaschine

Alle Berechnungen laufen über einen oder mehrere Stack(Stapel)speicher

Abbildung 14-1. Prinzipielle Architektur einer Stackmaschine mit einem Programmspeicher, Programmzähler PC und Stackzeiger SP

Die Continuum VM ist ein Beispiel für eine Stackmaschine.

Continuum ist eine virtuelle JavaScript-Maschine, die in JavaScript implementiert ist.

Sie setzt Bytecode aus Quellcode zusammen und führt ihn in einer ES6-Laufzeitumgebung aus.

Ein Assembler wird verwendet, um den AST in Bytecode und statische Skriptinformationen zu konvertieren.

Ein Codeobjekt enthält den kompilierten Bytecode eines Skripts.

Es enthält auch die meisten statischen Semantiken, die von der Quelle abgeleitet wurden, z. B. gebundene Namen, Deklarationen, Importe / Exporte usw.

Vorteil: Codeobjekte können eine portable Form serialisierbar sein, so dass Code einmal kompiliert und dann in dieser Form weiterverteilt und ausgeführt werden kann.

Ein Skriptobjekt enthält alle statischen Informationen zu einem Codeabschnitt: die angegebenen Optionen, die Originalquelle, den AST, den Bytecode und den kompilierten Thunk (Operationssatz, ISA), der den Bytecode ausführt.

Skripte enthalten keine Laufzeitinformationen, sodass sie zwischen Realms portierbar sind und mehrmals ausgeführt werden können.

Das besondere von Continuum ist die enge Kopplung von Bytecode Instruktionen (die innerhalbe der VM ausgeführt werden) mit externen JavaScript Funktionen und Daten (z.B. Ein- und Ausgabe).

Abbildung 14-2. Prinzipielle Architekturder Continuum VM

Befehlssatz

ADD, AND, ARRAY, ARG, ARGS, ARGUMENTS, ARRAY_DONE, BINARY, BINDING,
CALL, CASE, CLASS_DECL, CLASS_EXPR, COMPLETE, CONST, CONSTRUCT, DEBUGGER,
DEFAULT, DEFINE, DUP, ELEMENT, ENUM, EXTENSIBLE, EVAL, FLIP, FUNCTION,
GET, GET_GLOBAL, HAS_BINDING, HAS_GLOBAL, INC, INDEX, INTERNAL_MEMBER,
ITERATE, JUMP, JEQ_NULL, JEQ_UNDEFINED, JFALSE, JLT, JLTE, JGT, JGTE, JNEQ_NULL,
JNEQ_UNDEFINED, JTRUE, LET, LITERAL, LOG, LOOP, MEMBER, METHOD, MOVE, NATIVE_CALL,
NATIVE_REF, OBJECT, OR, POP, POPN, PROPERTY, PROTO, PUT, PUT_GLOBAL, REF, REFSYMBOL,
REGEXP, REST, RETURN, ROTATE, SAVE, SCOPE_CLONE, SCOPE_POP, SCOPE_PUSH, SPREAD,
SPREAD_ARG,    SPREAD_ARRAY, STRING, SUPER_ELEMENT, SUPER_MEMBER, SWAP, SYMBOL,
TEMPLATE, THIS, THROW, TO_OBJECT, UNARY, UNDEFINED, UPDATE, VAR, WITH, YIELD

Definition 14-3. Der ISA Befehlsatz von Continuum: Doch schon umfangreicher als bei rein formalen Modellen und Maschinen!

ADD(context)
───────────────────────────────────────────────────────────
context
context.sp - 1
 += context
context.ip
[0]

DUP(context)
───────────────────────────────────────────────────────────
context
context.sp
 = context
context.sp++ - 1

LITERAL(context)
───────────────────────────────────────────────────────────
context
context.sp++
 = context
context.ip
[0]

JUMP(context)
───────────────────────────────────────────────────────────
context.ip = context
context.ip
[0]

JTRUE(context)
───────────────────────────────────────────────────────────
isTrue(context
--context.sp
)? context.ip = context
context.ip
[0]

Definition 14-4. Wirkung von einzelnen Bytecode Befehlen

Abstrakte Maschine

TODO

Markov Algorithmen

TODO

Church’sche These

TODO

Endliche Automaten

TODO

AuD DP 17.4.1/17.4.2

Sortierverfahren

Bisher waren die drei wichtigsten Operationen auf Abstrakten Datentypen:

Einfügen von Elementen

Löschen von Elementen

Suchen nach Elementen

Ein weiteres grundlegendes Problem in der Informatik neben dem Suchen ist das Sortieren.

Bereits bei den Listen und dann bei den Bäumen war Restrukturierung wichtig um optimale Rechenzeiten zu erzielen

Sortieren von Elementen ist Restrukturierung

Taxonomie der Sortierverfahren

Unter Sortieren versteht man das Anordnen einer Menge von Objekten in einer bestimmten Ord-nung. Diese Ordnung kann z. B. bei numerischen Daten durch die größer/kleiner-Relation oder bei Texten durch die lexikografische Reihenfolge gegeben sein.

Die zu sortierenden n Elemente seien in einem Feld a mit den Komponenten a[0], a[1], ... , a[n − 1] gespeichert.

Sortieren bedeutet nun, dass die Feldkomponenten durch eine Permutation i₁ , i₂ , ... , in der Indizes 0, 1, ... , n − 1 in diejenige Reihenfolge gebracht werden, die der gewünschten Ordnung, ausgedrückt durch eine Ordnungsrelation ≤f , entspricht:

image-placeholder
(15-1)

Der Sinn des Sortierens bzw. Ordnens liegt darin, dass der Zugriff auf Datensätze in einer geordneten Datei oder Datenstruktur wesentlich effizienter und schneller vonstatten geht, als in einer nicht geordneten Anordnung.

Die Problematik des Sortierens

Sortieren ist damit eine in der Datenverarbeitung elementare, weit verbreitete und wichtige Operation.

In fast allen Problemstellungen spielt das Sortieren von Daten eine mehr oder weniger bedeutende Rolle.

Dies gilt insbesondere für die kommerzielle Datenverarbeitung, aber auch den technisch/wissenschaftlichen Bereich.

Untersuchungen haben ergeben, dass auf kommerziellen Anlagen ca. 25% der CPU-Zeit auf Sortierläufe entfällt.

Es existiert eine große Anzahl von Sortieralgorithmen unter denen man im Einzelfall den geeig-netsten auswählen muss.

Die Sortiermethoden hängen stärker als die meisten anderen Algorithmen von der Struktur der zu sortierenden Daten ab.

Es ist ein ganz wesentlicher Unterschied, ob man die zu sortierenden Daten im relativ beschränkten Hauptspeicher mit wahlfreiem Zugriff oder auf langsameren, jedoch größeren sequentiell oder zyklisch arbeitenden externen Speichermedien – also auf Band- oder Plattenlaufwerken – halten muss.

Gerade bei Sortieralgorithmen spielen auch kleine Leistungssteigerungen eine große Rolle, da sich dies wegen der Häufigkeit von Sortierläufen sehr stark auswirken kann.

Komplexitätsberechnungen sind oft nichttrivial.

Bei Algorithmen mit im Normalfall hervorragendem Zeitverhalten kann das Verhalten im ungünstigsten Fall (worst case) katastrophal sein.

Welche dramatischen Effekte die Verbesserung der Komplexitätsordnung eines Sortierverfahrens haben kann, zeigt das Beispiel einer 1987 in der damaligen Bundesrepublik Deutschland durchgeführten Volkszählung.

Mit ca. n = 60.000.000 Datensätzen

Bei einem angenommenen Zeitbedarf von nur einer Mikrosekunde pro Schlüsselvergleich würde ein Sortierlauf unter Verwendung des Bubblesort mit einer Komplexität von der Ordnung O(n²) ca. 114 Jahre dauern

Bei Verwendung von Quicksort mit einer Komplexität von O(n log₁₀ n) ergibt sich dagegen eine Sortierzeit von nur 26 Minuten!

Ein wichtiges Merkmal von Sortierverfahren ist die Stabilität.

Ein Verfahren heißt stabil, wenn es die relative Reihenfolge gleicher Schlüssel in der Datei beibehält.

Abbildung 15-1. Stabilität von Sortierverfahren: Nehmen wir eine Liste mit Daten zu Personen an, die alphabetisch nach den Namen sortiert ist. Wird diese Liste nun nach dem Alter der Personen sortiert, so werden bei Anwendung eines stabilen Verfahrens Personeneinträge mit dem gleichen Alter auch weiterhin alphabetisch geordnet sein.

Sortierbare Aggregationen (Datenstrukturen/Objekte):

Arrays (Tabellen)

Listen

Bäume

(Graphen)

Zwei Speicherklassen werden unterschieden:

In-place Verfahren

Die Sortierung findet innerhalb und mit dem zu sortierenden Objekt statt. Es wird keine neue Datenstruktur erzeugt, die bestehende wird nur modifiziert. Auch alle Zwischenschritte werden mit dem Objekt direkt verarbeitet.

Out-of-place Verfahren

Die Sortierung findet außerhalb des zu sortierenden Objekts statt, auch alle Zwischenschritte werden in eignen Datenstrukturen ausgeführt.

Gemäß den Speicherklassen kann man direkte und indirekte Sortierverfahren unterscheiden.

Drei einfache, direkte Sortierverfahren, die ein gegebenes Feld a[i] von Objekten am Platz ordnen:

Sortieren durch Einfügen (Insertion)

Sortieren durch Auswählen (Selection)

Sortieren durch Austauschen (Swap).

Die Umstellung der Elemente geschieht dabei auf dem Eingabe-Array, das dann bei der Ausgabe die geordneten Daten enthält.

Die wesentlichen elementaren Operation beim Sortieren sind:

Vergleichen (Compare) von Daten;

Umstellen (Move) von Daten.

Sortieren durch Einfügen

Man geht von einem Array a mit n Komponenten und Indizierung von 0 bis n − 1 aus. Nun wird a in zwei Intervalle aufgeteilt, die Zielsequenz a[0] bis a[i − 1] und die Quellensequenz a[i] bis a[n − 1]. Beginnend mit i = 1 wird bei jedem Schritt das Element a[i] aus der Quellensequenz entfernt und an der durch die Ordnungsrelation gegebenen Stelle in die Zielsequenz eingefügt.

Abbildung 15-2. InsertionSort am Beispiel

function insertionSort(array) {
  for (i = 1; i < length(array); i++) {
    j = i;
    m = array[i];                                  m = array[i].key;
    // für alle Elemente links vom Marker-Feld
    while (j > 0 && array[j − 1] > m) {            .. array[j-i].key...
      // verschiebe alle größeren Elemente nach hinten
      array[j] = array[j − 1];
      j−− ;
    }
    // setze m auf das freie Feld
    array[j] = m;
  }
}

Algorithmus 15-1. Sortieren durch Einfügen bzw. Verschieben mit einem Array. Die Arrayelemente können auch Datenstrukturen sein und ein Attribute *key* bestimmt die Sortierung.

Komplexität des direkten Einfügens

Zur Berechnung der Komplexität berücksichtigt man,

dass die Anzahl der Schlüsselvergleiche c beim Durchlauf i höchstens cmax(i) = i und mindestens cmin (i) = 1 ist.

Nimmt man an, dass alle Permutationen gleich wahrscheinlich sind, erhält man im Mittel pro Durchlauf cavg(i) = (cmin(i) + cmax(i))/2 = (i + 1)/2 Schlüsselvergleiche.

Die Zahl der Zuweisungen von Elementen m ist für die einzelnen Durchläufe immer c(i) + 2.

image-placeholder
(15-2)

mit C als Gesamtkomplexität für den Vergleich und M für das Verschieben.

Die Komplexität ist also im Mittel sowohl für C(n) als auch für M(n) von der Ordnung O(n²).

Das Zeitverhalten ist am günstigsten, wenn alle Elemente von Anfang an geordnet sind und am ungünstigsten, wenn alle Elemente in umgekehrter Reihenfolge sortiert waren.

Dieses Verhalten wird als natürlich bezeichnet.

Offenbar ist diese Sortierfunktion auch stabil, da die Reihenfolge von Elementen mit übereinstimmenden Schlüsseln nicht geändert wird.

Sortieren durch Selektion

Auch das zweite hier zu betrachtende Verfahren kann dem Sortieren beim Kartenspielen entlehnt werden.

Die Idee ist hierbei, jeweils das größte Element auszuwählen und an das Ende der Folge zu setzen.

Dies wird in jedem Schritt mit einem jeweils um eins verkleinerten Bereich der Folge ausgeführt, so dass sich am Ende der Folge die bereits sortierten Elemente sammeln.

Das Prinzip des Auswählens oder Selektierens des größten Elementes hat diesem Verfahren auch den Namen SelectionSort gegeben.

Abbildung 15-3. SelectionSort am Beispiel

function swap (array,idx1,idx2) {
  t=array[idx1]
  array[idx1]=array[idx2]
  array[idx2]=t
}
function maxIndex(array,idx) {
  maxi=idx
  maxv=array[idx]
  for (var i=0;i<idx;i++) {
    if (array[i]>maxv) {
      maxi=i
      maxv=array[i]
    }
  }
  return maxi
}
function selectionSort(array) {
  p=length(array)-1
  while(p) {
    g = maxIndex(array,p)
    swap (array,p,g)
    p--
  }
}

Algorithmus 15-2. Sortieren durch Selektion, auch hier ein in-place Verfahren. Die wichtigsten Schritte sind Suche und Vertauschung (swap)

Sortieren durch Vertauschen

Eines der bekanntesten, wenn auch kein besonders effizientes Sortierverfahren ist BubbleSort.

Der Name ist aus der Vorstellung abgeleitet, dass sich bei einer vertikalen Anordnung der Elemente der Folge verschieden große, aufsteigende Blasen (»Bubbles«) wie in einer Flüssigkeit von allein sortieren, da die größeren Blasen die kleineren »überholen«.

Das Grundprinzip besteht demzufolge darin, die Folge immer wieder zu durchlaufen und dabei benachbarte Elemente, die nicht der gewünschten Sortierreihenfolge entsprechen, zu vertauschen.

Elemente, die größer als ihre Nachfolger sind, überholen diese daher und steigen zum Ende der Folge hin auf.

function BubbleSort (array)
  // Eingabe: zu sortierende Folge F der Länge n
  do {
    swaps=0
    for (i=0;i<n;i++) {
      if (array[i]> array[i + 1]) {
        swap(array,i,i+1)
        swaps++
      }
    }
  } while (swaps==0)
}

Algorithmus 15-3. Nachbarschaftsvergleich und Vertauschung

Abbildung 15-4. Bubblesort im Beipiel, Gezeigt sind nur Schritte wo eine Vertauschung stattfindet.

Der Algorithmus weist schon eine Verbesserung gegenüber der ursprünglichen Idee auf, indem die Folge nicht n · n-mal durchlaufen wird, sondern der Abbruch bereits dann erfolgt, wenn keine Vertauschung mehr stattgefunden hat.

Eine weitere Optimierung ist dass in jedem Durchlauf das jeweils größte Element an das Ende bewegt wird. Daher genügt es, im zweiten Durchlauf nur den Bereich 1 … n − 2, im dritten Durchlauf den Bereich 1 … n − 3 usw. zu betrachten.

Schließlich kann auch noch »Lokalität« von Feldzugriffen speziell bei großen Folgen ausgenutzt werden, indem der Durchlauf abwechselnd auf- bzw. abwärts erfolgt.

So kann die Effizienz der Sortierung dadurch verbessert werden, dass Teile der Folge noch im CPU-Cache – einem schnellen Zwischenspeicher des Prozessors – vorhanden sind, wenn ein neuer Durchlauf gestartet wird.

Nicht nur die Rechenkomplexitätsklasse ist relevant, auch die Implementierung im Detail, die signifikanten Einfluss auf die Rechenzeit haben kann.

Vergleich Sortierenverfahren

Sortieren durch Mischen

MergeSort: Die bisher vorgestellten Verfahren erfordern einen direkten Zugriff auf einzelne Elemente der Folge und sind daher nur für internes Sortieren geeignet. Sollen dagegen Dateien sortiert werden, die nicht in den Hauptspeicher passen, müssen andere Verfahren zum Einsatz kommen. Eine Möglichkeit ist hier, das Sortieren in zwei Schritten oder Phasen auszuführen:

Die Folge wird in Teile zerlegt, die jeweils in den Hauptspeicher passen und daher getrennt voneinander mit internen Verfahren sortiert werden können. Diese sortierten Teilfolgen werden wieder in Dateien ausgelagert.

Anschließend werden die Teilfolgen parallel eingelesen und gemischt, indem jeweils das kleinste Element aller Teilfolgen gelesen und in die neue Folge (d.h. wieder in eine Datei) geschrieben wird.

Dieses MergeSort-Verfahren lässt sich aber auch für das interne Sortieren anwenden. Hierbei wird zunächst die zu sortierende Folge in zwei Teilfolgen zerlegt, diese werden durch rekursive Anwendung von MergeSort sortiert und anschließend gemischt.

Es stellt sich jedoch die Frage, wie man dabei zu sortierten Teilfolgen kommt.

Dies wird dadurch erreicht, dass MergeSort so lange rekursiv angewendet wird, bis die zu sortierenden Teilfolgen nur noch aus einem Element bestehen.

In diesem Fall liefert das Mischen ja eine neue, sortierte Folge.

Das eigentliche Sortieren kann rekursiv realisiert werden.

Der Algorithmus ist aufgeteilt in:

Mischen von zwei Folgen mit Auswahl Merge (Conquer)

Sortieren durch Mischen MergeSort (Divide), obwohl hier nur das Teilen stattfindet.

Abbildung 15-5. Aufteilen, Verarbeiten, und Zusammenführung

function MergeSort (array) {
  // Eingabe: eine zu sortierende Folge F
  // Ausgabe: eine sortierte Folge FS
  n = length(array)
  if (n==1) // einelementig then
    return array
  else {
   // Teile F in F1 und F2;
   splitIndex = n/2
   F1 = slice(array,0,splitIndex-1)
   F2 = slice(array,splitIndex,n-1)
   F1 = MergeSort (F1)
   F2 = MergeSort (F2)
   // Mische und füge zusammen
   return Merge (F1, F2)
  }
}

Algorithmus 15-4. Grundgerüst des Sortieren durch Mischen

Der Vorgang des Mischens erfordert in der Regel doppelten Speicherplatz, da ja eine neue Folge aus den beiden sortierten Folgen erzeugt wird. Eine Alternative ist das Mischen in einem Feld, allerdings ist hier ein aufwendigeres Verschieben notwendig.

Die Aufteilung in die zwei Abschnitte »Split« und »Merge« entsteht nur durch die Rekursion im Algorithmus, indem zu Beginn jeweils das Zerlegen erfolgt und erst als letzter Schritt das eigentliche Mischen.

function Merge (F1, F2) {
  // Eingabe: zwei zu sortierende Folgen F1, F2
  // Ausgabe: eine sortierte Folge F
  var F = vector(length(F1)+length(F2))
  var i=0,j=0,k=0
  while (i<length(F1) && j<length(F2)) {
    // Entferne das kleinere der Anfangselemente aus F1 bzw. F2;
    if (F1[i]<F2[j]) {
      x=F1[i]
      i++;
    } else {
      x=F2[j]
      j++;
    }
    // Füge dieses Element an F an
    F[k]=x
    k++
  }
  // Füge die verbliebene nichtleere Folge F1 oder F2 an F an;
  for(;i<length(F1);i++,k++) F[k]=F1[i]
  for(;j<length(F2);j++,k++) F[k]=F2[j]
  return F
}

Algorithmus 15-5. Mischen von zwei Folgen

QuickSort

Das wohl am häufigsten angewandte Sortierverfahren ist QuickSort, das wie MergeSort auf dem Prinzip »Teile und herrsche« basiert: Eine Folge wird in zwei Teile zerlegt, die unabhängig voneinander sortiert werden. Im Gegensatz zu MergeSort wird jedoch bei QuickSort der Mischvorgang vermieden. Dadurch benötigt dieses Verfahren weniger Ressourcen.

Die Grundidee von QuickSort ist die Zerlegung der Folge in zwei Teile, wobei alle Elemente der einen Teilfolge kleiner als ein Referenzelement (das sogenannte Pivot-Element) und alle Elemente der anderen Teilfolge größer als das Referenzelement sind.

Das Pivot-Element kann beliebig gewählt werden. Typischerweise wird das mittlere Element der Folge verwendet, es kann aber auch das erste oder das letzte Element genutzt werden.

Abbildung 15-6. Die Rolle des Pivot-Elementes: Alle Elemente links von 6 sind kleiner oder gleich 6, alle Elemente rechts davon größer.

Die beiden Teilfolgen werden durch den rekursiven Aufruf sortiert.

Das Verfahren bricht für eine Teilfolge ab, wenn diese die Länge 0 hat.

Da das Pivot-Element gegebenenfalls verschoben werden muss – beispielsweise wenn es das kleinste oder größte Element der Folge darstellt – ist die beim Zerlegen bestimmte und eventuell neue Position pn des Pivot-Elementes zu berücksichtigen

function QuickSort (F, u, o) {
  // Eingabe: eine zu sortierende Folge F,
  // die untere und obere Grenze u, o
  if (o > u) {
    // Bestimme Position p des Pivot-Elementes;
    pn = splitPivot(F, u, o, p);
    QuickSort (F, u, pn − 1);
    QuickSort (F, pn + 1, o)
  }
}

Algorithmus 15-6. QuickSort

Der entscheidende Schritt ist demnach das Zerlegen der Folge.

function splitPivot (F, u, o, p) {
  // Eingabe: zu zerlegende Folge F, untere und obere Grenze u, o,
  // Position p des Pivot-Elementes
  // Ausgabe: neue Position pn des Pivot-Elementes
  pn = u
  pv = F[p]
  swap(F, p, o) // Pivot-Element nach rechts
  for (i = u; i<=(o − 1); i++) {
    if (F[i] <= pv) {
      swap(F,pn,i)
      pn++
    }
  }
  swap(F, o, pn) // Pivot-Element zurück
  return pn
}

Algorithmus 15-7. Split

Abbildung 15-7. QuickSort am Beispiel

Für die gegebene Folge wird zunächst das mittlere Element (hier 5) als Pivot-Element gewählt und mit dem am Ende stehenden Element getauscht. Danach wird die Folge so umgeordnet, dass sich »links« vom Pivot-Element die Elemente 2, 1, 3 befinden, wobei die neue (und in diesem Fall gleichzeitig auch die alte) Position des Pivot-Elementes 4 ist. Nach dieser Zerlegung wird das Pivot-Element an diese Stelle zurückgetauscht und es ergibt sich der in Ebene 0 dargestellte Aufbau der Folge (2, 1, 3, 5, 9, 7, 8).

Im nächsten Schritt werden die beiden entstandenen Partitionen weiter sortiert. Im linken Teil wird das Element 1 als Pivot-Element bestimmt, im rechten Teil das Element 7.

Daraus resultiert die für Ebene 1 angegebene Zerlegung, wobei die Pivot-Elemente in beiden Fällen verschoben werden.

Anschließend ergibt die Zerlegung der linken Partition, dass nur noch die Folge (3, 2) sortiert werden muss:

Hier wird 3 als Pivot-Element bestimmt und nach den Vertauschungen liegt die Reihenfolge (2, 3) vor. Nachdem die letzte Partition (2) nur noch aus einem Element besteht, ist die Sortierung für diesen Zweig beendet.

Im rechten Teil wird noch einmal für die Folge (8, 9) das Pivot-Element bestimmt und nach der Zerlegung ist auch dieser Zweig fertig sortiert.

Die tatsächliche Sortierung erfolgt jedoch nicht so symmetrisch. Vielmehr wird aufgrund der Rekursion zuerst der linke Zweig des Baumes bis zur Folge (2, 3) verfolgt und erst danach wird die rechte Partition nach dem gleichen Prinzip verarbeitet.

Bäume

Übergang von linearen Listen auf Baumstrukturen; Skip-Listen als "Vermittler"

Vor- und Nachteile

Algorithmen

Anwendungen

Motivation

Die bisher betrachteten Datenstrukturen waren im Wesentlichen eindimensional oder linear: sie weisen mit der Vorgänger-Nachfolger-Relation nur eine Form von Beziehungen zwischen den einzelnen Elementen auf.

Das hat Auswirkungen auf die Algorithmik und deren Komplexitätsklassen, vor allem die Suche mit O(N).

In diesem Kapitel wollen wir mit den Bäumen eine Klasse von Datenstrukturen kennen lernen, die eine zweite Dimension einbeziehen und dadurch auch die Darstellung von hierarchischen Strukturen ermöglichen.

Baumstrukturen sind nicht nur in der Informatik von fundamentaler Bedeutung, etwa zur Organisation von Daten, sondern sind auch im Alltag in vielfältiger Form wiederzufinden.

Taxonomie

Allgemeines Beispiel

Formales Modell

Bäume sind hierarchische Strukturierungshilfsmittel oder rin Organisationsprinzip für Daten, Klassen, Fakten.

Ein typisches Beispiel ist etwa der Stammbaum einer Familie, der die Vererbungsbeziehungen darstellt, oder die Systematik in der Biologie

Allgemein können wir unter einem Baum eine Menge von Knoten ℕ (Nodes) und Kanten 𝔼 (Edges) verstehen, die besondere Eigenschaften aufweisen:

So besitzt jeder Baum genau einen ausgezeichneten Knoten, der als Wurzel bezeichnet wird.

Weiterhin ist jeder Knoten außer der Wurzel durch genau eine Kante mit seinem Vorgängerknoten verbunden.

Jeder Knoten na kann 0..k Nachfolgerknoten u besitzen die durch Kanten ka,u verbunden sind.

Die Kanten sind (zunächst noch) gerichtet ("von oben nach unten")

Ein Knoten oder der Baum haben eine Ordnung d: Die maximale Anzahl von Kanten pro Knoten.

Abbildung 16-1. Nicht jede Struktur ist ein Baum (aber ein Graph) [https://ac.informatik.uni-freiburg.de/lak_teaching/ss_06/info2/Slides/18_Baeume_Grundlagen_Natuerliche_Suchbaeume.pdf]

Ein Knoten ohne Nachfolger kann als Blatt(knoten) bezeichnet werden.

Ein Pfad in einem Baum ist eine Folge von unterschiedlichen Knoten, in der die aufeinander folgenden Knoten durch Kanten miteinander verbunden sind.

Mithilfe des Pfades lässt sich auch die grundlegende Eigenschaft eines Baumes definieren: Zwischen jedem Knoten und der Wurzel gibt es genau einen Pfad. Dies bedeutet, dass:

ein Baum zusammenhängend ist und

es keine Zyklen gibt.

Weitere Eigenschaften (Parameter) von Bäumen: Höhe und Niveau.

Unter dem Niveau eines Knotens versteht man die Länge des Pfades von der Wurzel zu diesem Knoten. Die Höhe eines Baumes entspricht dem größtem Niveau eines Blattes plus 1.

Es muss im Gegensatz zu lineare Listen Entscheidungsfunktionen f geben, die einen Übergang von Knoten na auf einen Nachfolgerknoten nb berechenn.

Anders ausgedrückt: Jeder Knoten muss mit Daten verknüpft sein die entscheiden welche Kante als nächstes ausgewählt wird.

Ein Knoten kann mit einer Variable xi verknüpft sein, eine Kante (a,b) die zwei Knoten na mit nb verbindet mit eine Aktivierungsfunktion f(xi)a,b: na → nb

Beispiel: Jeder Knoten ist mit dem Alter eines Menschen verknüpft, und die Kanten bestimmen Altersanschnitte.

Ein Stammbaum hat keine Kantenfunktionen!!!

Ein Baum ist neben einer Beziehungsrelation (Stammbaum) eine Suchmaschine.

Die Knoten können mit den Ergebnisdaten verknüpft sein, müssen aber nicht.

Es kann Blätter mit den Ergebnisdaten geben (Blattsuchbaum), oder auch nicht.

Höhe und Niveau von Bäumen

Bottom-up Berechnungsbaum

Die Richtung von Bäumen muss nicht immer top-down sein. Ein Berechungsbaum für arithmetische Ausdrücke fängt bei den Blättern an und liefert ein Ergebnis im Wurzelknoten (Bottom-up).

Ist mit jedem Knoten ein Datensatz verbunden D und ein Schlüssel k verbunden, so spricht man von einem Suchbaum.

Die Kanten bestimmen Bereiche (Intervalle) von Schlüsseln [k₁,k₂]

Jeder Baum kann in Teilbäume zerlegt werden. Der atomare Baum besteht aus einem Knoten. Bäume sind rekursive Datenstrukturen. Unterbäume sind auch Bäume.

Hat man einen Bereichsbaum so sind die Datensätze nach ihrem Schlüssel sortiert, aber nicht mehr linear, sondern in Teilbäumen. Jeder Knoten ist mit einem Intervall [k₁,k₂] verknüpft.

In Such- und Bereichsbäumen werden die Kanten mit einer Relation zum aktuellen Knotenschlüssel ki ausgewählt. Z.B.

Linke Kante wenn k<l, Rechte Kante wenn k>l ⇒ Binärbaum

Abbildung 16-2. Suche nach Schlüssel *s* endet beim Suchbaum in Knoten *k* mit *k*.key == *s* oder in Blatt, dessen Intervall *s* enthält.

Zusammenfassung:

Baumstrukturen dienen im Wesentlichen zur hierarchischen Repräsentation und Organisation von Daten. Eine der wichtigsten Einsatzgebiete von Bäumen ist jedoch die Unterstützung einer effizienten Suche. Hierfür werden in den einzelnen Knoten eines Baumes neben den eigentlichen Nutzdaten (bzw. einen Verweis darauf) zusätzlich noch Schlüsselwerte gespeichert, über die die Suche erfolgt.

Abstrakter Datentyp Binärer Baum

Da der ADT Tree parametrisierbar bezüglich des Typs der Elemente sein soll, wird in der folgenden Spezifikation wieder ein Sortenparameter T verwendet.

Die entscheidende Funktion ist bin, die einen binären Baum aus einem linken und einem rechten Teilbaum sowie einem Element des Datentyps T konstruiert.

Für einen gegebenen Baum liefern daher left und right den linken bzw. rechten Teilbaum, während value das Wurzelelement dieses Baumes ermittelt.

Für einen aus den Teilbäumen x und y sowie dem Element b konstruierten Baum bin(x,b,y) liefert left demnach den Teilbaum x, right den Teilbaum y und value das Element b. Die beiden weiteren Funktionen empty und is_empty werden zur Konstruktion eines leeren Baumes bzw. zum Test auf einen leeren Baum benötigt.

 1: type Tree(T)
 2: import Bool
 3: operators
 4:   empty : → Tree
 5:   bin : Tree × T × Tree → Tree
 6:   left : Tree → Tree
 7:   right : Tree → Tree
 8:   value : Tree → T
 9:   isempty : Tree → Bool
10: axioms ∀x,y: Tree, ∀b: T
11:   left (bin (x, b, y)) = x
12:   right (bin (x, b, y)) = y
13:   value (bin (x, b, y)) = b
14:   isempty (empty) = true
15:   isempty (bin (x, b, y)) = false

Definition 16-1. ADT Tree(T) mit Operatoren und Axiomen die das Verhalten der Operationen definieren

Datenstrukturen

Suchbaum

Knoten sind mit Daten und Schlüssel verknüpft

typeof root = node
typeof node = {
  left  : node,
  right : node,
  data  : data,
  key  : number
}

Blattsuchbaum

Knoten sind nur mit Schlüsseln verknüpft, d.h. innere Knoten sind Wegweiser, die Daten sind nur in den Blättern

typeof root = node
typeof node = {       leaf = {
  left  : node|leaf,    key  : number,
  right : node|leaf,    data : data
  key   : number      }
}

Algorithmen

Es gibt wieder den bisher bekannten Satz an Basisoperationen die auf Bäume angewendet werden:

search(k)

Suche nach einem Datensatz mit dem Schlüssel k

insert(node | ⟨data,k⟩)

Einfügen eines neues Datensatzes mit dem Schlüssel k oder eine bereits erstellten Knotens.

remove(node|data|k)

Entfernen eines eines Knotens mit dem Schlüssel k, Suche nach dem Datensatz, Schlüssel, oder Knoten.

Suche (Binärbaum)

function Node(data,k) { return { left:null,right:null,data:data,key:k }}
function search (node,k) {
  if (node.key==k) return node
  if (node.left && node.left.key<k) return search(node.left,k)
  if (node.right && node.right.key<k) return search(node.right,k)
  error(NOTFOUND)
}
search(root,100)

Algorithmus 16-1. Suche in einem Bereichsbaum nach dem Schlüüsel *k*

Suche (k-stelliger Baum)

Hier gibt es mehr als zwei Nachfolger. Jeder Nachfolgeknoten ist ein Teilbaum mit einem Intervallbereich [k₁,k₂]. Dieses Intervall wird in einem Knoten als lowerBound und upperBound in keyRange gespeichert.

function node(data,k) { return { children:[],data:data,key:k,keyRange:[k,k] }}
function search (node,k) {
  if (node.key==k) return node
  for(i=0;i<length(node.children);i++) {
    if (node
i
0
>=k && node
i
1
<=k)
      return search(node
i
,k)
  }
  error(NOTFOUND)
}

Algorithmus 16-2. Suche in einem Bereichsbaum nach dem Schlüüsel *k*

Strategien zur Traversierung

Es gibt verschiedene Strategien zur Traversierung (für Suche, Einfügen, Löschen von Knoten) eines Baums.

Abbildung 16-3. Ein Beispielsbaum mit den Knoten A,B,C,D,E,F und G

Inorder-Durchlauf

Hier wird zuerst rekursiv der linke Teilbaum besucht, dann der Knoten selbst und anschließend der rechte Teilbaum. Für den binären Baum aus der Abbildung entspricht das der Reihenfolge:

Inorder-Durchlauf

D → B → E → A → F → C → G

Ein Beispiel für die Anwendung dieser Strategie ist das Auslesen eines Baumes für einen arithmetischen Ausdruck in Infixschreibweise.

Der Algorithmus für einen Inorder-Durchlauf lässt sich am einfachsten rekursiv formulieren. Der gesamte Baum wird nach der Inorder-Strategie durchlaufen, wenn der Algorithmus mit der Wurzel des Baumes als Parameter aufgerufen wird.

function Inorder (k) {
  // Eingabe: Knoten k eines binären Baumes mit Verweis auf
  // linken (k.left) und rechten (k.right) Teilbaum sowie
  // dem Element k seleber (Daten data und Schlüssel k)

  Inorder (k.left)  /* besuche linken Teilbaum */
  Process (k.data,k.key)  /* Verarbeite aktuellen Knoten */
  Inorder (k.right) /* besuche rechten Teilbaum */
}

Algorithmus 16-3. Inorder-Traversierung

Preorder-Durchlauf

Bei dieser Strategie wird zuerst der Knoten selbst besucht und erst danach erfolgt das Traversieren des linken bzw. rechten Teilbaumes. Für den Beispielbaum liefert das die Reihenfolge:

A → B → D → E → C → F → G

Neben der Ausgabe eines arithmetischen Ausdrucks in Präfixschreibweise ist die Erzeugung einer eingerückten Baumdarstellung für ein Dateisystem ein typisches Anwendungsbeispiel. Hier wird zuerst der Name des Verzeichnisses ausgegeben und darunter eingerückt eine Liste der darin enthaltenen Dateien und Verzeichnisse.

Der Algorithmus für den Preorder-Durchlauf kann wiederum rekursiv formuliert werden

Preorder-Durchlauf

function Preorder (k) {
  // Eingabe: Knoten k eines binären Baumes mit Verweis auf
  // linken (k.left) und rechten (k.right) Teilbaum sowie
  // dem Element k seleber (Daten data und Schlüssel k)

  Process  (k.data,k.key)  /* Verarbeite aktuellen Knoten */
  Preorder (k.left)  /* besuche linken Teilbaum */
  Preorder (k.right) /* besuche rechten Teilbaum */
}

Algorithmus 16-4. Preorder-Traversierung

Postorder-Durchlauf

Beim Postorder-Durchlauf werden erst beide Teilbäume durchlaufen, bevor der Knoten selbst besucht wird. Dies führt in unserem Beispiel zur Reihenfolge

D → E → B → F → G → C → A

Ein Beispiel für die Anwendung dieser Strategie ist die Erstellung einer Stückliste mit Aufsummierung, etwa beim UNIX-Kommando du (disk usage), das den Platzbedarf eines Verzeichnisses und aller Unterverzeichnisse im Dateisystem ermittelt. Hierbei werden zuerst die Größen der Einträge in den Blättern (d.h. der Dateien) bestimmt und für den direkten Vaterknoten (d.h. das enthaltende Verzeichnis) addiert. Der Platzbedarf dieser Verzeichnisse wird wiederum zum Platzbedarf des übergeordneten Verzeichnisses zusammengefasst usw., bis die Gesamtgröße der Wurzel bestimmt werden kann.

Wie bereits bei den anderen beiden Strategien wird der Algorithmus zum Postorder-Durchlauf am einfachsten rekursiv formuliert

Postorder-Durchlauf

function Postorder (k) {
  // Eingabe: Knoten k eines binären Baumes mit Verweis auf
  // linken (k.left) und rechten (k.right) Teilbaum sowie
  // dem Element k seleber (Daten data und Schlüssel k)

  Postorder (k.left)  /* besuche linken Teilbaum */
  Postorder (k.right) /* besuche rechten Teilbaum */
  Process   (k.data,k.key)  /* Verarbeite aktuellen Knoten */
}

Algorithmus 16-5. Postorder-Traversierung

Levelorder-Durchlauf

Während bei den ersten drei Strategien der Baum zuerst in der Tiefe durchwandert wird, entspricht der Levelorder-Durchlauf einer Breitensuche, d.h., auf jedem Niveau des Baumes werden erst alle Knoten besucht, bevor auf das nächste Niveau gewechselt wird. Danach ergibt sich die Reihenfolge:

A → B → C → D → E → F → G

Der Algorithmus zum Levelorder-Durchlauf ist im Gegensatz zu den bisher betrachteten Strategien nicht rekursiv. Stattdessen wird eine Warteschlange verwendet, in der die noch zu verarbeitenden Knoten abgelegt werden. Der Baum wird durchlaufen, indem der nächste zu besuchende Knoten aus der Warteschlange entnommen wird. Nach dem Besuch dieses Knotens werden die Kinder am Ende der Warteschlange eingetragen, bevor mit dem nächsten Knoten fortgefahren wird.

Die Levelorder-Strategie wird iterativ implementiert.

Levelorder-Durchlauf

function Levelorder (k) {
  // Eingabe: Knoten k eines binären Baumes

  q = [] // leere Warteschlange;
  addTail (q, k) /* Wurzel in die Warteschlange aufnehmen */
  while (length(q)!=0) {
    n = removeHead(q);
    Process (n.data, n.key)
    addTail(q, n.left)  /* linken Knoten eintragen */
    addTail(q, n.right) /* rechten Knoten eintragen */
  }
}

Algorithmus 16-6. Levelorder-Traversierung

Wenn der Baum nicht geordnet oder die Knoten nicht mit Schlüssel assoziert sind (generischer Baum) müssen alle Teilbäume und Pfade durchsucht werden.

Das klinkt sinnlos, da das Suchen scheinbar wieder einer lineare Liste entspricht.

Aber bei Parallelisierung der Suche in Teilbäume (Divide-and-Conquer Methode) könnte dennoch eine geringere Suchzeit notwendig sein!

function parSearch(node,k) {
  if (node.key==k) terminateSearchWith(node)
  startProcess(parSearch,node.left,k)
  startProcess(parSearch,node.right,k)
}
parSearch(root,k)

Algorithmus 16-7. Parallele Suche. Es werden bis zu *N*-1-*L* Prozesse gestartet, bei *N* Knoten und *L* Endknoten ohne Nachfolger.

Bäume sind daher selber Organisationsstrukturen für Algorithmen die einen Programmablauf steuern können!

Z\.B. auch Suche im Internet (Suchmaschine!)

Verteilung von Berechnungen auf Rechner mittels hierarchischer Teilung

Baumstrukturen stellen verteilte Kommunikationsnetze dar (Verbindung von Rechnern), die Kanten sind Kommunikationskanäle.

In Betriebssystemen (UNIX) können Prozesse weietere Prozesse starten. Die neuen Prozesse werden Kindprozesse des Elternprozesses ⇒ Baumstruktur!

Dateisysteme sind Baumstrukturen

Höhe eines symmetrischen ideal besetzten Binärbaums: H=O(log N).

Die Baum-Struktur hängt von Einfügereihenfolge in anfangs leeren Baum ab

Höhe kann linear zunehmen, sie kann aber auch in O(log N) sein, genau ⎡log2 (N+1)⎤.

Abbildung 16-4. Einfügen eines neues Elements (Schlüssel *k*=5) in einen bestehenden Baum verändert die Höhe des Baums und dessen Symmetrie

Einfügen

Das Einfügen in einem geordneten Baum hängt von seiner Stelligkeit (Ordnung) ab.

Bei Binärbäumen sind häufig schon alle Kanten belegt, und der neue Knoten muss am Ende eingefügt werden

Bei k-stelligen Bäumen könnten noch freie Kanten für das Einhängen des neuen Knoten vorhanden sein, sofern die Ordnungsrelation noch gegeben ist (hie rnicht trival zu bestimmen).

Einfügen (Binärbaum)

Gegeben ist ein neuer Datensatz D mit dem Schlüssel k

Es muss zuerst die korrekte Einfügeposition gefunden werden, so dass die Ordnung der Elemente nicht verletzt wird.

Diese Position muss ein Knoten sein, dessen Schlüsselwert größer als der des einzufügenden Elementes ist und der noch keinen linken Nachfolger hat oder einen Knoten mit einem kleineren Schlüsselwert und einen freien Platz für den rechten Nachfolger. Dabei sind im Prinzip zwei Fälle zu unterscheiden:

Der Baum ist leer, d.h., der einzufügende Knoten wird die neue Wurzel.

Es gibt bereits Knoten im Baum. In diesem Fall ist der Knoten zu identifizieren, der Elternknoten des neuen Elementes werden soll.

function Node(data,k) { return { left:null,right:null,data:data,key:k }}
function insert(node,data,k) {
  if (node.key==k) error(Error);
  if (k>node.key) {
    if (!node.right) node.right=Node(data,k)
    else insert(node.right,data,k)
  } else {
    if (!node.left) node.left=Node(data,k)
    else insert(node.left,data,k)
  }
}
if (!root) root=Node(data,k)
else insert(root,data,k)

Algorithmus 16-8. Einfügen eines neuen Datensatzs in einen Binärbaum

Hier wird die Preorder Traversierung angewendet.

Abbildung 16-5. Beispiel des Einfügens eines neuen Knotens mit dem Schlüssel k=4

Entfernen eines Knotens

Die komplizierteste Operation im binären Suchbaum ist das Löschen. Dies liegt daran, dass beim Entfernen eines inneren Knotens einer der beiden Teilbäume des Knotens »hochgezogen« und gegebenenfalls umgeordnet werden muss.

Grundsätzlich müssen beim Löschen eines Knotens k drei Fälle berücksichtigt werden:

Der Knoten k ist ein Blatt. Dieser Fall ist der einfachste, da hier nur der Elternknoten zu bestimmen ist und dessen Verweis auf Knoten k entfernt werden muss.

Der Knoten k besitzt nur ein Kindknoten. In diesem Fall ist der Verweis vom Elternknoten auf den Kindknoten von k umzulenken.

Der Knoten k ist ein innerer Knoten mit zwei Kindknoten. Hierbei muss der Knoten durch den am weitesten links stehenden Knoten des rechten Teilbaumes ersetzt werden, da dieser in der Sortierreihenfolge der nächste Knoten ist. Alternativ kann auch der am weitestens rechts stehende Knoten des linken Teilbaumes verwendet werden.

Für das Ersetzen eines Knotens gibt es wiederum zwei Varianten:

Entweder werden die Daten der Knoten ausgetauscht oder

es werden nur die Verweise auf die Knoten aktualisiert.

Die erste Variante ist einfacher zu implementieren, die zweite Methode vermeidet ein unter Umständen aufwendiges Kopieren.

function removeNode(root,k) {
  // Eingabe: Wurzel vom Suchbaum T, Schlüssel k des zu löschenden Elementes
  node = searchNode (root, k)
  if (node = null) error(Error)
  parent = searchParent (root, node) // Arrg, sollte mit Search kombiniert werden
  /* 1. Fall */
  if (!node.left && !node.right) { // node ist Blattknoten
    if (parent.left===node) // node ist linkes Kind
      parent.left = null
    else
      parent.right = null
  /* 2. Fall */
  } else if (!node.left)  {
    if (parent.left===node)  // node ist linkes Kind
      parent.left = node.right
    else
      parent.right = node.right
  } else if (!node.right) {
    if (parent.left===node) // node ist linkes Kind
      parent.left  = node.left
    else
      parent.right = node.left
  } else /* 3. Fall */
    child = minElement (node.right)
    replaceNode(node,child) // Ersetze node durch child
  }

Algorithmus 16-9. Entfernen eines Knotens mit dem Schlüssel k

function minElement(node) {
  if (!node.left && !node.right) return node;
  if (node.left) return minElement(node.left)
  else           return node
}

Algorithmus 16-10. Minimales Element eines Teilbaums

Abbildung 16-6. Löschen im binären Suchbaum [asdp]

Komplexität

.. it depends.

Die (erfolglose) Suchzeit als Anzahl der Knoteniterationen ist bei einem ausgeglichenen und symmetrischen Binärbaum einfach gleich der Höhe, und diese ist O(log N) bei N Knoten.

Der Extremfall eines Baums (nicht ausgegelichen und asymmetrisch) ist die lineare Liste (jeder Baum kann in einer lineare Liste transformiert werden). Dann ist die Suchzeit wieder O(N)

In der Realität hat man etwas dazwischen liegendes

Die noch einzuführenden Operationen zum EInfügen und Entfernen von Knoten benötigen i.A. auch eine Suche. Für diese giltg die gleiche Komplexitäsklasse.

Beispiele

Abstrakter Syntaxbaum (AST)

... oder nur Syntaxbaum

Worum geht es? Um Compiler und Syntaxanalyse von Programmen die in einer bestimmten Programmiersrpache geschrieben wurden.

Ein Compiler ist typischweise aus folgenden Komponenten im Schichtenmodell aufgebaut:

Analysephase:

Ein Lexer, der einen Textzeichenstrom in eine lineare Liste von Tokens (Symbolen) und Werten transformiert.

Ein Parser, der diese lineare Liste aus Token zu einem (Abstrakten) Syntaxbaum wieder zusammensetzt.

Synthesephase:

Vereinfachung des AST (Konstantenfaltung), Kompaktierung

Erzeugung einer Zwischenrepräsentation (IR)

Optimierung

Erzeugung von Zielcode (Maschinencode, VM Bytecode oder andere Programmiersprache; Transpiler)

Abbildung 16-7. Typisches Schichten- und Phasenmodell eines Compielrs

Man kann einen Baum auch als geschachtelte Liste (Array) von Listen verstehen.

Daher kann ein Tokenstrom (TOkenliste) mit bestimmten Regeln wieder in eine Baumstruktur transformiert werden.

Abbildung 16-8. Konkerter versa abstrakten Syntaxbaum

Beispiel: Arithmetische Berechnungen wie (x*n+1)/y

code   = "(x*n+1)/y"
tokens = lexer(code)
tokens := [LPAR,LIT(x),MUL,LIT(n),ADD,NUM(1),RPAR,DIV,LIT(y)]
tree   = parser(tokens)
tree   := [DIV,[ADD,[MUL,VAR(x),VAR(n)],[NUM(1)]]],[VAR(y)]]

Beispiel 16-1. Der Lexer und Parser im Zusammenspiel

Beim Abstrakten Syntaxbaum fehlen alle unwesentlichen, grammatikspezifischen Elemente:

Der Abstrakte Syntaxbaum gibt die logische Struktur des Ausdrucks wieder

Der Syntaxbaum kann einfach (rekursiv) interpretiert werden

Deklarationen von Bezeichnern (Variablen, Typen, Funktionen) erfordern eine Symboltabelle

Der Syntaxbaum kann Reihenfolgen und Bindungen bewahren, im Gegensatz zur linearen Liste

Beispiel 16-2. Strukturen und Bindungen im Syntaxbaum am Beispiel von Ausdrücken. Token werden hierarchisch geordnet, implizite (Bindungs- und Reihenfolge) Regeln werden explizit.

Der Tokenstrom

Der Tokenstrom (oder Liste):

Gruppierung von Textzeichen zu sprachspezifischen Bausteinen

Der Tokenstrom enthält keine Leerzeichen oder Kommentare

Token haben eine Klasse und ggfs. eine "Nutzlast" (Funktionale, Argumente)

Unterschiedliche Schreibweisen sind vereinheitlicht (0x18,1.2,1E-9,100)

Ziele der Abstraktion:

Komplexitätsreduktion (Es gibt immer weniger Token als Textzeichen)

Fokussierung aus Sprachelemente und erste lexikalische Syntaxprüfung

Vereinfachung des Parsers und des Parsens

Beispiel 16-3. Beispiel der Ezeugung eines Tokenstroms

Algorithmen auf AST

Die Suche ist eher sekundär.

Die Transformationen dieses Baumes ist primär und steht im Vordergrund

Ein Beispiel für eine Transformation ist die Konstantenfaltunf, d.h. die Umstellung von Ausdrücken so dass Konstanten zusammengefasst und zur Kompilierungszeit evaluiert werden können.

x = (a+2)-(b+4)
  =  a+2 + (-b) + (-4)
  =  a-b + 2-4
  =  a-b - 2

Beispiel 16-4. Beispiel der Konstantenfaltung

Ziel ist es einfache Elementaroperationen wiederholend auf Teilbäume anzuwenden bis keine weriter Vereinfachung eines Ausdricks möglich ist

Das Problem bei der Konstantenfaltung: Die Konstanten können in verschiedenen Teilbäumen verteilt sein. Ein Transformation der Baumstruktur kann die Konstanten dann in einem Knoten zusammenbringen.

Dazu müssen Auswerte- und Binderegeln beachtet werden.

Eine Möglichkeit ist die Normalisierung von komplimentären Ausdrücken

Subtrkation in Addition transformieren

Division in Multiplikation transformieren

Dann Kommutativgesetz anwenden und Operanden / Knoten vertauschen

Wir werden weitere Transformationen von Bäumen kennen lernen (da vor allem zur Symmetrisierung), wie LR und RL Transformationen.

Beispiel 16-5. Konstantefaltung durch Baumtransformation mit Operationsnormalisierung

Transformation von Bäumen

Wir hatten bereits spezielle Transformationen von Syntaxbäumen kennen gelernt

Jetzt geht es um allgemeine Transformationen

Bei den Komplexitätsbetrachtungen fiel schon auf dass Bäume optimal balanziert sein müssen um O(log(N)) zu erreichen

Abbildung 16-9. »Gute« und »schlechte« Suchbäume

Balanzierung von Bäumen

Ziel ist die Balanzierung von Bäumen um "optimale" Bäume zu erhalten, also balanziert oder ausgeglichen.

Neben vollständig balanzierten Bäumen gibt es schwächere Varianten wie AVL Bäume:

Beim balanzierten Baum ist der Höhenunterschied benachbarter Teilbäume Null

Bei einem AVL (Adelson-Velskij und Landis) Baum ist der Höhenunterschied maximal 1

B-Bäume besitzen eine ausgeglichene Höhe, lassen aber einen unausgeglichenen Verzweigungsgrad zu.

Für die Höhe h eines AVL-Baums mit n Knoten gilt:

image-placeholder
(16-1)

Abbildung 16-10. Verschiedene AVL Bäume im Vergleich zu einem vollständig balanzierten Baum [O\. Bittel, HTWG Konstanz]

Bei Binärbäumen geht die Balanzierung sehr einfach durch Vertauschen von Knoten, wie das bereits bei der Einfügeoperation zu sehen war.

Abbildung 16-11. Vollständiges Ausgleichen eines Baumes nach Einfügen eines neuen Knotens: Kein Knoten bleibt an seinem Platz! Eine teure Operation! [addp]

Rechts-Rotation

Fall A: Baum ist linkslastig, d.h. Höhenunterschied = -2

Unterfall A1: linker Teilbaum hat Höhenunterschied -1 oder 0

Abbildung 16-12. Rechts-Rotation [O\. Bittel, HTWG Konstanz]

function Node(data,k) { return { left:null,right:null,data:data,key:k }}
function rotateRight(p) {
  q = p.left
  A = q.left
  B = q.right
  C = p.right
  pp = parentOf(p)
  q.left  = A
  q.right = q
  p.left  = B
  p.right = C
  if (pp.left === p) pp.left = q
  else               pp.right= q
}

Algorithmus 16-11. Rechts-Rotation mit Elternsuche von Rotationsknoten p

function Node(data,k) { return { left:null,right:null,data:data,key:k }}
function swap(p,q) {
  data=p.data; key=p.key;
  p.data=q.data; p.key=q.key; q.data=data; q.key=key
}
function rotateRight(p) {
  q = p.left
  A = q.left
  B = q.right
  C = p.right
  // tauscht Daten und Key, damit wir keinen Elternknoten benötigen!!!
  // Die parent-p Relation bleibt erhalten
  swap(p,q)
  // p ist nun q, q ist nun p
  p.left  = A
  p.right = q
  q.left  = B
  q.right = C
}

Algorithmus 16-12. Rechts-Rotation: Optimiert ohne Elternsuche vom Rotationsknoten p

Links-Rotation

Fall B: Baum ist rechtslastig, d.h. Höhenunterschied = +2

Unterfall B1: rechter Teilbaum hat Höhenunterschied 0 oder +1:

Abbildung 16-13. Links-Rotation [O\. Bittel, HTWG Konstanz]

function Node(data,k) { return { left:null,right:null,data:data,key:k }}
function rotateLeft(p) {
  q = p.right
  A = p.left
  B = q.left
  C = q.right
  pp = parentOf(p)
  p.left  = A
  p.right = B
  q.left  = p
  q.right = C
  if (pp.left === p) pp.left = q
  else               pp.right= q
}

Algorithmus 16-13. Links-Rotation mit Elternsuche von Rotationsknoten p

Rechts-Links-Rotation

Die Rechts- (genauso analog die Links-) Rotation verändert den Baum, aber ausgeglichen ist er nicht. Dazu wird eine Kombination aus Links- und Rechts-Rotation verwendet.

Fall B: Baum ist rechtslastig, d.h. Höhenunterschied = +2&br; Unterfall B2: rechter Teilbaum hat Höhenunterschied -1

Abbildung 16-14. Rechts-Links-Rotation

function Node(data,k) { return { left:null,right:null,data:data,key:k }}
function rotateLeft(p) {
  pp = parentOf(p)
  q = p.right
  r = q.left
  A = p.left  ; B = r.left
  C = r.right ; D = q.right
  p.left  = A ; p.right = B
  q.left  = C ; q.right = D
  r.left  = p ; r.right = q
  if (pp.left === p) pp.left = r
  else               pp.right= r
}

Algorithmus 16-14. Rechts-Links-Rotation mit Elternsuche von Rotationsknoten p

Analog für die Links-Rechts-Rotation bei linkslastigen Baum (oder Teilbaum)

Rotation

Da der Baum vor dem Einfügen bzw. Löschen balanciert war, haben alle Teilbäume einen Höhenunterschied von -1, 0 oder +1.

Damit können nach einem Einfüge- oder Löschschritt nur die Fälle A1, A2, B1 oder B2 auftreten.

Es lässt sich zeigen, dass beim Einfügen insgesamt maximal eine der 4 Rotationsoperationen notwendig ist.

Beim Löschen müssen i.a. mehrere Rotationsoperationen durchgeführt werden (siehe Beispiel später)

Das Einfügen bedarf bei AVL Bäumen u.U. nur eine Links- oder Rechts-Rotation, bei vollständig balanzierten Bäumen aber i.A. Kombinationen!

Einfügen und Rotation

Abbildung 16-15. Beispiel 1 zu Einfügen in AVL-Bäumen

Abbildung 16-16. Beispiel 2 zu Einfügen in AVL-Bäumen

Balanzierung eines gesamten Baums

Ein iterativer und rekursiver Vorgang!

B-Bäume

AVL-B äume werden annähernd balanziert gehalten.

Eine weitere Variante einer ausgeglichenen Baumstruktur ist der von R. Bayer und E. McCreight entwickelte B-Baum.

Hierbei steht der Name »B« für balanciert, breit, buschig oder auch Bayer, nicht jedoch für binär.

Die Grundidee des B-Baumes ist es gerade, dass der Verzweigungsgrad variiert, während die Baumhöhe vollständig ausgeglichen ist.

Den Ausgangspunkt bildet somit auch wieder ein ausgeglichener Suchbaum, bei dem alle Pfade von der Wurzel zu den Blättern gleich lang sind.

Eine Variation des Verzweigungsgrades bedeutet nun, dass ein Knoten mehrere Elemente enthalten kann – wir sprechen daher von Mehrwegebäumen.

Prinzip des B-Baumes

Wendet man das Kriterium der Ausgeglichenheit auf einen Mehrwegebaum an, so müssten folgende Forderungen für einen vollständig ausgeglichenen Baum erfüllt sein:

Alle Wege von der Wurzel bis zu den Blättern sind gleich lang.

Jeder Knoten besitzt gleich viele Einträge.

Das vollständige Ausgleichen in einem solchen Baum wäre jedoch zu aufwendig. Daher wird das B-Baum-Kriterium eingeführt:

Jeder Knoten außer der Wurzel enthält zwischen m und 2m Schlüsselwerte.

Im Kontext von B-Bäumen spricht man auch von Seiten anstelle von Knoten.

Seiten entsprechen dabei Speichereinheiten, die auf einem externen Medium verwaltet werden und mit einer Operation ein- bzw. ausgelagert werden können.

Daher sind B-Bäume besonders gut für Datenstrukturen geeignet, die aufgrund ihrer Größe nicht mehr im Hauptspeicher, sondern extern gespeichert werden.

Abbildung 16-17. Struktur einer Seite im B-Baum

Die Höhe eines B-Baumes ergibt sich danach bei minimaler Füllung aus logm n.

Gleichzeitig lassen sich somit n Datensätze mit logm n Seitenzugriffen von der Wurzel zum Blatt lesen.

Jede Seite enthält i geordnete Elemente oder Schlüsselwerte, wobei es einen Wert m gibt, so dass m ≤ i ≤ 2m gilt.

Dieses m wird auch als Ordnung des B-Baumes bezeichnet.

Zusätzlich zu den Schlüsselwerten enthält jede Seite noch Verweise auf die Kindknoten mit den Unterbäumen, wobei für einen inneren Knoten jeweils i + 1 solcher Verweise vorhanden sind.

Jede Seite enthält höchstens 2m Elemente.

Jede Seite außer der Wurzelseite enthält mindestens m Elemente.

Jede Seite ist entweder eine Blattseite ohne Nachfolger oder hat i + 1 Nachfolger, falls i die Anzahl ihrer Elemente ist.

Alle Blattseiten liegen auf der gleichen Stufe.

Für einen B-Baum der Ordnung m gilt:

Suchen im B-Baum

Abbildung 16-18. Suchen im B-Baum

Einfügen und Löchen

Bei den Einfüge- und Löschoperationen muss die Forderung nach mindestens m und maximal 2m Elementen pro Seite eingehalten werden.

Bäume Live

Textverarbeitung

Wie werden Texte maschinell verarbeitet?

Welche Algorithmen und Datenstrukturen werden gebraucht?

Was sind reguläre Ausdrücke und wie und wofür verwendet man sie?

Anwendungen für Textverarbeitung

Übersetzer

Übersetzung einer natürlichen Sprache in eine andere natürliche

Übersetzung einer natürlichen Sprache in eine maschinelle Speache oder Notation (symbolische Repräsentation, symbolische KI)

Übersetzung einer maschinellen (Programmier-) Sprache in eine andere

Meistens Reduktion der Ausdrucksfähigkeit und Komplexität

Beispiel: C++ in konkrete Maschinensprache eines Mikroprozessors (strukturiert und hierarchisch auf lineare Struktur)

Beispiel: Java in abstralte Maschinensprache einer Virtuellen Maschine

Suche

Bisher haben wie in strukturierten Daten gescuht. Jetzt Suche un unstrukturierten Daten - den Texten.

Ein Text besteht aus Zeichen mit einem Alphabet, ggfs. unterteilt uin Worte mit Trennzeichen

Suche in Texten bedarf vor allem effiziente Algorithmen, häufig mit Zustandsautomaten verbunden.

Reguläre Ausdrücke

[https://files.ifi.uzh.ch/cl/hess/classes/le/regex.0.l.pdf]

Wozu braucht man RA?

Die Verwendung regulärer Ausdrücke (RA) ist heute weit verbreitet im Bereich grundlegender, einfacherer Verfahren der Computerlinguistik (z.B. Tokenisierung und Tagging), Suchmaschinen oder in einfachen Interpretern, der sogenannten flachen Textverarbeitung.

Mit Hilfe von regulären Ausdrücken lassen sich Muster für einfache sprachliche Ausdrücke spezifizieren, nach denen automatisch in Texten gesucht werden kann.

Ein Beispiel hierfür, umgangssprachlich ausgedrückt, wäre "Wort, das mit einem Grossbuchstaben anfängt und mit einem 'k' aufhört".

Je nach Textkorpus, in dem man sucht, lässt sich damit das Wort "Computerlinguistik" finden.

Die gefundenen Instanzen (Matches) eines solchen Mustervergleichs (Pattern matching) stehen dann zum Teil direkt der weiteren Verarbeitung zur Verfügung.

Woher kommen RA?

Die Verwendung regulärer Ausdrücke ist vor allem durch Suchfunktionen (egrep) und Skriptsprachen (lex und flex) auf Unix-Ebene sowie durch plattformübergreifende Skriptsprachen (vor allem Perl, JavaScript) bekannt geworden

Mittlerweile können RA in vielen gängigen Programmiersprachen verwendet werden.

Was sind RA?

Reguläre Ausdrücke sind zunächst einmal einfach zu spezifizieren.

Einfach heisst dabei nicht unbedingt leicht verständlich, ganz im Gegenteil!, sondern gemäss formaler Kriterien wie Repräsentations- und Verarbeitungskomplexität einfach - das macht sie so attraktiv.

Entsprechend lassen sich Sprachen, die RA beschreiben (sogenannte reguläre Sprachen), mithilfe des einfachsten Grammatiktyps (sogenannten Typ-3-Grammatiken) beschreiben.

Solche Sprachen können nachweislich in effizient zu verarbeitende Strukturen (sogenannte Endliche Automaten) übersetzt werden, die durch RA spezifizierte Ausdrücke schnell aufspüren.

Was kann man mit RA machen?

Programmiersprachen, die die Verwendung von RA implementieren, bieten in der Regel mindestens die folgenden Möglichkeiten:

checken, ob ein RA in einem Text vorkommt

angeben, wo ein RA in einem Text vorkommt

den Zugriff auf Teile eines Matches im Text

den Zugriff auf alle zu findenden Matches im Text

die Möglichkeit zur Ersetzung eines (oder aller) Vorkommen in einem Text durch etwas anderes

die Möglichkeit zur Zerlegung eines Textes an den Stellen, an denen ein gegebener RA vorkommt.

Konstruktion regulärer Ausdrücke

Im folgenden sollen die wesentlichen Möglichkeiten zur Konstruktion von RA vorgestellt werden.

Hierzu werden RA in den Beispielen stets durch Schrägstriche ("/") (slashes) eingerahmt (wie es z.B. in Perl oder JavaScript üblich ist).

Anhand eines solchermassen angegebenen Suchmusters wird ein Text von Anfang bis Ende durchsucht und es wird der zuerst gefundene Match als Ergebnis geliefert.

Im Folgenden gehen wir davon aus, dass jeweils alle Ergebnisse gesammelt werden.

Direkte Angabe von Zeichenketten

Direkte Angabe von Zeichenketten, also Abfolgen von Zeichen, sind der einfachste Fall:

/einzig/
/einzig|winzig/

Suche nach dem Vorkommen von "einzig" im Text oder alternativ durch "|" getrennt nach "einzig" und "winzig" (Disjunktion).

Zeichenklassen

Zeichenklassen ("character classes") sind eine wichtige Möglichkeit, reguläre Ausdrücke kürzer zu formulieren

In "[]" eingeschlossen lassen sich Zeichen ange-ben, die an einer bestimmten Position auftreten sollen/dürfen.

Sie dienen im wesentlichen der Vereinfachung von RA (um nicht jeweils die Zeichenalternativen an einer Position explizit angeben zu müssen).

weitere Möglichkeiten, Zeichenklassen zu spezifizieren:

/[A-Z]/ ein beliebiger Grossbuchstabe (aber ohne Umlaute, ß und Buchstaben mit Akzenten)

/[A-Za-z]/ ein beliebiger Gross- oder Kleinbuchstabe (ditto)

/[0-9]/ eine beliebige Ziffer

Mischungen und Teilbereichsangaben sind möglich, z.B. /[ab17G-K]/

Ausschluss: /[^abc]/ passt auf alle Zeichen außer a,b und c.

Man kann bei der Suche das Flag "g" hinter den Ausdruck setzen. Dann wird dieser mehrfach angewendet und liefert alle passenden Ergebnisse.

Wiederholungen

Häufig sollen Muster mehrfach expandiert werden, d.h. z.B. würde /a/ nur ein Zeichen "a" im Text "aabbba" suchen.

Sollen Sequenzen von Zeichen die aus einzelnen Teilen zusammengesetzt sind gesucht werden braucht man Wiederholungen.

Quantifikatoren geben an, wie häufig das direkt vorangehende Zeichen bzw. die direkt vorangehende Gruppe oder Zeichenklasse vorkommen können soll.

Es gibt einige allgemeine und eine Reihe von numerischen Wiederholungen.

Allgemeine Wiederholungen sind:

* Keinmal oder beliebig oft

+ Mindestens einmal

? Einmal oder keinmal

Beispiel:

s="aabbba"
match(/a+|b+/g,"abbaab") => [ 'a', 'bb', 'aa', 'b' ]

Reguläre Ausdrücke und Automaten

Reguläre Ausdrücke bzw. deren Anwendung ist i.A. zustandslos und kontextfrei.

Folgendes Beispiel:

if a=0 then a=1 end

Das "then" ist nur nach einem "if" zulässig, dazwischen befindet sich ein Ausdruck. Es gibt also einen Kontext. Das Gleichheitszeichen hat hier zwei Bedeutungen: Vergleich und Zuweisung (wie z.B. in der Programmiersprache Basic). Es gibt also einen Kontext. Ist = in einem Ausdruck dann ist es ein Vergleich und liefert einen Booleschen Wert, ist es Bestandteil einer Anweisung dann ist es eine Zuweisung. Das kann ein regulärer Ausdruck nicht unterscheiden.

Mit einer Ausnahme:

Rückverweise sind ein sehr mächtiges Instrument beim Schreiben von regulären Ausdrücken.

Für gruppierte (d.h. in runde Klammern eingeschlossene) Teilmuster werden systematisch Register angelegt, so dass mit Hilfe von Variablen der Form "$i" (mit i aus [1-9]) ein Rückbezug auf Matches dieser Teilstrukturen möglich ist.

Dies ist insbesondere bei Ersetzungen sehr hilfreich.

Innerhalb des RA kann mit "\i" auf Teilmuster(matches) zurückverwiesen werden:

/\b([egin]{3,3}).*?\b\s\1/

Suche nach dem Vorkommen einer Zeichenkette, die mit einer Wortgrenze beginnt, gefolgt von genau 3 Zeichen, die jeweils entweder "e", "g", "i" oder "n" sind (dieses Muster wird als erstes Muster gespeichert), gefolgt von beliebigen Zeichen bis zur ersten Wortgrenze, gefolgt von einem white space, gefolgt vom ersten Muster

Man kann jeden regulären Ausdruck in einen Endlichen Zsutandsautomaten übersetzen. RA sind aber viel mächtiger und ausdrucksstärker. RA können Graphen beschreiben!

Abbildung 17-1. Endlicher Automat zum regulären Ausdruck `0+1(0+1)*`

Suche in Texten

Jetzt wollen wir uns einen Algorithmus für eine Suche eines einfachen Musters in einem Text anschauen.

Brute-Force

function BruteForceSearch (text, pat) {
  // Eingabe: zu durchsuchender Text text der Länge n,
  // gesuchtes Muster pat der Länge m
  for (i= 0; i<= n − m;i++) {
    j = 0;
    while (j < m && pat[j] == text[i + j]) {
      j = j + 1
    }
    if (j >= m) return i
  }
  return −1
}

Algorithmus 17-1. Zwei geschachtelte Schleifen für die Brute-Force-Suche in Texten

Abbildung 17-2. Ablauf beim Brute-Force-Algorithmus [addp]

Die Laufzeitkomplexität beträgt im ungünstigsten Fall O((n − m) m) = O(nm) bei einer Textlänge n und einer Musterlänge m, der zusätzliche Platzbedarf ist aber konstant und damit O(1).

Insbesondere für lange Muster wünscht man sich daher eine Verbesserung der Laufzeitkomplexität, gegebenenfalls auch bei einer Verschlechterung des Platzbedarfs.

Das Problem des Brute-Force-Verfahrens ist im Wesentlichen, dass bei Feststellen einer Nichtübereinstimmung sowohl der Zeiger im Muster als auch der Zeiger im Text zurückgesetzt werden.

An dieser Stelle setzt der Algorithmus von Knuth, Morris und Pratt an, der die Suche mit einer Komplexität von O(n + m) ermöglicht.

function KMPSearch (text, pat) {
  // Eingabe: zu durchsuchender Text text der Länge n,
  // gesuchtes Muster pat der Länge m
  j = 0;
  for (i = 0;i<n;i++) {
    while (j >= 0 && pat[j] != text[i]) j = next[j]
    j = j + 1;
    if (j = m) return i − m + 1
  }
  return -1
}

Algorithmus 17-2. Zwei geschachtelte Schleifen für die Brute-Force-Suche in Texten. Es wird ein voraus berechnetes Hilfsfeld *next* verwendet was Rücksrpungpositionen bei Nichtübereinstimmung angibt

function initNext (pat) {
  i = 0, j = − 1
  next[0] = − 1
  while (i < pat.length() − 1) {
    while (j > = 0 && pat[i] != pat[j])
      j = next[j]
    i++; j++
    next[i] = j
  }
  return next;
}

Algorithmus 17-3. Berechung des Hilfsfeldes *next*

Die Anzahl der zu verschiebenden Stellen ist dabei nur vom Muster abhängig. Der Knuth-Morris-Pratt-Algorithmus (kurz »KMP«) nutzt dies aus, indem in einem Vorverarbeitungsschritt die Struktur des Musters analysiert wird. Daraus kann abgeleitet werden, wie weit im Fall einer Nichtübereinstimmung zurückgegangen werden muss. Diese Informationen werden in einem Feld gespeichert, das als next- bzw. border-Feld oder manchmal auch als Fehlerfunktion bezeichnet wird. Es enthält für jede Position des Musters die Distanz für eine sichere Verschiebung. Diese Werte werden bestimmt, indem für jedes j das längste Präfix des Musters pat ermittelt wird, das auch Suffix von pat[1… j] ist.

Abbildung 17-3. Berechnung des next Feldes für das Muster `ABCAAB`

Zusammenfassung