Gliederung der Vorlesung: Difference between revisions
From Alda
Jump to navigationJump to search
(Beschreibendes Index des Vorlesungsskriptes sollte jetzt vollständig sein (Design ändert sich vielleicht noch)) |
(Titelgröße geändert) |
||
| Line 1: | Line 1: | ||
<!-------------> | <!-------------> | ||
==[[Einführung]]== | ===[[Einführung]]=== | ||
(17.4.2012) | (17.4.2012) | ||
* Definition von Algorithmen und Datenstrukturen, Geschichte | * Definition von Algorithmen und Datenstrukturen, Geschichte | ||
| Line 7: | Line 7: | ||
* Python-Grundlagen | * Python-Grundlagen | ||
<!-------------> | <!-------------> | ||
==[[Container]]== | ===[[Container]]=== | ||
(19.4.2012) | (19.4.2012) | ||
* Anforderungen von Algorithmen an Container | * Anforderungen von Algorithmen an Container | ||
| Line 14: | Line 14: | ||
* Sequenzen und Intervalle (Ranges) | * Sequenzen und Intervalle (Ranges) | ||
<!-------------> | <!-------------> | ||
==[[Sortieren]]== | ===[[Sortieren]]=== | ||
(24. und 26.4.2012) | (24. und 26.4.2012) | ||
* Spezifikation des Sortierproblems | * Spezifikation des Sortierproblems | ||
| Line 23: | Line 23: | ||
* Laufzeitmessung in Python | * Laufzeitmessung in Python | ||
<!-------------> | <!-------------> | ||
==[[Korrektheit]]== | ===[[Korrektheit]]=== | ||
(3. und 8.5.2012) | (3. und 8.5.2012) | ||
* Definition von Korrektheit, Algorithmen-Spezifikation | * Definition von Korrektheit, Algorithmen-Spezifikation | ||
| Line 31: | Line 31: | ||
* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | * Ausnahmen (exceptions) und Ausnahmebehandlung in Python | ||
<!-------------> | <!-------------> | ||
==[[Effizienz]]== | ===[[Effizienz]]=== | ||
(10. und 15.5.2012) | (10. und 15.5.2012) | ||
* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference | * Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference | ||
| Line 39: | Line 39: | ||
* Amortisierte Komplexität | * Amortisierte Komplexität | ||
<!-------------> | <!-------------> | ||
==[[Suchen]]== | ===[[Suchen]]=== | ||
(22. und 24.5.2012) | (22. und 24.5.2012) | ||
* Lineare Suche | * Lineare Suche | ||
| Line 47: | Line 47: | ||
* Komplexität der Suche | * Komplexität der Suche | ||
<!-------------> | <!-------------> | ||
==[[Prioritätswarteschlangen]]== | ===[[Prioritätswarteschlangen]]=== | ||
(29.5.2012) | (29.5.2012) | ||
* Heap-Datenstruktur | * Heap-Datenstruktur | ||
| Line 54: | Line 54: | ||
* Komplexität des Heaps | * Komplexität des Heaps | ||
<!-------------> | <!-------------> | ||
==[[Hashing und assoziative Arrays]]== | ===[[Hashing und assoziative Arrays]]=== | ||
(31.5.und 5.6.2012) | (31.5.und 5.6.2012) | ||
* Implementation assoziativer Arrays mit Bäumen | * Implementation assoziativer Arrays mit Bäumen | ||
| Line 61: | Line 61: | ||
* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus | * Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus | ||
<!-------------> | <!-------------> | ||
==[[Iteration versus Rekursion]]== | ===[[Iteration versus Rekursion]]=== | ||
(12.6.2012) | (12.6.2012) | ||
* Typen der Rekursion und ihre Umwandlung in Iteration | * Typen der Rekursion und ihre Umwandlung in Iteration | ||
* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode | * Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode | ||
<!-------------> | <!-------------> | ||
==[[Generizität]]== | ===[[Generizität]]=== | ||
(14.6.2012) | (14.6.2012) | ||
* Abstrakte Datentypen, Typspezifikation | * Abstrakte Datentypen, Typspezifikation | ||
| Line 74: | Line 74: | ||
* Operator overloading in Python | * Operator overloading in Python | ||
<!-------------> | <!-------------> | ||
==[[Graphen und Graphenalgorithmen]]== | ===[[Graphen und Graphenalgorithmen]]=== | ||
(19. bis 28.6.2012) | (19. bis 28.6.2012) | ||
* Einführung | * Einführung | ||
| Line 98: | Line 98: | ||
<!--* Systematisierung von Algorithmen aus der bisherigen Vorlesung--> | <!--* Systematisierung von Algorithmen aus der bisherigen Vorlesung--> | ||
<!-------------> | <!-------------> | ||
<!--==[[Analytische Optimierung]]== | <!--===[[Analytische Optimierung]]=== | ||
(25.6.2008)//--> | (25.6.2008)//--> | ||
<!--* Methode der kleinsten Quadrate--> | <!--* Methode der kleinsten Quadrate--> | ||
<!--* Approximation von Geraden--> | <!--* Approximation von Geraden--> | ||
<!-------------> | <!-------------> | ||
==[[Randomisierte Algorithmen]]== | ===[[Randomisierte Algorithmen]]=== | ||
(3. und 5.7.2012) | (3. und 5.7.2012) | ||
* Zufallszahlen, Zyklenlänge, Pitfalls | * Zufallszahlen, Zyklenlänge, Pitfalls | ||
| Line 113: | Line 113: | ||
* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate) | * RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate) | ||
<!-------------> | <!-------------> | ||
==[[Greedy-Algorithmen und Dynamische Programmierung]]== | ===[[Greedy-Algorithmen und Dynamische Programmierung]]=== | ||
(10. und 12.7.2012) | (10. und 12.7.2012) | ||
* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen | * Prinzipien, Aufwandsreduktion in Entscheidungsbäumen | ||
| Line 120: | Line 120: | ||
* Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung | * Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung | ||
<!-------------> | <!-------------> | ||
==[[NP-Vollständigkeit]]== | ===[[NP-Vollständigkeit]]=== | ||
(17. und 19.7.2012) | (17. und 19.7.2012) | ||
* die Klassen P und NP | * die Klassen P und NP | ||
* NP-Vollständigkeit und Problemreduktion | * NP-Vollständigkeit und Problemreduktion | ||
<!-------------> | <!-------------> | ||
==Reserve und/oder Wiederholung== | ===Reserve und/oder Wiederholung=== | ||
(24. und 26.7.2012) | (24. und 26.7.2012) | ||
Latest revision as of 01:18, 27 May 2012
Einführung
(17.4.2012)
- Definition von Algorithmen und Datenstrukturen, Geschichte
- Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
- Fundamentale Datenstrukturen: Zahlen, Container, Handles
- Python-Grundlagen
Container
(19.4.2012)
- Anforderungen von Algorithmen an Container
- Einteilung der Container
- Grundlegende Container: Array, verkettete Liste, Stack und Queue
- Sequenzen und Intervalle (Ranges)
Sortieren
(24. und 26.4.2012)
- Spezifikation des Sortierproblems
- Selection Sort und Insertion Sort
- Merge Sort
- Quick Sort und seine Varianten
- Vergleich der Anzahl der benötigten Schritte
- Laufzeitmessung in Python
Korrektheit
(3. und 8.5.2012)
- Definition von Korrektheit, Algorithmen-Spezifikation
- Korrektheitsbeweise versus Testen
- Vor- und Nachbedingungen, Invarianten, Programming by contract
- Testen, Execution paths, Unit Tests in Python
- Ausnahmen (exceptions) und Ausnahmebehandlung in Python
Effizienz
(10. und 15.5.2012)
- Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
- Laufzeit versus Komplexität
- Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
- Bester, schlechtester, durchschnittlicher Fall
- Amortisierte Komplexität
Suchen
(22. und 24.5.2012)
- Lineare Suche
- Binäre Suche in sortierten Arrays, Medianproblem
- Suchbäume, balancierte Bäume
- selbst-balancierende Bäume, Rotationen
- Komplexität der Suche
Prioritätswarteschlangen
(29.5.2012)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
Hashing und assoziative Arrays
(31.5.und 5.6.2012)
- Implementation assoziativer Arrays mit Bäumen
- Hashing und Hashfunktionen
- Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
- Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
Iteration versus Rekursion
(12.6.2012)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
Generizität
(14.6.2012)
- Abstrakte Datentypen, Typspezifikation
- Required Interface versus Offered Interface
- Adapter und Typattribute, Funktoren
- Beispiel: Algebraische Konzepte und Zahlendatentypen
- Operator overloading in Python
Graphen und Graphenalgorithmen
(19. bis 28.6.2012)
- Einführung
- Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
- Gerichtete und ungerichtete Graphen
- Vollständige Graphen
- Planare Graphen, duale Graphen
- Pfade, Zyklen
- Tiefensuche und Breitensuche
- Zusammenhang, Komponenten
- Gewichtete Graphen
- Minimaler Spannbaum
- Kürzeste Wege, Best-first search (Dijkstra)
- Most-Promising-first search (A*)
- Problem des Handlungsreisenden, exakte Algorithmen (erschöpfende Suche, Branch-and-Bound-Methode) und Approximationen
- Erfüllbarkeitsproblem, Darstellung des 2-SAT-Problems durch gerichtete Graphen, stark zusammenhängende Komponenten
Randomisierte Algorithmen
(3. und 5.7.2012)
- Zufallszahlen, Zyklenlänge, Pitfalls
- Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
- Randomisierte vs. deterministische Algorithmen
- Las Vegas vs. Monte Carlo Algorithmen
- Beispiel für Las Vegas: Randomisiertes Quicksort
- Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems
- RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)
Greedy-Algorithmen und Dynamische Programmierung
(10. und 12.7.2012)
- Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
- bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
- Beispiel: Interval Scheduling Problem und Weighted Interval Scheduling Problem
- Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung
NP-Vollständigkeit
(17. und 19.7.2012)
- die Klassen P und NP
- NP-Vollständigkeit und Problemreduktion
Reserve und/oder Wiederholung
(24. und 26.7.2012)
