Gedächtnisprotokolle zur Diplomprüfung
"Effiziente Algorithmen (1822)"

Henrik Behrens hat sich die Mühe gemacht, alle bis zum Sommer 1996 erhältlichen Prüfungsprotokolle zum Kurs "Effiziente Algorithmen (1822)" zusammenzufassen und die Fragen den jeweiligen Kurskapiteln unterzuordnen.
Vielen Dank!

1 Berechnungsmodelle

1.1 Algorithmen und ihre Komplexität

1.2 Random Access - Maschinen (RAM)

1.3 Berechnungskomplexität von RAM-Programmen

1.4 Random Access Stored Program - Maschinen (RASP)

1.5 Abstraktionen der RAM

I. Straight-Line-Programme
II. Bitweise Berechnungen
III. Bitvektor-Operationen
IV. Entscheidungsbäume

1.6 Ein einfaches Berechnungsmodell: Die Turingmaschine

1.7 Beziehung zwischen der Turingmaschine und den RAM-Modellen

1.8 Pidgin Algol - eine Hochsprache

2. Entwurf effizienter Algorithmen

2.1 Datenstrukturen: Listen, Schlangen und Stapel

2.2 Mengendarstellungen

2.3 Graphen

2.4 Bäume

2.5 Rekursion

2.6 Divide-and-Conquer

2.7 Balancierung

2.8 Dynamisches Programmieren

3 Sortieren und Order Statistics

3.1 Das Sortierproblem

3.2 Radix-Sortieren

3.3 Sortieren durch Vergleichen

3.4 Heapsort - Ein O(n log n) - Sortieralgorithmus mit Vergleichen

3.5 Quicksort - Ein Sortieralgorithmus mit erwartetem Zeitbedarf von O(n log n)

3.6 Order Statistics

3.7 Erwarteter Zeitbedarf für Order Statistics

4. Datenstrukturen für mengenbearbeitende Probleme

4.1 Grundlegende Operationen auf Mengen

4.2 Hashing

4.3 Binäre Suche

4.4 Binäre Suchbäume

4.5 Optimale binäre Suchbäume

4.6 Ein einfacher Algorithmus zur Vereinigung disjunkter Mengen

4.7 Baumstrukturen für das Union-Find - Problem

4.8 Anwendungen und Erweiterungen des Union-Find - Problems

1. Offline-Minimum-Problem
2. Tiefenermittlungsproblem
3. Äquivalenz finiter Automaten

4.9 Schemata für balancierte Bäume

4.10 Dictionaries und Priority Queues

4.11 Mergeable Heaps

4.12 Concatenable Queues

4.13 Mengenzerlegung (Partitioning)

4.14 Zusammenfassung des Kapitels

5. Algorithmen auf Graphen

5.1 Minimale Spannbäume

5.2 Tiefensuche

5.3 Doppelte Verbundenheit (Biconnectivity)

5.4 Tiefensuche in einem gerichteten Graphen

5.5 Starke Verbundenheit (Strong Connectivity)

5.6 Pfadfindungs-Probleme

5.7 Algorithmus: transitive Hülle (transitive closure)

5.8 Algorithmus: Kürzester Pfad

5.9 Pfadprobleme und Matrixmultiplikation

5.10 Probleme mit festem Startpunkt (Single-Source Problems)

5.11 Dominierer in einem gerichteten azyklischen Graph: Konzepte zusammenfassen

6. Matrixmultiplikation und verwandte Operationen

6.1 Grundlagen

6.2 Strassen-Algorithmus für Matrix-Multiplikation

6.3 Matrizeninversion

6.4 LUP-Zerlegung von Matrizen

6.5 Anwendungen der Zerlegung

6.6 Multiplikation boolescher Matrizen

7. Die schnelle Fouriertransformation und ihre Anwendungen

7.1 Die diskrete Fouriertransformation und ihre Umkehrung

7.2 Der FFT-Algorithmus

7.3 Der FFT-Algorithmus mit Bit-Operationen

7.4 Produkt von Polynomen

7.5 Der Schönhage-Strassen-Algorithmus zur Integermultiplikation

8. Integer- und Polynom-Arithmetik

8.1 Die Ähnlichkeit von Integer-Zahlen und Polynomen

8.2 Quadieren durch Kehrwertberechnung

8.3 Polynom-Multiplikation und -Division

8.4 Modulare Arithmetik

8.5 Modulare polynomiale Arithmetik und Polynomauswertung

8.6 Chinesische Restberechnung (Chinese Remaindering)

8.7 Chinesische Restberechnung und Interpolation von Polynomen

8.8 Größter gemeinsamer Teiler und der euklidische Algorithmus

8.9 Ein asymptotisch schneller Algorithmus für den ggT von Polynomen

8.10 ggT von Integer-Zahlen

8.11 Nochmal Chinesische Restberechnung

8.12 Schwach besetzte Polynome (Sparse Polynomials)