Entwurf und Analyse von Algorithmen

Die über mehrere Jahre hinweg gewachsenen Materialien zur gleichnamigen Vorlesung wurden erneut überarbeitet, um interessante Inhalt ergänzt und im Springer Vieweg Verlag als Studienbuch veröffentlicht. Das Werk deckt entsprechend alle Inhalte der Vorlesung ab und gestattet es, verschiedenste Aspekte über den Stoff der Vorlesung hinaus zu vertiefen.

Aus dem Inhalt

1. Einleitung
1. Ziele und Überblick
2. Algorithmentheorie - eine kurze Einführung
3. Grundlagen der Analyse von Algorithmen
4. Abstrakte Datentypen
5. Quellenangaben und Literaturhinweise
6. Aufgaben
2. Elementare Datenstrukturen
1. Lineare Listen
2. Stacks und Queues
3. Mengen
4. Graphen und Bäume
5. Partitionen
6. Quellenangaben und Literaturhinweise
7. Aufgaben
3. Das Wörterbuchproblem
1. Binäre Suchbäume
2. Balancierte Bäume
3. Digitale Suchbäume und Tries
4. Hashing
5. Datenstrukturen für das Information Retrieval
6. Quellenangaben und Literaturhinweise
7. Aufgaben
4. Graph-Algorithmen
1. Kürzeste Wege
2. Minimale Spannbäume
3. Quellenangaben und Literaturhinweise
4. Aufgaben
5. Sortieren
1. Primitive Sortier-Algorithmen
2. Quicksort
3. Heapsort
4. Mergesort
5. Distribution Counting, Radix-Exchange und Radixsort
6. Sortiernetzwerke
7. Quellenangaben und Literaturhinweise
8. Aufgaben
6. String-Algorithmen
1. String-Matching
2. Suffix-Bäume
3. Quellenangaben und Literaturhinweise
4. Aufgaben
   
7. Entwurfsmethoden für Algorithmen
1. Divide and Conquer
2. Dynamisches Programmieren
   
3. Greedy Algorithmen
   
4. Lineares Programmieren
   
5. Transformationen
   
6. Quellenangaben und Literaturhinweise
   
7. Aufgaben
   
8. Komplexitätstheorie
1. NP-Vollständigkeit
2. Wichtige NP-vollständige Probleme
   
3. Quellenangaben und Literaturhinweise
   
4. Aufgaben
   
9. Entwurfsmethoden für schwere Optimierungsprobleme
1. Backtracking und Branch&Bound
2. Approximations-Algorithmen und Heuristiken
   
3. Randomisierte Algorithmen
   
4. Quellenangaben und Literaturhinweise
   
5. Aufgaben
   

Anhang

1. Notationsverzeichnis
2. Formelsammlung
3. Syntax der Modell-Programmiersprache

Für Dozenten

Die Inhalte des Buches werden in über 100 Aufgaben vertieft, für die ich auf Anfrage gerne Lösungsvorschläge zur Verfügung stelle. Alternative können diese auch über das Dozenten-Portal des Springer Teubner Verlages bezogen werden.

Downloads

Formale Grundlagen der Programmierung

Auch zur Vorlesung Formale Grundlagen der Programmierung gibt es ein Lehrbuch, das deren Inhalte (Syntax, Semantik, Berechenbarkeit) behandelt. Über den Inhalt des Buches hinaus stehen unten (sowie auf dem Studierenden-Portal des Springer Vieweg Verlages) den Stoff vertiefende Dokumente zum download bereit.

Aus dem Inhalt

1. Syntax von Programmiersprachen
1. Grundlegende Definitionen
2. Das Wort- und Analyseproblem
3. Eigenschaften formaler Sprachen
4. Quellenangaben und Literaturhinweise
5. Aufgaben
2. Semantik von Programmiersprachen
1. Operationelle Semantik
2. Denotationelle Semantik
3. Programmverifikation
4. Quellenangaben und Literaturhinweise
5. Aufgaben
3. Die Grenzen des Berechenbaren
1. Registermaschinen und primitive Rekursion
2. Partiell rekursive Funktionen
3. Berechnebare Mengen
4. Turingmaschinen revisited
5. Loop-, While- und Goto-Berechenbarkeit
6. Chursche These
7. Schlussbemerkungen
8. Quellenangaben und Literaturhinweise
9. Aufgaben

Anhang

1. Notationsverzeichnis
2. Beweistechniken
3. Literaturverzeichnis

 Downloads