Das LEDA-Tutorium

Joachim Ziegler

Version 0.5.3.pre7

09.01.2009 12:21:29


Widmung

 

Das ständige Ausschauhalten nach neuen Dingen, die man tut, und nach neuen technischen Spielereien, die man ausprobieren kann, ist nur ein Mittel, um sich davor zu schützen, sich selbst oder anderen nahe zu sein.

 
 -- Erich Fromm

Dieses Tutorium ist Erich Fromm (1900-1980) gewidmet, aus dessen Büchern ich viel gelernt habe, z. B. nicht ständig Ausschau halten zu müssen nach neuen Dingen, die ich tun muss, und technischen Spielereien, die ich ausprobieren kann, um mich davor zu schützen, mir selbst oder anderen nahe zu sein. Sondern nur manchmal.

Inhaltsverzeichnis

Vorwort
1. Was ist LEDA?
2. An wen wendet sich dieses Tutorium?
3. Wie ist dieses Tutorium aufgebaut?
4. Bei Fragen, Anmerkungen und Fehlern
5. Über den Autor
6. Danksagung
1. Auf die Plätze - fertig - LEDA!
1.1. Vorbereitungen
1.2. Hallo LEDA-Welt! - Das erste Programm
1.3. LEDA-Programme übersetzen, binden und starten
1.3.1. Die Unix-Welt
1.3.2. Die MS-Windows-Welt
2. Einfache Datentypen und einfache Containertypen
2.1. Zeichenketten (Klasse string)
2.1.1. Weitere Operationen auf Strings
2.1.2. Das LEDA-Regelwerk, Handle-Typen und die Klassifizierung der LEDA-Typen
2.2. Felder
2.2.1. Eindimensionale Felder (Klasse array)
2.2.2. Zweidimensionale Felder (Klasse array2)
2.2.3. Zeitkomplexität, Platzkomplexität und die O-Notation
2.3. Lineare Listen (Klasse list)
2.3.1. Grundlegende Operationen auf Listen
2.3.2. Listen und das Item-Container-Konzept
2.3.3. Listen verändern und in Listen suchen
2.3.4. Listen sortieren
2.3.5. Benutzerdefinierte Typparameter
2.3.6. Kopieren und Vergleichen von item-basierten Typen und Item-Typen
2.3.7. Weitere Informationen und Tipps
2.3.8. Einfach verkettete Listen (Klasse slist)
2.4. Stapel
2.4.1. Stapel mit unbeschränkter Elementanzahl (Klasse stack)
2.4.2. Stapel mit beschränkter Elementanzahl (Klasse b_stack)
2.5. Zufallszahlen (Klasse random_source)
2.5.1. Der ganzzahlige Modus
2.5.2. Der Bit-Modus
2.6. Zufallsvariablen
2.6.1. Statische Zufallsvariablen (Klasse random_variate)
2.6.2. Dynamische Zufallsvariablen (Klasse dynamic_random_variate)
2.7. Schlangen
2.7.1. Schlangen mit unbeschränkter Elementanzahl (Klasse queue)
2.7.2. Schlangen mit beschränkter Elementanzahl (Klasse b_queue)
2.8. Mengen (Klasse set)
2.8.1. Elemente einfügen und Test auf Enthaltensein
2.8.2. Vereinigung, Schnitt und Differenz von Mengen
2.8.3. Linear geordnete Typen
2.9. Mengen von ganzen Zahlen
2.9.1. Wenn man Minimum und Maximum im Voraus kennt (Klasse int_set)
2.9.2. Wenn Minimum oder Maximum unbekannt sind (Klasse d_int_set)
2.10. array, list, stack, queue, set und d_int_set im Vergleich
2.11. Nützliche Kleinigkeiten
2.11.1. Paare, Tripel und Quadrupel (Klassen two_tuple, three_tuple, four_tuple)
2.11.2. Mit Verzeichnissen und Dateien umgehen
2.11.3. Datumsangaben (Klasse date)
2.11.4. Effiziente Speicherverwaltung für eigene Typen
2.11.5. Einige nützliche Funktionen
2.12. Was wir nicht beschrieben haben
3. Assoziative Containertypen
3.1. Wörterbücher (Klasse dictionary)
3.2. Dictionary-Arrays (Klasse d_array)
3.3. Hashende Typen
3.3.1. Hashing und gehashte Typen
3.3.2. Hashing-Arrays (Klasse h_array)
3.3.3. Maps (Klasse map)
3.4. Geordnete Folgen (Klasse sortseq)
3.4.1. Grundfunktionalität
3.4.2. Fingersuche und schnelles Einfügen
3.4.3. Aufspalten, aneinanderhängen und zusammenmischen
3.5. dictionary, d_array, h_array, map und sortseq im Vergleich
3.6. Implementierungsparameter
3.7. Was wir nicht beschrieben haben
4. Prioritäts-Warteschlangen
4.1. Prioritäts-Warteschlangen mit unbeschränkten Prioritäten (Klasse p_queue)
4.2. Prioritäts-Warteschlangen mit beschränkten, ganzzahligen Prioritäten (Klasse b_priority_queue)
5. Graphen und Graphenalgorithmen
5.1. Grundlagen
5.2. Graphen und assoziierte Informationen
5.2.1. Wie man anfängt
5.2.2. Graphen mit Informationen versehen
5.2.3. Gerichtete und ungerichtete Graphen
5.2.4. Über Knoten und Kanten iterieren und in Graphen navigieren
5.2.5. Erzeugen und Speichern von Graphen und der Editor GraphWin
5.2.6. Planar eingebettete Graphen, Maps und Faces
5.2.7. Spezielle Hilfsdatenstrukturen für Graphenalgorithmen
5.3. Vorgefertigte Graphenalgorithmen
5.3.1. Algorithmen für grundlegende Eigenschaften
5.3.2. Grundlegende Graphenalgorithmen
5.3.3. Algorithmen für kürzeste Wege
5.3.4. Netzwerk-Fluss-Algorithmen
5.3.5. Matching-Algorithmen
5.3.6. Minimale aufspannende Bäume
5.3.7. Algorithmen für planare Graphen
5.3.8. Algorithmen zum Zeichnen von Graphen
5.4. Ein selbstgeschriebener Graphenalgorithmus
5.5. Markov-Ketten (Klassen markov_chain und dynamic_markov_chain)
5.6. Was wir nicht beschrieben haben
A. Klassifizierung der LEDA-Datentypen
B. Die goldenen LEDA-Regeln
Literaturverzeichnis
Stichwortverzeichnis

Abbildungsverzeichnis

2.1. Ein Array von Zeichen
2.2. Ein LEDA-Array mit negativen Indizes
2.3. Die Funktion resize() von Arrays
2.4. Das Pascal'sche Dreieck
2.5. Ein zweidimensionales Array
2.6. Die Regeln von Conways Spiel des Lebens
2.7. Tic-Tac-Toe
2.8. Laufzeitanalyse von Sortieren durch Minimumsuche
2.9. Die asymptotischen Schranken O und Theta
2.10. Eine Deque
2.11. Einfügen und Löschen von Elementen am Anfang und Ende einer Liste
2.12. Eine Liste mit 5 Integer
2.13. Iteration in einer Liste mit Hilfe von Items
2.14. Das Josephus-Problem
2.15. Paarungen erzeugen
2.16. Eine einfach verkettete Liste
2.17. Ein Stack
2.18. Ein Stapel zur Auswertung von arithmetischen Ausdrücken
2.19. Ein Galton-Brett
2.20. Ein zufälliger Spaziergang (Random Walk)
2.21. Eine Schlange
2.22. Altes System am Saarbrücker Hauptbahnhof
2.23. Neues System am Saarbrücker Hauptbahnhof
2.24. Eine Menge
2.25. Die Mengenoperationen Schnitt, Vereinigung und symmetrische Differenz
2.26. Ein Suchbaum
2.27. Eine fraktale Menge
2.28. Eine Menge von ganzen Zahlen realisiert als Bitvektor
3.1. Ein englisch-deutsches Wörterbuch
3.2. Ein Graph
3.3. Breitensuche
3.4. Hashing
3.5. Hashing mit Verkettung
3.6. Eine geordnete Folge
3.7. Items und Container in einer geordneten Folge
3.8. Fingersuche
4.1. Huffman-Kodierung als vollständiger binärer Baum
4.2. Konstruktion des Huffman-Codes
5.1. Ein gerichteter Graph
5.2. Ein ungerichteter Graph
5.3. Graph oder Baum?
5.4. Ein Abhängigkeitsgraph
5.5. Der Graph K3,3
5.6. Interne Darstellung eines gerichteten Graphen
5.7. Interne Darstellung eines ungerichteten Graphen
5.8. Graphen editieren mit GraphWin
5.9. Graphen visualisieren mit GraphWin
5.10. Ein DFS-Wald, berechnet von DFS_NUM() und dargestellt mit GraphWin
5.11. Die nicht-planaren Kuratowski-Graphen K5 und K3,3
5.12. Das Saarland als Graph
5.13. Das Saarland als bidirektionaler Graph
5.14. Eine Map
5.15. Maps und Face-Zyklen
5.16. Das Saarland als ebene Map
5.17. Eine ebene Map des Saarlands, die mit einer planaren Einbettung übereinstimmt.
5.18. Ein einfach, aber nicht zweifach zusammenhängender Graph
5.19. Starke Zusammenhangskomponenten
5.20. Ein Abstands-Graph und kürzeste Wege darin
5.21. Ein Netzwerk
5.22. Ein maximaler Fluss
5.23. Ein minimaler Schnitt
5.24. Ein Netzwerk mit in die Quelle einmündenden und aus der Senke ausgehenden Kanten.
5.25. Das Heiratsproblem
5.26. Ein maximales allgemeines, gewichtetes Matching
5.27. Ein minimaler aufspannender Baum
5.28. Ein planarer Graph und sein dualer Graph
5.29. Eine 5-Färbung eines Graphen
5.30. Spring Embedding eines Graphen
5.31. Straight Line Embedding eines Graphen
5.32. Tutte Embedding eines Graphen
5.33. Ein genetischer Graph
5.34. Ein nicht genetischer Graph
5.35. Eine Markov-Kette
A.1. Klassifizierung der LEDA-Datentypen

Tabellenverzeichnis

1.1. Die LEDA-Bibliotheken
2.1. array, list, stack, queue, set und d_int_set im Vergleich
3.1. dictionary, d_array, h_array und map im Vergleich
4.1. Der Huffman-Code
5.1. 5 Möglichkeiten, zu einem Graphen Informationen zu assoziieren