Algorithmen

Themenübersicht

Beispiel: Euklidischer Algorithmus

Datentypen

Ein-/ Ausgabe

Abschließende Bemerkungen

Felder

Verkettete Listen

Speicherzuweisung

Stapel

Schlangen

Abstrakte Datentypen

Terminologie

Eigenschaften

Darstellung binärer Bäume

Darstellung von Wäldern

Traversierung von Bäumen

Rekurrente Beziehungen

Teile und Herrsche

Rekursive Traversierung von Bäumen

Beseitigung der Rekursion

Ausblick

Rahmen

Klassifikation von Algorithmen

Berechnungskomplexität

Analyse des durchschnittlichen Falles

Näherungsweise und asymptotische Ergebnisse

Grundlegende rekurrente Beziehung

Ausblick

Auswahl eines Algorithmus

Empirische Analyse

Programmoptimierung

Algorithmen und Systeme

Sortieralgorithmen

Selection Sort

Insertion Sort

Exkurs: Bubble Sort

Kenngrößen der Leistungsfähigkeit elementarer Sortiermethoden

Sortieren von Dateien mit großen Datensätzen

Shellsort

Distribution Counting

Der grundlegende Algorithmus

Kenngrößen der Leistungsfähigkeit von Quicksort

Beseitigung der Rekursion

Kleine Teildateien

Zerlegung mit Hilfe des mittleren von drei Elementen

Auswählen

Bits

Radix Exchange Sort

Straight Radix Sort

Kenngrößen der Leistungsfähigkeit digitaler Sortierverfahren

Ein lineares Sortierverfahren

Elementare Implementationen

Die Datenstruktur des Heaps

Algorithmen mit Heaps

Heapsort

Indirekte Heaps

Weiterentwickelte Implementationen

Mischen

Mergesort

Mergesort von Listen

Bottom-Up Mergesort

Kenngrößen der Leistungsfähigkeit

Optimierte Implementationen

Weitere Bemerkungen zur Rekursion

Sortieren-Mischen

Ausgeglichenes Mehrweg-Mischen

Replacement Selection

Praktischen Erwägungen

Mehrphasen-Mischen

Ein einfacherer Weg

Suchalgorithmen

Binäre Suche

Suche in einem Binärbaum

Löschen

Indirekte binäre Suchbäumen

Top-Down 2-3-4-Bäumen

Rot-Schwarz-Bäumen

Andere Algorithmen

Hash-Funktionen

Getrennte Verkettung

Lineares Austesten

Doppeltes Hashing

Ausblick

Digitale Suchbäumen

Digitale Such-Tries

Digitales Mehrwege-Suchen

Patricia

Indexsequentielle Zugriff

B-Bäume

Erweiterbares Hashing

Virueller Speicher

Verarbeitung von Zeichenfolgen

Der grobe Algorithmus

Der Algorithmus von Kunth-Morris-Pratt

Der Algorithmus von Boyer-Moore

Der Algorithmus von Rabin-Krap

Mehrfache Suche

Beschreibung von Mustern

Automaten für das Pattern Matching

Darstellung des Automaten

Simulation des Automaten

Der rekursive Abstieg (Top-Down-Syntaxanalyse)

Bottom-Up-Syntaxanalyse

Compiler

Compiler-Compiler

Kodierung mit variabler Länge

Erzeugung des Huffman-Codes

Implementation

Spielregeln

Einfache Methoden

Ver- und Entschlüsselungsmaschinen

Kryptosysteme mit öffentlichen Schlüsseln

Geometrische Algorithmen

Punkte, Linien und Polygone

Schnitt von Strecken

Einfacher geschlossener Pfad

Enthaltensein in einem Polygon

Ausblick

Spielregeln

Einwickeln

Das Durchsuchen nach Graham

Innere Elimination

Aspekte der Leistungsfähigkeit

Elementare Verfahren

Gitterverfahren

Zweidimensionale Bäume

Mehrdimensionale Bereichssuche

Horizontale und vertikale Linien

Implementation

Allgemeiner Schnitt von Strecken

Das Problem des nächsten Paares

Voronoi-Diagramme

Algorithmen für Graphen

Glossar

Darstellung

Tiefensuche

Nichtrekursive Tiefensuche

Breitensuche

Labyrinthe

Ausblick

Zusammenhängende Komponenten

Zweifacher Zusammenhang

Algorithmen zur Vereinigungs-Suche

Minimaler Spannbaum

Prioritätssuche

Das Verfahren von Kruskal

Kürzester Pfad

Minimaler Spannbaum und kürzeste Pfade in dichten Graphen

Geometrische Probleme

Tiefensuche

Transitive Hülle

Alle kürzesten Pfade

Topologisches Sortieren

Streng zusammenhängende Komponenten

Das Problem des Flusses in einem Netzwerk

Das Verfahren von Ford-Fulkerson

Suche in Netzwerke

Bipartite Graphen

Problem der Stabilen Ehe

Weiterentwickelte Algorithmen

Mathematische Algorithmen

Methode der linearen Kongruenz

Methode der additiven Kongruenz

Test der Zufälligkeit

Bemerkungen zur Implementation

Arithmetik für Polynome

Berechnung und Interpolation von Polynomen

Multiplikation von Polynomen

Rechenoperationen mit großen ganzen Zahlen

Rechenoperationen mit Matrizen

Ein einfaches Beispiel

Beschreibung des Verfahrens

Variationen und Erweiterungen

Interpolation mit Hilfe von Polynomen

Spline-Interpolation

Methode der kleinsten Quadrate

Einfache Quadraturverfahren

Zusammengesetzte Verfahren

Adaptive Quadratur

Weiterführende Themen

Perfektes Mischen

Systolische Felder

Ausblick

Berechnen, Multiplizieren, Interpolieren

Komplexe Einheitswurzeln

Berechnung in den Einheitswurzeln

Interpolation mit Hilfe der Einheitswurzeln

Implementation

Das Rucksack-Problem

Das Produkt mehrerer Matrizen

Optimale binäre Suchbäume

Zeit- und Speicheraufwand

Lineare Optimierungsaufgaben

Geometrische Interpretation

Die Simplexmethode

Implementation

Erschöpfendes Durchsuchen in Graphen

Backtracking

Digression: Erzeugung von Permutationen

Approximationsalgorithmen