Einstieg in die Algorithmik

Einleitung

Algorithmen – also abstrakte Beschreibungen von Programmen oder allgemeiner: Lösungsverfahren für bestimmte Aufgabenstellungen – sind uns bereits in mehreren Zusammenhängen begegnet: In der visuellen Programmierung haben wir selbst Algorithmen entwickelt und in der Programmiersprache Scratch umgesetzt, etwa um eine Spielfigur zu steuern oder ein Quiz zu entwickeln, im Kapitel “Informationsdarstellung” wurden Algorithmen zum Berechnen von Prüfziffern für Barcodes oder zur Datenkompression behandelt.

In diesem Kapitel werden wir Algorithmen unter abstrakteren Gesichtspunkten betrachten, also welche Eigenschaften Algorithmen haben, welche grundlegenden Strategien sich in Algorithmen finden lassen, und wie sich Algorithmen unabhängig von einer konkreten Programmiersprache formulieren lassen.

Dieser allgemeinere Blick ist sinnvoll, da die Bildungsziele, die mit den Themen “Programmierkompetenz” und “Algorithmik” verknüpft sind, weniger auf rein technisches Verständnis abzielen, also etwa das Beherrschen einzelner Programmiersprachen, sondern auf die Förderung des sogenannten “algorithmischen Denkens” (Computational Thinking) als Metakompetenz.

So heißt es in den Fachanforderungen in der Einleitung zum inhaltsbezogenen Kompetenzbereich “Algorithmen und Programmierung”:

Indem die Schülerinnen und Schüler Handlungsabläufe in natürlicher Sprache strukturiert darstellen, erlernen sie mit Kontrollstrukturen die Grundelemente imperativer Programme sowie des algorithmischen Denkens (Computational Thinking).

Computational Thinking

Der Begriff “Computation Thinking”¹ (oft als “Informatisches Denken” oder “Algorithmisches Denken” übersetzt) bezeichnet kurz zusammengefasst eine Kompetenz zum (meist maschinellen) Lösen komplexer Probleme. Es beschreibt einen gedanklichen Prozess zur Lösungsplanung, der darauf basiert, Problemstellungen und ihre Lösungen so darzustellen, dass die Problemlösungen auch durch eine Maschine, z. B. einen Computer, durchgeführt werden können. Dazu wird der Lösungsprozess in immer kleinere Teilschritte zerlegt, bis nur noch maschinell durchführbare Grundstrukturen übrigbleiben – also etwa elementare Rechenoperationen bzw. Anweisungen, Sequenzen, Wiederholungen und Fallunterscheidungen.

Computational Thinking wird manchmal fälschlicherweise mit dem Programmieren gleichgesetzt, geht aber als Denkmodell zum Lösen komplexer Probleme darüber hinaus und gilt heute weitestgehend übereinstimmend als Schlüsselkompetenz. Auf der anderen Seite ist aber auch klar, dass Programmierenlernen und der Kompentenzerwerb des “Computational Thinking” intrinsisch miteinander verwoben sind – das Erlernen einer Programmiersprache stellt einen wichtigen Zugang zum “Computational Thinking” dar, während andersherum der strukturierte Problemlöseprozess des “Computational Thinking” eine wesentliche Voraussetzung zum erfolgreichen Entwickeln von Programmen ist.

Was ist ein Algorithmus?

Der Begriff “Algorithmus” lässt sich folgendermaßen definieren:

Die Eingabedaten beschreiben dabei das gegebene Problem und werden durch den Algorithmus verarbeitet, dessen Ausgabedaten die Lösung beschreiben. Die Verarbeitungsvorschrift – also der Algorithmus – muss dabei so präzise und eindeutig formuliert sein, dass selbst eine Maschine (z. B. ein Computer) sie durch stures Befolgen der Befehle durchführen kann.

Alltagsbeispiele, die oft als Analogien für Algorithmen verwendet werden, sind etwa Kochrezepte oder Spielanleitungen.²

Ein Algorithmus lässt sich quasi als abstrakte Form eines Programms auffassen. Programme wiederum setzen Algorithmen in einer konkreten Programmiersprache um, sie implementieren die Algorithmen.

Eigenschaften von Algorithmen

Damit eine Handlungsvorschrift als Algorithmus gilt, muss sie mehrere grundlegende Eigenschaften erfüllen, die sicherstellen, dass auch eine rein maschinelle Ausführung möglich ist:

• Allgemeinheit: Das Lösungsverfahren muss eine ganze Klasse von Problemen lösen und nicht nur eine spezielle Probleminstanz.
  Eine Handlungsanweisung, die angibt, wie die Wurzel der Zahl 81 berechnet wird, wäre nicht allgemein (hier würde es prinzipiell reichen, einfach den Wert 9 zurückzugeben), während eine Anleitung, wie die Wurzel einer beliebigen positiven Zahl berechnet wird, als allgemein gelten würde.

• Ausführbarkeit: Jeder Einzelschritt und jede einzelne Anweisung, die im Algorithmus vorkommt, muss ausführbar sein. Dazu muss jede Anweisung insbesondere so formuliert sein, dass klar ist, wie sie durchgeführt werden muss. Ist eine Anweisung dagegen zu komplex, muss sie gegebenenfalls durch einen Unteralgorithmus in Form von weiteren Einzelschritten präzisiert werden.
  Hierbei spielt die Frage eine Rolle, was als “elementare Anweisung” gilt. Dazu muss berücksichtigt werden, durch wen und in welchem Kontext der Algorithmus ausgeführt wird, und was mit den hierbei verwendeten Objekten gemacht werden kann: Bei einem Computerprogramm ist die Menge der ausführbaren Anweisungen durch die verwendete Programmiersprache und die Methoden der Datenstrukturen beschränkt. Wenn wir unserem Hund (oder vielleicht auch einem Roboterhund) Kunststücke beibringen möchten, müssen wir uns auf die Befehle beschränken, die er versteht.

• Endlichkeit: Die Beschreibung der Handlungsvorschrift muss eine endliche Länge besitzen, also mit endlich vielen Anweisungen auskommen, beispielsweise als Text auf einer Seite. Diese Eigenschaft wird auch als Finitheit oder auch spezifischer als “statische Endlichkeit” bezeichnet, um zu betonen, dass hier die Begrenztheit der Beschreibung des Algorithmus gemeint ist und nicht seiner Ausführungsdauer.

• Eindeutigkeit: Die Abfolge der einzelnen Schritte in der Handlungsvorschrift muss genau festgelegt sein. Zu jedem Zeitpunkt der Ausführung muss also klar sein, welcher Schritt als Nächstes ausgeführt wird. Das bedeutet nicht, dass es nur eine einzige Reihenfolge gibt, in der die Einzelschritte eines Algorithmus durchlaufen werden: Durch bedingte Wiederholungen und Fallunterscheidungen sind je nach Eingabe unterschiedliche Abfolgen möglich. Dabei muss aber klar festgelegt sein, wann und unter welcher Bedingung welcher Weg gewählt wird.

Verfahren, die zufallsbasiert Entscheidungen fällen, zählen aber auch als Algorithmen. Der Begriff der “Eindeutigkeit” wird in der theoretischen Informatik daher noch weiter differenziert in Determinismus und Determiniertheit.

• Determinismus: Ein Algorithmus gilt als deterministisch, wenn er bei wiederholter Ausführung mit der gleichen Eingabe immer den gleichen Ablauf hat – also dieselben Einzelschritte in derselben Reihenfolge durchläuft.

• Determiniertheit: Der Begriff der Determiniertheit ist weniger streng als Determinismus: Ein Algorithmus gilt als determiniert, wenn er bei wiederholter Ausführung mit der gleichen Eingabe immer das gleiche Ergebnis liefert, aber nicht unbedingt immer auf demselben Weg. Das kann etwa der Fall sein, wenn bestimmte Entscheidungen im Algorithmus zufallsbasiert getroffen werden, aber trotzdem sichergestellt ist, dass der Algorithmus immer die richtige (und damit gleiche) Lösung berechnet.³

• Korrektheit: Nicht zuletzt muss das Lösungsverfahren für jede Eingabe die richtige Lösung liefern. Die Korrektheit eines Algorithmus kann exemplarisch anhand von repräsentativen Testfällen gezeigt werden oder mit formalen Methode theoretisch bewiesen werden. Formale Beweise für Algorithmen sind eines der wichtigsten Themengebiete der Theoretischen Informatik, setzen aber höhere mathematische Kenntnisse voraus.

Prozessbezogene Eigenschaften

Ein Algorithmus lässt sich neben seiner Beschreibung auch auf Aspekte untersuchen, die sich auf seinen Ausführungsprozess beziehen.

• Terminiertheit: Ein Algorithmus sollte für jede Eingabe nach einer endlichen Rechenzeit zu einer Lösung kommen – er muss also nach endlich vielen Einzelschritten terminieren. Anderenfalls hätte der Algorithmus keinen praktischen Nutzen.

• Dynamische Endlichkeit: Der Speicherplatz, der während der Ausführung für Variablen und Datenstrukturen benötigt wird, muss ebenfalls endlich sein. In der Praxis muss der Speicherbedarf darüber hinaus in einem angemessenen Rahmen bleiben in Bezug auf das System, auf dem der Algorithmus als Programm ausgeführt werden soll (z. B. auf einem Handy, PC oder einem Hochleistungsrechner).

• Komplexität: Der theoretische Aufwand an Rechenzeit und Speicherbedarf eines Algorithmus wird unter dem Begriff “Komplexität” zusammengefasst.

• Effizienz: Ein Algorithmus gilt als effizient, wenn seine Komplexität – also Rechenzeit und Speicherbedarf in Abhängigkeit von der Größe des Problems – “gut” ist, also so niedrig wie nötig oder möglich für die Problemklasse, die er löst.

Beschreibung von Algorithmen

Wir wissen bereits aus den vorigen Lektionen (z. B. aus der Einführung in die visuelle Programmierung), dass sich Algorithmen mit Hilfe von bestimmten Grundbausteinen konstruieren lassen, nämlich aus:

• einzelnen Anweisungen
• Sequenzen von Grundbausteinen
• Kontrollstrukturen

Die sogenannten Kontrollstrukturen sind spezielle Anweisungen zur Ablaufsteuerung weiterer Grundbausteine. Dazu gehören im Wesentlichen:

• Wiederholungen
• Fallunterscheidungen

Bei Wiederholungen werden bestimmte Grundbausteine mehrmals nacheinander ausgeführt, wobei es in der Regel von bestimmten angegebenen Bedingungen abhängt, wie viele Wiederholungsschritte durchgeführt werden. Bei Fallunterscheidungen (bzw. bedingten Anweisungen) werden bestimmte Grundbausteine in Abhängigkeit von bestimmten Bedingungen ausgeführt oder nicht. Daneben kommen als weitere Bestandteile von Algorithmen Ausdrücke vor, zum Beispiel mathematische Ausdrücke oder Vergleiche, die unter anderem zur Berechnung von Parameterwerten für Anweisungen, Werten für Variablen oder als Bedingungen der Kontrollstrukturen dienen.

Welche Anweisungen konkret ausführbar sind, hängt dabei wie oben erwähnt vom Kontext ab (in der Programmierung z. B. von der verwendeten Programmiersprache). Variablenzuweisungen – also das Speichern eines Wertes, der durch einen Ausdruck berechnet wird, in einer Variablen – sind Anweisungen, die in der imperativen Programmierung in der Regel immer zur Verfügung stehen. In der objektbasierten Programmierung (z. B. in Scratch) gibt es daneben größtenteils Anweisungen, um den Zustand von Objekten zu ändern, sowie Ausdrücke, um ihren Zustand abzufragen (z. B. Position einer Figur auf der Zeichenfläche abfragen oder eine Figur auf der Zeichenfläche um 10 Pixel verschieben).

Beispiel: Code knacken

Als praktisches Beispiel für den Entwurf und die Analyse von Algorithmen soll das folgende Problem betrachtet werden: Angenommen, Sie haben Ihr Fahrrad mit einem Zahlenschloss gesichert, in dem vier Stellen auf die Ziffern 0 bis 9 gedreht werden können. Leider haben Sie die richtige Zahlenkombination vergessen. Es soll nun ein Algorithmus entwickelt werden, der beschreibt, wie sich durch systematisches Überprüfen aller Kombinationen von 0000 bis 9999 die richtige Kombination ermitteln lässt.

Dabei lassen sich die folgenden Aktionen durchführen: Die einzelnen Ziffern können durch Vor- und Zurückdrehen der einzelnen Räder eingestellt werden, und es kann durch Ziehen am Bügel geprüft werden, ob das Schloss für die gerade eingestellte Zahl offen ist.

Tool: In dieser interaktiven Anzeige können Sie Ihren Algorithmus testen.⁴ Klicken Sie die Schaltfläche an, um zu versuchen, das Schloss zu öffnen. Die Schaltfläche setzt das Schloss auf eine zufällige Kombination zurück und legt eine neue Kombination als Lösung fest. Mit den Schaltflächen und können Sie die Anzahl der Stellen verringern (um das Problem zu vereinfachen) oder erhöhen.

Dabei sollten Sie maximal für zwei Stellen versuchen, manuell die richtige Lösung zu finden, da das Ermitteln der richtigen Kombination sehr langwierig werden kann – bei 4 Stellen müssen immerhin 10000 verschiedene Kombinationen ausgetestet werden. Solche Aufgaben sind also eher für Maschinen geeignet, weswegen der Algorithmus möglichst präzise und eindeutig formuliert werden sollte.

Wir untersuchen als Nächstes verschiedene Vorschläge, wie ein Lösungsverfahren formuliert werden könnte, und überprüfen daran jeweils die grundlegenden Eigenschaften von Algorithmen.

1. Ansatz

Der erste Vorschlag, ein Lösungsverfahren zu beschreiben, besteht aus einem einzigen Satz:

• Teste nacheinander jede Kombination der Ziffern 0 bis 9.

Diese Beschreibung ist allgemein, da sie unabhängig davon funktioniert, welches Ergebnis das richtige ist – wenn dagegen nur vorgeschlagen würde “Teste die Zahl 8361” kann das für ein bestimmtes Zahlenschloss die richtige Lösung liefern, im Allgemeinfall aber nicht. Die Beschreibung ist natürlich auch endlich, da sie in einem Satz formuliert wird.

Sie ist allerdings weder ausführbar noch eindeutig: Für Menschen ist die Anleitung aus dem Kontext heraus zwar verständlich, für eine Maschine ist aber im Detail unklar, wie die Einzelschritte ausgeführt werden sollen. Darüber hinaus ist die Reihenfolge der Einzelschritte unklar.

2. Ansatz

Um das Lösungsverfahren möglichst eindeutig und ausführbar zu beschreiben, sollten wir uns also auf einfache, elementare Anweisungen beschränken, die darüber hinaus so formuliert sind, dass klar wird, in welcher Reihenfolge, in Abhängigkeit von welchen Bedingungen und wie oft die Einzelschritte ausgeführt werden sollen:

• Stelle Code 0000 ein
• Versuche Schloss zu öffnen
• Wiederhole bis Schloss offen ist:
  • Stelle nächsten Code ein
  • Versuche Schloss zu öffnen

Diese Anleitung erfüllt die Mindestanforderungen an einen Algorithmus: Sie ist endlich, allgemein, eindeutig und ausführbar, sofern die enthaltenen Anweisungen “stelle Code 0000 ein”, “stelle nächsten Code ein” für das ausführende System verständlich genug sind – anderenfalls müssten wir diese Anweisungen präzisieren, indem wir uns auf elementarste Anweisungen beschränken, was wir im nächsten Abschnitt noch vertiefen werden.

3. Ansatz

Der nächste Vorschlag beinhaltet zufallsbasierte Entscheidungen:

• Wiederhole bis Schloss offen ist:
  • Stelle zufälligen Code ein
  • Versuche Schloss zu öffnen

Auch diese Beschreibung stellt einen Algorithmus dar, sofern die Anweisung “stelle zufälligen Code ein” als ausführbar gilt. Hier wird also ein Zufallszahlengenerator benötigt. Außerdem ist die Anzahl der Wiederholungen hier nicht in jedem Ablauf für dieselbe Eingabe (das heißt hier: für dasselbe Schloss) gleich, der Algorithmus ist also nicht deterministisch. Auf der anderen Seite ist zu jedem Zeitpunkt klar, welche Anweisung als nächste ausgeführt wird, der Algorithmus ist also trotzdem eindeutig.

Diese Beschreibung stellt also ein typisches Beispiel für einen randomisierten Algorithmus dar, also einen Algorithmus, in dem einzelne Entscheidungen zufallsbasiert getroffen werden.³ Theoretisch kann es passieren, dass dieser Algorithmus nie terminiert (wenn zufälligerweise die richtige Zahlenkombination niemals gewählt wird), was aber extrem unwahrscheinlich ist. Wir können davon ausgehen, dass der Algorithmus in endlicher Zeit die richtige Lösung liefert, er ist also determiniert.

4. Ansatz

Betrachten wir noch einen weiteren Ansatz zum Einstellen der richtigen Ziffern:

• Wiederhole für 1. bis 4. Stelle:
  • Wiederhole bis Ziffer an dieser Stelle richtig ist:
    • Stelle nächste Ziffer ein
• Öffne Schloss

Dieses Verfahren ist zwar allgemein, endlich und eindeutig formuliert, für die gegebene Problemstellung aber nicht ausführbar, da die Überprüfung, ob eine Ziffer an einer bestimmten Stelle richtig ist, nicht möglich ist. Wir können nur überprüfen, ob die gesamte eingestellte Zahlenkombination richtig ist, indem wir versuchen, das Schloss zu öffnen.

Auf den Kontext objektbasierter Programmierung übertragen bedeutet das, dass wir hier Methoden von Objekten benötigen würden, die von diesen nicht unterstützt werden.

Zwischenfazit

• Zuerst sollte überlegt werden, welche elementaren Anweisungen und Werteabfragen verwendet werden dürfen, um das Problem zu lösen. Das hängt natürlich stark vom gegebenen Problemkontext ab.
• Diese elementaren Anweisungen werden dann mit den grundlegenden Kontrollstrukturen (“wiederhole solange/bis …”, “falls … mache … sonst …”) kombiniert, um eine eindeutige Abfolge von Einzelschritten zu formulieren.
• Daneben dürfen in der Regel immer auch eigene Variablen zur Problemlösung verwendet werden.⁵ Variablenzuweisungen sind also Anweisungen, die wir unabhängig vom konkreten Problemkontext immer verwenden dürfen.
• Außerdem dürfen immer logische Ausdrücke (z. B. Vergleich, Verknüpfung von Vergleich mit “und”, “oder”) und mathematische Ausdrücke (z. B. Addition, Multiplikation, Funktionsaufrufe) zur Berechnung von Parameterwerten, Variablenwerten oder Bedingungen verwendet werden. Solche Ausdrücke können als allgemein bekannt gelten oder vereinbart werden.

Komplexere Anweisungen können in Form von Unteralgorithmen formuliert werden, ggf. auch mit Parametern (vgl. Unterprogramme in Scratch). Das macht besonders dann Sinn, wenn solche komplexeren Anweisungen an mehreren Stellen im Algorithmus verwendet werden.

Auf diese Weise erhalten wir klar verständliche, wenn auch sprachlich nicht ganz natürlich formulierte Handlungsanweisungen. Diese stark reduzierte und formalisierte Sprache wird als Pseudocode bezeichnet, da sie schon relativ nahe am Code einer Programmiersprache liegt.

Vertiefung: Code knacken

Wir betrachten hier noch einmal den 2. Ansatz für das Ermitteln der richtige Zahlenkombination:

• Stelle Code 0000 ein
• Versuche Schloss zu öffnen
• Wiederhole bis Schloss offen ist:
  • Stelle nächsten Code ein
  • Versuche Schloss zu öffnen

Um das Verfahren in allen Einzelschritten möglichst klar zu beschreiben, beschränken wir uns nun aber bei den elementaren Anweisungen auf die folgenden:⁶

Drehe Stelle ... weiter Versuche Schloss zu öffnen

In Bedingungen und anderen Ausdrücken beschränken wir uns bei den Zustandsabfragen für dieses Problem auf die folgenden:⁷

• Ziffer an Stelle ... ist eine Ziffer zwischen 0 und 9.
• Zustand des Schlosses ist “offen” oder “geschlossen”.

Zur Angabe der Stellenposition sollte hierbei jeweils eine Zahl zwischen 1 und 4 gewählt werden, z. B. “Drehe Stelle 1 weiter”.

Die Anweisungen “stelle Code 0000 ein” und “stelle nächsten Code ein” gelten unter diesen Voraussetzungen als zu komplex und damit als nicht ausführbar. Daher werden wir diese Anweisungen durch Unteralgorithmen präzisieren.

Unteralgorithmen

Code 0000 einstellen

Formulieren wir als Erstes einen Unteralgorithmus für die Anweisung “stelle Code 0000 ein”, d. h. setze alle Stellen auf 0:

• Wiederhole für 1. bis 4. Stelle:
  • Wiederhole solange die aktuelle Stelle ≠ 0 ist:
    • Drehe die aktuelle Stelle weiter

Formulierungen wie “die aktuelle Stelle” können allerdings verwirrend sein und für die maschinelle Ausführung zu unklar. Besser ist es, solche Formulierungen durch Variablen zu präzisieren:

• Setze n auf 1
• Wiederhole 4-mal:
  • Wiederhole solange n-te Stelle ≠ 0:
    • Drehe n-te Stelle weiter
  • Erhöhe n um 1

Hier wird eine Variable n verwendet, um die “aktuelle Stelle” zu kennzeichnen: Wir beginnen bei Stelle 1 und wiederholen für alle Stellen 1 bis 4. Hier ist zu jedem Zeitpunkt klar, was mit der “aktuellen Stelle” gemeint ist.

Nächsten Code einstellen

Sehen wir uns nun an, wie die Anweisung “stelle nächsten Code ein” mit Hilfe elementarer Anweisungen formuliert werden kann: Im Prinzip soll hier nur die letzte Stelle einmal weitergedreht werden. Dabei müssen wir aber Überträge berücksichtigen: Wenn wir die letzte Stelle auf 0 drehen (z. B. von 1899 auf 1890), müssen wir ebenfalls die vorletzte Stelle weiterdrehen (von 1890 auf 1800). Das muss wiederholt werden (1800 auf 1900), bis wir eine Stelle nicht auf 0 gedreht haben, sondern auf eine andere Ziffer.

Wir müssen also einen Algorithmus zur “Addition von 1 mit Übertrag” formulieren:

• Setze n auf 4
• Drehe n-te Stelle weiter
• Wiederhole solange n-te Stelle = 0:
  • Verringere n um 1
  • Drehe n-te Stelle weiter

Wir beginnen bei der letzten Stelle, drehen diese einmal weiter, und solange wir beim Weiterdrehen 0 als neuen Wert der Stelle erhalten wiederholen wir diesen Prozess für die jeweils vorige Stelle. Die Wiederholung lässt sich auch äquivalent mit “bis ungleich 0” statt “solange gleich 0” formulieren:

• Wiederhole bis n-te Stelle ≠ 0:
  • …

Der so formulierte Algorithmus mit Unteralgorithmen ist nun bezüglich der festgelegten elementaren Anweisungen und Zustandsabfragen ausführbar und könnte so auch in einer einfachen Programmiersprache umgesetzt werden.

Sie haben sich eventuell schon gefragt, ob es wirklich nötig ist, zu Beginn die Zahlenkombination 0000 einzustellen. Die Antwort lautet: nein. Im Prinzip können wir von jeder beliebigen Zahlenkombination aus starten – nach spätestens 10000 Versuchen müssen wir den richtigen Code gefunden haben. In diesem Fall müssten wir den Unteralgorithmus “stelle nächsten Code ein” aber anpassen, da es dann passieren kann, dass wir von der Zahlenkombination 9999 aus weiterdrehen.

Warum ist dieser Fall problematisch? Es werden alle Stellen von der 4-ten aus jeweils von 9 auf 0 weitergedreht, bis die 1. Stelle erreicht und auf 0 gedreht wird. Laut Algorithmus wird nun n auf 0 gesetzt und die 0-te Stelle weitergedreht, was Unsinn ist. Dieser Sonderfall ist für Menschen klar (an dieser Stelle wird abgebrochen), für eine Maschine aber nicht: Bei der Programmausführung wird hier in der Regel ein Fehler auftreten, da es keine “0-te Stelle” gibt. Wir müssen die Abbruchbedingung im Algorithmus für diesen Sonderfall also explizit anpassen:

• Wiederhole solange n-te Stelle = 0 und n > 1:
  • …

Auf diese Weise wird die Wiederholung auch dann beendet, wenn die 1. Stelle erreicht und weitergedreht worden ist (auch wenn sie dabei ebenfalls auf 0 gedreht wird).⁸

Algorithmus verallgemeinern

Wir haben so also einen eindeutigen und mit grundlegendsten Anweisungen ausführbaren Algorithmus zum Ermitteln der richtigen Zahlenkombination gefunden, der das Problem allgemein für alle Zahlenschlösser mit 4 Stellen löst – unabhängig davon, was die richtige Kombination ist. Was aber, wenn wir ein Zahlenschloss mit mehr Stellen, ein Schloss mit Buchstabenkombination oder gar ein Schloss mit Farbkombination haben?

Zunächst verallgemeinern wir das Lösungsverfahren weiter, indem wir die Beschränkung auf 4 Stellen aufheben und stattdessen die Anzahl der Stellen als frei wählbaren Eingabeparameter angeben. Nennen wir diesen Wert beispielsweise Anzahl, so muss in den Beschreibungen des Algorithmus und seiner Unteralgorithmen aus diesem Abschnitt jedes Vorkommen des Werts 4 durch den Wert von Anzahl ersetzt werden. Nun lassen sich mit demselben Algorithmen auch Zahlenschlösser mit 3, 5 oder 100 Ziffern knacken, indem einfach der Wert für Anzahl variiert wird.

Ähnlich können wir den Algorithmus so verallgemeinern, dass wir nicht auf die Ziffern 0 bis 9 für die einzelnen Stellen beschränkt sind, sondern beliebige Zeichen für die Kombination verwenden können – etwa die Buchstaben A bis Z, verschiedene Farben oder mysteriöse Symbole. In diesem Fall muss das Zeichen 0 in der Abbruchbedingung des Unteralgorithmus “stelle nächsten Code ein” einfach durch ein beliebiges (z. B. das erste) der verwendeten Zeichen ersetzt werden, das hier mit dem Parameter Startzeichen bezeichnet wird:⁹

• Wiederhole solange n-te Stelle = Startzeichen und n > 1:
  • …

Für ein Buchstabenschloss mit 8 Stellen würden wir den Algorithmus dann mit den konkreten Parameterwerten Anzahl = 8 und Startzeichen = A durchführen (und müssten im schlimmsten Fall 26⁸ ≈ 200 Mrd. verschiedene Kombinationen austesten…).

Auf einer abstrakteren Ebene beschreibt dieser Algorithmus ein sehr einfaches (und im Zweifelsfall sehr aufwendiges) Suchverfahren nach einem Codewort oder Passwort mit einer bestimmten Länge und begrenzten Zeichenmenge, hier durch ein Kombinationsschloss verschaulicht. Dabei werden der Reihe nach alle möglichen Zeichenkombinationen durchgegangen, bis die richtige Kombination gefunden wurde.¹⁰