Zum Inhalt springen
Zurück zur Themenübersicht

Algorithmen

Was ist ein Algorithmus?

Die vier Eigenschaften, an denen sich jede Handlungsanweisung messen lassen muss, und die Grenzen dessen, was Algorithmen leisten.

Einführung

„Man nehme etwas Mehl, backe bei mittlerer Hitze, bis es gut aussieht.“

Ein Mensch kommt damit vielleicht zurecht. Eine Maschine nicht: Wie viel ist etwas? Wie heiß ist mittel? Wann sieht etwas gut aus? An diesen drei Fragen scheitert das Rezept, und zwar an genau den Stellen, an denen es ungenau ist.

Ein Algorithmus ist nichts anderes als eine Handlungsanweisung, die diese Lücken nicht hat. Die vier Eigenschaften, die das sicherstellen, sind keine Schulbuchdefinition zum Auswendiglernen: Jede von ihnen verhindert genau einen Weg, auf dem eine Anleitung scheitern kann.

Das kannst du nach diesem Kapitel

  • die vier Eigenschaften allgemeingültig, ausführbar, endlich, eindeutig nennen und je begründen, wovor sie schützen.

  • prüfen, ob eine gegebene Anweisung ein Algorithmus ist, und bei Verstößen die verletzte Eigenschaft benennen.

  • einen Algorithmus verbal und als Ablaufdiagramm darstellen.

  • beschreiben, was Algorithmen leisten, und ein Problem nennen, für das es keinen gibt.

Wir entwickeln die Eigenschaften aus Fehlern

Statt vier Merkmale zu behaupten, sehen wir uns vier kaputte Anleitungen an. Jede scheitert anders.

Anleitung 1: „Addiere 17 und 25.“

Sie funktioniert genau einmal. Für andere Zahlen ist sie nutzlos. Ein Algorithmus soll eine ganze Klasse von Aufgaben lösen, nicht einen Einzelfall. Also: allgemeingültig.

Anleitung 2: „Teile die Zahl durch null.“

Der Schritt ist klar formuliert und trotzdem nicht durchführbar. Jeder Schritt muss mit den vorhandenen Mitteln tatsächlich ausführbar sein.

Anleitung 3: „Zähle von 1 aufwärts und schreibe jede Zahl auf.“

Sie ist eindeutig und ausführbar, aber sie hört nie auf. Ein Algorithmus muss nach endlich vielen Schritten fertig sein.

Anleitung 4: „Nimm eine der beiden Zahlen und verdopple sie.“

Welche? Zwei Menschen erhalten verschiedene Ergebnisse, obwohl beide der Anleitung folgen. Jeder Schritt muss eindeutig sein.

Damit sind die vier Eigenschaften nicht Merkmale, die man auswendig lernt, sondern Antworten auf vier verschiedene Arten des Scheiterns:

EigenschaftVerhindert
allgemeingültigdass die Anleitung nur einen Einzelfall löst
ausführbardass ein Schritt gar nicht durchführbar ist
endlichdass die Ausführung nie endet
eindeutigdass zwei Ausführungen verschieden enden

Alltagsanweisung und Algorithmus

AlltagsanweisungAlgorithmusWie lautet die Anweisung?„Rühre, bis derTeig glatt ist.“„Rühre 120Sekunden.“Was muss der Ausführende tun?selbstentscheiden,wann glatt istnichtsentscheiden, nurausführenZwei Leute, dasselbe Ergebnis?nein, jeder hörtwoanders aufja, immerdasselbeEin Algorithmus lässt demAusführenden keine Wahl. Genau dasmacht ihn maschinentauglich.

Beide Anweisungen meinen dasselbe, aber nur eine ist ein Algorithmus. Der Unterschied steht in der mittleren Zeile: Links muss der Ausführende selbst beurteilen, wann „glatt“ erreicht ist, rechts nicht. Eine Maschine kann nichts beurteilen; sie kann nur ausführen. Deshalb ist die dritte Zeile keine Zusatzeigenschaft, sondern die Folge der zweiten.

Die genaue Formulierung

Ein Algorithmus ist eine endliche, eindeutige Handlungsvorschrift aus ausführbaren Schritten, die eine ganze Klasse gleichartiger Probleme löst.

Wichtig ist der Zusatz „Klasse von Problemen“. Ein Algorithmus zur Flächenberechnung eines Rechtecks arbeitet mit beliebigen Seitenlängen, nicht mit 3 und 5.

Vier Eigenschaften, vier Fehlerquellen

Sie verlangtOhne sieEndlichkeitDas Verfahrenhört nachendlich vielenSchritten auf.läuft dasProgramm ewigund liefert nieein Ergebnis.EindeutigkeitJeder Schrittist eindeutigbeschrieben.bekommen zweiAusführendeVerschiedenesheraus.AusführbarkeitJeder Schrittist wirklichausführbar.steht „Rate dierichtige Zahl“als Schritt da.AllgemeingültigkeitEs löst alleAufgaben dieserArt, nicht nureine.passt dasVerfahren nur zugenau einemBeispiel.

Die vier Eigenschaften klingen nach einer Liste zum Auswendiglernen. Lies die Tafel deshalb zeilenweise: Jede Eigenschaft steht neben dem Schaden, den ihr Fehlen anrichtet. Genau so sind sie entstanden, nicht als Definition am Anfang, sondern als Antwort auf vier Arten, wie eine Anweisung unbrauchbar wird.

Wie man Algorithmen aufschreibt

Es gibt mehrere übliche Darstellungen, und sie sind gleichwertig.

Verbal, also in nummerierten Sätzen:

  1. Lies die Länge aa ein.
  2. Lies die Breite bb ein.
  3. Berechne A=a⋅bA = a \cdot b.
  4. Gib AA aus.

Als Ablaufdiagramm (Programmablaufplan): Ovale für Anfang und Ende, Rechtecke für Anweisungen, Rauten für , Pfeile für die Reihenfolge. Der Vorteil ist, dass man Verzweigungen und Wiederholungen sofort sieht.

Als Pseudocode, also in einer programmiersprachenähnlichen, aber freien Schreibweise:

LIES a
LIES b
A := a * b
SCHREIBE A

Welche Darstellung du wählst, hängt vom Zweck ab: Verbal ist am leichtesten zu lesen, das Diagramm zeigt die Struktur, Pseudocode ist am nächsten am späteren Programm.

Ein Algorithmus als Ablaufdiagramm

StartWasser zum Kochen bringenNudeln hineingeben10 Minuten kochen lassenNudeln sind fertig

Dieselbe Anweisungsfolge, die man auch als Text aufschreiben könnte, aber die Form macht zwei Dinge sichtbar, die im Fließtext untergehen: Es gibt genau einen Anfang und genau ein Ende, und zwischen zwei Schritten führt immer nur ein Weg. Die abgerundeten Felder oben und unten sind deshalb keine Schritte, sondern Grenzen.

Was Algorithmen leisten und was nicht

Algorithmen sind erstaunlich mächtig. Sie steuern Ampeln, berechnen Routen, sortieren Millionen Datensätze, erkennen Sprache. Ihre Stärke ist, dass eine Maschine sie beliebig oft, schnell und ermüdungsfrei ausführt.

Trotzdem gibt es Grenzen, und sie sind von drei verschiedenen Arten:

Erstens: Manche Probleme sind nicht eindeutig gestellt. „Male ein schönes Bild“ lässt sich nicht algorithmisieren, weil „schön“ keine überprüfbare Bedingung ist. Das ist keine Schwäche der Informatik, sondern eine Eigenschaft der Frage.

Zweitens: Manche Probleme dauern zu lange. Für sie gibt es Algorithmen, die aber selbst mit großen Rechenzentren Jahrtausende bräuchten. Ein Beispiel ist das Durchprobieren aller Reihenfolgen bei einer Rundreise durch viele Städte: Bei 20 Städten sind es bereits mehr als 101710^{17} Möglichkeiten.

Drittens: Für manche Probleme gibt es beweisbar keinen Algorithmus. Das bekannteste ist das Halteproblem: Es gibt kein Programm, das für jedes beliebige andere Programm zuverlässig vorhersagt, ob dieses irgendwann anhält oder ewig weiterläuft. Dass es keines geben kann, ist bewiesen; wie dieser Beweis funktioniert, siehst du in der Qualifikationsphase.

Halte den Unterschied auseinander: „noch nicht gefunden“, „zu langsam“ und „beweisbar unmöglich“ sind drei verschiedene Aussagen.

Wo ein Algorithmus an seine Grenze stößt

Ein Problemein Verfahrendafür angebenEndet esimmer?janeinkeinAlgorithmusAlgorithmusgefunden

Der Nein-Zweig führt aus dem Bild heraus, und das ist die Aussage: Es gibt Probleme, für die kein Verfahren existiert, das bei jeder Eingabe anhält, nicht etwa, weil noch niemand eines gefunden hätte, sondern beweisbar keines. Das Bild zeigt die Grenze, statt sie zu behaupten; warum es sie gibt, klärst du in Klasse 12 beim Halteproblem.

Ein Rezept auf die vier Eigenschaften prüfen

Prüfe: „Gib etwas Salz in das kochende Wasser und koche die Nudeln, bis sie gar sind.“

  1. 1

    Eindeutig? Nein. „Etwas Salz“ ist keine Menge, und „gar“ ist keine überprüfbare Bedingung. Zwei Köche kommen zu verschiedenen Ergebnissen.

  2. 2

    Ausführbar? Ja, jeder Schritt ist grundsätzlich machbar.

  3. 3

    Endlich? Ja, nach endlicher Zeit sind die Nudeln fertig.

  4. 4

    Allgemeingültig? Eingeschränkt. Es gilt für Nudeln, nicht für beliebige Speisen, aber immerhin für jede Nudelmenge.

  5. 5

    Verbesserung: „Gib 10 g Salz je Liter Wasser hinzu. Koche die Nudeln 9 Minuten lang.“ Jetzt sind alle Angaben überprüfbar, und zwei Personen erhalten dasselbe Ergebnis.

Kein Algorithmus, weil die Eindeutigkeit verletzt ist. Mit messbaren Angaben wird einer daraus.

Vom Einzelfall zum Algorithmus

„Berechne den Flächeninhalt eines Rechtecks mit 3 cm und 5 cm.“ Warum ist das kein Algorithmus, und wie macht man einen daraus?

  1. 1

    Verletzt ist die Allgemeingültigkeit: Die Vorschrift löst genau eine Aufgabe. Für ein Rechteck mit 4 cm und 7 cm hilft sie nicht.

  2. 2

    Der Ausweg ist immer derselbe: Feste Zahlen werden durch Namen für Werte ersetzt.

  3. 3
    1. Lies die Länge aa ein. 2. Lies die Breite bb ein. 3. Berechne A=a⋅bA = a \cdot b. 4. Gib AA aus.
  4. 4

    Jetzt löst dieselbe Vorschrift alle Rechteckaufgaben. Man führt sie mit a=3a = 3 und b=5b = 5 aus und erhält 15, genauso mit jedem anderen Paar.

  5. 5

    Merke dir den Schritt: Aus einem Beispiel wird ein Algorithmus, indem man die konkreten Zahlen durch Platzhalter ersetzt, die beim Ausführen gefüllt werden. Genau das leisten später die .

Konkrete Werte durch Eingabegrößen ersetzen. Das ist der Übergang vom Einzelfall zur Klasse von Aufgaben.

Typischer Fehler

„Wenn wir noch bessere Rechner bauen, lässt sich irgendwann jedes Problem algorithmisch lösen.“

Hier werden drei verschiedene Aussagen vermischt, und nur eine davon hat mit Rechenleistung zu tun.

„Zu langsam“ ist tatsächlich eine Frage der Leistung, allerdings selten eine lösbare: Bei einer Rundreise durch 20 Städte gibt es über 101710^{17} Reihenfolgen. Ein Rechner, der eine Milliarde pro Sekunde prüft, bräuchte Jahre; bei 25 Städten sind es schon Milliarden Jahre. Ein tausendmal schnellerer Rechner verschiebt die Grenze um wenige Städte.

„Nicht eindeutig gestellt“ liegt gar nicht an der Technik. Für „male ein schönes Bild“ fehlt eine überprüfbare Bedingung; ohne sie kann niemand entscheiden, ob die Aufgabe gelöst ist, auch kein Mensch.

„Beweisbar unmöglich“ ist die stärkste Aussage. Beim Halteproblem ist bewiesen, dass es kein solches Programm geben kann. Ein Beweis für Unmöglichkeit wird durch schnellere Hardware nicht ungültig, so wenig wie ein schnellerer Taschenrechner die Zahl 2\sqrt{2} zu einem Bruch macht.

Übung 1

leicht

Welche Eigenschaft ist jeweils verletzt?

a) „Wiederhole: Ziehe 1 ab.“ (ohne Abbruchbedingung) b) „Berechne 12 mal 8.“ c) „Wähle irgendeine Zahl und addiere sie.“ d) „Bestimme die letzte Nachkommastelle von π\pi.“

Tipp anzeigen

Zu d): Kann dieser Schritt jemals abgeschlossen werden?

Lösung anzeigen

a) Endlichkeit (die Wiederholung endet nie) b) Allgemeingültigkeit (nur ein Einzelfall) c) Eindeutigkeit („irgendeine“ lässt offen, welche) d) Ausführbarkeit (die Dezimaldarstellung von π\pi bricht nie ab, also gibt es keine letzte Stelle)

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Die vier Eigenschaften als Prüfliste bereitlegen

    Man legt die vier Eigenschaften nebeneinander und prüft jeden Fall gegen alle vier: Endlichkeit (endet nach endlich vielen Schritten), Eindeutigkeit (jeder Schritt ist unmissverständlich), Ausführbarkeit (jeder Schritt ist tatsächlich durchführbar), Allgemeingültigkeit (gilt für eine ganze Klasse von Fällen, nicht nur für einen).

  2. 2

    a) und b): die klaren Fälle

    „Wiederhole: Ziehe 1 ab.“ ohne Abbruchbedingung endet nie, verletzt ist die Endlichkeit. „Berechne 12 mal 8.“ löst genau einen Einzelfall und lässt sich auf keinen anderen anwenden, verletzt ist die Allgemeingültigkeit.

  3. 3

    c) Eindeutigkeit: Wer entscheidet, was „irgendeine“ ist?

    „Wähle irgendeine Zahl und addiere sie.“ lässt offen, welche Zahl gemeint ist. Zwei Ausführende kämen zu verschiedenen Ergebnissen, obwohl beide die Anweisung befolgt haben. Verletzt ist die Eindeutigkeit.

  4. 4

    d) Der Stolperfall: nicht endlos, sondern unmöglich

    „Bestimme die letzte Nachkommastelle von π\pi.“ lässt sich nicht ausführen, weil die Dezimaldarstellung von π\pi nie abbricht. Es gibt keine letzte Stelle. Verletzt ist die Ausführbarkeit.

Übung 2

mittel

Schreibe einen Algorithmus, der zu drei eingegebenen Zahlen die größte ausgibt.

a) Formuliere ihn verbal in nummerierten Schritten. b) Weise nach, dass alle vier Eigenschaften erfüllt sind. c) Erkläre, warum die Formulierung „Nimm die größte der drei Zahlen“ als Algorithmus nicht ausreicht.

Tipp anzeigen

Zu a): Vergleiche immer nur zwei Zahlen miteinander, nie drei auf einmal.

Lösung anzeigen

a) 1. Lies xx, yy und zz ein. 2. Setze max=x\text{max} = x. 3. Wenn y>maxy > \text{max}, dann setze max=y\text{max} = y. 4. Wenn z>maxz > \text{max}, dann setze max=z\text{max} = z. 5. Gib max\text{max} aus.

b) Eindeutig: Jeder Schritt hat genau eine Bedeutung, jeder Vergleich genau zwei mögliche Ausgänge. Ausführbar: Zuweisen und Vergleichen sind Grundoperationen. Endlich: Es sind genau 5 Schritte ohne Wiederholung. Allgemeingültig: Er arbeitet mit beliebigen Zahlen, auch mit gleichen.

c) Weil sie das Problem nur wiederholt, statt es zu lösen. Sie sagt nicht, wie man die größte findet. Für einen Menschen genügt das, weil er den Vergleich selbst beherrscht; eine Maschine kann nur die Grundoperationen, und die Anweisung müsste in genau diese zerlegt werden.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Erst überlegen: Was kann die Maschine überhaupt?

    Bevor man einen Algorithmus schreibt, muss man wissen, welche Schritte als „ausführbar“ gelten. Hier sind das: einen Wert einlesen, einen Wert zuweisen, zwei Werte vergleichen, einen Wert ausgeben. „Die größte nehmen“ gehört nicht dazu.

    Zwischenergebnis

    Die Lösung muss aus Vergleichen von jeweils zwei Zahlen bestehen.

    Diese Frage steht am Anfang jeder Algorithmusentwicklung. Sie entscheidet, wie fein man zerlegen muss.

  2. 2

    Die Idee: einen Zwischenstand mitführen

    Man merkt sich die bisher größte Zahl in einem eigenen Namen, hier max\text{max}. Am Anfang ist das einfach die erste Zahl, denn wenn man nur eine gesehen hat, ist sie zwangsläufig die größte davon.

    \text{max} := x

    Zwischenergebnis

    Nach Schritt 2 gilt: max\text{max} ist die größte der bisher betrachteten Zahlen.

  3. 3

    Jede weitere Zahl einzeln prüfen

    Für jede weitere Zahl gilt dieselbe Frage: Ist sie größer als der bisherige Zwischenstand? Wenn ja, wird sie der neue Zwischenstand; wenn nein, bleibt alles, wie es war.

    \text{wenn } y > \text{max} \text{ dann } \text{max} := y

    Zwischenergebnis

    Nach Schritt 3 stimmt die Aussage auch für xx und yy, nach Schritt 4 für alle drei.

  4. 4

    Teil c): Warum die Kurzfassung nicht genügt

    „Nimm die größte“ beschreibt das Ziel, nicht den Weg. Ein Algorithmus muss aber sagen, wie man dorthin kommt, und zwar in Schritten, die der Ausführende beherrscht.

    Zwischenergebnis

    Die Anweisung ist zwar eindeutig gemeint, aber nicht ausführbar im Sinne der Grundoperationen.

    Dieselbe Falle steckt in Formulierungen wie „sortiere die Liste“ oder „finde den kürzesten Weg“. Das sind Aufgabenstellungen, keine Algorithmen.

Übung 3

schwer

a) Eine Rundreise soll die kürzeste Strecke durch 20 Städte finden. Es gibt einen Algorithmus, der alle Reihenfolgen durchprobiert. Warum hilft er praktisch nicht? b) Erkläre den Unterschied zwischen „für dieses Problem kennt man noch keinen schnellen Algorithmus“ und „für dieses Problem kann es keinen Algorithmus geben“. c) Ein Mitschüler behauptet: „Ein Algorithmus muss immer eine Wiederholung enthalten.“ Widerlege ihn. d) Warum ist die Anweisung „Prüfe, ob dieses Programm jemals anhält“ für beliebige Programme nicht algorithmisch lösbar? Beschreibe nur die Aussage, nicht den Beweis.

Tipp anzeigen

Zu a): Rechne aus, wie viele Reihenfolgen es gibt, und teile durch eine Milliarde pro Sekunde.

Lösung anzeigen

a) Bei 20 Städten gibt es rund 19!≈1,2⋅101719! \approx 1{,}2 \cdot 10^{17} Reihenfolgen. Bei einer Milliarde geprüfter Reihenfolgen pro Sekunde dauert das etwa 1,2⋅1081{,}2 \cdot 10^{8} Sekunden, also fast vier Jahre. Bei 25 Städten wären es Milliarden Jahre. Der Algorithmus ist korrekt und trotzdem unbrauchbar; man braucht Verfahren, die eine gute statt der besten Lösung liefern.

b) Der erste Satz ist eine Aussage über den heutigen Wissensstand; morgen kann jemand einen schnellen Algorithmus finden. Der zweite ist eine Aussage über die Sache selbst und beweisbar; sie kann durch keinen künftigen Einfall und keine schnellere Hardware widerlegt werden.

c) Gegenbeispiel genügt: Der Algorithmus zur Rechteckfläche (einlesen, multiplizieren, ausgeben) enthält keine Wiederholung und erfüllt trotzdem alle vier Eigenschaften. Eine Wiederholung ist ein nützlicher Baustein, keine Bedingung.

d) Die Aussage lautet: Es gibt kein Programm, das für jedes beliebige andere Programm samt Eingabe zuverlässig entscheidet, ob dieses anhält oder ewig läuft. Für viele Einzelfälle kann man die Frage sehr wohl beantworten; unmöglich ist nur ein Verfahren, das alle Fälle korrekt entscheidet.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) Korrekt und trotzdem unbrauchbar: erst rechnen, dann urteilen

    Bei 20 Städten gibt es rund 19!≈1,2⋅101719! \approx 1{,}2 \cdot 10^{17} Reihenfolgen. Prüft man eine Milliarde davon je Sekunde, dauert das etwa 1,2⋅1081{,}2 \cdot 10^{8} Sekunden, also fast vier Jahre. Der Algorithmus ist korrekt und liefert die beste Lösung, nur nicht zu Lebzeiten.

    1,2⋅1017:109=1,2⋅108 s≈3,8 Jahre1{,}2 \cdot 10^{17} : 10^{9} = 1{,}2 \cdot 10^{8}\ \text{s} \approx 3{,}8\ \text{Jahre}

    Zwischenergebnis

    Rund vier Jahre für 20 Städte.

  2. 2

    b) Wissensstand gegen Sachaussage

    „Man kennt noch keinen schnellen Algorithmus“ ist eine Aussage über den heutigen Wissensstand, morgen kann jemand einen finden. „Es kann keinen Algorithmus geben“ ist eine Aussage über die Sache selbst, sie ist beweisbar und durch keinen künftigen Einfall und keine schnellere Hardware widerlegbar.

  3. 3

    c) Eine Behauptung mit einem Gegenbeispiel widerlegen

    Die Behauptung „ein Algorithmus muss immer eine Wiederholung enthalten“ fällt durch ein einziges Gegenbeispiel: Der Algorithmus zur Rechteckfläche (einlesen, multiplizieren, ausgeben) enthält keine Wiederholung und erfüllt trotzdem alle vier Eigenschaften. Eine Wiederholung ist ein nützlicher Baustein, keine Bedingung.

  4. 4

    d) Die Aussage des Halteproblems genau formulieren

    Die Aussage lautet: Es gibt kein Programm, das für jedes beliebige andere Programm samt Eingabe zuverlässig entscheidet, ob dieses anhält oder ewig läuft. Für viele Einzelfälle kann man die Frage sehr wohl beantworten; unmöglich ist nur ein Verfahren, das alle Fälle korrekt entscheidet.

Zusammenfassung

Ein Algorithmus ist eine Handlungsvorschrift, die allgemeingültig, ausführbar, endlich und eindeutig ist. Jede dieser Eigenschaften verhindert eine eigene Fehlerart: den Einzelfall statt der Klasse, den undurchführbaren Schritt, die endlose Ausführung und das mehrdeutige Verständnis. Aus einem Beispiel wird ein Algorithmus, indem man feste Zahlen durch Eingabegrößen ersetzt. Aufschreiben lässt er sich verbal, als Ablaufdiagramm oder als Pseudocode, wobei alle drei Darstellungen dieselbe Vorschrift beschreiben. Die Grenzen sind von drei Arten und dürfen nicht vermischt werden: Manche Aufgaben sind gar nicht eindeutig gestellt, manche Verfahren dauern selbst auf schnellen Rechnern zu lange, und für manche Fragen ist bewiesen, dass es keinen Algorithmus geben kann.