Logik, Algorithmen, Datenstrukturen, Sortieren, Komplexität & UML

2.1 Prädikate und Quantoren

Ein Prädikat P(x) ist eine Aussageform, die erst durch Einsetzen eines konkreten Objekts für x zu einer Aussage mit Wahrheitswert wird. Der Allquantor ∀x: P(x) besagt, dass P für alle Objekte des Diskursbereichs gilt; der Existenzquantor ∃x: P(x) besagt, dass mindestens ein Objekt existiert, für das P gilt.

Die Negation eines quantifizierten Ausdrucks vertauscht den Quantor: ¬∀x:P(x) ≡ ∃x:¬P(x), und ¬∃x:P(x) ≡ ∀x:¬P(x) — eine Regel, die beim formalen Widerlegen von Aussagen ständig gebraucht wird.

2.2 Mehrstellige Prädikate und Quantorenreihenfolge

Mehrstellige Prädikate wie R(x,y) drücken Beziehungen zwischen mehreren Objekten aus. Bei mehreren Quantoren ist die Reihenfolge entscheidend: ∀x∃y: R(x,y) bedeutet, dass zu jedem x ein (möglicherweise von x abhängiges) y existiert, während ∃y∀x: R(x,y) ein einziges y verlangt, das für ALLE x gleichzeitig funktioniert — eine deutlich stärkere Aussage.

Diese Unterscheidung ist in der Informatik z. B. bei der Definition von Grenzwerten, Sicherheitsgarantien (für jeden Input existiert eine korrekte Antwort) oder verteilten Protokollen (existiert ein Koordinator, der für alle Knoten funktioniert) von praktischer Bedeutung.

2.3 Formalisierung natürlichsprachlicher Aussagen

Eine zentrale Fertigkeit der Prädikatenlogik ist die korrekte Formalisierung natürlichsprachlicher Sätze. 'Alle Studierenden bestehen die Klausur, wenn sie lernen' formalisiert man als ∀x: (Studierender(x) ∧ Lernt(x)) ⇒ Besteht(x) — NICHT als ∀x: Studierender(x) ⇒ (Lernt(x)⇒Besteht(x)), obwohl beide Formeln oft verwechselt werden.

Ein häufiger Fehler ist die falsche Kombination von Quantor und Junktor: Bei Allaussagen verwendet man typischerweise die Implikation (⇒), bei Existenzaussagen typischerweise die Konjunktion (∧) — 'Es gibt einen Studierenden, der lernt UND besteht' wäre ∃x: Studierender(x)∧Lernt(x)∧Besteht(x).

2.4 Pränexnormalform und Skolemisierung

Eine prädikatenlogische Formel liegt in Pränexnormalform vor, wenn alle Quantoren am Anfang stehen und sich die quantorenfreie Matrix anschließt: Q₁x₁...Qₙxₙ: M(x₁,...,xₙ). Durch Umbenennen gebundener Variablen und schrittweises Herausziehen der Quantoren lässt sich jede Formel äquivalent in diese Form überführen.

Für automatisierte Beweisverfahren wie Resolution (siehe 1.4) müssen zusätzlich die Existenzquantoren eliminiert werden — dies leistet die Skolemisierung: Eine existenzquantifizierte Variable, die im Wirkungsbereich vorausgehender Allquantoren x₁,...,xₖ steht, wird durch eine neue Skolemfunktion f(x₁,...,xₖ) ersetzt (bei fehlenden vorausgehenden Allquantoren durch eine Skolemkonstante); anschließend werden alle Existenzquantoren gestrichen. Die entstehende Formel ist nicht mehr äquivalent zur Ausgangsformel, aber erfüllbarkeitsäquivalent — für automatisierte Beweisverfahren genügt das.

2.5 Unifikation

Unifikation ist der Prozess, zwei Terme oder Literale durch geeignetes Einsetzen von Termen für Variablen syntaktisch identisch zu machen. Eine Substitution σ, die zwei Ausdrücke E₁,E₂ identisch macht (E₁σ = E₂σ), heißt Unifikator; existiert ein solches σ, heißen die Ausdrücke unifizierbar.

Unter allen Unifikatoren interessiert meist der allgemeinste Unifikator (Most General Unifier, MGU): eine Substitution, aus der sich jede andere gültige Unifikation durch zusätzliche Substitution ableiten lässt. Der Unifikationsalgorithmus findet den MGU (falls er existiert), indem er beide Ausdrücke Position für Position vergleicht: Bei einer Diskrepanz zwischen einer Variablen und einem Term wird die Variable durch den Term ersetzt (sofern die Variable nicht selbst im Term vorkommt — Occurs-Check); bei einer Diskrepanz zwischen zwei unterschiedlichen Funktionssymbolen scheitert die Unifikation.

3.1 Boolesche Operationen und Gesetze

Die Boolesche Algebra arbeitet mit den Werten {0,1} und den Operationen UND (·), ODER (+) und NICHT (¯). Es gelten Kommutativ-, Assoziativ- und Distributivgesetze sowie die booleschen De-Morgan-Regeln: (a·b)‾ = ā+b̄ und (a+b)‾ = ā·b̄.

Zusätzlich gelten Absorptionsgesetze a+(a·b) = a und a·(a+b) = a, die beim Vereinfachen boolescher Ausdrücke helfen, überflüssige Terme zu erkennen und zu eliminieren.

3.2 Schaltfunktionen und Karnaugh-Diagramme

Eine Schaltfunktion bildet n boolesche Eingänge auf einen booleschen Ausgang ab und lässt sich als Wahrheitstafel, boolescher Ausdruck oder Schaltbild (aus UND-, ODER- und NICHT-Gattern) darstellen. Karnaugh-Diagramme ordnen die Wahrheitstafel so an, dass sich benachbarte Zellen jeweils nur in einer Variablen unterscheiden, wodurch sich minimale boolesche Ausdrücke grafisch ablesen lassen.

Das Ziel der Minimierung ist eine Schaltfunktion mit möglichst wenigen Gattern und Eingängen — dies reduziert Kosten, Energieverbrauch und Verzögerung realer Schaltkreise.

3.3 Huntingtonsche Axiome und das Dualitätsprinzip

Der Mathematiker Edward Huntington zeigte 1904, dass sich die gesamte Boolesche Algebra aus einer kleinen Menge von Axiomen ableiten lässt, statt jedes Rechengesetz einzeln voraussetzen zu müssen. Die Huntingtonschen Axiome fordern: Abgeschlossenheit von · und + auf der Trägermenge, Existenz neutraler Elemente 0 (für +) und 1 (für ·), Kommutativität beider Operationen, wechselseitige Distributivität (a·(b+c)=(a·b)+(a·c) UND a+(b·c)=(a+b)·(a+c)), sowie die Existenz eines Komplements ā zu jedem Element a mit a+ā=1 und a·ā=0.

Aus dieser Axiomenmenge folgt das Dualitätsprinzip: Vertauscht man in einer beliebigen gültigen booleschen Identität systematisch · mit + und gleichzeitig 0 mit 1, entsteht wieder eine gültige Identität (das duale Gesetz) — ohne dass diese erneut einzeln bewiesen werden müsste. Das Dualitätsprinzip folgt direkt aus der symmetrischen Struktur der Huntington-Axiome in · und + bzw. 0 und 1.

4.1 Was ist ein Algorithmus?

Ein Algorithmus ist eine endliche, eindeutige Handlungsvorschrift, die aus einer Eingabe in endlich vielen Schritten eine Ausgabe erzeugt. Zentrale Eigenschaften: Determiniertheit (bei gleicher Eingabe immer dieselbe Ausgabe), Terminierung (er hält nach endlich vielen Schritten an), und Effektivität (jeder Schritt ist mit endlichem Aufwand ausführbar).

Ein Algorithmus lässt sich auf verschiedenen Abstraktionsebenen beschreiben: in natürlicher Sprache, als Pseudocode, als Flussdiagramm oder in einer konkreten Programmiersprache — alle Darstellungen beschreiben dasselbe zugrundeliegende Verfahren.

Determiniertheit ist von der eng verwandten, aber unterschiedlichen Eigenschaft Determinismus zu unterscheiden: Determinismus bezieht sich auf den ABLAUF (enthält der Algorithmus an irgendeiner Stelle einen zufälligen oder unspezifizierten Schritt, z. B. das Ziehen einer Zufallszahl?), Determiniertheit dagegen auf das ERGEBNIS (liefert derselbe Input am Ende stets denselben Output, unabhängig davon, ob der Weg dorthin zufällig war?). Ein Algorithmus kann nicht-deterministisch, aber dennoch determiniert sein — etwa ein randomisierter Algorithmus, der über verschiedene zufällige Zwischenschritte am Ende stets zum selben korrekten Ergebnis kommt.

Zwei weitere Eigenschaften ergänzen das Bild: Statische Finitheit fordert, dass die BESCHREIBUNG des Algorithmus selbst endlich ist (endlich viele Anweisungen im Programmtext), unabhängig davon, ob die AUSFÜHRUNG terminiert. Universalität fordert, dass der Algorithmus für die GESAMTE spezifizierte Eingabemenge korrekt arbeitet, nicht nur für einen Teil davon oder für günstige Spezialfälle.

4.2 Terminierungsnachweis mit Invarianten

Um zu zeigen, dass eine Schleife terminiert, sucht man eine Terminierungsfunktion (oft eine Variante genannt): eine Größe, die bei jedem Schleifendurchlauf strikt kleiner wird und dabei stets nicht-negativ (bzw. nach unten beschränkt) bleibt. Da eine solche Größe nicht unendlich oft strikt fallen kann, muss die Schleife nach endlich vielen Durchläufen enden.

Eine Schleifeninvariante ist dagegen eine Aussage, die vor und nach jedem Schleifendurchlauf wahr bleibt und zusammen mit der Abbruchbedingung die Korrektheit des Ergebnisses beweist — Terminierung und Korrektheit sind zwei getrennte Beweisaufgaben.

4.3 Rekursive Algorithmen

Ein rekursiver Algorithmus löst ein Problem, indem er es auf eine oder mehrere kleinere Instanzen desselben Problems zurückführt (Rekursionsschritt) und für eine minimale Instanz direkt eine Lösung angibt (Basisfall/Rekursionsanker). Ohne Basisfall oder ohne echte Verkleinerung der Probleminstanz terminiert die Rekursion nicht.

Viele Algorithmen lassen sich sowohl iterativ (mit Schleifen) als auch rekursiv formulieren; rekursive Formulierungen sind oft näher an der mathematischen Problemdefinition, können aber bei tiefer Rekursion höheren Speicherbedarf durch den Aufrufstapel (Call-Stack) verursachen.

Man unterscheidet direkte Rekursion, bei der eine Funktion sich unmittelbar selbst aufruft (f ruft f auf), von indirekter Rekursion, bei der der Selbstaufruf über eine oder mehrere Zwischenfunktionen erfolgt (f ruft g auf, das seinerseits — direkt oder über weitere Zwischenschritte — wieder f aufruft). Beide Formen benötigen einen Basisfall, um zu terminieren; bei indirekter Rekursion muss dieser Basisfall in mindestens einer der beteiligten Funktionen erreicht werden.

5.1 Entwurfsprinzipien und Entwurfstechniken

Beim Entwurf eines Algorithmus lassen sich zwei Ebenen unterscheiden. Entwurfsprinzipien sind grundlegende, universelle Denkweisen zur Strukturierung eines Algorithmus oder Programms: allen voran die schrittweise Verfeinerung (ein Problem wird in immer kleinere, konkretere Teilschritte zerlegt, bis jeder Schritt direkt umsetzbar ist) und die Modularisierung (Aufteilung in unabhängige, wiederverwendbare Bausteine mit klar definierten Schnittstellen).

Entwurfstechniken sind demgegenüber konkretere, für bestimmte Problemklassen anwendbare Vorgehensweisen. Divide-and-Conquer löst ein Problem, indem es in kleinere Teilprobleme derselben Art zerlegt wird, diese (oft rekursiv) gelöst werden, und die Teillösungen zu einer Gesamtlösung kombiniert werden (typisches Beispiel: Mergesort, siehe Kapitel 9). Backtracking durchsucht den Lösungsraum systematisch, indem es schrittweise Teillösungen aufbaut und bei einer Sackgasse (keine gültige Fortsetzung möglich) zur letzten Entscheidung zurückspringt und eine Alternative probiert. Problemtransformation löst ein Problem, indem es auf ein bereits gelöstes anderes Problem zurückgeführt wird, statt eine neue Lösung von Grund auf zu entwickeln. Greedy-Algorithmen treffen in jedem Schritt die lokal beste Entscheidung, ohne spätere Konsequenzen zu berücksichtigen — dies liefert nicht immer, aber bei geeigneter Problemstruktur eine global optimale Lösung.

Ob ein Greedy-Ansatz zulässig ist, hängt von der Problemstruktur ab: Besitzt das Problem die 'Greedy-Choice-Eigenschaft' (eine lokal optimale Wahl lässt sich immer zu einer global optimalen Lösung erweitern), liefert Greedy garantiert das Optimum — andernfalls kann Greedy beliebig weit vom Optimum entfernt liegen.

5.2 Testfallentwurf: Äquivalenzklassen und Grenzwertanalyse

Da erschöpfendes Testen aller möglichen Eingaben praktisch unmöglich ist, teilt man den Eingaberaum in Äquivalenzklassen ein: Teilmengen von Eingaben, von denen man annimmt, dass sie den Algorithmus gleichartig testen. Aus jeder Klasse wird typischerweise nur ein repräsentativer Testfall gewählt.

Die Grenzwertanalyse ergänzt dies gezielt um Testfälle an den Rändern der Äquivalenzklassen (und knapp innerhalb/außerhalb), da Fehler in der Praxis überproportional häufig an solchen Grenzen auftreten (sogenannte 'Off-by-one'-Fehler).

5.3 Weiße-Box- und Schwarze-Box-Tests

Beim Blackbox-Test wird der Algorithmus nur über seine Ein-/Ausgabe-Beziehung getestet, ohne Kenntnis der internen Implementierung — Testfälle werden aus der Spezifikation abgeleitet. Beim Whitebox-Test kennt man die interne Struktur und leitet Testfälle so ab, dass bestimmte Code-Pfade oder -Zweige tatsächlich durchlaufen werden (z. B. Zweigüberdeckung: jeder if/else-Zweig wird mindestens einmal ausgeführt).

Beide Testarten ergänzen sich: Blackbox-Tests prüfen, ob die Spezifikation korrekt umgesetzt wurde, Whitebox-Tests stellen sicher, dass auch selten ausgeführte Code-Pfade (z. B. Fehlerbehandlung) tatsächlich getestet werden.

6.1 Abstrakte Datentypen

Ein abstrakter Datentyp (ADT) definiert eine Menge von Werten zusammen mit den auf ihnen erlaubten Operationen, unabhängig von der konkreten Implementierung. Diese Trennung von Schnittstelle und Implementierung erlaubt es, die interne Realisierung (z. B. Array vs. verkettete Liste) auszutauschen, ohne den Code zu verändern, der den ADT verwendet.

Diese Abstraktion ist ein zentrales Prinzip guten Software-Designs: Nutzer eines ADT müssen nur die Schnittstelle (welche Operationen mit welchem Verhalten existieren) kennen, nicht die konkrete Datenrepräsentation dahinter.

6.2 Listen: Array- und verkettete Implementierung

Eine Liste speichert Elemente in einer bestimmten Reihenfolge. Bei einer Array-basierten Implementierung ist der Zugriff auf ein beliebiges Element in konstanter Zeit O(1) möglich, aber das Einfügen/Löschen in der Mitte erfordert das Verschieben nachfolgender Elemente (O(n)). Bei einer verketteten Liste (jedes Element speichert einen Zeiger auf das nächste) ist Einfügen/Löschen an bekannter Position in O(1) möglich, aber der Zugriff auf ein beliebiges Element erfordert das sequentielle Durchlaufen (O(n)).

Die Wahl zwischen beiden Implementierungen hängt vom Nutzungsmuster ab: häufiger wahlfreier Zugriff spricht für Arrays, häufiges Einfügen/Löschen an beliebiger Stelle spricht für verkettete Listen.

Bei der beschriebenen (einfach verketteten) Liste kennt jedes Element nur seinen Nachfolger — das Entfernen eines bereits bekannten Knotens erfordert daher trotzdem, zunächst dessen Vorgänger durch Durchlaufen der Liste zu finden (O(n)). Eine doppelt verkettete Liste speichert zusätzlich einen Zeiger auf den Vorgänger jedes Elements: Das Entfernen eines bekannten Knotens gelingt dadurch in O(1), ebenso die Rückwärtstraversierung der Liste — auf Kosten des zusätzlichen Speicherbedarfs für den zweiten Zeiger pro Element.

6.3 Keller (Stack) und Schlange (Queue)

Ein Keller (Stack) folgt dem LIFO-Prinzip (Last In, First Out): Nur das zuletzt eingefügte Element (oben) kann entnommen werden (push/pop, beide O(1) bei geeigneter Implementierung). Eine Schlange (Queue) folgt dagegen dem FIFO-Prinzip (First In, First Out): Elemente werden am Ende eingefügt (enqueue) und am Anfang entnommen (dequeue).

Beide Strukturen sind Spezialisierungen der allgemeinen Liste mit eingeschränkter Zugriffsreihenfolge — diese Einschränkung erlaubt gleichzeitig besonders effiziente Implementierungen und ist algorithmisch fundamental (z. B. Keller für Rekursion/Backtracking, Schlangen für Breitensuche).

7.1 Graphen: Grundbegriffe

Ein Graph G=(V,E) besteht aus einer Knotenmenge V und einer Kantenmenge E⊆V×V. Bei einem ungerichteten Graphen sind Kanten ungeordnete Paare (die Kante {u,v} verbindet u und v symmetrisch), bei einem gerichteten Graphen sind Kanten geordnete Paare (u,v) mit einer Richtung von u nach v. Der Grad eines Knotens gibt die Anzahl der mit ihm verbundenen Kanten an.

Graphen lassen sich als Adjazenzmatrix (n×n-Matrix, Eintrag 1 falls Kante vorhanden) oder als Adjazenzliste (jeder Knoten speichert eine Liste seiner Nachbarn) implementieren. Adjazenzlisten sind bei dünn besetzten Graphen (wenige Kanten relativ zu Knoten) speichereffizienter.

7.2 Bäume als spezielle Graphen

Ein Baum ist ein zusammenhängender, kreisfreier ungerichteter Graph. Ein Baum mit n Knoten besitzt stets genau n−1 Kanten. Wählt man einen Knoten als Wurzel aus, entsteht ein gewurzelter Baum mit Eltern-Kind-Beziehungen; Knoten ohne Kinder heißen Blätter.

Die Höhe eines Baumes (die Länge des längsten Pfads von der Wurzel zu einem Blatt) bestimmt maßgeblich die Effizienz vieler Algorithmen auf Bäumen — je flacher (balancierter) der Baum, desto schneller viele Operationen.

7.3 Binäre Suchbäume

Ein binärer Suchbaum ist ein Binärbaum (jeder Knoten hat höchstens zwei Kinder), bei dem für jeden Knoten gilt: alle Werte im linken Teilbaum sind kleiner, alle Werte im rechten Teilbaum sind größer als der Knotenwert. Diese Ordnungseigenschaft erlaubt Suchen, Einfügen und Löschen in O(h), wobei h die Höhe des Baumes ist.

Im ungünstigsten Fall (z. B. Einfügen bereits sortierter Werte) entartet ein unbalancierter binärer Suchbaum zu einer Liste mit Höhe h=n, wodurch Operationen auf O(n) verschlechtern. Balancierte Suchbäume (z. B. AVL-Bäume, Rot-Schwarz-Bäume) garantieren dagegen h=O(log n) durch aktive Ausgleichsoperationen bei jeder Änderung.

Ein AVL-Baum (benannt nach Adelson-Velsky und Landis) definiert Balance formal über den Balance-Faktor eines Knotens: BF(v) = h(rechter Teilbaum) − h(linker Teilbaum). Das AVL-Kriterium verlangt |BF(v)| ≤ 1 für JEDEN Knoten v. Wird dieses Kriterium nach einer Einfüge- oder Löschoperation verletzt, stellt eine Rotation (Links-, Rechts- oder eine Kombination aus beiden) die Balance lokal wieder her, ohne die Ordnungseigenschaft des Suchbaums zu verletzen.

8.1 Die Landau-Notation (O-Notation)

Die O-Notation beschreibt das asymptotische Wachstum des Ressourcenbedarfs (Zeit/Speicher) eines Algorithmus in Abhängigkeit von der Eingabegröße n, unabhängig von konstanten Faktoren und niedrigeren Ordnungstermen. f(n)=O(g(n)) bedeutet formal: es existieren Konstanten c>0 und n₀, sodass f(n)≤c·g(n) für alle n≥n₀.

Neben der oberen Schranke O (Worst-Case-Abschätzung nach oben) gibt es Ω (untere Schranke) und Θ (exakte asymptotische Ordnung, wenn obere und untere Schranke übereinstimmen). In der Praxis wird meist O verwendet, da es die relevante Garantie für den ungünstigsten Fall liefert.

8.2 Wichtige Komplexitätsklassen im Vergleich

Gängige Laufzeitklassen in aufsteigender Reihenfolge: O(1) (konstant), O(log n) (logarithmisch, z. B. binäre Suche), O(n) (linear), O(n log n) (z. B. Mergesort), O(n²) (quadratisch, z. B. Insertion Sort), O(2ⁿ) (exponentiell) und O(n!) (faktoriell). Bereits bei moderaten n unterscheidet sich das praktische Laufzeitverhalten dieser Klassen dramatisch.

Diese Unterschiede sind praktisch bedeutsam: Ein O(n²)-Algorithmus mag für n=1.000 noch akzeptabel sein (1 Million Schritte), wird aber für n=1.000.000 (1 Billion Schritte) unbrauchbar, während ein O(n log n)-Algorithmus für dieselbe Eingabegröße nur etwa 20 Millionen Schritte benötigt.

8.3 P, NP und NP-Vollständigkeit

Die Klasse P umfasst Probleme, die in Polynomialzeit (O(n^k) für eine Konstante k) lösbar sind. Die Klasse NP umfasst Probleme, deren Lösung sich in Polynomialzeit VERIFIZIEREN lässt (auch wenn das Finden der Lösung selbst länger dauern könnte). Es gilt offensichtlich P⊆NP; ob P=NP gilt, ist eines der bedeutendsten ungelösten Probleme der Informatik.

Ein Problem heißt NP-vollständig, wenn es in NP liegt und jedes andere NP-Problem sich in Polynomialzeit darauf reduzieren lässt — NP-vollständige Probleme (wie SAT aus Kapitel 1, oder das Problem des Handlungsreisenden) gelten als die 'schwersten' Probleme in NP: Fände man für eines von ihnen einen Polynomialzeit-Algorithmus, würde daraus P=NP folgen.

9.1 Einfache Sortierverfahren: Insertion Sort und Selection Sort

Insertion Sort baut die sortierte Ausgabe schrittweise auf, indem es jedes Element an der richtigen Stelle in den bereits sortierten Teil der Liste einfügt — effizient bei bereits fast sortierten Listen (bestenfalls O(n)), im Mittel und schlechtesten Fall O(n²). Selection Sort sucht in jedem Durchlauf das kleinste (verbleibende) Element und tauscht es an die richtige Position — stets O(n²), unabhängig von der Vorsortierung, aber mit minimaler Anzahl an Vertauschungen.

Beide Verfahren benötigen nur konstanten zusätzlichen Speicherplatz (In-Place-Sortierung) und sind für kleine oder fast sortierte Datenmengen praktisch durchaus konkurrenzfähig, trotz ihrer quadratischen Worst-Case-Laufzeit.

9.2 Mergesort

Mergesort ist ein Divide-and-Conquer-Verfahren: Die Liste wird rekursiv in zwei Hälften geteilt, bis Teillisten der Länge 1 entstehen (per Definition sortiert), und anschließend werden je zwei sortierte Teillisten in linearer Zeit zu einer sortierten Liste verschmolzen (Merge-Schritt). Die Laufzeit beträgt in jedem Fall (bestenfalls, mittel, schlechtestenfalls) O(n log n).

Mergesort ist stabil (die relative Reihenfolge gleicher Elemente bleibt erhalten), benötigt aber zusätzlichen Speicherplatz O(n) für den Merge-Schritt — ein klassischer Zeit-gegen-Speicher-Kompromiss gegenüber In-Place-Verfahren wie Quicksort.

9.3 Quicksort

Quicksort wählt ein Pivot-Element, partitioniert die Liste in Elemente kleiner und größer als das Pivot, und sortiert beide Partitionen rekursiv. Im Durchschnitt (bei guter Pivot-Wahl) beträgt die Laufzeit O(n log n); im ungünstigsten Fall (z. B. Pivot ist stets das kleinste/größte Element, etwa bei bereits sortierten Listen und naiver Pivot-Wahl) verschlechtert sie sich auf O(n²).

Anders als Mergesort arbeitet Quicksort In-Place (kein wesentlicher zusätzlicher Speicherbedarf) — in der Praxis ist Quicksort deshalb bei zufälligen Daten häufig schneller als Mergesort, trotz der schlechteren Worst-Case-Garantie.

9.4 Heapsort

Ein (Max-)Heap ist ein vollständiger Binärbaum mit der Heap-Eigenschaft: Der Wert jedes Knotens ist mindestens so groß wie die Werte seiner Kinder — insbesondere steht das Maximum stets an der Wurzel. Da ein Heap vollständig ist (alle Ebenen bis auf die letzte voll besetzt), lässt er sich platzsparend als Array speichern, ohne explizite Zeiger: Für einen Knoten an Index i liegen seine Kinder an den Indizes 2i+1 und 2i+2.

Heapsort nutzt diese Struktur in zwei Phasen: Zunächst wird das unsortierte Array in O(n) zu einem Max-Heap umgeformt (BottomUp-Heapify: von den untersten inneren Knoten beginnend aufwärts wird die Heap-Eigenschaft schrittweise per Sift-Down wiederhergestellt). Anschließend wird n-mal das Wurzelelement (das jeweils aktuelle Maximum) mit dem letzten Heap-Element vertauscht, der Heap um ein Element verkleinert, und die Heap-Eigenschaft an der Wurzel erneut per Sift-Down in O(log n) wiederhergestellt.

Da sowohl der Heap-Aufbau (O(n)) als auch die n Sift-Down-Operationen (je O(log n)) zur Gesamtlaufzeit beitragen, ergibt sich für Heapsort in JEDEM Fall (Best, Average, Worst Case) eine Laufzeit von O(n log n) — anders als Quicksort besitzt Heapsort also keinen quadratischen Worst-Case und arbeitet zudem In-Place (O(1) Zusatzspeicher), ist aber (anders als Mergesort) nicht stabil.

10.1 Breiten- und Tiefensuche

Die Breitensuche (BFS) durchläuft einen Graphen ebenenweise ausgehend von einem Startknoten und findet dabei in ungewichteten Graphen den kürzesten Weg (gemessen in Kantenanzahl) zu jedem erreichbaren Knoten. Die Tiefensuche (DFS) verfolgt dagegen jeden Pfad so weit wie möglich, bevor sie zurückgeht (Backtracking), und eignet sich u. a. zur Erkennung von Zusammenhangskomponenten und Zyklen.

Beide Verfahren besitzen eine Laufzeit von O(|V|+|E|) bei Adjazenzlisten-Darstellung, unterscheiden sich aber in der verwendeten Hilfsstruktur: BFS nutzt eine Schlange (FIFO), DFS nutzt einen Keller (LIFO) bzw. Rekursion.

10.2 Der Dijkstra-Algorithmus

Der Dijkstra-Algorithmus berechnet kürzeste Wege von einem Startknoten zu allen anderen Knoten in einem Graphen mit nichtnegativen Kantengewichten. Er hält für jeden Knoten eine vorläufige Distanzschätzung, wählt in jedem Schritt greedy den noch nicht endgültig bestimmten Knoten mit kleinster vorläufiger Distanz, und aktualisiert (relaxiert) die Distanzen seiner Nachbarn.

Die Korrektheit von Dijkstra beruht entscheidend auf der Nichtnegativität der Kantengewichte: Bei negativen Gewichten kann ein bereits als 'endgültig' markierter Knoten später doch noch über einen anderen Pfad günstiger erreichbar sein, wodurch der Algorithmus fehlerhafte Ergebnisse liefern würde.

10.3 Minimale Spannbäume: Kruskal und Prim

Ein Spannbaum eines zusammenhängenden Graphen ist ein Teilgraph, der alle Knoten mit der minimal möglichen Anzahl an Kanten (n−1) verbindet, ohne Kreise. Ein minimaler Spannbaum minimiert zusätzlich die Summe der Kantengewichte. Der Kruskal-Algorithmus fügt Kanten in aufsteigender Gewichtsreihenfolge hinzu, sofern sie keinen Kreis erzeugen; der Prim-Algorithmus wächst stattdessen einen einzigen zusammenhängenden Baum, indem er in jedem Schritt die günstigste Kante zu einem neuen, noch nicht enthaltenen Knoten hinzufügt.

Beide Algorithmen sind Greedy-Verfahren und liefern (anders als beim allgemeinen Wechselgeldproblem aus Kapitel 5) nachweislich immer die global optimale Lösung — eine direkte Folge der sogenannten Schnitteigenschaft minimaler Spannbäume.

10.4 Eulersche und Hamiltonsche Kreise

Ein Eulerkreis ist ein geschlossener Weg durch einen Graphen, der JEDE KANTE genau einmal durchläuft (Knoten dürfen dabei mehrfach besucht werden). Ein zusammenhängender Graph besitzt genau dann einen Eulerkreis, wenn jeder Knoten geraden Grad hat (Satz von Euler) — besitzen genau zwei Knoten ungeraden Grad, existiert immerhin ein offener Eulerweg (Start und Ende an den beiden ungeradzahligen Knoten).

Ein Hamiltonkreis ist demgegenüber ein geschlossener Weg, der JEDEN KNOTEN genau einmal besucht (Kanten können dabei ausgelassen werden). Anders als beim Eulerkreis gibt es für die Existenz eines Hamiltonkreises kein einfaches notwendiges-und-hinreichendes Kriterium — das Entscheidungsproblem ist NP-vollständig (siehe Kapitel 8), sodass im Allgemeinen nur Brute-Force-Suche über alle n! Knotenpermutationen bleibt.

10.5 Der Bellman-Ford-Algorithmus

Der Bellman-Ford-Algorithmus berechnet wie Dijkstra kürzeste Wege von einem Startknoten zu allen anderen Knoten, funktioniert aber im Gegensatz zu Dijkstra auch bei NEGATIVEN Kantengewichten. Statt greedy den nächstgünstigsten Knoten zu wählen, relaxiert Bellman-Ford in |V|−1 Runden systematisch ALLE Kanten des Graphen: In jeder Runde wird für jede Kante (u,v) geprüft, ob der Weg über u eine kürzere Distanz zu v liefert als die bisher bekannte, und die Distanz gegebenenfalls aktualisiert.

Nach |V|−1 Runden sind alle kürzesten Wege korrekt berechnet, sofern der Graph keinen vom Startknoten aus erreichbaren negativen Zyklus enthält (einen Kreis, dessen Kantengewichte in Summe negativ sind — dort gäbe es keinen kürzesten Weg mehr, da man durch beliebig häufiges Durchlaufen des Zyklus die Distanz beliebig weit senken könnte). Eine zusätzliche |V|-te Runde prüft genau das: Lässt sich in dieser Runde noch eine Distanz verbessern, enthält der Graph einen negativen Zyklus.

11.1 Anwendungsfalldiagramme

Ein Anwendungsfalldiagramm (Use-Case-Diagramm) beschreibt aus Nutzersicht, welche Funktionalitäten ('Anwendungsfälle') ein System bereitstellt, und welche Akteure (Nutzer oder externe Systeme) mit welchen Anwendungsfällen interagieren. Es abstrahiert bewusst von der internen Implementierung und konzentriert sich auf das WAS (welche Funktionen), nicht das WIE.

Beziehungen zwischen Anwendungsfällen wie «include» (ein Anwendungsfall schließt einen anderen zwingend ein) und «extend» (ein Anwendungsfall erweitert einen anderen optional) strukturieren komplexere Anforderungen, ohne Funktionalität mehrfach zu beschreiben.

11.2 Klassendiagramme

Ein Klassendiagramm modelliert die statische Struktur eines Systems: Klassen mit ihren Attributen und Methoden, sowie Beziehungen zwischen Klassen. Wichtige Beziehungstypen sind Assoziation (allgemeine strukturelle Verbindung), Aggregation (Ganzes-Teil-Beziehung, Teile existieren auch unabhängig vom Ganzen) und Komposition (starke Ganzes-Teil-Beziehung, Teile existieren nicht ohne das Ganze).

Vererbung (Generalisierung) modelliert eine Ist-Ein-Beziehung zwischen einer allgemeineren Oberklasse und spezielleren Unterklassen, die deren Attribute und Methoden erben und um eigene ergänzen oder überschreiben können.

Attribute und Methoden tragen zusätzlich ein Sichtbarkeitssymbol, das ihre Zugreifbarkeit von außen regelt: + steht für public (von überall zugreifbar), − für private (nur innerhalb der eigenen Klasse) und # für protected (innerhalb der Klasse und ihrer Unterklassen). Neben der klassischen Vererbung modelliert UML auch abstrakte Klassen (nicht direkt instanziierbar, enthalten mindestens eine nur deklarierte, kursiv dargestellte Methode) und Interfaces (reine Verhaltensverträge ohne eigene Implementierung, gekennzeichnet durch «interface»): Eine Klasse kann nur von EINER Oberklasse erben, aber MEHRERE Interfaces gleichzeitig implementieren — Interfaces erlauben so, unabhängige Rollen zu kombinieren, ohne die Beschränkung der Einfachvererbung.

11.3 Objektdiagramme und Multiplizitäten

Ein Objektdiagramm zeigt eine konkrete Momentaufnahme von Objekten (Instanzen von Klassen) und ihren tatsächlichen Verbindungen zu einem bestimmten Zeitpunkt — im Unterschied zum Klassendiagramm, das die allgemeine, zeitunabhängige Struktur beschreibt. Multiplizitäten an den Enden einer Assoziation (z. B. 1, 0..1, 1..*, 0..*) geben an, wie viele Objekte auf jeder Seite einer Beziehung minimal/maximal beteiligt sein können.

Objektdiagramme sind besonders nützlich, um komplexe oder potenziell missverständliche Multiplizitäten anhand eines konkreten Beispiels zu verdeutlichen, bevor das allgemeine Klassendiagramm final festgelegt wird.

12.1 Sequenzdiagramme

Ein Sequenzdiagramm zeigt den zeitlichen Ablauf von Nachrichten (Methodenaufrufen) zwischen Objekten für ein konkretes Szenario. Objekte werden als vertikale Lebenslinien dargestellt, Nachrichten als horizontale (meist beschriftete) Pfeile zwischen ihnen — die vertikale Achse repräsentiert die Zeit, typischerweise von oben nach unten.

Aktivierungsbalken auf den Lebenslinien markieren, während welcher Zeitspanne ein Objekt aktiv Verarbeitung durchführt (z. B. weil es gerade eine Methode ausführt oder auf eine Antwort wartet) — dies macht auch komplexe, verschachtelte Aufrufsequenzen übersichtlich nachvollziehbar.

Für Kontrollstrukturen innerhalb eines Sequenzdiagramms definiert UML kombinierte Fragmente, die als beschrifteter Rahmen um den betroffenen Diagrammbereich gezeichnet werden: loop rahmt einen wiederholt ausgeführten Nachrichtenaustausch ein, alt modelliert alternative Abläufe (wie ein if/else, mit mehreren durch eine gestrichelte Linie getrennten Bereichen), opt einen optionalen, nur unter einer Bedingung ausgeführten Bereich, par kennzeichnet mehrere nebenläufig ablaufende Bereiche, und critical (bzw. strict) markiert einen Bereich, der als atomare, nicht unterbrechbare Einheit ausgeführt werden muss.

Nachrichten selbst unterscheiden sich in ihrer Pfeilnotation je nach Aufrufart: Ein synchroner Methodenaufruf (der Sender wartet auf die Antwort) wird als durchgezogener Pfeil mit gefüllter Pfeilspitze dargestellt, ein asynchroner Aufruf (der Sender wartet nicht) als durchgezogener Pfeil mit offener Pfeilspitze.

12.2 Zustandsdiagramme

Ein Zustandsdiagramm (Statechart) modelliert die möglichen Zustände eines Objekts und die Übergänge zwischen ihnen als Reaktion auf Ereignisse. Zustände werden als abgerundete Rechtecke, Übergänge als beschriftete Pfeile dargestellt; ein ausgefüllter Kreis markiert den Startzustand, ein umkreister ausgefüllter Kreis den Endzustand.

Zustandsdiagramme eignen sich besonders für Objekte mit komplexem, ereignisgesteuertem Verhalten (z. B. eine Bestellung, die verschiedene Stadien von 'Aufgegeben' über 'Versendet' bis 'Zugestellt' oder 'Storniert' durchläuft), bei denen zu jedem Zeitpunkt nur bestimmte Übergänge zulässig sind.

Die in UML verwendete Notation für Zustandsdiagramme geht auf die von David Harel 1987 eingeführten Statecharts zurück, die klassische endliche Automaten um hierarchische und nebenläufige Zustände erweiterten.

12.3 Aktivitätsdiagramme

Ein Aktivitätsdiagramm modelliert den Kontrollfluss eines Prozesses oder Algorithmus — ähnlich einem klassischen Flussdiagramm, aber mit zusätzlichen UML-spezifischen Notationselementen für Nebenläufigkeit (Gabelung/Vereinigung paralleler Abläufe) und Entscheidungen (Verzweigung basierend auf Bedingungen).

Anders als Sequenzdiagramme (die auf die Interaktion zwischen konkreten Objekten fokussieren) modellieren Aktivitätsdiagramme den GESAMTABLAUF eines Geschäftsprozesses oder Algorithmus, unabhängig davon, welches Objekt welchen Schritt konkret ausführt.