Algorithmen untersuchen
- Wie lässt sich „Algorithmen untersuchen“ mit einem Modell erklären?
- Ist die Anweisung für jede Person eindeutig und endet der Ablauf sicher?
- Wie kann ich meine Lösung testen und verständlich dokumentieren?
Themen in diesem Bereich
Eigenschaften von Algorithmen
Algorithmen erfüllen verschiedene Bedingungen.
Determiniertheit
Ein Algorithmus ist determiniert, wenn er bei gleichen Startbedingungen und der gleichen Eingabe immer das gleiche Ergebnis liefert.
Terminiertheit
Ein Algorithmus ist terminierend, wenn er immer nach endlich vielen Schritten anhält/abbricht.
Beispiel: Fibonacchi-Zahlen
Die Fibonacchi-Zahlen sind die Zahlenreihe 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Dabei kommt auf die nächste Zahl, indem man die beiden Zahlen davor addiert: Die 6. Zahl ist 3 + 5 = 8, die 7. Zahl ist 5 + 8 = 13, usw.
Der einfachste Algorithmus, um eine beliebige Fibonacchi-Zahl zu berechnen:
$$fib(x)\;=\left\{\begin{array}{lc}1&falls\;x=1\;oder\;x=2\\fib(x-2)+fib(x-1)&falls\;x>2\end{array}\right.$$
Der Algorithmus gibt 1 für die ersten beiden Fibonacchi-Zahlen zurück. Danach ergibt es immer die Summe der vorherigen Fibonacchi-Zahlen.
Der Algorithmus ist deterministisch, denn wenn man den Algorithmus 1000 Mal für das gleiche x anwendet, erhält man jedes Mal das gleiche Ergebnis.
Der Algorithmus ist terminierend. Zwar wendet sich der Algorithmus sich selbst an, was zuerst nach einer Endlosschleife klingt. Aber da dabei das x immer kleiner wird, gelangt man irgendwann am Anfang der Fibonacchi-Reihe, wo die Endlosschleife abgebrochen wird.
Hier ist die Ausführung für x = 5 als Baum dargestellt:
Fibonacchi in Java
Der obige Algorithmus ließe sich in der Programmiersprache Java folgendermapen programmieren:
Beispiel: Fakultät
Die Fakultät von x ist das Produkt aller Zahlen von 1 bis x. Die Fakultät von 5 ist zum Beispiel 1 × 2 × 3 × 4 × 5 = 120. Der Algorithmus lässt sich so formulieren:
- Setze y auf 1
- Falls x = 1, wird der Algorithmus beendet, das Ergebnis ist y
- Multipliziere y mit x.
- Verringere x um 1.
- Fahre mit Punkt 2 fort.
Das passiert für x = 5:
Fakultät in Java
Der obige Algorithmus ließe sich in Java folgendermapen programmieren:
Erklärung von Serlo Education e. V., lizenziert unter CC BY-SA 4.0 – Original bei Serlo, CC BY-SA 4.0, übernommen am 2026-09-03.
Schlau Fassung
Algorithmen untersuchen Algorithmen werden nicht nur ausgeführt, sondern auf Korrektheit, Verständlichkeit und Aufwand geprüft. Zwei richtige Verfahren können unterschiedlich schnell sein.
Algorithmen untersuchen ist in der Informatik kein isolierter Merksatz. Entscheidend ist, welche Daten oder Zustände am Anfang vorliegen, nach welcher Regel sie verarbeitet werden und wie sich das Ergebnis überprüfen lässt. Bei tausend Namen ist eine alphabetisch sortierte Liste mit Halbierungssuche deutlich schneller als das Prüfen jedes Eintrags.
Beim Bearbeiten trennst du deshalb Beobachtung und Vermutung: Zuerst beschreibst du, was tatsächlich eingegeben, gespeichert, übertragen oder ausgegeben wird. Danach begründest du mit Fachbegriffen, warum der Ablauf so funktioniert.
Drei Bausteine, die du sicher können musst
Jeder Schritt ist ohne Raten ausführbar.
Der Ablauf erreicht nach endlich vielen Schritten ein Ende.
Eingabe und erwartetes Ergebnis prüfen einen bestimmten Weg.
Ausgearbeitetes Beispiel
Ausgangslage: Bei tausend Namen ist eine alphabetisch sortierte Liste mit Halbierungssuche deutlich schneller als das Prüfen jedes Eintrags.
- Modell festlegen: Benenne Eingaben, gespeicherte Werte und die gewünschte Ausgabe.
- Regel anwenden: Formuliere die Verarbeitung so genau, dass eine andere Person jeden Schritt wiederholen kann.
- Ergebnis prüfen: Vergleiche die beobachtete Wirkung mit einer vorher notierten Erwartung und untersuche mindestens einen Randfall.
Begründung: Algorithmen werden nicht nur ausgeführt, sondern auf Korrektheit, Verständlichkeit und Aufwand geprüft. Zwei richtige Verfahren können unterschiedlich schnell sein. Dadurch wird nicht nur das Ergebnis, sondern auch sein Zustandekommen nachvollziehbar.
So gehst du informatisch vor
Fachbegriffe in eigenen Worten
- Eindeutigkeit
- Jeder Schritt ist ohne Raten ausführbar.
- Endlichkeit
- Der Ablauf erreicht nach endlich vielen Schritten ein Ende.
- Testfall
- Eingabe und erwartetes Ergebnis prüfen einen bestimmten Weg.
Aufgaben
- StartBegriffe sichern: Erkläre „Algorithmen untersuchen“ in mindestens vier Sätzen und verwende zwei Begriffe aus dem Glossar.
Musterlösung
Algorithmen werden nicht nur ausgeführt, sondern auf Korrektheit, Verständlichkeit und Aufwand geprüft. Zwei richtige Verfahren können unterschiedlich schnell sein. Bei tausend Namen ist eine alphabetisch sortierte Liste mit Halbierungssuche deutlich schneller als das Prüfen jedes Eintrags. Eine vollständige Antwort benennt zusätzlich Eingabe oder Ausgangszustand, Verarbeitung und überprüfbares Ergebnis. - OrdnenModell bilden: Zerlege das Beispiel der Seite in Ausgangslage, Regel, Ergebnis und Test.
Musterlösung
Ausgangslage: die im Beispiel genannten Daten oder Geräte. Regel: der beschriebene Verarbeitungsschritt. Ergebnis: die sichtbare Wirkung. Test: ein normaler Fall und ein bewusst veränderter Randfall. - AnwendenSelbst lösen: Schreibe einen Algorithmus, der eine Figur vom Start durch ein 4-mal-4-Feld zum Ziel führt, ohne ein Hindernis zu berühren.
Musterlösung
Eine korrekte Lösung nennt Startposition und Blickrichtung und gibt jeden Schritt oder jede geprüfte Bedingung eindeutig an. - FehlersucheDiagnose: Verändere im Beispiel genau eine Voraussetzung. Sage vorher, welche Wirkung du erwartest, und begründe sie.
Lösungshinweis
Eine gute Lösung benennt die veränderte Voraussetzung, den betroffenen Verarbeitungsschritt und eine beobachtbare Ausgabe. Mehrere Dinge gleichzeitig zu ändern erlaubt keine eindeutige Ursache. - TransferNeuer Zusammenhang: Finde ein zweites Beispiel aus Schule oder Alltag und erkläre Gemeinsamkeit sowie Unterschied.
Lösungshinweis
Nutze dieselben Fachbegriffe, aber übertrage sie auf andere Daten, Geräte oder Regeln. Der Unterschied muss fachlich relevant sein und darf nicht nur den Namen betreffen. - ProfiVertiefung: Kürze eine lange Befehlsfolge durch eine Schleife und erkläre, warum beide Fassungen dasselbe leisten.
Lösungshinweis
Suche zuerst den kleinsten Abschnitt, der unverändert mehrfach vorkommt, und bestimme danach die Wiederholungszahl.
Weiterführende Aufgaben
Abgabe in fünf Teilen
- Ziel: Ein Satz, der messbar sagt, was funktionieren soll.
- Plan: Skizze, Ablaufplan, Tabelle oder Pseudocode.
- Produkt: Programm, Modell, Untersuchung oder dokumentierter Versuch.
- Tests: Normalfall, Randfall und mindestens ein absichtlich provozierter Fehler.
- Reflexion: Gefundener Fehler, vorgenommene Verbesserung und nächster sinnvoller Schritt.
Bewertungsraster für Partnerfeedback
- Fachlich richtig und mit passenden Begriffen erklärt
- Plan und Ergebnis stimmen sichtbar überein
- Tests sind reproduzierbar dokumentiert
- Quellen, Bilder und fremde Hilfen sind angegeben