Main Page: Difference between revisions

From Alda
Jump to navigationJump to search
Line 57: Line 57:
=== Gliederung der Vorlesung ===
=== Gliederung der Vorlesung ===
<!------------->
<!------------->
# [[Einführung]] (17.4.2012)  
# [[Einführung]] (15.4.2014)  
#* Definition von Algorithmen und Datenstrukturen, Geschichte
#* Definition von Algorithmen und Datenstrukturen, Geschichte
#* Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
#* Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
Line 63: Line 63:
#* Python-Grundlagen
#* Python-Grundlagen
<!------------->
<!------------->
# [[Container]] (19.4.2012)
# [[Container]] (17.4.2014)
#* Anforderungen von Algorithmen an Container
#* Anforderungen von Algorithmen an Container
#* Einteilung der Container
#* Einteilung der Container
Line 69: Line 69:
#* Sequenzen und Intervalle (Ranges)
#* Sequenzen und Intervalle (Ranges)
<!------------->
<!------------->
# [[Sortieren]] (24. und 26.4.2012)
# [[Sortieren]] (22. und 24.4.2014)
#* Spezifikation des Sortierproblems
#* Spezifikation des Sortierproblems
#* Selection Sort und Insertion Sort
#* Selection Sort und Insertion Sort
Line 77: Line 77:
#* Laufzeitmessung in Python
#* Laufzeitmessung in Python
<!------------->
<!------------->
# [[Korrektheit]] (3. und 8.5.2012)
# [[Korrektheit]] (29.4. und 6.5.2014)
#* Definition von Korrektheit, Algorithmen-Spezifikation
#* Definition von Korrektheit, Algorithmen-Spezifikation
#* Korrektheitsbeweise versus Testen
#* Korrektheitsbeweise versus Testen
Line 84: Line 84:
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python
<!------------->
<!------------->
# [[Effizienz]] (10. und 15.5.2012)
# [[Effizienz]] (8. und 13.5.2014)
#* 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 91: Line 91:
#* Amortisierte Komplexität
#* Amortisierte Komplexität
<!------------->
<!------------->
# [[Suchen]] (22. und 24.5.2012)
# [[Suchen]] (15. und 20.5.2014)
#* Sequentielle Suche
#* Sequentielle Suche
#* Binäre Suche in sortierten Arrays, Medianproblem
#* Binäre Suche in sortierten Arrays, Medianproblem
Line 98: Line 98:
#* Komplexität der Suche
#* Komplexität der Suche
<!------------->
<!------------->
# [[Sortieren in linearer Zeit]] (29.5.2012)
# [[Sortieren in linearer Zeit]] (22.5.2014)
#* Permutationen
#* Permutationen
#* Sortieren als Suchproblem
#* Sortieren als Suchproblem
#* Bucket Prinzip, Bucket Sort
#* Bucket Prinzip, Bucket Sort
<!------------->
<!------------->
# [[Prioritätswarteschlangen]] (31.5.2012)
# [[Prioritätswarteschlangen]] (27.5.2014)
#* Heap-Datenstruktur
#* Heap-Datenstruktur
#* Einfüge- und Löschoperationen
#* Einfüge- und Löschoperationen
Line 109: Line 109:
#* Komplexität des Heaps
#* Komplexität des Heaps
<!------------->
<!------------->
# [[Assoziative Arrays]] (5.6.2012)
# [[Assoziative Arrays]] (3.6.2014)
#* Datenstruktur-Dreieck für assoziative Arrays
#* Datenstruktur-Dreieck für assoziative Arrays
#* Definition des abstrakten Datentyps
#* Definition des abstrakten Datentyps
Line 115: Line 115:
#* Realisierung durch sequentielle Suche und durch Suchbäume
#* Realisierung durch sequentielle Suche und durch Suchbäume
<!------------->
<!------------->
# [[Hashing und Hashtabellen]] (5.6.und 12.6.2012)
# [[Hashing und Hashtabellen]] (5. und 10.6.2014)
#* Implementation assoziativer Arrays mit Bäumen
#* Implementation assoziativer Arrays mit Bäumen
#* Hashing und Hashfunktionen
#* Hashing und Hashfunktionen
Line 121: Line 121:
#* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
#* Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
<!------------->
<!------------->
# [[Iteration versus Rekursion]] (14.6.2012)
# [[Iteration versus Rekursion]] (12.6.2014)
#* 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]] (19.6.2012)
# [[Generizität]] (17.6.2014)
#* Abstrakte Datentypen, Typspezifikation
#* Abstrakte Datentypen, Typspezifikation
#* Required Interface versus Offered Interface
#* Required Interface versus Offered Interface
Line 132: Line 132:
#* Operator overloading in Python
#* Operator overloading in Python
<!------------->
<!------------->
# [[Graphen und Graphenalgorithmen]] (21.6. bis 5.7.2012)
# [[Graphen und Graphenalgorithmen]] (24.6. bis 3.7.2014)
#* Einführung
#* Einführung
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
Line 159: Line 159:
<!---#* Approximation von Geraden--->
<!---#* Approximation von Geraden--->
<!------------->
<!------------->
# [[Randomisierte Algorithmen]] (10. und 12.7.2012)
# [[Randomisierte Algorithmen]] (8. und 10.7.2014)
#* Zufallszahlen, Zyklenlänge, Pitfalls
#* Zufallszahlen, Zyklenlänge, Pitfalls
#* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
#* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
Line 168: Line 168:
#* 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]] (17.7.2012)
# [[Greedy-Algorithmen und Dynamische Programmierung]] (15.7.2014)
#* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
#* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
#* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
#* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
Line 174: Line 174:
#* 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]] (19.7.2012)
# [[NP-Vollständigkeit]] (17.7.2014)
#* die Klassen P und NP
#* die Klassen P und NP
#* NP-Vollständigkeit und Problemreduktion
#* NP-Vollständigkeit und Problemreduktion
<!------------->
<!------------->
# Reserve und/oder Wiederholung (24. und 26.7.2012)
# Reserve und/oder Wiederholung (22. und 24.7.2014)


== Übungsaufgaben ==
== Übungsaufgaben ==

Revision as of 20:17, 16 January 2014

Vorlesung Algorithmen und Datenstrukturen

Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2012

Die Vorlesung findet dienstags und donnerstags jeweils um 14:15 Uhr in INF 227 (KIP), HS 2 statt.

Klausur und Nachprüfung

Die Abschlussklausur findet am Dienstag, dem 31.7.2012 von 10:00 bis 12:00 Uhr im HS 1 in INF 306 statt. Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht. (Hinweis: Sie benötigen einen Lichtbildausweis, um sich bei der Klausur zu indentifizieren!) Die Nachklausur finet am 4.10.2012, 10:00 bis 12:00 im großen Seminarraum des HCI, Speyerer Str. 6 statt.

Leistungsnachweise

Für alle Leistungsnachweise ist die erfolgreiche Teilnahme an den Übungen erforderlich. Für Leistungspunkte bzw. den Klausurschein muss außerdem die schriftliche Prüfung bestanden werden. Einzelheiten werden noch bekanntgegeben.

Übungsbetrieb

  • Termine und Räume:
  • Die Übungsgruppen werden über MÜSLI verwaltet. Dort erfolgt auch die Anmeldung.
  • Übungsaufgaben (Übungszettel mit Abgabetermin, Musterlösungen). Lösungen bitte per Email an den jeweiligen Übungsgruppenleiter.
  • Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht. Außerdem muss jeder Teilnehmer eine Lösung (bzw. einen Teil davon) in der Übungsgruppe vorrechnen.
  • Durch das Lösen von Bonusaufgaben und gute Mitarbeit in den Übungen können Sie Zusatzpunkte erlangen. Zusatzpunkte werden auch vergeben, wenn Sie größere Verbesserungen an diesem Wiki vornehmen. Damit solche Verbesserungen der richtigen Person zugeordnet werden, sollten Sie dafür ein eigenes Wiki-Login verwenden, das Ihnen Stephan Meister oder Ullrich Köthe auf Anfrage gerne einrichten.

Prüfungsvorbereitung

Zur Hilfe bei der Prüfungsvorbereitung hat Andreas Fay Quizfragen erstellt.

Literatur

  • R. Sedgewick: Algorithmen (empfohlen für den ersten Teil, bis einschließlich Graphenalgorithmen)
  • J. Kleinberg, E.Tardos: Algorithm Design (empfohlen für den zweiten Teil, einschließlich Graphenalgorithmen)
  • T. Cormen, C. Leiserson, R.Rivest: Algorithmen - eine Einführung (empfohlen zum Thema Komplexität)
  • Wikipedia und andere Internetseiten (sehr gute Seiten über viele Algorithmen und Datenstrukturen)

Gliederung der Vorlesung

  1. Einführung (15.4.2014)
    • Definition von Algorithmen und Datenstrukturen, Geschichte
    • Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
    • Fundamentale Datenstrukturen: Zahlen, Container, Handles
    • Python-Grundlagen
  2. Container (17.4.2014)
    • Anforderungen von Algorithmen an Container
    • Einteilung der Container
    • Grundlegende Container: Array, verkettete Liste, Stack und Queue
    • Sequenzen und Intervalle (Ranges)
  3. Sortieren (22. und 24.4.2014)
    • 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
  4. Korrektheit (29.4. und 6.5.2014)
    • 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
  5. Effizienz (8. und 13.5.2014)
    • 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
  6. Suchen (15. und 20.5.2014)
    • Sequentielle Suche
    • Binäre Suche in sortierten Arrays, Medianproblem
    • Suchbäume, balancierte Bäume
    • selbst-balancierende Bäume, Rotationen
    • Komplexität der Suche
  7. Sortieren in linearer Zeit (22.5.2014)
    • Permutationen
    • Sortieren als Suchproblem
    • Bucket Prinzip, Bucket Sort
  8. Prioritätswarteschlangen (27.5.2014)
    • Heap-Datenstruktur
    • Einfüge- und Löschoperationen
    • Heapsort
    • Komplexität des Heaps
  9. Assoziative Arrays (3.6.2014)
    • Datenstruktur-Dreieck für assoziative Arrays
    • Definition des abstrakten Datentyps
    • JSON-Datenformat
    • Realisierung durch sequentielle Suche und durch Suchbäume
  10. Hashing und Hashtabellen (5. und 10.6.2014)
    • 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
  11. Iteration versus Rekursion (12.6.2014)
    • Typen der Rekursion und ihre Umwandlung in Iteration
    • Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
  12. Generizität (17.6.2014)
    • Abstrakte Datentypen, Typspezifikation
    • Required Interface versus Offered Interface
    • Adapter und Typattribute, Funktoren
    • Beispiel: Algebraische Konzepte und Zahlendatentypen
    • Operator overloading in Python
  13. Graphen und Graphenalgorithmen (24.6. bis 3.7.2014)
    • 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
  14. Randomisierte Algorithmen (8. und 10.7.2014)
    • 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)
  15. Greedy-Algorithmen und Dynamische Programmierung (15.7.2014)
    • 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
  16. NP-Vollständigkeit (17.7.2014)
    • die Klassen P und NP
    • NP-Vollständigkeit und Problemreduktion
  17. Reserve und/oder Wiederholung (22. und 24.7.2014)

Übungsaufgaben

zur Zeit nicht freigeschaltet.

Retrieved from "https://alda.iwr.uni-heidelberg.de/index.php?title=Main_Page&oldid=5456"