Algorithmus

Wenn du morgens nach einem Rezept Pfannkuchen machst, eine Route zur Schule suchst oder eine Liste sortierst, folgst du einer Schrittfolge. In der Informatik nennt man eine solche präzise Schrittfolge Algorithmus. Nach dieser Erklärung kannst du Algorithmen erkennen, ihre Eigenschaften prüfen und einfache Verfahren in eigenen Worten beschreiben.

Deine Lernziele

• Ich kann erklären, was ein Algorithmus ist.
• Ich kann Eingabe, Verarbeitung und Ausgabe unterscheiden.
• Ich kann Eigenschaften wie Eindeutigkeit, Ausführbarkeit und Endlichkeit prüfen.
• Ich kann Algorithmus, Programm und Heuristik voneinander abgrenzen.
• Ich kann einfache Algorithmen mit Schleifen und Verzweigungen verstehen.

Eine Anleitung, die wirklich ausführbar ist

Nicht jede Anleitung ist automatisch ein guter Algorithmus. "Mach das Bild schöner" ist zu ungenau. "Erhöhe die Helligkeit jedes Pixels um 10, höchstens bis 255" ist viel präziser.

Definition

Algorithmus

Ein Algorithmus ist eine eindeutige, ausführbare und endliche Schrittfolge zur Lösung eines Problems oder einer Problemklasse. Er verarbeitet Eingaben und erzeugt Ausgaben.

Definition

Problemklasse

Eine Problemklasse ist eine Gruppe ähnlicher Aufgaben. Ein Sortieralgorithmus soll zum Beispiel nicht nur eine konkrete Liste sortieren, sondern viele mögliche Listen.

Ein Algorithmus kann in Alltagssprache, Pseudocode, einem Flussdiagramm oder einer Programmiersprache formuliert sein. Entscheidend ist nicht die Darstellungsform, sondern ob die Schritte klar genug sind.

Beispiel

Kein guter Algorithmus:

"Sortiere die Namen sinnvoll."

Problem: Was heißt sinnvoll? Nach Vorname? Nach Nachname? Aufsteigend? Absteigend?

Besser:

1. Vergleiche die Nachnamen alphabetisch.
2. Wenn zwei Nachnamen gleich sind, vergleiche die Vornamen.
3. Ordne kleinere Namen vor größeren Namen ein.
4. Wiederhole das, bis die Liste vollständig geordnet ist.

Merke

Ein Algorithmus muss so genau sein, dass ein geeigneter Ausführer bei jedem Schritt weiß, was zu tun ist.

Eingabe, Verarbeitung, Ausgabe

Viele Algorithmen kannst du als EVA-Prinzip lesen: Eingabe, Verarbeitung, Ausgabe. Die Eingabe sind die Daten am Anfang. Die Verarbeitung sind die Schritte. Die Ausgabe ist das Ergebnis.

Definition

Eingabe

Die Eingabe sind die Daten, mit denen ein Algorithmus startet. Beispiele sind eine Zahl, ein Text, eine Liste oder ein Bild.

Definition

Ausgabe

Die Ausgabe ist das Ergebnis, das der Algorithmus nach der Verarbeitung liefert.

Definition

Verarbeitung

Die Verarbeitung ist die Folge von Schritten, mit denen die Eingabe in die Ausgabe umgewandelt wird.

Ohne klare Eingabe und Ausgabe kann man schwer prüfen, ob ein Algorithmus korrekt ist. Ein Suchalgorithmus braucht zum Beispiel eine Liste und einen Suchwert als Eingabe. Als Ausgabe kann er die Position liefern oder melden, dass der Wert nicht vorkommt.

Beispiel

Algorithmus: Größte Zahl in einer Liste finden.

Eingabe:

Liste [4, 9, 2, 7]

Verarbeitung:

1. Merke die erste Zahl als bisher größtes Ergebnis: 4.
2. Vergleiche 9 mit 4. 9 ist größer, also merke 9.
3. Vergleiche 2 mit 9. 9 bleibt größer.
4. Vergleiche 7 mit 9. 9 bleibt größer.

Ausgabe:

9

Eigenschaften guter Algorithmen

In der Schule werden oft mehrere Eigenschaften geprüft. Sie helfen dir zu entscheiden, ob eine Beschreibung wirklich als Algorithmus taugt.

Definition

Eindeutigkeit

Eindeutigkeit bedeutet, dass bei jedem Schritt klar ist, was als Nächstes passiert. Es darf keine unklare Auswahl ohne Regel geben.

Definition

Ausführbarkeit

Ausführbarkeit bedeutet, dass jeder Schritt vom vorgesehenen Ausführer tatsächlich ausgeführt werden kann.

Definition

Endlichkeit

Endlichkeit bedeutet, dass die Beschreibung des Algorithmus endlich lang ist und das Verfahren für die betrachtete Aufgabe nach endlich vielen Schritten zu einem Ergebnis kommen soll.

Ein Algorithmus für einen Menschen darf andere Schritte enthalten als einer für einen Computer. "Schmecke ab" kann für einen Koch ausführbar sein, aber für einen einfachen Roboter ohne Geschmackssensor nicht.

Beispiel

Prüfe diese Anleitung:

"Nimm eine Zahl. Wenn sie gerade ist, teile sie durch 2. Wenn sie ungerade ist, addiere 1. Wiederhole das, bis du zufrieden bist."

Probleme:

• "bis du zufrieden bist" ist nicht eindeutig.
• Die Abbruchbedingung ist unklar.
• Für einen Computer ist "zufrieden" nicht ausführbar.

Besser:

"Wiederhole die Schritte genau 5-mal."

Oder:

"Wiederhole, bis die Zahl 1 erreicht ist."

Merke

Wenn du einen Algorithmus prüfst, frage: Sind die Schritte eindeutig? Kann der Ausführer sie ausführen? Gibt es ein klares Ende?

Schleifen und Verzweigungen

Viele Algorithmen brauchen nicht nur eine gerade Liste von Schritten. Sie müssen Entscheidungen treffen oder Schritte wiederholen.

Definition

Verzweigung

Eine Verzweigung ist eine Wenn-dann-sonst-Entscheidung. Je nach Bedingung wird ein anderer Schritt ausgeführt.

Definition

Schleife

Eine Schleife wiederholt Schritte, solange eine Bedingung gilt oder bis eine bestimmte Anzahl erreicht ist.

Verzweigungen machen Algorithmen flexibel. Schleifen machen sie allgemein: Du musst nicht für jede Listenlänge eine eigene Anleitung schreiben.

Beispiel

Algorithmus: Zähle alle geraden Zahlen in einer Liste.

Eingabe: Liste von Zahlen.

1. Setze anzahl auf 0.
2. Gehe jede Zahl der Liste durch.
3. Wenn die Zahl ohne Rest durch 2 teilbar ist, erhöhe anzahl um 1.
4. Wenn alle Zahlen geprüft wurden, gib anzahl aus.

Für [3, 8, 10, 11, 14] ist die Ausgabe 3.

Gut zu wissen

Eine Schleife ohne sinnvolle Abbruchbedingung kann zur Endlosschleife werden. Manche Systeme laufen absichtlich dauerhaft, zum Beispiel ein Betriebssystem. Für typische Schulalgorithmen zur Berechnung eines Ergebnisses erwartest du aber eine klare Terminierung.

Algorithmus, Programm und Heuristik

Die Begriffe werden im Alltag oft gemischt. Für Informatikaufgaben lohnt die Unterscheidung.

Definition

Programm

Ein Programm ist eine konkrete Umsetzung eines Algorithmus in einer Programmiersprache, sodass ein Computer ihn ausführen kann.

Definition

Heuristik

Eine Heuristik ist eine Vorgehensweise, die oft gute Lösungen findet, aber nicht unbedingt immer die perfekte Lösung garantiert.

Ein Algorithmus ist die Idee der Schrittfolge. Ein Programm ist eine konkrete technische Form davon. Eine Heuristik ist eher eine kluge Suchstrategie, wenn die perfekte Lösung zu teuer, zu langsam oder unbekannt ist.

Beispiel

Navigation zur Schule:

Algorithmus:

"Berechne aus allen möglichen Wegen den kürzesten Weg."

Problem: In großen Netzen kann das aufwendig sein.

Heuristik:

"Bevorzuge zuerst Hauptstraßen und meide bekannte Baustellen."

Das kann sehr gut funktionieren, garantiert aber nicht in jedem Sonderfall den mathematisch kürzesten Weg.

Merke

Algorithmus ist die Schrittidee. Programm ist die Umsetzung. Heuristik ist eine oft nützliche, aber nicht immer perfekte Strategie.

Prüfungsmodus

Wenn du einen Algorithmus entwerfen sollst, starte nicht mit Code. Beschreibe erst Eingabe, Ausgabe und die Hauptidee. Danach formulierst du die Schritte.

Beispiel

Aufgabe:

"Entwirf einen Algorithmus, der prüft, ob ein Wort den Buchstaben a enthält."

Eingabe:

Ein Wort.

Ausgabe:

Ja oder Nein.

Algorithmus:

1. Gehe die Buchstaben des Wortes von links nach rechts durch.
2. Wenn der aktuelle Buchstabe a ist, gib "Ja" aus und stoppe.
3. Wenn alle Buchstaben geprüft wurden und kein a gefunden wurde, gib "Nein" aus.

Warum ist das allgemein? Es funktioniert für Wörter unterschiedlicher Länge.

Alles auf einen Blick

Abschluss-Check

Zusammenfassung

Ein Algorithmus ist eine klare Schrittfolge, die Eingaben verarbeitet und Ausgaben erzeugt. Gute Algorithmen sind eindeutig, ausführbar und für die Aufgabe endlich formuliert.

Wichtige Bausteine sind Verzweigungen und Schleifen. Mit ihnen kann ein Verfahren Entscheidungen treffen und wiederholt auf beliebig viele Daten anwenden.

Ein Programm ist die konkrete Umsetzung eines Algorithmus. Eine Heuristik ist eine praktische Strategie, die oft gute Lösungen findet, aber nicht immer eine perfekte Lösung garantiert.