Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 13

IGrundlegende Konzepte

1Vorbemerkungen und Überblick

1.1Informatik, Algorithmen und Datenstrukturen

1.2Historischer Überblick: Algorithmen

1.3Historie von Programmiersprachen und Java

1.4Grundkonzepte der Programmierung in Java

2Algorithmische Grundkonzepte

2.1Intuitiver Algorithmusbegriff

2.1.1Beispiele für Algorithmen

2.1.2Bausteine für Algorithmen

2.1.3Pseudocode-Notation für Algorithmen

2.1.4Struktogramme

2.1.5Rekursion

2.2Sprachen und Grammatiken

2.2.1Begriffsbildung

2.2.2Reguläre Ausdrücke

2.2.3Backus-Naur-Form (BNF)

2.3Elementare Datentypen

2.3.1Datentypen als Algebren

2.3.2Signaturen von Datentypen

2.3.3Der Datentyp bool

2.3.4Der Datentyp integer

2.3.5Felder und Zeichenketten

2.4Terme

2.4.1Bildung von Termen

2.4.2Algorithmus zur Termauswertung

2.5Datentypen in Java

2.5.1Primitive Datentypen

2.5.2Referenzdatentypen

2.5.3Operatoren

3Algorithmenparadigmen

3.1Überblick über Algorithmenparadigmen

3.2Applikative Algorithmen

3.2.1Terme mit Unbestimmten

3.2.2Funktionsdefinitionen

3.2.3Auswertung von Funktionen

3.2.4Erweiterung der Funktionsdefinition

3.2.5Applikative Algorithmen

3.2.6Beispiele für applikative Algorithmen

3.3Imperative Algorithmen

3.3.1Grundlagen imperativer Algorithmen

3.3.2Komplexe Anweisungen

3.3.3Beispiele für imperative Algorithmen

3.4Das logische Paradigma

3.4.1Logik der Fakten und Regeln

3.4.2Deduktive Algorithmen

3.5Weitere Paradigmen

3.5.1Genetische Algorithmen

3.5.2Neuronale Netze

3.6Umsetzung in Java

3.6.1Ausdrücke und Anweisungen

3.6.2Methoden

3.6.3Applikative Algorithmen und Rekursion

4Literaturhinweise zum Teil I

IIAlgorithmen

5Ausgewählte Algorithmen

5.1Suchen in sortierten Folgen

5.1.1Sequenzielle Suche

5.1.2Binäre Suche

5.2Sortieren

5.2.1Sortieren: Grundbegriffe

5.2.2Sortieren durch Einfügen

5.2.3Sortieren durch Selektion

5.2.4Sortieren durch Vertauschen: BubbleSort

5.2.5Sortieren durch Mischen: MergeSort

5.2.6QuickSort

5.2.7Sortieren durch Verteilen: RadixSort

5.2.8Sortierverfahren im Vergleich

6Formale Algorithmenmodelle

6.1Registermaschinen

6.2Abstrakte Maschinen

6.3Markov-Algorithmen

6.4Church’sche These

6.5Interpreter für formale Algorithmenmodelle in Java

6.5.1Java: Markov-Interpreter

6.5.2Registermaschine in Java

7Eigenschaften von Algorithmen

7.1Berechenbarkeit und Entscheidbarkeit

7.1.1Existenz nichtberechenbarer Funktionen

7.1.2Konkrete nichtberechenbare Funktionen

7.1.3Das Halteproblem

7.1.4Nichtentscheidbare Probleme

7.1.5Post’sches Korrespondenzproblem

7.2Korrektheit von Algorithmen

7.2.1Relative Korrektheit

7.2.2Korrektheit von imperativen Algorithmen

7.2.3Korrektheitsbeweise für Anweisungstypen

7.2.4Korrektheit imperativer Algorithmen an Beispielen

7.2.5Korrektheit applikativer Algorithmen

7.3Komplexität

7.3.1Motivierendes Beispiel

7.3.2Asymptotische Analyse

7.3.3Komplexitätsklassen

7.3.4Analyse von Algorithmen

8Entwurf von Algorithmen

8.1Entwurfsprinzipien

8.1.1Schrittweise Verfeinerung

8.1.2Einsatz von Algorithmenmustern

8.1.3Problemreduzierung durch Rekursion

8.2Algorithmenmuster: Greedy

8.2.1Greedy-Algorithmen am Beispiel

8.2.2Greedy: Optimales Kommunikationsnetz

8.2.3Verfeinerung der Suche nach billigster Kante

8.3Rekursion: Divide-and-conquer

8.3.1Das Prinzip »Teile und herrsche«

8.3.2Beispiel: Spielpläne für Turniere

8.4Rekursion: Backtracking

8.4.1Prinzip des Backtracking

8.4.2Beispiel: Das Acht-Damen-Problem

8.4.3Beispiel: Tic Tac Toe mit Backtracking

8.5Dynamische Programmierung

8.5.1Das Rucksackproblem

8.5.2Rekursive Lösung des Rucksackproblems

8.5.3Prinzip der dynamischen Programmierung

9Parallele und verteilte Berechnungen

9.1Grundlagen

9.2Modell der Petri-Netze

9.2.1Definition von Petri-Netzen

9.2.2Formalisierung von Petri-Netzen

9.2.3Das Beispiel der fünf Philosophen

9.3Programmieren nebenläufiger Abläufe

9.3.1Koordinierte Prozesse

9.3.2Programmieren mit Semaphoren

9.3.3Philosophenproblem mit Semaphoren

9.3.4Verklemmungsfreie Philosophen

9.4Nebenläufige Berechnungen in Java

9.4.1Threads und wechselseitiger Ausschluss

9.4.2Parallelisierung in Java

9.4.3Das Philosophenproblem in Java

10Literaturhinweise zum Teil II

IIIDatenstrukturen

11Abstrakte Datentypen

11.1Signaturen und Algebren

11.2Algebraische Spezifikation

11.2.1Spezifikationen und Modelle

11.2.2Termalgebra und Quotiententermalgebra

11.2.3Probleme mit initialer Semantik

11.3Beispiele für abstrakte Datentypen

11.3.1Der Kellerspeicher (Stack)

11.3.2Beispiel für Kellernutzung

11.3.3Die Warteschlange (Queue)

11.4Entwurf von Datentypen

12Klassen, Schnittstellen und Objekte in Java

12.1Grundzüge der Objektorientierung

12.2Klassen und Objekte in Java

12.3Vererbung

12.4Abstrakte Klassen und Schnittstellen

12.5Ausnahmen

12.6Umsetzung abstrakter Datentypen

12.7Lambda-Ausdrücke

13Grundlegende Datenstrukturen

13.1Stack und Queue als Datentypen

13.1.1Implementierung des Stacks

13.1.2Implementierung der Queue

13.1.3Bewertung der Implementierungen

13.2Verkettete Listen

13.3Doppelt verkettete Listen

13.4Skip-Listen

13.5Das Iterator-Konzept

13.6Java Collection Framework

13.7Generics in Java

14Bäume

14.1Bäume: Begriffe und Konzepte

14.2Binärer Baum: Datentyp und Basisalgorithmen

14.2.1Der Datentyp »Binärer Baum«

14.2.2Algorithmen zur Traversierung

14.3Suchbäume

14.3.1Suchen in Suchbäumen

14.3.2Einfügen und Löschen

14.3.3Komplexität der Operationen

14.4Ausgeglichene Bäume

14.4.1Rot-Schwarz-Bäume

14.4.2AVL-Bäume

14.4.3B-Bäume

14.5Digitale Bäume

14.5.1Tries

14.5.2Patricia-Bäume

14.6Praktische Nutzung von Bäumen

14.6.1Sortieren mit Bäumen: HeapSort

14.6.2Sets mit binären Suchbäumen

15Hashverfahren

15.1Grundprinzip des Hashens

15.2Grundlagen und Verfahren

15.2.1Hashfunktionen

15.2.2Behandlung von Kollisionen

15.2.3Aufwand beim Hashen

15.2.4Hashen in Java

15.2.5Cuckoo-Hashing

15.3Dynamische Hashverfahren

15.3.1Grundideen für dynamische Hashverfahren

15.3.2Erweiterbares Hashen

15.3.3Umsetzung des erweiterbaren Hashens

16Graphen

16.1Arten von Graphen

16.1.1Ungerichtete Graphen

16.1.2Gerichtete Graphen

16.1.3Gewichtete Graphen

16.1.4Weitere Eigenschaften von Graphen

16.2Realisierung von Graphen

16.2.1Knoten- und Kantenlisten

16.2.2Adjazenzmatrix

16.2.3Graphen als dynamische Datenstrukturen

16.2.4Transformationen zwischen Darstellungen

16.2.5Vergleich der Komplexität

16.2.6Eine Java-Klasse für Graphen

16.3Ausgewählte Graphenalgorithmen

16.3.1Breitendurchlauf

16.3.2Tiefendurchlauf

16.3.3Zyklenfreiheit und topologisches Sortieren

16.4Algorithmen auf gewichteten Graphen

16.4.1Kürzeste Wege

16.4.2Dijkstras Algorithmus

16.4.3A*-Algorithmus

16.4.4Kürzeste Wege mit negativen Kantengewichten

16.4.5Maximaler Durchfluss

16.4.6Der Ford-Fulkerson-Algorithmus

16.5Zentralitätsanalyse in Graphen

16.6Weitere Fragestellungen für Graphen

17Algorithmen auf Texten

17.1Probleme der Worterkennung

17.2Knuth-Morris-Pratt

17.3Boyer-Moore

17.4Pattern Matching

17.4.1Reguläre Ausdrücke

17.4.2Endliche Automaten

17.4.3Java-Klassen für reguläre Ausdrücke

17.5Ähnlichkeit von Zeichenketten

17.5.1Levenshtein-Distanz

17.5.2n-Gramme

17.5.3Anwendungen der Ähnlichkeitsvergleiche

18Literaturhinweise zum Teil III

IVAnhang

AQuelltext der Klasse IOUtils

Abbildungsverzeichnis

Tabellenverzeichnis

Algorithmenverzeichnis

Beispielverzeichnis

Programmverzeichnis

Literaturverzeichnis

Index