Gliederung der Vorlesung: Difference between revisions
From Alda
Jump to navigationJump to search
(Test, ob Titel mit Datum verhashte Links akzeptiert) |
(Titelgröße geändert) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
<!-------------> | <!-------------> | ||
==[[Einführung]] (17.4.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) | ===[[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 | |||
<!-------------> | <!-------------> | ||
<!-- | <!--* Repetition--> | ||
<!-- | <!--* Orthogonale Zerlegung des Problems--> | ||
<!-- | <!--* Hierarchische Zerlegung der Daten (Divide and Conquer)--> | ||
<!-- | <!--* Randomisierung--> | ||
<!-- | <!--* Optimierung, Zielfunktionen--> | ||
<!-- | <!--* Systematisierung von Algorithmen aus der bisherigen Vorlesung--> | ||
<!-------------> | <!-------------> | ||
<!-- | <!--===[[Analytische Optimierung]]=== | ||
<!-- | (25.6.2008)//--> | ||
<!-- | <!--* Methode der kleinsten Quadrate--> | ||
<!--* Approximation von Geraden--> | |||
<!-------------> | <!-------------> | ||
===[[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) | |||
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)
