| Di 18.10.2005 |
- Überblick
- Wiederholung
- Divide and Conquer
- Bsp. Mergesort
- Bsp. Quicksort
- Lösen von Rekursionsgleichungen
|
| Fr 21.10.2005 |
- Divide and Conquer
- Bsp. Multiplikation nach Karatsuba
- Dynamisches Programmieren
- Bsp. Planung der Multiplikation mehrerer Matrizen
|
| Di 25.10.2005 |
- Dynamisches Programmieren
- Bsp. CYK (Cocke-Younger-Kasami) Algorithmus für kontextfreie Sprachen
- Branch and Bound
|
| Fr 28.10.2005 |
- Dynamisches Programmieren
- Bsp. 0-1-Rucksackproblem (alternativ)
- Divide and Conquer
- Bsp. Auswahlproblem - Bestimmung des Median
|
| Di 01.11.2005 |
- Lösen von Rekursionsgleichungen
- Einsetzen
- Induktion
- Betrachten des Rekursionsbaums
- Master Methode
|
| Fr 04.11.2005 |
- Graphenalgorithmen [2.]
- kürzeste Wege (Bellman-Ford) [2.1]
|
| Di 08.11.2005 |
keine Vorlesung
|
| Fr 11.11.2005 |
keine Vorlesung
|
| Di 15.11.2005 |
- Graphenalgorithmen
- kürzeste Wege (Bellman-Ford / Moore) [2.1]
|
| Fr 18.11.2005 |
- Graphenalgorithmen
- kürzeste Wege in DAGs [2.2]
- kürzeste Wege (Dijkstra) [2.3]
|
| Di 22.11.2005 |
- Graphenalgorithmen
- algebraische Formulierung des Wegeproblems (über Halbringen) [2.4]
|
| Fr 25.11.2005 |
- Graphenalgorithmen
- algebraische Formulierung des Wegeproblems (über Halbringen) [2.4]
- Algorithmus von Floyd und Warshall [2.5]
|
| Di 29.11.2005 |
- Graphenalgorithmen
- Algorithmus von Floyd und Warshall [2.5]
- Verallgemeinerung des Algorithmus von Dijkstra
- Binomial-Halden
|
| Fr 02.12.2005 |
|
| Di 06.12.2005 |
- Datenstrukturen
- Fibonacci-Halden
- Amortisierte Analyse
|
| Fr 09.12.2005 |
- Datenstrukturen
- Amortisierte Analyse
- Treaps (Balden)
|
| Di 13.12.2005 |
|
| Fr 16.12.2005 |
- Graphenalgorithmen
- Minimum Spanning Tree (MST) - Kruskals Algorithmus
|
| Di 03.01.2006 |
- Datenstrukturen
- Union-Find mit Bäumen (Analyse)
|
| Fr 06.01.2006 |
- Datenstrukturen
- Union-Find mit Bäumen (Analyse)
- Union-Find Anwendung: Offline-Min-Problem
- Komplexitätstheorie
|
| Di 10.01.2006 |
- Komplexitätstheorie
- Random Access Memory/Machine (RAM)
- Turing-Maschine
- Die Klasse P
|
| Fr 13.01.2006 |
- Komplexitätstheorie
- Nichtdeterministische Turing-Maschine
- Die Klasse NP
- Polynomialzeitreduktion
|
| Di 17.01.2006 |
- Komplexitätstheorie
- NP-schwerheit
- NP-vollständigkeit
- SAT als NP-vollständiges Problem (Satz von Cook)
|
| Fr 20.01.2006 |
- Komplexitätstheorie
- Unabhängige Knotenmenge (Independent Set)
- Hamilton Kreis
|
| Di 24.01.2006 |
- Komplexitätstheorie
- Graphenfärbungen
- Teilmengensumme (Subset Sum)
- Rucksack
|
| Fr 27.01.2006 |
- Komplexitätstheorie
- starke/schwache NP-schwerheit
- Approximation für TSP mit Dreiecksungleichung
- Co-NP, PSACE, ...
|
| Di 31.01.2006 |
keine Vorlesung
|
| Fr 03.02.2006 |
keine Vorlesung
|
| Di 07.02.2006 |
|
| Fr 10.02.2006 |
Klausur
|