Neue Startseite: Difference between revisions

From Alda
Jump to navigationJump to search
(Skript bis Kap. 5 minimiert)
(Skript bis letzen Kap. minimiert)
Line 28: Line 28:
<!------------->
<!------------->
# [[Effizienz]] (10. und 15.5.2012) - [[Gliederung der Vorlesung#Effizienz|(detailliertere Beschreibung)]]
# [[Effizienz]] (10. und 15.5.2012) - [[Gliederung der Vorlesung#Effizienz|(detailliertere Beschreibung)]]
#* Laufzeit & Optimierung // Laufzeit vs. Komplexität // Landausym. (O-, <math>\Omega</math>- & <math>\Theta</math>-Notation), Komplexitätsklassen // Bester, schlechtester, durchschnittlicher Fall // Amortisierte Komplexität
#* Laufzeit & Optimierung // Laufzeit vs. Komplexität // Landausym. (O-, <math>\Omega</math>- & <math>\Theta</math>-Notation), Komplexitätsklassen // Bester, schlechtester, durchschn. Fall // Amorti. Komplexität
<!------------->
<!------------->
# [[Suchen]] (22. und 24.5.2012)  - [[Gliederung der Vorlesung#Suchen|(detailliertere Beschreibung)]]
# [[Suchen]] (22. und 24.5.2012)  - [[Gliederung der Vorlesung#Suchen|(detailliertere Beschreibung)]]
#* Lineare Suche // Binäre Suche in sortierten Arrays, Medianproblem // Suchbäume, balancierte Bäume // selbst-balancierende Bäume, Rotationen // Komplexität der Suche
#* Lin. -, Binäre Suche in sort. Arrays // Medianproblem // Suchbäume, balancierte Bäume // selbst-balancierende Bäume, Rotationen // Komplex. der Suche
<!------------->
<!------------->
# [[Prioritätswarteschlangen]] (29.5.2012) - [[Gliederung der Vorlesung#Prioritätswarteschlangen|(detailliertere Beschreibung)]]
# [[Prioritätswarteschlangen]] (29.5.2012) - [[Gliederung der Vorlesung#Prioritätswarteschlangen|(detailliertere Beschreibung)]]
#* Heap-Datenstruktur // Einfüge- und Löschoperationen // Heapsort // Komplexität des Heaps
#* Heap-Datenstruktur // Einfüge- und Löschoperat. // Heapsort // Kompl. des Heaps
<!------------->
<!------------->
# [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012) - [[Gliederung der Vorlesung#Hashing und assoziative Arrays|(detailliertere Beschreibung)]]
# [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012) - [[Gliederung der Vorlesung#Hashing und assoziative Arrays|(detailliertere Beschreibung)]]
#* Implementation assoziativer Arrays mit Bäumen // Hashing und Hashfunktionen // Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierun // Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
#* Impl. assoz. Arrays mit Bäumen // Hashing & Hashfunktionen // Impl. assoz. Arrays als Hashtabelle mit lin. Verkettung bzw. mit offener Adressierung // Anwendung des Hashings zur String-Suche: Rabin-Karp-Algorithmus
<!------------->
<!------------->
# [[Iteration versus Rekursion]] (12.6.2012) - [[Gliederung der Vorlesung#Iteration versus Rekursion|(detailliertere Beschreibung)]]
# [[Iteration versus Rekursion]] (12.6.2012) - [[Gliederung der Vorlesung#Iteration versus Rekursion|(detailliertere Beschreibung)]]
#* Typen der Rekursion und ihre Umwandlung in Iteration // Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
#* Typen der Rekursion & ihre Umwandlung in Iteration // Auflösung rek. Formeln mittels Master- & Substitutionsmeth.
<!------------->
<!------------->
# [[Generizität]] (14.6.2012) - [[Gliederung der Vorlesung#Generizität|(detailliertere Beschreibung)]]
# [[Generizität]] (14.6.2012) - [[Gliederung der Vorlesung#Generizität|(detailliertere Beschreibung)]]
#* Abstrakte Datentypen, Typspezifikation // Required Interface versus Offered Interface // Adapter und Typattribute, Funktoren // Beispiel: Algebraische Konzepte und Zahlendatentypen // Operator overloading in Python
#* Abstrakte Datentypen, Typspezifikation // Required Interface vs. Offered Interface // Adapter & Typattribute, Funktoren // Bsp.: Alg. Konz. & Zahlendatentypen // Operator overloading in Python
<!------------->
<!------------->
# [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012) - [[Gliederung der Vorlesung#Graphen und Graphenalgorithmen|(detailliertere Beschreibung)]]
# [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012) - [[Gliederung der Vorlesung#Graphen und Graphenalgorithmen|(detailliertere Beschreibung)]]
#* Einführung // Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen // Gerichtete und ungerichtete Graphen // Vollständige Graphen // Planare Graphen, duale Graphen // Pfade, Zykle // 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
#* Einführung // Graphendatenstrukturen, Adjazenzlisten & Adjazenzmatrizen // Gerichtete & ungerichtete & vollständige & planare & duale Graphen // Pfade, Zyklen // Tiefen- & Breitensuche // Zusammenhang, Komponenten // Gewichtete Graphen // Minimaler Spannbaum // Kürzeste Wege, Best-first search (Dijkstra) // Most-Promising-first search (A*) // Problem des Handlungsreisenden, exakte Alg. (erschöpfende Suche, Branch-and-Bound-Methode) und Approx. // Erfüllbarkeitsprob., Darst. des 2-SAT-Prob.s durch gerichtete Graphen, stark zusammenhängende Komponenten
<!------------->
<!------------->
<!---#* Repetition--->
<!---#* Repetition--->
Line 60: Line 60:
<!------------->
<!------------->
# [[Randomisierte Algorithmen]] (3. und 5.7.2012) - [[Gliederung der Vorlesung#Randomisierte Algorithmen|(detailliertere Beschreibung)]]
# [[Randomisierte Algorithmen]] (3. und 5.7.2012) - [[Gliederung der Vorlesung#Randomisierte Algorithmen|(detailliertere Beschreibung)]]
#* 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)
#* Zufallszahlen, Zyklenlänge, Pitfalls // Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister // Randomisierte vs. determ. Alg. // Las Vegas vs. Monte Carlo Alg. // Bsp. für Las Vegas: Randomisiertes Quicksort // Bsp.e für Monte Carlo: Randomisierte Lösung des k-SAT Prob. // RANSAC-Alg., Erfolgswahrsch., Vergleich mit analyt. Optimierung (Meth. der kleinsten Quadrate)
<!------------->
<!------------->
# [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012) - [[Gliederung der Vorlesung#Greedy-Algorithmen und Dynamische Programmierung|(detailliertere Beschreibung)]]
# [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012) - [[Gliederung der Vorlesung#Greedy-Algorithmen und Dynamische Programmierung|(detailliertere Beschreibung)]]
#* 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
#* Prinzipien, Aufwandsred. in Entscheidungsbäumen // bereits bekannte Alg.: min. Spannbäume nach Kruskal, kürz. Wege nach Dijkstra // Bsp.: Interval Scheduling Prob. und Weighted Interval Sched. Prob. // Bew. der Optimalität beim Sched. Prob.: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dyn. Programmierung
<!------------->
<!------------->
# [[NP-Vollständigkeit]] (17. und 19.7.2012) - [[Gliederung der Vorlesung#NP-Vollständigkeit|(detailliertere Beschreibung)]]
# [[NP-Vollständigkeit]] (17. und 19.7.2012) - [[Gliederung der Vorlesung#NP-Vollständigkeit|(detailliertere Beschreibung)]]
#* die Klassen P und NP // NP-Vollständigkeit und Problemreduktion
#* die Klassen P und NP // NP-Vollständigkeit & Problemreduktion
<!------------->
<!------------->
# Reserve und/oder Wiederholung (24. und 26.7.2012)
# Reserve und/oder Wiederholung (24. und 26.7.2012)

Revision as of 02:04, 27 May 2012

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.

Organisation

Gliederung der Vorlesung

  1. Einführung (17.4.2012) - (detailliertere Beschreibung)
    • Def. von Algorithmen & Datenstrukturen, Geschichte // Fundamentale Algo. & Dat. // Python-Grundlagen
  2. Container (19.4.2012) - (detailliertere Beschreibung)
    • Anforderungen von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen & Intervalle (Ranges)
  3. Sortieren (24. und 26.4.2012) - (detailliertere Beschreibung)
    • Spez. des Sortierprob. // Selection, Insertion, Merge & Quick Sort und seine Varianten // Vergl. der Anz. der ben. Schritte // Laufzeitmessung in Python
  4. Korrektheit (3. und 8.5.2012) - (detailliertere Beschreibung)
    • Def. von Korrektheit, Alg.-Spezifikation // Korrektheitsbew. vs. Test. // Vor- & Nachbed., Inv., Programming by contract // test, execution paths, unit test, exceptions & Ausnahmebehandlung in Python
  5. Effizienz (10. und 15.5.2012) - (detailliertere Beschreibung)
    • Laufzeit & Optimierung // Laufzeit vs. Komplexität // Landausym. (O-, <math>\Omega</math>- & <math>\Theta</math>-Notation), Komplexitätsklassen // Bester, schlechtester, durchschn. Fall // Amorti. Komplexität
  6. Suchen (22. und 24.5.2012) - (detailliertere Beschreibung)
    • Lin. -, Binäre Suche in sort. Arrays // Medianproblem // Suchbäume, balancierte Bäume // selbst-balancierende Bäume, Rotationen // Komplex. der Suche
  7. Prioritätswarteschlangen (29.5.2012) - (detailliertere Beschreibung)
    • Heap-Datenstruktur // Einfüge- und Löschoperat. // Heapsort // Kompl. des Heaps
  8. Hashing und assoziative Arrays (31.5.und 5.6.2012) - (detailliertere Beschreibung)
    • Impl. assoz. Arrays mit Bäumen // Hashing & Hashfunktionen // Impl. assoz. Arrays als Hashtabelle mit lin. Verkettung bzw. mit offener Adressierung // Anwendung des Hashings zur String-Suche: Rabin-Karp-Algorithmus
  9. Iteration versus Rekursion (12.6.2012) - (detailliertere Beschreibung)
    • Typen der Rekursion & ihre Umwandlung in Iteration // Auflösung rek. Formeln mittels Master- & Substitutionsmeth.
  10. Generizität (14.6.2012) - (detailliertere Beschreibung)
    • Abstrakte Datentypen, Typspezifikation // Required Interface vs. Offered Interface // Adapter & Typattribute, Funktoren // Bsp.: Alg. Konz. & Zahlendatentypen // Operator overloading in Python
  11. Graphen und Graphenalgorithmen (19. bis 28.6.2012) - (detailliertere Beschreibung)
    • Einführung // Graphendatenstrukturen, Adjazenzlisten & Adjazenzmatrizen // Gerichtete & ungerichtete & vollständige & planare & duale Graphen // Pfade, Zyklen // Tiefen- & Breitensuche // Zusammenhang, Komponenten // Gewichtete Graphen // Minimaler Spannbaum // Kürzeste Wege, Best-first search (Dijkstra) // Most-Promising-first search (A*) // Problem des Handlungsreisenden, exakte Alg. (erschöpfende Suche, Branch-and-Bound-Methode) und Approx. // Erfüllbarkeitsprob., Darst. des 2-SAT-Prob.s durch gerichtete Graphen, stark zusammenhängende Komponenten
  12. Randomisierte Algorithmen (3. und 5.7.2012) - (detailliertere Beschreibung)
    • Zufallszahlen, Zyklenlänge, Pitfalls // Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister // Randomisierte vs. determ. Alg. // Las Vegas vs. Monte Carlo Alg. // Bsp. für Las Vegas: Randomisiertes Quicksort // Bsp.e für Monte Carlo: Randomisierte Lösung des k-SAT Prob. // RANSAC-Alg., Erfolgswahrsch., Vergleich mit analyt. Optimierung (Meth. der kleinsten Quadrate)
  13. Greedy-Algorithmen und Dynamische Programmierung (10. und 12.7.2012) - (detailliertere Beschreibung)
    • Prinzipien, Aufwandsred. in Entscheidungsbäumen // bereits bekannte Alg.: min. Spannbäume nach Kruskal, kürz. Wege nach Dijkstra // Bsp.: Interval Scheduling Prob. und Weighted Interval Sched. Prob. // Bew. der Optimalität beim Sched. Prob.: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dyn. Programmierung
  14. NP-Vollständigkeit (17. und 19.7.2012) - (detailliertere Beschreibung)
    • die Klassen P und NP // NP-Vollständigkeit & Problemreduktion
  15. Reserve und/oder Wiederholung (24. und 26.7.2012)

Übungsaufgaben

(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei Abgabe bis zum folgenden Montag 11:00 Uhr werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.

  1. Übung (Abgabe 24.4.2012) und Musterlösung
    • Python-Tutorial // Sieb des Eratosthenes // Wert- und Referenzsemantik
    • Dynamisches Array
  2. Übung (Abgabe 3.5.2012) und Musterlösung
    • Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von der Problemgröße) // Entwicklung eines Gewinnalgorithmus für ein Spiel
    • Bonus: Dynamisches Array mit verringertem Speicherverbrauch
  3. Übung (Abgabe 10.5.2012) und Musterlösung
    • Experimente zur Effektivität von Unit Tests // Bestimmung von Pi mit dem Algorithmus von Archimedes // Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests
  4. Übung (Abgabe Montag 21.5.2012)
    • Theoretische Aufgaben zur Komplexität // Amortisierte Komplexität von array.append() // Optimierung der Matrizenmultiplikation
  5. Übung (31.5.2012) // Implementation und Analyse eines Binärbaumes // Anwendung: einfacher Taschenrechner

Sonstiges

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