Algorithmentheorie

Einleitung

Die Algorithmentheorie ist ein zentraler Bereich der theoretischen Informatik. Sie untersucht, was ein Algorithmus ist, wie Algorithmen korrekt beschrieben, analysiert, verglichen und bewertet werden können und welche Probleme überhaupt algorithmisch lösbar sind. Dabei geht es nicht nur darum, ein Programm zu schreiben, sondern um die grundlegenden Fragen hinter jedem Programm: Löst das Verfahren wirklich das gewünschte Problem?, Wie viele Rechenschritte benötigt es?, Wie viel Speicher wird gebraucht? und gibt es Grenzen dessen, was ein Computer berechnen kann?

Ein Algorithmus ist eine endliche, eindeutig beschriebene Handlungsanweisung zur Lösung eines Problems oder einer Klasse von Problemen. Ein Kochrezept, ein schriftliches Divisionsverfahren oder eine Wegbeschreibung können algorithmische Eigenschaften besitzen. In der Informatik werden Algorithmen jedoch besonders präzise beschrieben, zum Beispiel mit Pseudocode, Flussdiagrammen, mathematischen Formulierungen oder Programmiersprachen.

Die Algorithmentheorie verbindet mehrere große Themenfelder: die Korrektheit von Algorithmen, die Laufzeitanalyse, die Speicherkomplexität, die Datenstrukturen, die Berechenbarkeitstheorie und die Komplexitätstheorie. Wer Algorithmentheorie versteht, kann Programme nicht nur benutzen, sondern auch begründen, warum sie funktionieren, wann sie effizient sind und wo ihre Grenzen liegen.

Lernziele

Nach diesem aiMOOC kannst Du erklären, was ein Algorithmus ist, typische Eigenschaften von Algorithmen benennen, einfache Algorithmen mit Pseudocode beschreiben, die Idee der Korrektheit verstehen, grundlegende Formen der Laufzeitanalyse anwenden und wichtige Unterschiede zwischen Berechenbarkeit, Entscheidungsproblem, Komplexitätsklasse und praktischer Effizienz erläutern. Außerdem lernst Du, warum manche Probleme schnell lösbar sind, andere sehr aufwendig werden und manche grundsätzlich nicht von einem Algorithmus entschieden werden können.

Medien und OER-Hinweise für den Lernraum

Da bei diesem aiMOOC keine separate Medienrecherche durchgeführt werden soll, werden hier sichere, schulgeeignete Such- und OER-Hinweise angegeben, die im Unterricht direkt genutzt werden können:

Wikimedia Commons: Suche nach frei lizenzierten Bildern und Diagrammen zu Algorithmus, Sortieralgorithmus, Graphentheorie und Flussdiagramm über https://commons.wikimedia.org/wiki/Special:MediaSearch?type=image&search=algorithm
Wikipedia und OER: Nutze die Artikel zu Algorithmus, Berechenbarkeitstheorie, Komplexitätstheorie, Turingmaschine und Landau-Symbol als Einstieg über https://de.wikipedia.org/wiki/Algorithmus
Lernvideo: Suche schulgeeignete Erklärvideos zu Algorithmen, Laufzeit und Komplexität über https://www.youtube.com/results?search_query=Algorithmen+Laufzeit+Komplexit%C3%A4t+Informatik
OER-Repositorium: Suche offene Unterrichtsmaterialien zur Informatik und Algorithmenanalyse über https://oercommons.org/search?f.search=algorithm

Grundlagen der Algorithmentheorie

Was ist ein Algorithmus?

Ein Algorithmus ist eine präzise Vorschrift, die aus einer Eingabe in endlich vielen Schritten eine Ausgabe erzeugt. Damit ein Verfahren als Algorithmus gelten kann, sollte es mehrere Eigenschaften erfüllen. Es muss eindeutig formuliert sein, damit jeder einzelne Schritt ohne Interpretationsspielraum ausgeführt werden kann. Es muss endlich beschrieben sein, auch wenn es auf sehr viele verschiedene Eingaben angewendet werden kann. Außerdem soll es nach endlich vielen Schritten enden, wenn es sich um einen Algorithmus zur vollständigen Problemlösung handelt. Diese Eigenschaft nennt man Terminierung.

Ein einfaches Beispiel ist der euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers zweier natürlicher Zahlen. Er wiederholt die Division mit Rest, bis der Rest null ist. Das Verfahren ist eindeutig, endlich beschreibbar, liefert ein korrektes Ergebnis und kann für beliebige geeignete Eingaben verwendet werden.

Algorithmus, Programm und Prozess

Ein Algorithmus ist nicht dasselbe wie ein Computerprogramm. Der Algorithmus ist die abstrakte Lösungsidee oder Handlungsanweisung. Ein Programm ist eine konkrete Umsetzung dieses Algorithmus in einer Programmiersprache. Derselbe Algorithmus kann in Python, Java, C++, JavaScript oder einer anderen Sprache implementiert werden. Ein Prozess wiederum ist eine konkrete Ausführung eines Programms auf einem Rechner.

Diese Unterscheidung ist wichtig, weil die Algorithmentheorie vor allem die allgemeine Struktur und Leistungsfähigkeit von Lösungsverfahren untersucht. Ob ein Programm schön formatiert ist oder auf einem bestimmten Gerät läuft, ist für die Theorie weniger entscheidend als die Frage, wie der zugrunde liegende Algorithmus arbeitet.

Eingabe, Ausgabe und Spezifikation

Jeder Algorithmus hat eine Eingabe und eine Ausgabe. Die Spezifikation beschreibt, welche Ausgabe für welche Eingabe erwartet wird. Bei einem Sortieralgorithmus besteht die Eingabe beispielsweise aus einer Liste von Elementen, die miteinander verglichen werden können. Die Ausgabe soll dieselben Elemente in sortierter Reihenfolge enthalten.

Eine genaue Spezifikation ist die Grundlage für die spätere Korrektheit. Ohne klare Spezifikation kann man nicht sinnvoll prüfen, ob ein Algorithmus richtig arbeitet. Wenn eine Suchmaschine beispielsweise Ergebnisse liefert, muss zunächst definiert werden, was ein relevantes Ergebnis überhaupt bedeutet.

Deterministische und nichtdeterministische Algorithmen

Ein deterministischer Algorithmus führt bei derselben Eingabe immer dieselben Schritte aus und erzeugt dieselbe Ausgabe. Viele klassische Sortier- und Suchverfahren sind deterministisch. Ein nichtdeterministischer Algorithmus kann dagegen modellhaft mehrere Möglichkeiten gleichzeitig betrachten. In der praktischen Programmierung begegnet man häufiger randomisierten Algorithmen, die Zufallsentscheidungen nutzen. Sie können bei derselben Eingabe unterschiedliche Wege nehmen, sollen aber mit hoher Wahrscheinlichkeit gute oder korrekte Ergebnisse liefern.

Nichtdeterminismus spielt besonders in der Komplexitätstheorie eine große Rolle, etwa bei der Erklärung der Klasse NP. Dort geht es nicht darum, dass reale Computer magisch mehrere Wege gleichzeitig gehen, sondern um ein mathematisches Modell, mit dem man Lösbarkeit und Überprüfbarkeit präzise untersuchen kann.

Darstellung von Algorithmen

Natürliche Sprache

Algorithmen können in natürlicher Sprache beschrieben werden. Das ist für den Einstieg hilfreich, aber oft ungenau. Sätze wie „sortiere die Liste geschickt“ oder „wähle ein gutes Element“ sind nicht eindeutig genug. Die Algorithmentheorie verlangt präzisere Beschreibungen, damit ein Verfahren analysiert und bewiesen werden kann.

Pseudocode

Pseudocode ist eine halbformale Beschreibung eines Algorithmus. Er ähnelt einer Programmiersprache, verzichtet aber auf technische Details einer konkreten Sprache. Dadurch eignet er sich gut, um die Grundidee eines Verfahrens darzustellen.

Beispiel für eine lineare Suche:

Algorithmus LineareSuche(Liste, Ziel)
  für jedes Element in Liste:
    wenn Element gleich Ziel ist:
      gib Position zurück
  gib "nicht gefunden" zurück

Dieser Algorithmus durchsucht die Liste von vorne nach hinten. Im schlechtesten Fall muss er jedes Element ansehen.

Flussdiagramme

Ein Flussdiagramm stellt Abläufe grafisch dar. Entscheidungen werden häufig als Rauten, Verarbeitungsschritte als Rechtecke und Start- oder Endpunkte als abgerundete Formen dargestellt. Flussdiagramme helfen, Verzweigungen und Wiederholungen sichtbar zu machen. In der Algorithmentheorie sind sie vor allem didaktisch nützlich, während formale Beweise meist mit mathematischer Notation oder Pseudocode arbeiten.

Rekursion

Rekursion bedeutet, dass ein Algorithmus sich selbst auf kleinere Teilprobleme anwendet. Ein rekursiver Algorithmus benötigt eine Abbruchbedingung, damit er nicht unendlich weiterläuft. Viele wichtige Algorithmen, darunter Mergesort, Quicksort, Tiefensuche und Verfahren aus der dynamischen Programmierung, lassen sich rekursiv beschreiben.

Ein klassisches Beispiel ist die Berechnung der Fakultät:

Fakultät(n)
  wenn n = 0:
    gib 1 zurück
  sonst:
    gib n mal Fakultät(n - 1) zurück

Die Abbruchbedingung ist hier n = 0. Ohne sie würde der Algorithmus nicht terminieren.

Korrektheit von Algorithmen

Warum Korrektheit wichtig ist

Ein Algorithmus ist nicht schon gut, weil er schnell ist. Er muss zuerst das richtige Ergebnis liefern. Die Korrektheit eines Algorithmus bedeutet, dass er für alle zulässigen Eingaben die geforderte Ausgabe erzeugt. Dabei unterscheidet man häufig zwischen partieller und totaler Korrektheit.

Ein Algorithmus ist partiell korrekt, wenn er im Fall seiner Terminierung ein korrektes Ergebnis liefert. Er ist total korrekt, wenn er zusätzlich für alle zulässigen Eingaben tatsächlich terminiert. Für die Praxis sind beide Eigenschaften wichtig: Ein Programm, das zwar theoretisch das richtige Ergebnis liefern würde, aber nie fertig wird, ist kaum brauchbar.

Schleifeninvariante

Eine Schleifeninvariante ist eine Aussage, die vor und nach jedem Durchlauf einer Schleife wahr bleibt. Sie ist ein wichtiges Werkzeug, um die Korrektheit von Algorithmen zu beweisen. Bei einem Sortieralgorithmus könnte eine Invariante etwa lauten: „Der bereits bearbeitete Teil der Liste ist sortiert.“

Ein Beweis mit einer Schleifeninvariante hat typischerweise drei Schritte. Zuerst zeigt man, dass die Invariante vor dem ersten Schleifendurchlauf gilt. Dann zeigt man, dass ein Schleifendurchlauf die Invariante erhält. Schließlich zeigt man, dass aus der Invariante und dem Ende der Schleife die gewünschte Korrektheit folgt.

Terminierung

Terminierung bedeutet, dass ein Algorithmus nach endlich vielen Schritten endet. Um Terminierung zu beweisen, verwendet man oft eine Größe, die bei jedem Schritt kleiner wird und nicht unendlich oft kleiner werden kann. Beim euklidischen Algorithmus wird beispielsweise der Rest immer kleiner, bis er null erreicht.

Die Frage der Terminierung ist tief mit der Berechenbarkeitstheorie verbunden. Das berühmte Halteproblem zeigt, dass es keinen allgemeinen Algorithmus geben kann, der für jedes beliebige Programm und jede beliebige Eingabe entscheidet, ob dieses Programm irgendwann anhält.

Effizienz und Laufzeitanalyse

Warum Effizienz zählt

Ein korrekter Algorithmus kann trotzdem unpraktisch sein, wenn er zu lange braucht oder zu viel Speicher verwendet. Die Laufzeitanalyse untersucht, wie die Anzahl der Rechenschritte mit der Größe der Eingabe wächst. Dabei interessiert meist nicht die exakte Zeit auf einem bestimmten Computer, sondern das Wachstum bei großen Eingaben.

Wenn ein Algorithmus bei einer Liste mit 100 Elementen schnell ist, sagt das wenig darüber aus, wie er sich bei einer Liste mit 10 Millionen Elementen verhält. Deshalb betrachtet die Algorithmentheorie die asymptotische Analyse.

Landau-Notation

Die Landau-Notation beschreibt das Wachstumsverhalten von Funktionen. Besonders bekannt ist die O-Notation. Sie gibt eine obere Schranke für das Wachstum an. Wenn ein Algorithmus eine Laufzeit von O(n) hat, wächst seine Laufzeit höchstens proportional zur Eingabegröße n. Bei O(n²) wächst sie quadratisch, bei O(log n) logarithmisch.

Wichtige typische Laufzeiten sind:

Konstante Zeit: O(1), zum Beispiel Zugriff auf ein bestimmtes Feld-Element
Logarithmische Zeit: O(log n), zum Beispiel Binäre Suche
Lineare Zeit: O(n), zum Beispiel einfache Suche in einer unsortierten Liste
Linearithmische Zeit: O(n log n), typisch für effiziente Sortierverfahren wie Mergesort
Quadratische Zeit: O(n²), zum Beispiel einfache Sortierverfahren wie Bubblesort
Exponentielle Zeit: O(2ⁿ), typisch für viele vollständige Suchverfahren über alle Teilmengen
Fakultative Laufzeit: O(n!), etwa bei naiver vollständiger Suche über alle Permutationen

Best Case, Average Case und Worst Case

Bei der Analyse unterscheidet man verschiedene Fälle. Der Best Case beschreibt die günstigste Eingabe, der Worst Case die ungünstigste Eingabe und der Average Case eine durchschnittliche Situation unter bestimmten Annahmen. Die Worst-Case-Analyse ist besonders wichtig, wenn man garantieren möchte, dass ein Algorithmus nie schlechter als eine bestimmte Schranke wird.

Bei der linearen Suche tritt der Best Case ein, wenn das gesuchte Element direkt an erster Stelle steht. Der Worst Case tritt ein, wenn es am Ende steht oder gar nicht vorkommt. Dann muss jedes Element geprüft werden.

Speicherkomplexität

Neben der Zeit spielt die Speicherkomplexität eine wichtige Rolle. Sie beschreibt, wie viel zusätzlicher Speicher ein Algorithmus benötigt. Ein Algorithmus kann schnell sein, aber sehr viel Speicher verbrauchen. In eingebetteten Systemen, Smartphones oder großen Datenzentren kann der Speicherbedarf entscheidend sein.

Ein Sortierverfahren, das die Liste direkt im vorhandenen Speicher umordnet, wird als In-place-Algorithmus bezeichnet. Andere Verfahren benötigen zusätzliche Hilfslisten. Auch Rekursion kann Speicher verbrauchen, weil jeder rekursive Aufruf Informationen auf dem Stack ablegt.

Grundlegende Algorithmustypen

Suchalgorithmen

Suchalgorithmen finden ein bestimmtes Element oder eine Struktur in Daten. Die Lineare Suche funktioniert auch bei unsortierten Listen, benötigt aber im schlechtesten Fall O(n) Vergleiche. Die Binäre Suche ist deutlich schneller, setzt aber eine sortierte Liste voraus und benötigt O(log n) Vergleiche.

Diese Gegenüberstellung zeigt ein wichtiges Prinzip der Algorithmentheorie: Eine bessere Laufzeit kann bestimmte Voraussetzungen erfordern. Wer schneller suchen will, muss die Daten oft vorher sortieren oder in einer geeigneten Datenstruktur speichern.

Sortieralgorithmen

Sortieralgorithmen ordnen Daten nach einer festgelegten Relation, zum Beispiel alphabetisch oder numerisch. Einfache Verfahren wie Bubblesort, Selectionsort und Insertionsort sind leicht zu verstehen, aber für große Datenmengen meist nicht optimal. Effizientere Verfahren wie Mergesort, Quicksort oder Heapsort erreichen bessere asymptotische Laufzeiten.

Die Analyse von Sortieralgorithmen ist ein klassisches Beispiel dafür, wie Laufzeit, Speicherbedarf, Stabilität und Implementierungsaufwand gegeneinander abgewogen werden müssen. Ein stabiler Sortieralgorithmus erhält die ursprüngliche Reihenfolge gleicher Elemente. Das kann bei mehrstufigem Sortieren wichtig sein.

Graphalgorithmen

Ein Graph besteht aus Knoten und Kanten. Viele reale Probleme lassen sich als Graph modellieren: soziale Netzwerke, Verkehrsnetze, Computernetze, Abhängigkeiten in Projekten oder Webseitenverlinkungen. Graphalgorithmen untersuchen zum Beispiel Erreichbarkeit, kürzeste Wege, Zusammenhang oder Flüsse.

Wichtige Verfahren sind die Breitensuche, die Tiefensuche, der Dijkstra-Algorithmus für kürzeste Wege mit nichtnegativen Kantengewichten und Algorithmen für minimale Spannbäume. Graphalgorithmen zeigen besonders gut, wie eng Datenstruktur, Modellierung und Effizienz zusammenhängen.

Greedy-Algorithmen

Ein Greedy-Algorithmus trifft in jedem Schritt die lokal beste Entscheidung. Diese Strategie ist einfach und oft effizient, aber nicht immer korrekt. Beim Wechselgeldproblem funktioniert eine greedyartige Strategie für manche Münzsysteme, aber nicht für alle. Beim Algorithmus von Dijkstra funktioniert die Greedy-Idee unter der Voraussetzung nichtnegativer Kantengewichte.

Für Greedy-Algorithmen muss man besonders sorgfältig beweisen, dass lokale Entscheidungen tatsächlich zu einer global optimalen Lösung führen.

Divide and Conquer

Teile und herrsche oder Divide and Conquer zerlegt ein Problem in kleinere Teilprobleme, löst diese und kombiniert die Teillösungen. Mergesort teilt eine Liste, sortiert die Hälften und führt sie wieder zusammen. Quicksort wählt ein Pivotelement und ordnet kleinere und größere Elemente darum herum.

Diese Strategie ist in der Algorithmentheorie wichtig, weil sie oft zu effizienten rekursiven Verfahren führt. Die Laufzeit kann mit Rekurrenzgleichungen beschrieben werden.

Dynamische Programmierung

Dynamische Programmierung wird eingesetzt, wenn ein Problem aus überlappenden Teilproblemen besteht. Statt dieselben Teilprobleme immer wieder neu zu lösen, speichert man bereits berechnete Ergebnisse. Dadurch können exponentielle Verfahren oft erheblich verbessert werden.

Typische Beispiele sind die Berechnung der Fibonacci-Folge, das Rucksackproblem, kürzeste Wege in bestimmten Graphen oder Sequenzvergleiche in der Bioinformatik. Entscheidend ist, das Problem so zu zerlegen, dass Teilergebnisse wiederverwendet werden können.

Berechenbarkeit und Grenzen

Entscheidungsprobleme

Ein Entscheidungsproblem ist ein Problem, dessen Antwort Ja oder Nein lautet. Zum Beispiel: „Gibt es in diesem Graphen einen Weg von Knoten A zu Knoten B?“ Viele komplizierte Fragen lassen sich als Entscheidungsprobleme formulieren. Das ist hilfreich, weil die Berechenbarkeitstheorie und die Komplexitätstheorie Entscheidungsprobleme besonders gut untersuchen können.

Turingmaschine

Die Turingmaschine ist ein mathematisches Modell für Berechnung. Sie besteht vereinfacht aus einem Band, einem Lese-Schreib-Kopf, Zuständen und Übergangsregeln. Obwohl das Modell sehr einfach wirkt, kann es im Prinzip alles berechnen, was auch moderne Computer berechnen können, sofern genügend Zeit und Speicher vorhanden sind.

Die Turingmaschine ist wichtig, weil sie eine präzise Definition dafür liefert, was algorithmisch berechenbar bedeutet. Viele theoretische Aussagen über Algorithmen werden mithilfe dieses Modells formuliert.

Halteproblem

Das Halteproblem fragt, ob es einen Algorithmus geben kann, der für jedes Programm und jede Eingabe entscheidet, ob das Programm irgendwann anhält oder endlos weiterläuft. Die Antwort lautet: Einen solchen allgemeinen Algorithmus gibt es nicht. Dieses Ergebnis zeigt eine grundlegende Grenze der Berechenbarkeit.

Für die Praxis bedeutet das nicht, dass man nie über Terminierung nachdenken kann. Für viele konkrete Programme lässt sich Terminierung beweisen. Aber es gibt kein universelles Verfahren, das diese Frage für alle denkbaren Programme automatisch entscheidet.

Komplexitätstheorie

Von lösbar zu effizient lösbar

Die Komplexitätstheorie fragt nicht nur, ob ein Problem lösbar ist, sondern wie aufwendig die Lösung ist. Ein Problem kann berechenbar sein, aber so viel Zeit benötigen, dass es praktisch unlösbar wirkt. Deshalb unterscheidet man zwischen grundsätzlich lösbaren und effizient lösbaren Problemen.

Ein Algorithmus mit polynomialer Laufzeit, zum Beispiel O(n²) oder O(n³), gilt in der Theorie oft als effizient. Ein Algorithmus mit exponentieller Laufzeit, zum Beispiel O(2ⁿ), wird bei großen Eingaben sehr schnell unpraktisch.

Klasse P

Die Klasse P enthält Entscheidungsprobleme, die von einer deterministischen Turingmaschine in polynomialer Zeit gelöst werden können. Viele alltägliche algorithmische Probleme liegen in P, zum Beispiel das Prüfen, ob ein Element in einer sortierten Liste vorkommt, oder viele Varianten kürzester Wege.

P steht nicht für „praktisch immer schnell“, sondern für eine theoretische Einordnung. Ein polynomialer Algorithmus mit sehr hohem Exponenten kann in der Praxis dennoch unbrauchbar sein.

Klasse NP

Die Klasse NP enthält Entscheidungsprobleme, bei denen eine vorgeschlagene Lösung in polynomialer Zeit überprüft werden kann. Ein Beispiel ist das Erfüllbarkeitsproblem der Aussagenlogik: Wenn jemand eine Belegung der Variablen vorgibt, kann man schnell prüfen, ob sie die Formel erfüllt.

NP bedeutet nicht „nicht polynomial“ und auch nicht „unlösbar“. Es bedeutet, dass Lösungen effizient überprüfbar sind. Manche Probleme in NP können auch effizient gelöst werden; alle Probleme aus P liegen ebenfalls in NP.

P-NP-Problem

Das P-NP-Problem fragt, ob jedes Problem, dessen Lösung schnell überprüft werden kann, auch schnell gelöst werden kann. Formal lautet die Frage: Ist P = NP? Diese Frage ist eines der bedeutendsten offenen Probleme der Informatik und Mathematik.

Eine Lösung hätte große Auswirkungen auf Kryptographie, Optimierung, Automatisierung, Künstliche Intelligenz und viele andere Bereiche. Bis heute ist nicht bewiesen, ob P gleich NP oder ungleich NP ist.

NP-Vollständigkeit

Ein Problem heißt NP-vollständig, wenn es in NP liegt und jedes Problem aus NP in polynomialer Zeit auf dieses Problem zurückgeführt werden kann. NP-vollständige Probleme gelten als besonders zentrale schwierige Probleme. Würde man für ein NP-vollständiges Problem einen polynomialen Algorithmus finden, dann könnte man alle Probleme in NP polynomial lösen.

Bekannte Beispiele sind das Erfüllbarkeitsproblem der Aussagenlogik, das Problem des Handlungsreisenden in Entscheidungsform und bestimmte Varianten des Rucksackproblems.

Datenstrukturen und Algorithmen

Warum Datenstrukturen wichtig sind

Eine Datenstruktur bestimmt, wie Daten organisiert und verarbeitet werden. Algorithmen und Datenstrukturen gehören eng zusammen. Ein Suchalgorithmus kann langsam oder schnell sein, je nachdem, ob die Daten in einer unsortierten Liste, einem sortierten Feld, einem Hash-Table oder einem Baum gespeichert sind.

Die Wahl der passenden Datenstruktur kann die Laufzeit eines Algorithmus stark beeinflussen. Deshalb ist Algorithmentheorie nicht nur eine Theorie der Schritte, sondern auch eine Theorie der geeigneten Repräsentation von Informationen.

Listen, Felder, Stapel und Warteschlangen

Ein Array erlaubt schnellen Zugriff auf Elemente über einen Index. Eine Liste ist flexibler beim Einfügen und Löschen, kann aber beim Zugriff auf ein bestimmtes Element langsamer sein. Ein Stack arbeitet nach dem Prinzip Last In, First Out. Eine Queue arbeitet nach dem Prinzip First In, First Out.

Diese einfachen Datenstrukturen bilden die Grundlage vieler komplexerer Verfahren. Die Tiefensuche verwendet oft einen Stack, die Breitensuche eine Queue.

Bäume und Hashing

Bäume eignen sich, um hierarchische Strukturen zu speichern. Suchbäume können effizientes Einfügen, Löschen und Suchen ermöglichen. Hashfunktionen ordnen Schlüsseln Speicherpositionen zu. In einer gut konstruierten Hash-Tabelle kann Suchen im Durchschnitt sehr schnell sein.

Auch hier zeigt sich: Ein Algorithmus kann nicht unabhängig von seiner Datenstruktur bewertet werden. Die theoretische Analyse muss Annahmen über Operationen wie Vergleichen, Einfügen, Löschen und Zugriff berücksichtigen.

Anwendungen der Algorithmentheorie

Alltag und Gesellschaft

Algorithmen steuern Suchmaschinen, Navigationssysteme, Empfehlungen in Medienplattformen, automatische Übersetzungen, medizinische Bildanalyse, Finanzsysteme und viele Bereiche der Verwaltung. Die Algorithmentheorie hilft zu verstehen, welche Verfahren effizient, nachvollziehbar und verlässlich sind.

Gleichzeitig entstehen gesellschaftliche Fragen. Wenn algorithmische Systeme Entscheidungen vorbereiten, müssen Transparenz, Fairness, Datenschutz und Verantwortung bedacht werden. Algorithmentheorie allein beantwortet diese ethischen Fragen nicht, liefert aber wichtige Grundlagen, um technische Möglichkeiten und Grenzen realistisch einzuschätzen.

Kryptographie und Sicherheit

In der Kryptographie spielen Algorithmen und Komplexität eine zentrale Rolle. Verschlüsselungsverfahren sollen für berechtigte Personen effizient nutzbar sein, aber für Angreifende praktisch nicht zu brechen. Viele Verfahren beruhen darauf, dass bestimmte mathematische Probleme mit bekannten Methoden sehr schwierig zu lösen sind.

Wenn sich die Komplexitätseinschätzung eines Problems ändert oder neue Rechenmodelle wie Quantencomputer relevant werden, kann dies Auswirkungen auf die Sicherheit kryptographischer Verfahren haben.

Künstliche Intelligenz und Optimierung

Auch Künstliche Intelligenz verwendet Algorithmen. Suchverfahren, Optimierungsverfahren, Lernalgorithmen und graphbasierte Methoden spielen eine große Rolle. Die Algorithmentheorie hilft, die Leistungsfähigkeit und Grenzen dieser Verfahren zu verstehen. Viele Aufgaben in der KI sind komplex, sodass Näherungsverfahren, Heuristiken oder probabilistische Methoden eingesetzt werden.

Beispiel: Binäre Suche

Problemstellung

Die Binäre Suche findet ein Element in einer sortierten Liste. Sie vergleicht das gesuchte Element mit dem mittleren Element der Liste. Ist das gesuchte Element kleiner, wird nur noch die linke Hälfte betrachtet. Ist es größer, wird nur noch die rechte Hälfte betrachtet. Dadurch halbiert sich der Suchbereich in jedem Schritt.

Pseudocode

Algorithmus BinäreSuche(Liste, Ziel)
  links = 0
  rechts = Länge(Liste) - 1
  solange links <= rechts:
    mitte = ganzzahliger Mittelwert von links und rechts
    wenn Liste[mitte] = Ziel:
      gib mitte zurück
    wenn Liste[mitte] < Ziel:
      links = mitte + 1
    sonst:
      rechts = mitte - 1
  gib "nicht gefunden" zurück

Analyse

Die binäre Suche ist korrekt, wenn die Liste sortiert ist und die Grenzen des Suchbereichs korrekt angepasst werden. Ihre Laufzeit ist O(log n), weil sich die Anzahl der verbleibenden Kandidaten in jedem Schritt ungefähr halbiert. Sie zeigt sehr anschaulich, warum Vorwissen über die Datenstruktur die Effizienz eines Algorithmus verbessern kann.

Beispiel: Sortieren durch Einfügen

Grundidee

Insertionsort sortiert eine Liste, indem es die Elemente nacheinander in einen bereits sortierten Teil einfügt. Das Verfahren ähnelt dem Sortieren von Spielkarten auf der Hand. Es ist einfach zu verstehen und für kleine oder fast sortierte Datenmengen oft brauchbar.

Analyse

Im besten Fall ist die Liste bereits sortiert. Dann benötigt Insertionsort nur lineare Zeit O(n). Im schlechtesten Fall ist die Liste umgekehrt sortiert. Dann müssen viele Elemente verschoben werden, und die Laufzeit beträgt O(n²). Das Beispiel zeigt, warum Best Case und Worst Case deutlich voneinander abweichen können.

Zusammenfassung

Die Algorithmentheorie untersucht die abstrakten Grundlagen algorithmischer Problemlösung. Sie fragt, wie Algorithmen beschrieben, bewiesen, analysiert und verglichen werden. Zentrale Begriffe sind Algorithmus, Korrektheit, Terminierung, Laufzeit, Speicherkomplexität, Datenstruktur, Berechenbarkeit und Komplexitätsklasse. Besonders wichtig ist die Unterscheidung zwischen Problemen, die grundsätzlich lösbar sind, Problemen, die effizient lösbar sind, und Problemen, deren Lösbarkeit oder Effizienz grundlegende Grenzen berührt. Dadurch bildet die Algorithmentheorie eine Grundlage für Programmierung, Softwareentwicklung, Kryptographie, Künstliche Intelligenz, Datenanalyse und viele technische Anwendungen.

Interaktive Aufgaben

Quiz: Teste Dein Wissen

Was beschreibt ein Algorithmus am besten? (Eine endliche und eindeutige Handlungsanweisung zur Lösung eines Problems) (!Eine zufällige Sammlung von Programmzeilen) (!Eine Hardwarekomponente im Computer) (!Eine Datei mit beliebigem Inhalt)

Was bedeutet Terminierung bei einem Algorithmus? (Der Algorithmus endet nach endlich vielen Schritten) (!Der Algorithmus verwendet besonders wenig Speicher) (!Der Algorithmus wird automatisch schneller) (!Der Algorithmus erzeugt immer zufällige Ergebnisse)

Welche Aussage beschreibt partielle Korrektheit? (Wenn der Algorithmus endet, liefert er ein korrektes Ergebnis) (!Der Algorithmus endet immer sofort) (!Der Algorithmus benötigt immer konstante Zeit) (!Der Algorithmus ist in jeder Programmiersprache gleich schnell)

Welche Laufzeit gehört typischerweise zur binären Suche in einer sortierten Liste? (O log n) (!O n hoch zwei) (!O n Fakultät) (!O zwei hoch n)

Was untersucht die Komplexitätstheorie besonders? (Den Aufwand zur Lösung von Problemen) (!Die Farbe von Benutzeroberflächen) (!Die elektrische Spannung eines Prozessors) (!Die Lautstärke eines Computers)

Was ist eine Schleifeninvariante? (Eine Aussage, die vor und nach jedem Schleifendurchlauf gilt) (!Ein Fehler in einer Programmiersprache) (!Eine Datei zur Speicherung von Quellcode) (!Ein zufälliger Wert in einer Liste)

Welche Voraussetzung braucht die binäre Suche? (Die Liste muss sortiert sein) (!Die Liste muss leer sein) (!Alle Elemente müssen gleich sein) (!Die Liste darf nur aus Buchstaben bestehen)

Was zeigt das Halteproblem? (Es gibt keinen allgemeinen Algorithmus zur Entscheidung des Haltens aller Programme) (!Jedes Programm hält nach genau einer Sekunde) (!Alle Algorithmen sind gleich effizient) (!Nur sortierte Listen können berechnet werden)

Was bedeutet NP in der Komplexitätstheorie? (Lösungen können in polynomialer Zeit überprüft werden) (!Probleme sind immer unlösbar) (!Programme sind nicht praktisch) (!Algorithmen dürfen keine Eingaben haben)

Welche Strategie zerlegt ein Problem in kleinere Teilprobleme und kombiniert die Lösungen? (Divide and Conquer) (!Zufälliges Löschen) (!Lineares Warten) (!Speicherloses Raten)

Memory

Algorithmus	Eindeutige Schrittfolge
Terminierung	Endet nach endlich vielen Schritten
Laufzeitanalyse	Wachstum der Rechenschritte
Schleifeninvariante	Aussage bleibt in der Schleife wahr
Binäre Suche	Halbiert den Suchbereich
Turingmaschine	Modell der Berechnung
NP	Effizient überprüfbare Lösung

Drag and Drop

Ordne die richtigen Begriffe zu.	Thema
Eindeutige Schrittfolge	Algorithmus
Endlichkeit der Ausführung	Terminierung
Wachstum des Aufwands	Laufzeitanalyse
Mathematisches Berechnungsmodell	Turingmaschine
Effiziente Überprüfbarkeit	NP
Lokale optimale Entscheidung	Greedy-Verfahren
Speichern von Teilergebnissen	Dynamische Programmierung

Kreuzworträtsel

Algorithmus	Wie nennt man eine eindeutige Schrittfolge zur Lösung eines Problems?
Laufzeit	Welche Größe beschreibt die benötigte Rechenzeit eines Verfahrens?
Rekursion	Wie heißt das Prinzip, wenn ein Verfahren sich selbst auf kleinere Teilprobleme anwendet?
Turing	Welcher Forscher steht namensgebend für ein wichtiges Modell der Berechnung?
Sortieren	Wie nennt man das Ordnen von Elementen nach einer Relation?
Graph	Wie heißt eine Struktur aus Knoten und Kanten?

LearningApps

Lückentext

Die Algorithmentheorie untersucht die Grundlagen von

und fragt, wie Verfahren beschrieben, bewiesen und analysiert werden können. Ein Algorithmus muss eindeutig formuliert sein und bei vollständiger Problemlösung nach endlich vielen Schritten

. Die Korrektheit beschreibt, ob ein Verfahren für zulässige Eingaben die geforderte

erzeugt. Mit der Landau-Notation wird das Wachstum der Laufzeit für große

beschrieben. Die binäre Suche ist effizient, weil sie den Suchbereich in jedem Schritt ungefähr

. Die Berechenbarkeitstheorie untersucht, welche Probleme überhaupt algorithmisch

sind. Das Halteproblem zeigt, dass es keinen allgemeinen Algorithmus gibt, der für alle Programme das

entscheidet. Die Komplexitätstheorie ordnet Probleme danach ein, wie viel

ihre Lösung benötigt. In der Klasse NP liegen Entscheidungsprobleme, deren vorgeschlagene Lösungen effizient

werden können. Datenstrukturen sind wichtig, weil sie beeinflussen, wie schnell ein Algorithmus Daten speichern, suchen und

kann.

Offene Aufgaben

Leicht

Algorithmus im Alltag: Beschreibe einen alltäglichen Algorithmus, zum Beispiel Zähneputzen, einen Schulweg oder ein Rezept, in eindeutigen Einzelschritten.
Pseudocode: Schreibe Pseudocode für einen Algorithmus, der prüft, ob eine Zahl gerade oder ungerade ist.
Lineare Suche: Erkläre an einer Liste von Namen, wie die lineare Suche funktioniert.
Flussdiagramm: Zeichne ein Flussdiagramm für eine einfache Entscheidung, zum Beispiel „Regnet es? Schirm mitnehmen?“

Standard

Binäre Suche: Simuliere die binäre Suche an einer sortierten Liste mit mindestens 16 Zahlen und dokumentiere jeden Vergleich.
Sortieralgorithmus: Vergleiche Bubblesort und Insertionsort an derselben Liste und zähle die Vergleiche.
Laufzeitanalyse: Ordne mehrere Algorithmen den Laufzeitklassen O(1), O(log n), O(n), O(n²) und O(2ⁿ) zu und begründe Deine Entscheidung.
Schleifeninvariante: Formuliere eine Schleifeninvariante für einen Algorithmus, der die Summe einer Zahlenliste berechnet.

Schwer

Korrektheitsbeweis: Beweise mithilfe einer Schleifeninvariante die Korrektheit eines einfachen Maximum-Algorithmus.
Graphalgorithmus: Modelliert den Schulweg mehrerer Personen als Graph und bestimmt mit einem geeigneten Verfahren kurze Wege.
Dynamische Programmierung: Erkläre am Beispiel der Fibonacci-Folge, warum das Speichern von Teilergebnissen Zeit spart.
P-NP-Problem: Recherchiere die Bedeutung des P-NP-Problems und verfasse einen kurzen Essay über mögliche Folgen einer Lösung.

type=create break=no preload=CHAT GPT TEXT HIER EINFÜGEN default= width=30 placeholder= Dein MOOC Titel buttonlabel=MOOC erstellen </inputbox>

Lernkontrolle

Algorithmus und Spezifikation: Du erhältst eine ungenaue Problembeschreibung. Formuliere daraus eine präzise Spezifikation mit Eingabe, Ausgabe und Randbedingungen.
Korrektheit und Terminierung: Vergleiche zwei Algorithmen, von denen einer nicht immer terminiert und einer falsche Ergebnisse liefern kann. Erkläre, welcher Fehler schwerer wiegt und warum.
Effizienzvergleich: Entscheide für eine konkrete Anwendung, ob ein langsamer, aber einfacher Algorithmus oder ein schneller, aber komplexer Algorithmus besser geeignet ist.
Datenstrukturwahl: Begründe, welche Datenstruktur für häufiges Suchen, häufiges Einfügen oder geordnete Ausgabe sinnvoll sein kann.
Komplexität und Praxis: Erkläre, warum ein theoretisch effizienter Algorithmus in der Praxis trotzdem ungünstig sein kann.
Berechenbarkeitsgrenze: Übertrage die Idee des Halteproblems auf automatische Softwareprüfung und beschreibe, welche Erwartungen realistisch sind.
Modellierung: Wandle ein reales Problem aus Verkehr, Schule oder Internet in ein Graphproblem um und beschreibe einen passenden Lösungsansatz.

OERs zum Thema

Wikipedia und freie Lernquellen

Weitere geeignete OER-Ausgangspunkte sind:

Links

Algorithmentheorie

Glossar

Algorithmus: Eine endliche, eindeutige Vorschrift zur Lösung eines Problems.
Eingabe: Die Daten, mit denen ein Algorithmus startet.
Ausgabe: Das Ergebnis, das ein Algorithmus erzeugt.
Spezifikation: Die genaue Beschreibung, was ein Algorithmus leisten soll.
Korrektheit: Eigenschaft, dass ein Algorithmus die geforderte Ausgabe liefert.
Terminierung: Eigenschaft, dass ein Algorithmus nach endlich vielen Schritten endet.
Laufzeit: Maß für die Anzahl der benötigten Rechenschritte.
Speicherkomplexität: Maß für den zusätzlich benötigten Speicher.
Berechenbarkeit: Frage, ob ein Problem überhaupt algorithmisch lösbar ist.
Komplexitätsklasse: Gruppe von Problemen mit vergleichbarem Ressourcenaufwand.

Unterrichtsideen

Einstieg: Sammle mit der Klasse alltägliche Algorithmen und prüfe, ob die Anweisungen eindeutig sind.
Partnerarbeit: Eine Person schreibt Pseudocode, die andere führt ihn exakt aus und markiert Unklarheiten.
Experiment: Vergleicht lineare und binäre Suche mit Papierkarten und messt die Anzahl der Vergleiche.
Diskussion: Besprecht, warum algorithmische Entscheidungen transparent und überprüfbar sein sollten.
Projekt: Erstellt ein Lernplakat oder ein kurzes Erklärvideo zu einem Algorithmustyp.

Kompetenzraster

Kompetenz	Grundlegend	Fortgeschritten	Vertieft
Algorithmus verstehen	Du kannst Beispiele für Algorithmen nennen.	Du kannst Algorithmen in Pseudocode beschreiben.	Du kannst Algorithmen hinsichtlich Korrektheit und Effizienz bewerten.
Laufzeit analysieren	Du kennst einfache Laufzeitklassen.	Du kannst lineare, logarithmische und quadratische Laufzeit unterscheiden.	Du kannst Laufzeiten begründen und auf neue Beispiele übertragen.
Korrektheit begründen	Du erkennst richtige und falsche Ergebnisse.	Du kannst Terminierung und partielle Korrektheit unterscheiden.	Du kannst einfache Invarianten formulieren.
Grenzen erkennen	Du weißt, dass nicht alles algorithmisch entscheidbar ist.	Du kannst das Halteproblem in eigenen Worten erklären.	Du kannst Folgen für automatische Programmanalyse diskutieren.

Lernnachweis

Der Lernnachweis besteht aus einer Kombination aus Erklärung, Anwendung und Reflexion. Er enthält keine externen Medien und keine eingebetteten Inhalte.

Erklärung: Erkläre den Unterschied zwischen Algorithmus, Programm und Prozess mit einem eigenen Beispiel.
Anwendung: Entwickle Pseudocode für einen Suchalgorithmus und analysiere seinen Worst Case.
Begründung: Formuliere eine einfache Schleifeninvariante und erkläre, wie sie zur Korrektheit beiträgt.
Transfer: Wähle ein reales Problem und beschreibe, welche Datenstruktur für eine algorithmische Lösung geeignet wäre.
Reflexion: Erkläre, warum die Grenzen der Berechenbarkeit für Softwareentwicklung und KI wichtig sind.

aiMOOC-Projekte

Schulfach+

Prüfungsliteratur 2026
Bundesland	Bücher	Kurzbeschreibung
Baden-Württemberg	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck Mittlere Reife Der Markisenmann - Jan Weiler oder Als die Welt uns gehörte - Liz Kessler Ein Schatten wie ein Leopard - Myron Levoy oder Pampa Blues - Rolf Lappert	Abitur Dorfrichter-Komödie über Wahrheit/Schuld; Roman über einen Ort und deutsche Geschichte. Mittlere Reife Wahllektüren (Roadtrip-Vater-Sohn / Jugendroman im NS-Kontext / Coming-of-age / Provinzroman).
Bayern	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Lustspiel über Machtmissbrauch und Recht; Roman als Zeitschnitt deutscher Geschichte an einem Haus/Grundstück.
Berlin/Brandenburg	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Der Biberpelz - Gerhart Hauptmann Heimsuchung - Jenny Erpenbeck	Abitur Gerichtskomödie; soziales Drama um Ausbeutung/Armut; Komödie/Satire um Diebstahl und Obrigkeit; Roman über Erinnerungsräume und Umbrüche.
Bremen	Abitur Nach Mitternacht - Irmgard Keun Mario und der Zauberer - Thomas Mann Emilia Galotti - Gotthold Ephraim Lessing oder Miss Sara Sampson - Gotthold Ephraim Lessing	Abitur Roman in der NS-Zeit (Alltag, Anpassung, Angst); Novelle über Verführung/Massenpsychologie; bürgerliche Trauerspiele (Moral, Macht, Stand).
Hamburg	Abitur Der zerbrochne Krug - Heinrich von Kleist Das kunstseidene Mädchen - Irmgard Keun	Abitur Justiz-/Machtkritik als Komödie; Großstadtroman der Weimarer Zeit (Rollenbilder, Aufstiegsträume, soziale Realität).
Hessen	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Heimsuchung - Jenny Erpenbeck Der Prozess - Franz Kafka	Abitur Gerichtskomödie; Fragmentdrama über Gewalt/Entmenschlichung; Erinnerungsroman über deutsche Brüche; moderner Roman über Schuld, Macht und Bürokratie.
Niedersachsen	Abitur Der zerbrochene Krug - Heinrich von Kleist Das kunstseidene Mädchen - Irmgard Keun Die Marquise von O. - Heinrich von Kleist Über das Marionettentheater - Heinrich von Kleist	Abitur Schwerpunkt auf Drama/Roman sowie Kleist-Prosatext und Essay (Ehre, Gewalt, Unschuld; Ästhetik/„Anmut“).
Nordrhein-Westfalen	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Komödie über Wahrheit und Autorität; Roman als literarische „Geschichtsschichtung“ an einem Ort.
Saarland	Abitur Heimsuchung - Jenny Erpenbeck Furor - Lutz Hübner und Sarah Nemitz Bahnwärter Thiel - Gerhart Hauptmann	Abitur Erinnerungsroman an einem Ort; zeitgenössisches Drama über Eskalation/Populismus; naturalistische Novelle (Pflicht/Überforderung/Abgrund).
Sachsen (berufliches Gymnasium)	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Irrungen, Wirrungen - Theodor Fontane Der gute Mensch von Sezuan - Bertolt Brecht Heimsuchung - Jenny Erpenbeck Der Trafikant - Robert Seethaler	Abitur Mischung aus Klassiker-Drama, sozialem Drama, realistischem Roman, epischem Theater und Gegenwarts-/Erinnerungsroman; zusätzlich Coming-of-age im historischen Kontext.
Sachsen-Anhalt	Abitur (keine fest benannte landesweite Pflichtlektüre veröffentlicht; Themenfelder)	Abitur Schwerpunktsetzung über Themenfelder (u. a. Literatur um 1900; Sprache in politisch-gesellschaftlichen Kontexten), ohne feste Einzeltitel.
Schleswig-Holstein	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Recht/Gerechtigkeit und historische Tiefenschichten eines Ortes – umgesetzt über Drama und Gegenwartsroman.
Thüringen	Abitur (keine fest benannte landesweite Pflichtlektüre veröffentlicht; Orientierung am gemeinsamen Aufgabenpool)	Abitur In der Praxis häufig Orientierung am gemeinsamen Aufgabenpool; landesweite Einzeltitel je nach Vorgabe/Handreichung nicht einheitlich ausgewiesen.
Mecklenburg-Vorpommern	Abitur (Quelle aktuell technisch nicht abrufbar; Beteiligung am gemeinsamen Aufgabenpool bekannt)	Abitur Land beteiligt sich am länderübergreifenden Aufgabenpool; konkrete, veröffentlichte Einzeltitel konnten hier nicht ausgelesen werden.
Rheinland-Pfalz	Abitur (keine landesweit einheitliche Pflichtlektüre; schulische Auswahl)	Abitur Keine landesweite Einheitsliste; Auswahl kann schul-/kursbezogen erfolgen.