Mit Google fortfahren
Algorithmus einfach erklärt: Merkmale und Beispiele
Ein Algorithmus ist eine genaue Schrittfolge, die eine Eingabe nach festen Regeln verarbeitet und zu einer Ausgabe führt. Er beschreibt also nicht nur das Ziel, sondern auch den Weg dorthin. Auf dieser Seite lernst du, Algorithmen zu erkennen, zu prüfen und von Programmen zu unterscheiden.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Vom Ziel zur genauen Schrittfolge
Die Anweisung „Ordne die Karten“ nennt ein Ziel. Sie sagt aber nicht, welche Karte du zuerst vergleichst, wie du sie verschiebst oder wann du fertig bist. Für eine Maschine ist das zu ungenau.
Algorithmus
Ein Algorithmus ist eine endlich beschriebene Folge ausführbarer und eindeutig geregelter Schritte zur Lösung eines Problems oder einer Problemklasse. Er verarbeitet eine Eingabe und erzeugt daraus eine Ausgabe.
Ein Algorithmus kann in Alltagssprache, als grafischer Ablauf oder in einer Programmiersprache dargestellt werden. Entscheidend ist nicht die Darstellungsform, sondern ob die Schritte genau genug sind.
Ziel: Eine unverschlossene Tür öffnen, die sich zu dir hin öffnet.
„Öffne die Tür“ reicht nur dann als Schritt, wenn die ausführende Person oder Maschine diese Grundoperation bereits beherrscht. Andernfalls muss die Handlung genauer zerlegt werden, zum Beispiel: Klinke herunterdrücken, Tür zu dir ziehen, Klinke loslassen.
Daran siehst du: Ob ein Schritt ausführbar ist, hängt von den Fähigkeiten des Ausführenden ab.
Woran du einen Algorithmus erkennst
Vier Fragen helfen dir beim Prüfen:
- Ausführbarkeit: Kann der vorgesehene Mensch oder die Maschine jeden Einzelschritt ausführen?
- Eindeutigkeit: Ist in jeder Situation geregelt, welcher Schritt als Nächstes folgt?
- Endlichkeit: Lässt sich die Vorschrift in einem endlichen Text vollständig angeben?
- Allgemeinheit: Löst sie eine ganze Problemklasse und nicht nur einen einzigen vorbereiteten Fall?
Allgemeinheit ist nur nötig, wenn tatsächlich eine Problemklasse gelöst werden soll. Für die Aufgabe „Vergleiche genau A, B und C“ darf ein Verfahren auf diese drei Gegenstände zugeschnitten sein.
Eine Wiederholungsregel wie „Solange noch Schachteln vorhanden sind“ kann endlich beschrieben sein, obwohl sie je nach Eingabe unterschiedlich oft ausgeführt wird.
Oft wird zusätzlich Terminierung verlangt: Der Algorithmus endet für jede zulässige Eingabe nach endlich vielen Schritten und liefert ein Ergebnis oder bricht geregelt ab. Dauerhaft laufende Systeme wie ein Betriebssystem sollen dagegen absichtlich weiterarbeiten. Je nach genauer Definition bezeichnet man solche Abläufe deshalb nicht als terminierende Algorithmen, sondern allgemeiner als rechnergestützte Verfahren.
In der theoretischen Informatik wird genauer unterschieden: deterministisch bedeutet, dass jederzeit genau ein nächster Schritt feststeht. Determiniertheit bedeutet, dass gleiche Eingaben zum gleichen Ergebnis führen. Ein festgelegter Weg führt bei gleichen Bedingungen zum gleichen Ergebnis; derselbe Ergebniswert kann aber auch über unterschiedlich gewählte Wege erreicht werden.
So findest du die schwerste Schachtel
Du hast vier Schachteln mit den Gewichten A: 8 g, B: 3 g, C: 11 g und D: 7 g. Die Waage kann immer zwei Schachteln vergleichen.
Eingabe: die vier Schachteln
Verarbeitung:
- Behalte A zunächst als Kandidatin.
- Vergleiche die Kandidatin nacheinander mit jeder übrigen Schachtel.
- Ist die neue Schachtel schwerer, wird sie zur neuen Kandidatin. Sonst bleibt die bisherige Kandidatin.
- Sind alle Schachteln geprüft, gib die Kandidatin aus.
| Vergleich | Schwerere Kandidatin danach | Begründung |
|---|---|---|
| A mit B | A mit 8 g | 8 g sind 5 g mehr als 3 g. |
| A mit C | C mit 11 g | 11 g sind 3 g mehr als 8 g. |
| C mit D | C mit 11 g | 11 g sind 4 g mehr als 7 g. |
Ausgabe: C ist mit 11 g die schwerste Schachtel.
Nach jedem Vergleich ist die Kandidatin die schwerste aller bisher geprüften Schachteln. Deshalb ist sie nach dem letzten Vergleich auch die schwerste der gesamten Eingabe. Bei gleichem Gewicht kann die bisherige Kandidatin bleiben; ihr Gewicht ist trotzdem maximal.
Vom Algorithmus zum Programm
Ein Algorithmus ist das abstrakte Verfahren. Ein Programm ist seine konkrete Umsetzung in einer Programmiersprache für einen Computer. Derselbe Algorithmus kann in verschiedenen Programmiersprachen programmiert werden.
Das Grundmuster lautet:
Eingabe → Verarbeitung nach Regeln → Ausgabe
Ein Verfahren soll die größere von zwei Zahlen ausgeben.
- Eingabe: zwei Zahlen
xundy - Regel: Wenn
xgrößer alsyist, gibxaus; sonst gibyaus. - Ausgabe: der größere Zahlenwert
Für x = 3 und y = 5 folgt die Ausgabe 5. Sind beide Werte gleich, gibt der Sonst-Fall y aus; der ausgegebene Zahlenwert bleibt korrekt.
Ein Programm muss die Regeln in Befehle übersetzen, die seine Programmiersprache und der Computer ausführen können. Dabei können Variablen Eingaben oder Zwischenergebnisse speichern, Bedingungen zwischen Fällen wählen und Schleifen Schritte wiederholen. Diese Bausteine gehören zur Umsetzung; die zugrunde liegende Lösungsidee bleibt der Algorithmus.
Gute Algorithmen auswählen und verbessern
Für dasselbe Problem kann es mehrere korrekte Algorithmen geben. Sie können sich darin unterscheiden, wie viel Zeit, Speicher oder andere Ressourcen sie benötigen. Welche Lösung geeignet ist, hängt von der Eingabe und vom Ziel ab.
Beim Finden der schwersten Schachtel wäre es unnötig, erst alle Schachteln vollständig nach Gewicht zu sortieren. Wenn nur das Maximum gesucht ist, reichen fortlaufende Vergleiche mit einer Kandidatin.
„Korrekt“ beantwortet die Frage: Liefert das Verfahren das richtige Ergebnis? „Geeignet“ fragt zusätzlich: Passt sein Aufwand zur Aufgabe und zu den verfügbaren Mitteln?
So verbesserst du eine unklare Schrittfolge:
- Markiere die erste Stelle, an der mehrere Deutungen möglich sind.
- Benenne die verfügbaren Grundoperationen.
- Ersetze das unklare Ziel durch ausführbare Einzelschritte.
- Ergänze bei Verzweigungen eine Bedingung.
- Ergänze bei Wiederholungen eine klare Endbedingung.
- Prüfe den Ablauf mit normalen Fällen und Randfällen, etwa gleichen Eingabewerten.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Algorithmus
- Aufbau
- Eingabe, Verarbeitung, Ausgabe
- genaue Schrittfolge
- Prüfkriterien
- ausführbar und eindeutig
- endlich beschrieben und passend allgemein
- bei terminierenden Algorithmen mit Endbedingung
- Umsetzung
- abstraktes Verfahren wird zum Programm
- Bedingungen wählen, Schleifen wiederholen
- Bewertung
- Korrektheit des Ergebnisses
- Zeit, Speicher und Einsatzbedingungen
- Aufbau