Gliederung der Vorlesung: Difference between revisions
From Alda
Jump to navigationJump to search
(Test, ob Hash funktioniert) |
(Test ob Hash zu verlinkten Artikeln funktioniert) |
||
| Line 14: | Line 14: | ||
#* Sequenzen und Intervalle (Ranges) | #* Sequenzen und Intervalle (Ranges) | ||
<!-------------> | <!-------------> | ||
# [[Sortieren]] (24. und 26.4.2012) | ==Sortieren== | ||
# [[Sortieren|Artikel]] (24. und 26.4.2012) | |||
#* Spezifikation des Sortierproblems | #* Spezifikation des Sortierproblems | ||
#* Selection Sort und Insertion Sort | #* Selection Sort und Insertion Sort | ||
| Line 22: | Line 23: | ||
#* Laufzeitmessung in Python | #* Laufzeitmessung in Python | ||
<!-------------> | <!-------------> | ||
# [[Korrektheit]] (3. und 8.5.2012) | ==Korrektheit== | ||
# [[Korrektheit|Artikel]] (3. und 8.5.2012) | |||
#* Definition von Korrektheit, Algorithmen-Spezifikation | #* Definition von Korrektheit, Algorithmen-Spezifikation | ||
#* Korrektheitsbeweise versus Testen | #* Korrektheitsbeweise versus Testen | ||
| Line 29: | Line 31: | ||
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | #* Ausnahmen (exceptions) und Ausnahmebehandlung in Python | ||
<!-------------> | <!-------------> | ||
# [[Effizienz]] (10. und 15.5.2012) | ==Effizienz== | ||
# [[Effizienz|Artikel]] (10. und 15.5.2012) | |||
#* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference | #* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference | ||
#* Laufzeit versus Komplexität | #* Laufzeit versus Komplexität | ||
| Line 36: | Line 39: | ||
#* Amortisierte Komplexität | #* Amortisierte Komplexität | ||
<!-------------> | <!-------------> | ||
# [[Suchen]] (22. und 24.5.2012) | ==[[Suchen]]== | ||
# [[Suchen|Artikel]] (22. und 24.5.2012) | |||
#* Lineare Suche | #* Lineare Suche | ||
#* Binäre Suche in sortierten Arrays, Medianproblem | #* Binäre Suche in sortierten Arrays, Medianproblem | ||
Revision as of 00:48, 27 May 2012
Einführung
- Artikel (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
- Artikel (19.4.2012)
- Anforderungen von Algorithmen an Container
- Einteilung der Container
- Grundlegende Container: Array, verkettete Liste, Stack und Queue
- Sequenzen und Intervalle (Ranges)
Sortieren
- Artikel (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
- Artikel (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
- Artikel (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
- Artikel (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)
