E1 Algorithmen

Dieses Kapitel enthält optionales Zusatzmaterial zur Vorlesung. Hier lernen Sie, Probleme in der Programmierung systematisch zu lösen.

E1.1 Was ist ein Algorithmus?

Ein Algorithmus ist eine Art Kochrezept, um ein Problem zu lösen. Wollen Sie z.B. Kaffee kochen, müssen Sie bestimmte Schritte befolgen:

1. Filter einsetzen
2. Kaffee einfüllen
3. Maschine einschalten

Natürlich kann es sein, dass kein Wasser mehr in der Maschine ist - das sollten Sie in Ihr Rezept einbauen:

1. Filter einsetzen
2. Kaffee einfüllen
3. Wenn kein Wasser in der Maschine ist, dann
   • Wasser einfüllen
4. Maschine einschalten

Der Schritt "Kaffee einfüllen, besteht eigentlich aus vielen Teilschritten, die wir genauer aufführen könnten

1. Filter einsetzen
2. Tu das folgende 3 Mal:
   • Löffel mit Kaffeepulver befüllen
   • Löffel im Filter ausleeren
3. Wenn kein Wasser in der Maschine ist, dann
   • Wasser einfüllen
4. Maschine einschalten

Sie sehen natürlich sofort, dass ein Algorithmus so ähnlich aussieht wie Processing-Code. Es gibt einfache Schritte, das einspricht einem Befehl (= Funktionsaufruf) in Processing. Und es gibt If-Anweisungen und Schleifen. Ihr Code löst andere Probleme, zum Beispiel das Problem, einen Ball zu bewegen und dabei darauf zu achten, dass der Ball korrekt von der Wand abprallt. Oder Ihr Code löst das Problem, einen Mittelwert zu berechnen, oder ein Sonnensystem zu animieren.

In nächsten Abschnitt schauen wir uns an, wie wir Algorithmen finden.

E1.2 Probleme lösen

Um ein Problem zu lösen, sollten Sie sich zunächst vor Augen führen, welche Daten Sie als Ausgangsbasis haben, das ist Ihr Input. Dann fragen Sie sich, was das Ziel Ihres Problems ist, d.h. was ist der gewünschte Output?

Im nächsten Schritt müssen Sie Ideen generieren, wie Sie das Problem in einem Programm lösen könnten. Sie sammeln Methoden (Hilfsvariablen, If-Anweisungen, Schleifen), die Ihrem Gefühl nach dabei eine Rolle spielen könnten.

Schließlich schreiben Sie Pseudo-Code. Das ist wie ein Programm, aber ganz informell formuliert. Erst dann gehen Sie an die Umsetzung - das nennt man auch Implementierung.

Der letzte Schritt besteht im Testen. Ihr Programm muss sich nicht nur starten lassen, sondern muss auch für alle möglichen Inputs die korrekte Lösung liefern. Natürlich können Sie nicht alle Möglichkeiten durchtesten, aber es ist wichtig, möglichst alle Extremfälle beispielhaft zu testen. Was sind Extremfälle? Wenn Sie einen Suchalgorithmus schreiben, der ein bestimmtes Element in einem Array finden muss, dann testen Sie den Fall, dass...

• ... das Suchergebnis ganz vorne ist
• ... das Suchergebnis ganz hinten ist
• ... das Array leer ist

Wir sehen uns das anhand von Beispielen an:

Aufgabe: Berechene die Summe 1 + 2 + ... + N

int sum(int n) {
   int result = 0;
   for (int i = 0; i <= n; i++) {
      result = result + i;
   }
   return result;
}

void setup() {
  println(sum(0));
  println(sum(5));
}

0
15

Noch ein Beispiel:

Aufgabe: Finde in einem Array die kleinste Zahl

int smallest(int[] a) {
   int smallest = a[0];
   for (int i = 1; i < a.length; i++) {
      if (smallest > a[i]) {
      	smallest = a[i];
      }
   }
   return smallest;
}

void setup() {
  int[] foo = { 10, 30, -20, 100 };
  println(smallest(foo));

  int[] boo = new int[0]; // Array mit null Elementen
  println(smallest(boo));
}

int smallest(int[] a) {
   if (a.length == 0) {
   	return 0; // Bei Länge 0 wird zurückgesprungen
   }
   int smallest = a[0];
   for (int i = 1; i < a.length; i++) {
      if (smallest > a[i]) {
      	smallest = a[i];
      }
   }
   return smallest;
}

-20
0

Noch ein "Klassiker":

Aufgabe: Tausche zwei Elemente in einem Array

void switchElements(int[] a, int x, int y) {
   int temp = a[x];
   a[x] = a[y];
   a[y] = temp;
}

void setup() {
  int[] a = { 3, 2, 1 };
  println("vorher");
  println(a);

  switchElements(a, 0, 2); // tauschen

  println("nachher");
  println(a);
}

vorher
[0] 3
[1] 2
[2] 1
nachher
[0] 1
[1] 2
[2] 3

void setup() {
  int[] a = { 1 };
  println("vorher");
  println(a);
  switchElements(a, 0, 0);
  println("nachher");
  println(a);
}

vorher
[0] 1
nachher
[0] 1

void setup() {
  int[] a = { 1 };
  println("vorher");
  println(a);
  switchElements(a, 0, 1);
  println("nachher");
  println(a);
}

Zum Abschluss ein etwas komplexeres Beispiel:

Aufgabe: Verändere ein Array so,
dass es aufsteigend sortiert ist

void sortArray(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int k = 0; k < i; k++) {
      if (arr[i] < arr[k]) {
        switchElements(arr, i, k);
      }
    }
  }
}

void setup() {
  int[] a = { 2, 3, -1, 1 };
  println("vorher");
  println(a);

  sortArray(a);

  println("nachher");
  println(a);
}

vorher
[0] 2
[1] 3
[2] -1
[3] 1
nachher
[0] -1
[1] 1
[2] 2
[3] 3

// Fall: Array richtig sortiert
void setup() {
  int[] a = { 1, 2, 3 };
  println("vorher");
  println(a);

  sortArray(a);

  println("nachher");
  println(a);
}

vorher
[0] 1
[1] 2
[2] 3
nachher
[0] 1
[1] 2
[2] 3

// Fall: Array falschrum sortiert
void setup() {
  int[] a = { 3, 2, 1 };
  println("vorher");
  println(a);

  sortArray(a);

  println("nachher");
  println(a);
}

vorher
[0] 3
[1] 2
[2] 1
nachher
[0] 1
[1] 2
[2] 3

// Fall: Array ist leer
void setup() {
  int[] a = new int[0];
  println("vorher");
  println(a);

  sortArray(a);

  println("nachher");
  println(a);
}

vorher
nachher

E1.3 Rekursion

Rekursion ist eine Methode, um Algorithmen zu implementieren, die darauf basiert, dass eine Funktion F sich selbst wiederholt aufruft, um ein Problem zu lösen.

Damit das funktioniert, muss Funktion F das Problem P, das es zu lösen gilt, in zwei Teile (P1 und P2) aufteilen. P1 ist dabei ein triviales Problem, das direkt von F gelöst wird, P2 ist so ähnlich wie P, aber "kleiner" und wird durch einen weiteren Aufruf von F auf P2 gelöst. Klingt wie Magie? Funktioniert aber!

Einfaches Beispiel

Schauen wir uns ein einfaches Beispiel an: Die Funktion printHashes() soll eine per Parameter spezifizierte Anzahl von Hash-Zeichen auf der Konsole ausgeben. Die einer Schleife würden Sie das so implementieren:

void setup() {
  printHashes(5);
}

void printHashes(int num) {
  for (int i = 0; i < num; i++) {
    print("#");
  }
}

Eine rekursive Version von printHashes()basiert auf folgender Einsicht: Das Problem P = "drucke 5 Hash-Zeichen" lässt sich in die zwei Teilprobleme P1 und P2 zerlegen:

• P1: Drucke 1 Hash-Zeichen (trivial)
• P2: Drucke 4 Hash-Zeichen (ähnliches, aber "kleineres" Problem)

Das erste Problem löst man direkt durch ein einziges print(), für das zweite Problem ruft man die gleiche Funktion mit dem Parameter 4 auf. Bei diesem Aufruf wird wieder ein Hash gedruckt und die Funktion mit Parameter 3 aufgerufen...

printHashes(5)
printHashes(4)
printHashes(3)
...

Jetzt müssen wir noch aufpassen, dass wir nicht in eine Art Endlosschleife verfallen. Denn wenn printHashes() mit dem Parameter 1 aufgerufen wird, wollen wir ja nicht printHashes im Anschluss mit 0 aufrufen (und dannach mit negativen Zahlen).

...
printHashes(1)
printHashes(0)
printHashes(-1)
printHashes(-2)
...

Wir müssen also den Basisfall abfangen, dass nur nur 1 Hash-Zeichen gedruckt wird, denn hier ist das Problem P identisch mit dem (trivialen) Teilproblem P1 und wir müssen die Funktion kein weiteres Mal aufrufen.

Im Code sieht die Funktion wie folgt aus:

void printHashes(int num) {
  // Teilproblem P1 direkt lösen
  print("#");

  // Ausschließen, dass dies der Basisfall ist
  if (num > 1) {

    // Teilproblem P2 durch Rekursion lösen
    printHashes(num - 1);

  }
}

Dies Beispiel diente nur der Erklärung. Die Lösung mit der Schleife nennt man auch ein iteratives Verfahren, die zweite Lösung ist dann das rekursive Verfahren.

Im vorliegenden Fall ist sicher das iterative Vorgehen vorzuziehen, denn Rekursion hat einige Nachteile:

• Fehleranfällig: Durch die ungewohnte Art des Programmierens entstehen leicht Fehler, z.B. dass man den Basisfall nicht abfängt.
• Performanz: Für jeden Funktionsaufruf muss eine Programmiersprache bestimmte Verwaltungsinformationen anlegen, damit nach Abarbeitung der Funktion auch alles korrekt abläuft. Das bedeutet, dass die iterative Methode um einiges schneller ist und weniger Speicherplatz verbraucht.

Jetzt fragen Sie sich, warum man sich überhaupt mit Rekursion beschäftigen muss? Es gibt ein paar Probleme, bei denen die rekursive Methode tatsächlich einfacher zu programmieren ist als die iterative Methode. Zwei typische Bereiche sind Sortieren und Suchen, beides enorm wichtige Aufgaben in der Programmierung, auch schon vor dem Zeitalter von Google. Dass hier Rekursion zum Zuge kommt, hat auch damit zu tun, dass sich Baumstrukturen sehr leicht und intuitiv mit Rekursion durchlaufen lassen und Bäume gehören zu den wichtigsten Strukturierungsmethoden in der Informatik überhaupt. Zum Beispiel bilden Verzeichnisse, Unterverzeichnisse und Datein einen Baum. Weiteres Beispiel sind Struktur und Inhalte einer Webseite (Texte, Überschriften, Bilder, Links etc.) als Baum strukturiert (das sog. document object model oder DOM).

Beispiele mit Rückgabe

Schauen wir uns ein etwas weniger triviales Beispiel an. Wir wollen jetzt die Summe 1 + 2 + .. + N berechnen.

Wieder hätten wir eine relativ leichte iterative Variante im Angebot:

void setup() {
  println(summeBis(5));
}

// Iterative Lösung

int summeBis(int ende) {
  int summe = 0;
  for (int i = 1; i <= ende; i++) {
    summe = summe + i;
  }
  return summe;
}

15

Wir überlegen uns wieder, wie wir das Problem P = "Summe von 0 bis N" zerlegen. Wir nehmen "0 bis N" statt "1 bis N", weil die Formulierung dann etwas eleganter ausfällt.

• P1: Addiere N zu der Teilsumme 0 bis (N-1)
• P2: Berechne die Teilsumme 0 bis (N-1)

Im Gegensatz zum ersten Beispiele, müssen wir bei P1 die Lösung von P2 verwenden. Außerdem müssen wir uns überlegen, was hier der Basisfall ist. Die Rekursion soll enden, wenn wir die Summe bis 0 berechnen sollen (ist natürlich 0).

Als Code:

int summeBis(int ende) {

  // Basisfall
  if (ende == 0) {
    return 0;
  }

  // Löse P2 durch Rekursion:
  int erg = summeBis(ende - 1);

  // Löse P1 mit Ergebnis von P2
  return ende + erg;
}

15

Oder etwas kompakter geschrieben:

int summeBis(int ende) {

  // Basisfall
  if (ende == 0) {
    return 0;
  }

  // Löse P1 und P2
  return ende + summeBis(ende - 1);
}

Der Gründlichkeit halber sollten wir uns überlegen, was passiert, wenn man die Funktion mit 0 oder negativen Werten aufruft: Hier würden wir in einen unendlichen Regress laufen. Also fangen wir diese Fälle ab:

int summeBis(int ende) {

  if (ende <= 0) {
    return 0;
  }

  return ende + summeBis(ende - 1);
}
	

Ein weiteres (klassisches) Beispiel für Rekursion ist die Berechnung der "Fakultät" einer Zahl. Die Fakultät von 5 wird auch 5! geschrieben und ist definiert durch:

	5! = 1 * 2 * 3 * 4 * 5 = 120

Für die rekursive Lösung überlegen wir wieder, wie wir das Problem P, die Fakultät für eine Zahl n zu berechnen zerlegen:

• P1: Multipliziere n mit der Fakultät von n-1
• P2: Berechne die Fakultät von n-1

Schließlich überlegen wir uns noch den Basisfall: Die Fakultät von 0 ist als 1 definiert. Hier darf nicht mehr die Funktion für n-1 aufgerufen werden!

Als Code:

void setup() {
  println(fak(5));
}

int fak(int n) {

  // Basisfall
  if (n == 0) {
    return 1;
  }

  // Teilprobleme P1 und P2
  return n * fak(n - 1);
}

120

Auch hier sollten wir überlegen, was passiert, wenn jemand negative Werte übergibt (für negative Werte ist Fakultät nicht definiert), damit unsere Funktion nicht in einen unendlichen Regress geht. Wir geben in diesen Fällen einfach eine 0 zurück.

int fak(int n) {

  // Fehlerfall
  if (n < 0) {
    return 0;
  }

  // Basisfall
  if (n == 0) {
    return 1;
  }

  // Teilprobleme P1 und P2
  return n * fak(n - 1);
}

Beispiel mit Array

Rekursion wird i.d.R. bei größeren Datenstrukturen angewandt, z.B. bei Arrays, die sortiert werden müssen oder in denen etwas gesucht wird.

Sehen wir uns zunächst wieder eine einfache Aufgabe an, die wir ohne weiteres mit einer Schleife - also iterativ - lösen könnten. Wir wollen alle Zahlen eines int-Arrays addieren.

Unsere zwei Teilprobleme sind hier:

• P1: Addiere Element 0 mit der Summe der Elemente 1 bis (N-1)
• P2: Berechne die Summe der Elemente 1 bis (N-1)

Ein erster Entwurf könnte so aussehen:

void setup() {
  int[] num = {5, 8, 4, 20, 1, -7 };
  println(summe(num));
}

int summe(int[] arr) {
  if (arr.length == 0) {
    return 0;
  }
  return arr[0] + summe(subset(arr, 1));
}

Wir wenden unsere Funktion summe rekursiv auf immer kürzere Teilarrays an, die wir mit subset erzeugen. Das Problem mit subset ist, dass hier immer ein komplett neues Array erzeugt wird (verbraucht Speicher) und dieses neue Array mit Hilfe des ursprünglichen Arrays befüllt wird (verbraucht Zeit). Also für größere Arrays eine reichlich ineffiziente Lösung.

Um das ganze effizienter zu lösen, müssen wir nicht nur den Array übergeben, sondern einen Parameter einführen, der den Startindex definiert.

void setup() {
  int[] num = {5, 8, 4, 20, 1, -7 };
  println(summeAb(num, 0));
}

int summeAb(int[] arr, int start) {
  if (start >= arr.length) {
    return 0;
  }
  return arr[start] + summeAb(arr, start + 1);
}

Wenn wir möchten, können wir jetzt die Funktion summe definieren, die man verwenden sollte:

int summe(int[] arr) {
  return summeAb(arr, 0);
}

Mergesort

Ein komplexeres Beispiel ist das Sortieren mittels "Mergesort". Mergesort basiert auf der Erkenntnis, dass folgendes Problem "Merge" leicht und effizient lösbar ist. Dieses Problem wird nicht rekursiv gelöst. Der rekursive Anteil von Mergesort kommt später.

Merge

Problem: Gegeben zwei bereits sortierte Arrays, erzeuge einen zusammengefügten Array, der ebenfalls sortiert ist.

Beispiel: Gegeben die sortierten Arrays a = { 2, 5 } und b = { 3, 10 }, stelle einen Array der Länge 4 her, der die Elemente von a und b in sortierter Folge enthält. In diesem Fall also { 2, 3, 4, 10 }.

Warum ist das Problem leicht? Weil Sie mit gleichzeitig durch die zwei Arrays a und b wandern und jeweils die kleinere Zahl in einen neuen Array r schieben.

int[] merge(int[] a, int[] b) {
  int[] r = new int[a.length + b.length];

  int ai = 0;
  int bi = 0;

  for (int ri = 0; ri < r.length; ri++) {
    if (ai < a.length && bi < b.length) {
      if (a[ai] < b[bi]) {
        r[ri] = a[ai];
        ai++;
      } else {
        r[ri] = b[bi];
        bi++;
      }
    } else {
      if (ai >= a.length) {
        r[ri] = b[bi];
        bi++;
      } else {
        r[ri] = a[ai];
        ai++;
      }
    }
  }
  return r;
}

Mergesort

• P2: Sortiere die zwei Hälften von c mit mergesort(). Die Hälften haben jeweils die Länge N/2, d.h. das Problem verkleinert sich erheblich.
• P1: Führe die zwei sortierten Hälften mit merge() zusammen.

Der Basisfall ist der Fall, dass der zu sortierende Array die Länge 1 hat. Dann wird der Array einfach wieder zurückgegeben.

Wir können uns das am Array { 4, 3, 2, 1 } vor Augen führen.

Als Code:

int[] mergesort(int[] arr) {

  // Basisfall
  if (arr.length <= 1) {
    return arr;
  }

	// P2: Rekursiver Aufruf von mergesort
  // Dazu den Array teilen...
  int mitte = arr.length/2;
  int[] arr1 = subset(arr, 0, mitte);
  int[] arr2 = subset(arr, mitte);

  // ...und die Teilarrays sortieren
  int[] sarr1 = mergesort(arr1);
  int[] sarr2 = mergesort(arr2);

  // P1: Zusammenführung mit merge
  int[] result = merge(sarr1, sarr2);

  return result;
}

Beachten Sie, dass auch ein Array mit ungerader Anzahl kein Problem darstellt. Ein Array { 3, 2, 1 } wird in die zwei "Hälften" { 3 } und { 2, 1 } geteilt.

void setup() {
  println(hoch(5, 2));
  println(hoch(3, 3));
}

25
27

void setup() {
  recursiveFor(0, 5, 1);
  println();
  recursiveFor(2, 6, 2);
}

0
1
2
3
4

2
4