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

1 Berechnungsmodelle

• Welche Möglichkeiten kennen Sie, die Komplexität eines Algorithmus zu messen?
• Welche Modelle können bei der Messung der Zeitkomplexität einer integer-Multiplikation verwendet werden? (Bitweises Modell, TM)

1.1 Algorithmen und ihre Komplexität

1.2 Random Access - Maschinen (RAM)

• Uniformes/logarithmisches Kostenmaß (O_A, O_B) ? Wie realistisch sind die Kostenmaße?
• Worst case, expected case
• Kann die logarithmische Speicherplatzkomplexität bei einer RAM durch die uniforme Speicherplatzkomplexität abgeschätzt werden? (Nein) Umgekehrt? (Ja(?))

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

• Wie werden Adreßberechnungen im Bitmodell behandelt?

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

• Verschiedene Methoden der integer-Multiplikation beschreiben, Laufzeit n^(log 3), warum ist der Algorithmus schneller?
• Rekursionsgleichung angeben.
• Wie erreicht man es, mit 3 Multiplikationen auszukommen?

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

• Union-Find-Problem erläutern und die Anwendungen dazu!
• Pfadkompression? Ist es egal, ob der kleinere Baum an die Wurzel des größeren gehängt wird oder umgekehrt? Brauchen wir Zeiger zu den Söhnen oder reichen Zeiger zum Vater? Wie funktioniert die Find- Operation? Was beschleunigt sie? Wie sind die Komplexitäten?

4.8 Anwendungen und Erweiterungen des Union-Find - Problems

• Kruskal? Komplexität?

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

• Welche Verfahren zur Matrixmultiplikation gibt es? Laufzeit?
• Herleitung der Laufzeit?

6.3 Matrizeninversion

6.4 LUP-Zerlegung von Matrizen

6.5 Anwendungen der Zerlegung

• Welche Anwendungen zur LUP-Zerlegung kennen Sie?

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

• Wie funktioniert der FFT-Algorithmus? Warum ist er so schnell?

7.3 Der FFT-Algorithmus mit Bit-Operationen

7.4 Produkt von Polynomen

• Vergleich von Schönhage-Strassen mit Polynom-Produkt-Berechnung

7.5 Der Schönhage-Strassen-Algorithmus zur Integermultiplikation

• Welche Verfahren zur Multiplikation zweier Zahlen gibt es?
• Wie funktioniert der Schönhage-Strassen-Algorithmus? (Analogie zur Polynommultiplikation)

8. Integer- und Polynom-Arithmetik

8.1 Die Ähnlichkeit von Integer-Zahlen und Polynomen

• Was haben Integer-Zahlen und Polynome gemeinsam?

8.2 Quadieren durch Kehrwertberechnung

8.3 Polynom-Multiplikation und -Division

• Wie hängen Multiplikation und Division, Quadrieren etc. komplexitätsmäßig zusammen?
• Wie funktioniert der Algorithmus zur Reziprokwertberechnung?

8.4 Modulare Arithmetik

• Was ist modulare Arithmetik? Wie werden Zahlen dabei dargestellt? In welchem Bereich kann man dabei problemlos rechnen? Warum? (chinesischer Restwertsatz) Wie funktioniert sie (z.B. Multiplikation)? Was gilt für die p_i's?

8.5 Modulare polynomiale Arithmetik und Polynomauswertung

• Wie kann man ein Polynom auswerten, wenn nicht an einer n-ten Einheitswurzel, sondern an einer beliebigen Zahl ausgewertet werden soll? Komplexität?
• Wieso ist die Darstellung mit Hilfe der Residuen eindeutig? Beweisidee zum chinesischen Resklassensatz.

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)