Algorithmus

Ein Algorithmus ist im D-Book zunächst kein Stück Programmcode, sondern eine präzise Verarbeitungsvorschrift. Er beschreibt ein allgemeines Verfahren, mit dem ein Problem oder eine Klasse gleichartiger Probleme nach einem bestimmten Prinzip gelöst werden kann ^[18]. Das einzelne konkrete Problem entsteht durch Eingabedaten oder Parameter: Ein Verfahren zur Berechnung einer Fakultät beschreibt nicht nur „berechne 7!“, sondern die Problemklasse „berechne n!“ für zulässige Werte von n. Diese Unterscheidung zwischen Problemklasse und konkreter Instanz ist entscheidend, weil sie den Algorithmus von einer einmaligen Tätigkeit trennt ^[18].

Zu einem Algorithmus gehören daher mehrere Kernbestandteile: eine Menge zulässiger Eingaben, ein Verfahren aus ausführbaren Einzelschritten und ein erwarteter Ergebnisbereich. Formal kann man das als Zuordnung von Eingabedaten zu Ausgabedaten lesen. Nicht jede denkbare Zuordnung ist aber algorithmisch realisierbar. Genau hier beginnt die Frage nach Berechenbarkeit: Der Algorithmusbegriff sagt nicht nur, wie ein Verfahren ausgeführt wird, sondern auch, welche Zuordnungen überhaupt durch ein Verfahren beschrieben werden können ^[16].

Algorithmische Eigenschaften beschreiben, unter welchen Bedingungen ein solches Verfahren fachlich brauchbar ist. Finitheit meint zunächst, dass die Beschreibung des Verfahrens endlich ist. Ausführbarkeit meint, dass jeder Schritt so bestimmt ist, dass ein Mensch, eine Maschine oder ein formales Modell ihn tatsächlich ausführen kann. Terminierung meint, dass das Verfahren für die betrachteten Eingaben nach endlich vielen Schritten zu einem Ergebnis kommt. Determiniertheit meint, dass gleiche Eingaben unter gleichen Startbedingungen dasselbe Ergebnis liefern ^{[16] [19]}.

Davon zu unterscheiden ist Determinismus im engeren Sinn: In jedem Schritt ist dann höchstens eine Fortsetzung vorgesehen. Ein nichtdeterministisches Verfahren kann mehrere mögliche Fortsetzungen zulassen; ein stochastisches Verfahren kann Zufall oder Wahrscheinlichkeiten verwenden. Solche Begriffe sind nicht bloße Zusatzwörter, sondern beschreiben, welche Art von Verfahren vorliegt und wie man seine Ausführung, Korrektheit und Wiederholbarkeit beurteilen kann ^[16].

Diese Unterscheidungen erklären, warum der Algorithmusbegriff im D-Book von E3 bis Q3 nicht einfach wiederholt, sondern schrittweise fachlich geschärft wird. In E3 genügt zunächst die Vorstellung genauer Schrittfolgen. In Q1.2 werden Algorithmen als Verfahren analysiert und verglichen. In Q3 wird daraus die Frage, was überhaupt berechenbar und entscheidbar ist.

Der Begriff Algorithmus führt sprachgeschichtlich zurück auf mhd. algorismus: Rechenkunst, besonders das Rechnen mit dem dezimalen Stellenwertsystem. Über mlat. algorismus geht das Wort letztlich auf Al-Ḫwārizmī zurück, den Beinamen des Mathematikers Muḥammad ibn Mūsā al-Ḫwārizmī aus dem 9. Jahrhundert. Seit dem 16. Jahrhundert setzt sich die Form Algorithmus durch; sie lehnt das Wort zusätzlich an griech. arithmós, „Zahl“, an. Für den heutigen informatischen Begriff ist daran entscheidend: Algorithmus meint nicht mehr nur Rechenkunst, sondern ein System von Regeln zur schrittweisen formalen Verarbeitung von Zeichen, Daten oder Informationen ^[17].

Ein Algorithmus kann in natürlicher Sprache, in Pseudocode, als Struktogramm, als Flussdiagramm, als mathematische Definition oder als Programm dargestellt werden. Diese Darstellungen sind nicht identisch mit dem Algorithmus selbst. Sie machen dasselbe Verfahren in unterschiedlichen Zeichensystemen sichtbar und ausführbar ^[16].

Die Grenze zum Programm ist fachlich wichtig. Ein Programm ist eine Codierung eines Algorithmus in einer für eine Maschine oder Laufzeitumgebung verständlichen Form ^[19]. Der Algorithmus beschreibt das Verfahren; das Programm bindet dieses Verfahren an eine konkrete Sprache, Syntax, Bibliothek, Maschine, Speicherorganisation und Ausführungsumgebung.

Schneider/Oldenbourg betonen, dass ein Algorithmus aus elementaren Anweisungen an einen menschlichen oder maschinellen Rechner bestehen kann ^[18]. Für den Unterricht ist diese Formulierung nützlich, weil sie den Begriff nicht vorschnell auf Java-Code verengt. Ein Kochrezept, eine Bauanleitung oder eine Spielregel ist aber nur dann algorithmusähnlich, wenn die Schritte hinreichend eindeutig, ausführbar und auf eine Problemklasse übertragbar sind.

In E3 begegnet Algorithmus häufig zuerst als Programmtext: Variablen werden gesetzt, Bedingungen geprüft, Schleifen wiederholt, Methoden aufgerufen. Diese technischen Bestandteile sind wichtig, aber sie sind nicht automatisch der begriffliche Kern. Ein Java-Programm kann unübersichtlich sein und trotzdem ein einfaches Verfahren implementieren; umgekehrt kann ein klar beschriebener Algorithmus in vielen Programmiersprachen unterschiedlich umgesetzt werden.

Formale Informatik schärft diese Unterscheidung weiter. Algorithmen können durch mathematisch präzise Maschinenmodelle beschrieben werden, etwa durch Turingmaschinen, Registermaschinen oder andere abstrakte Berechnungsmodelle ^[16]. Solche Modelle zeigen, dass es beim Algorithmusbegriff nicht um eine bestimmte Programmiersprache geht, sondern um die Frage, welche Schrittfolgen überhaupt als mechanisch ausführbare Verfahren gelten können.

Im D-Book verbindet dieser Abschnitt deshalb mehrere Ebenen: die alltagssprachliche Handlungsvorschrift, die schulische Darstellung als Struktogramm oder Pseudocode, die konkrete Implementierung in Java und die theoretische Fassung durch Maschinenmodelle. Diese Ebenen müssen unterschieden werden, ohne auseinanderzufallen.

Algorithmen werden nicht nur beschrieben, sondern ausgeführt, beobachtet und analysiert. Bei der Ausführung entsteht eine Folge von Zuständen: Eingabedaten werden gelesen, Variablen verändert, Bedingungen ausgewertet, Schleifen wiederholt und Zwischenergebnisse erzeugt. Die jeweils nächste auszuführende Anweisung ergibt sich aus Algorithmustext, Eingabe und bereits berechneten Zwischenergebnissen ^[18].

Eine Ablaufverfolgung oder ein Trace macht diese Zustandsfolge sichtbar. Man notiert nicht nur, dass ein Verfahren funktioniert, sondern welche Werte zu welchem Zeitpunkt vorliegen und welcher Schritt als nächstes ausgeführt wird. Dadurch werden Schleifen, Verzweigungen, Rekursion und Zwischenergebnisse nachvollziehbar. Für Lernende ist das die Brücke zwischen Programmlisting und Verfahren.

Algorithmusanalyse fragt anschließend nach Eigenschaften des Verfahrens. Korrektheit bedeutet, dass der Algorithmus für zulässige Eingaben das erwartete Ergebnis liefert. Terminierung fragt, ob er für diese Eingaben tatsächlich anhält. Laufzeitanalyse beschreibt, wie die Anzahl der Schritte mit der Eingabegröße wächst. Speicheranalyse fragt, wie viele zusätzliche Datenstrukturen oder Speicherplätze benötigt werden. Diese Fragen machen aus einer bloßen Programmausführung eine fachliche Untersuchung ^[16].

Mehrere Algorithmen können dieselbe Problemklasse lösen. Für Suchen, Sortieren, kürzeste Wege oder rekursive Berechnungen gibt es unterschiedliche Verfahren mit verschiedenen Voraussetzungen und Kosten. Sobald ein korrektes Verfahren gefunden ist, verschiebt sich die Frage häufig: Gibt es ein schnelleres, speichersparenderes, verständlicheres oder robusteres Verfahren? Genau hier wird Effizienz zum fachlichen Kriterium ^[16].

Komplexitätsklassen fassen solche Aufwandsunterschiede abstrakter. Sie ordnen Verfahren oder Probleme danach ein, wie ihr Ressourcenbedarf mit der Eingabegröße wächst. Fischer/Hofer nennen Komplexitätsklassen deshalb als Anschlussdimension des Algorithmusbegriffs ^[19]. Im D-Book wird diese Idee zuerst konkret aufgebaut: lineare Suche, binäre Suche, Sortierverfahren, rekursive Verfahren und Graphalgorithmen machen sichtbar, dass Verfahren nicht nur richtig, sondern unterschiedlich effizient sein können.

Der Artikel behandelt Algorithmus deshalb nicht als isolierte Definition. Er verbindet Darstellung, Ausführung, Trace, Korrektheitsidee, Terminierung, Ressourcenbedarf und Vergleichbarkeit. Diese Verbindung erklärt, warum Algorithmik im D-Book nicht nur ein Programmierthema ist, sondern ein zentrales Strukturprinzip informatischen Denkens.

Die formale Schärfung des Algorithmusbegriffs beginnt dort, wo die bloße Vorstellung einer Schrittfolge nicht mehr ausreicht. In der theoretischen Informatik muss präzisiert werden, was „ausführbar“, „berechenbar“ und „mechanisch beschreibbar“ heißt. Claus/Schwill führen diese Perspektive über berechenbare Zuordnungen, rekursive Funktionen und mathematisch exakte Maschinenmodelle aus ^[16].

Ein Maschinenmodell ist dabei kein Nachbau eines konkreten Computers, sondern eine mathematisch vereinfachte Beschreibung von Berechnung. Es legt fest, welche Zustände, Speicherformen und elementaren Operationen erlaubt sind. Dadurch kann man unabhängig von Java, Python oder realer Hardware untersuchen, was überhaupt als mechanisch ausführbares Verfahren gelten kann.

Die Turingmaschine ist ein solches Modell. Sie arbeitet mit einem Band, Symbolen, Zuständen und Übergangsregeln. In jedem Schritt liest sie ein Symbol, verändert gegebenenfalls das Band, wechselt den Zustand und bewegt den Lesekopf. Gerade weil dieses Modell extrem reduziert ist, eignet es sich, um Berechenbarkeit grundsätzlich zu untersuchen ^[1].

Der Lambda-Kalkül ist eine andere Formalisierung von Berechnung. Er beschreibt Berechnung nicht über Maschinenzustände und Bandbewegungen, sondern über Funktionen, Funktionsanwendung und Ersetzung von Ausdrücken. Damit macht er sichtbar, dass algorithmisches Rechnen auch als symbolische Umformung von Ausdrücken verstanden werden kann ^[2].

Ein Algorithmus kann eine Funktion berechnen, wenn für zulässige Eingaben nach endlich vielen Schritten ein Ergebnis erzeugt wird. Wenn das Problem für bestimmte Argumente nicht definiert ist, muss die Berechnung für diese Argumente nicht mit einem regulären Ergebnis terminieren ^[18]. Damit wird Terminierung nicht zu einem bloßen Bedienkomfort, sondern zu einer fachlichen Eigenschaft.

An dieser Stelle berührt der Algorithmusbegriff Entscheidbarkeit. Ein Entscheidungsproblem verlangt ein Verfahren, das für jede zulässige Eingabe mit Ja oder Nein endet. Manche präzise formulierbaren Probleme besitzen kein solches allgemeines Verfahren. Solche Grenzen sind für die Informatik grundlegend, weil sie zeigen, dass nicht jede formal beschreibbare Aufgabe automatisierbar ist ^[16].

Für das D-Book ist diese formale Ebene deshalb kein Zusatzkapitel neben der Programmierung. Sie zeigt, was hinter der scheinbar einfachen Frage steht, ob ein Verfahren „geht“: Es geht um Ausführbarkeit, Berechenbarkeit, Terminierung, Entscheidbarkeit und um Modelle, mit denen sich diese Begriffe präzise untersuchen lassen.

Der Begriff Algorithmus verweist historisch auf die Tradition regelgeleiteter Rechenverfahren. Fischer/Hofer führen die Wortherkunft auf das lateinische Pseudonym eines arabischen Mathematikers zurück ^[19]. Im D-Book wird diese Herkunft über Al-Chwarismi mit der längeren Geschichte schriftlicher, mathematischer und maschineller Rechenverfahren verbunden ^[10].

Der Abakus ist ein frühes mechanisches Rechenhilfsmittel. Zahlen werden nicht als abstrakte Zeichenfolge im Speicher abgelegt, sondern durch verschiebbare Steine oder Perlen in einer materiellen Anordnung dargestellt. Er ist deshalb kein Algorithmus im modernen Sinn, aber ein wichtiger Vorläufer: Rechnen wird an eine wiederholbare Handlungs- und Zeichenstruktur gebunden ^[11].

Der Jacquard-Webstuhl steht für eine andere Form der Materialisierung: Lochkarten steuern, welche Fäden gehoben werden und welches Muster entsteht. Damit wird ein Ablauf nicht nur ausgeführt, sondern vorher in einem Trägermedium codiert. Für die Geschichte der Informatik ist daran nicht der Stoff selbst entscheidend, sondern die Idee, Steuerinformation von der unmittelbaren Handarbeit zu trennen ^[12].

Babbages Difference Engine sollte numerische Tabellen mechanisch berechnen. Sie macht sichtbar, dass ein Verfahren auch durch Zahnräder, Register und mechanische Zustandsübergänge ausgeführt werden kann. Lovelaces Programmidee gehört in diesen Kontext der Analytical Engine: Sie dachte nicht nur an eine Rechenmaschine, sondern an eine Folge von Operationen, die auf einer allgemeinen Maschine ausgeführt werden können. Dadurch wird der Übergang von Recheninstrumenten zu programmierbarer Verarbeitung greifbar ^{[13] [14]}.

Mit Church und Turing wird aus der historischen Verfahrenstradition eine formale Grundfrage. Der Lambda-Kalkül beschreibt Berechnung als Umformung von Funktionsausdrücken; die Turingmaschine beschreibt Berechnung als regelgeleitete Zustandsveränderung auf einem Band. Beide Linien sind für den Algorithmusbegriff wichtig, weil sie zeigen, dass Berechnung unabhängig von einer konkreten Maschine präzise modelliert werden kann ^{[2] [1]}.

Colossus und die Turing-Welchman-Bombe zeigen algorithmische Verfahren im Kontext der Kryptanalyse. Die Bombe war ein elektromechanisches Suchgerät für mögliche Enigma-Einstellungen; Colossus war eine frühe elektronische Maschine zur Analyse verschlüsselter Nachrichten. In beiden Fällen wird nicht einfach „gerechnet“, sondern ein Such- und Prüfverfahren technisch materialisiert ^{[4] [3]}.

ENIAC steht für den Übergang zu elektronischem Rechnen. Er war kein Schulbeispiel für komfortable Programmierung, aber ein historischer Anker dafür, dass numerische Verfahren in elektronischer Geschwindigkeit ausgeführt werden konnten. Damit verschiebt sich Algorithmik stärker in Richtung programmierbarer Maschinen, Speicherorganisation und technischer Ausführungsbedingungen ^[15].

Dijkstra macht Algorithmik als Problemlösungsstrategie sichtbar. Sein Algorithmus für kürzeste Wege berechnet in einem gewichteten Graphen schrittweise die jeweils günstigsten bekannten Distanzen von einem Startknoten aus. Dadurch wird ein Wegproblem nicht durch Probieren gelöst, sondern durch ein systematisches Verfahren mit Datenstruktur, Auswahlregel und Korrektheitsidee ^[5].

PageRank und Websuche zeigen Algorithmik im Informationsraum. Webseiten können als Knoten eines gerichteten Graphen und Links als Kanten modelliert werden. Der Rankinggedanke besteht darin, Bedeutung nicht nur aus dem Text einer Seite, sondern aus der Linkstruktur des Webs zu berechnen. Damit wird der Algorithmus zum Ordnungsprinzip einer riesigen, vernetzten Informationsmenge ^[6].

AES steht für Algorithmik im Bereich der Kryptographie und Standardisierung. Der Advanced Encryption Standard beschreibt ein standardisiertes symmetrisches Verschlüsselungsverfahren, das Daten blockweise nach festgelegten Runden transformiert. Hier wird Algorithmus nicht nur als Verfahren, sondern als überprüfbarer, standardisierter und breit implementierter Sicherheitsbaustein sichtbar ^[7].

Shors Algorithmus zeigt, dass die Bewertung eines Problems vom Rechenmodell abhängen kann. Faktorisierung und diskrete Logarithmen gelten für klassische Computer als praktisch schwer und tragen wichtige Public-Key-Verfahren. Shor zeigte, dass ein Quantencomputer diese Problemklasse prinzipiell anders bearbeiten kann. Damit wird Algorithmik rechner- und modellabhängig ^[8].

Die Transformer-Architektur steht für eine moderne algorithmische Struktur in KI-Systemen. Ihr Kern ist ein Attention-Mechanismus, der Beziehungen zwischen Teilen einer Eingabe gewichtet und dadurch Sequenzen anders verarbeitet als klassische rekurrente Modelle. Im Algorithmusartikel dient Transformer deshalb nicht als vollständige KI-Sachanalyse, sondern als Beispiel dafür, dass algorithmische Architekturen heute auch Lern-, Sprach- und Generierungsprozesse prägen ^[9].

Die historische Dimension des Algorithmusartikels ist deshalb mehr als Illustration. Sie zeigt, wie Verfahren durch Zeichen, Tabellen, Rechenhilfen, Maschinen, Programme, Standards, wissenschaftliche Publikationen und gesellschaftliche Anwendungen wirksam werden. Algorithmus ist damit nicht nur ein abstraktes Konzept, sondern auch eine historische Form der Arbeitsteilung zwischen Mensch, Symbolsystem und Maschine.

Im D-Book ist Algorithmus ein Längsschnittbegriff. In E3 erscheint er zunächst praktisch: Lernende formulieren Schrittfolgen, testen Programme, verändern Variablenwerte und erfahren, dass ein Programm nicht nur aus Befehlen besteht, sondern ein Verfahren ausdrücken soll. Diese Perspektive passt zur lexikalischen Grundidee des Algorithmus als ausführbarer Folge von Teilhandlungen ^[19].

In Q1.2 wird Algorithmus zum eigenen Gegenstand. Such- und Sortieralgorithmen machen sichtbar, dass dieselbe Problemklasse durch unterschiedliche Verfahren bearbeitet werden kann. Damit treten Darstellung, Trace, Korrektheit, Laufzeit und Vergleichbarkeit in den Vordergrund. Die Unterscheidung zwischen Problemklasse und Einzelinstanz wird hier praktisch wichtig ^[18].

In Q1.3 und angrenzenden Kontexten wird Algorithmus mit Datenstruktur, Rekursion, Zerlegung und Entwurfsmuster verbunden. Ein Verfahren operiert nicht im luftleeren Raum; es nutzt Daten, Zustände und Repräsentationen. Gerade deshalb gehört Algorithmus im Wissensnetz eng zu Datenstruktur, Kontrollstruktur, Rekursion, Graph, Laufzeit, Effizienz und Teile-und-Herrsche.

In Q3.4 und Q3.5 wird der Begriff theoretisch geschärft. Formale Sprachen, Automaten, Registermaschinen, Turingmaschinen, Berechenbarkeit und Entscheidbarkeit zeigen, dass Algorithmus nicht nur ein Werkzeug zum Programmieren ist. Er ist ein Prüfbegriff dafür, welche Aufgaben überhaupt durch mechanische Verfahren bearbeitbar sind ^[16].

Der Concept-Wikiartikel bündelt diese Progression. Er ersetzt nicht die einzelnen Unterrichtsseiten, sondern macht sichtbar, wie ein Begriff in mehreren Halbjahren unterschiedliche Rollen annimmt: Einstieg in Programmierung, Gegenstand algorithmischer Analyse, Brücke zu Datenstrukturen, formale Tiefenschicht der Berechenbarkeit und historisches Leitmotiv der Informatik.