Neue Startseite: Difference between revisions

From Alda
Jump to navigationJump to search
No edit summary
(→‎Gliederung der Vorlesung: "Kapitalisierung")
Line 16: Line 16:


<!------------->
<!------------->
# [[Einführung]] (17.4.2012) - [[Gliederung der Vorlesung#Einführung|(detailliertere Beschreibung)]]
# Kap.: [[Einführung]] (17.4.2012) - [[Gliederung der Vorlesung#Einführung|(detailliertere Beschreibung)]]
#* Def. von Alg. & Dat., Geschichte // Fund. Alg. & Dat. // Python-Grundlagen
#* Def. von Alg. & Dat., Geschichte // Fund. Alg. & Dat. // Python-Grundlagen
<!------------->
<!------------->
# [[Container]] (19.4.2012) - [[Gliederung der Vorlesung#Container|(detailliertere Beschreibung)]]
# Kap.: [[Container]] (19.4.2012) - [[Gliederung der Vorlesung#Container|(detailliertere Beschreibung)]]
#* Anford. von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen & Intervalle (Ranges)
#* Anford. von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen & Intervalle (Ranges)
<!------------->
<!------------->
# [[Sortieren]] (24. und 26.4.2012) - [[Gliederung der Vorlesung#Sortieren|(detailliertere Beschreibung)]]
# Kap.: [[Sortieren]] (24. und 26.4.2012) - [[Gliederung der Vorlesung#Sortieren|(detailliertere Beschreibung)]]
#* Spez. des Sortierprob. // Selection, Insertion, Merge & Quick Sort und seine Varianten // Vergl. der Anz. der ben. Schritte // Laufzeitmessung in Python
#* Spez. des Sortierprob. // Selection, Insertion, Merge & Quick Sort und seine Varianten // Vergl. der Anz. der ben. Schritte // Laufzeitmessung in Python
<!------------->
<!------------->
# [[Korrektheit]] (3. und 8.5.2012) - [[Gliederung der Vorlesung#Korrektheit|(detailliertere Beschreibung)]]
# Kap.: [[Korrektheit]] (3. und 8.5.2012) - [[Gliederung der Vorlesung#Korrektheit|(detailliertere Beschreibung)]]
#* Def. von Korrektheit, Alg.-Spezifikation // Korrektheitsbew. vs. Test. // Vor- & Nachbed., Invar., Prog. by contract // test, exec. paths, unit test, exceptions & exept. handling in python
#* Def. von Korrektheit, Alg.-Spezifikation // Korrektheitsbew. vs. Test. // Vor- & Nachbed., Invar., Prog. by contract // test, exec. paths, unit test, exceptions & exept. handling in python
<!------------->
<!------------->
# [[Effizienz]] (10. und 15.5.2012) - [[Gliederung der Vorlesung#Effizienz|(detailliertere Beschreibung)]]
# Kap.: [[Effizienz]] (10. und 15.5.2012) - [[Gliederung der Vorlesung#Effizienz|(detailliertere Beschreibung)]]
#* Laufzeit & Opt. // Laufzeit vs. Kompl. // Landausym. (O-, <math>\Omega</math>- & <math>\Theta</math>-Notation), Komplexitätsklassen // Bester, schlechtester, durchschn. Fall // Amorti. Kompl.
#* Laufzeit & Opt. // Laufzeit vs. Kompl. // Landausym. (O-, <math>\Omega</math>- & <math>\Theta</math>-Notation), Komplexitätsklassen // Bester, schlechtester, durchschn. Fall // Amorti. Kompl.
<!------------->
<!------------->
# [[Suchen]] (22. und 24.5.2012)  - [[Gliederung der Vorlesung#Suchen|(detailliertere Beschreibung)]]
# Kap.: [[Suchen]] (22. und 24.5.2012)  - [[Gliederung der Vorlesung#Suchen|(detailliertere Beschreibung)]]
#* Lin. & Bin. Suche in sort. Arrays // Medianprob. // Suchb., balanz. Bäume // selbst-balanz. Bäume, Rotationen // Komplex. der Suche
#* Lin. & Bin. Suche in sort. Arrays // Medianprob. // Suchb., balanz. Bäume // selbst-balanz. Bäume, Rotationen // Komplex. der Suche
<!------------->
<!------------->
# [[Prioritätswarteschlangen]] (29.5.2012) - [[Gliederung der Vorlesung#Prioritätswarteschlangen|(detailliertere Beschreibung)]]
# Kap.: [[Prioritätswarteschlangen]] (29.5.2012) - [[Gliederung der Vorlesung#Prioritätswarteschlangen|(detailliertere Beschreibung)]]
#* Heap-Datenstruktur // Einfüge- & Löschoperat. // Heapsort // Kompl. des Heaps
#* Heap-Datenstruktur // Einfüge- & 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)]]
# Kap.: [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012) - [[Gliederung der Vorlesung#Hashing und assoziative Arrays|(detailliertere Beschreibung)]]
#* Implem. assoz. Arrays mit Bäumen // Hashing & Hashfkten // Implem. assoz. Arrays als Hashtabelle mit lin. Verkettung bzw. mit offener Adressierung // Anwendung des Hashings zur String-Suche: Rabin-Karp-Algorithmus
#* Implem. assoz. Arrays mit Bäumen // Hashing & Hashfkten // Implem. 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)]]
# Kap.: [[Iteration versus Rekursion]] (12.6.2012) - [[Gliederung der Vorlesung#Iteration versus Rekursion|(detailliertere Beschreibung)]]
#* Typen der Rekursion & ihre Umwandlung in Iteration // Auflösung rekurs. Formeln mittels Master- & Substitutionsmeth.
#* Typen der Rekursion & ihre Umwandlung in Iteration // Auflösung rekurs. Formeln mittels Master- & Substitutionsmeth.
<!------------->
<!------------->
Line 46: Line 46:
#* Abstrakte Datentypen, Typspez. // Required Interface vs. Offered Interface // Adapter & Typattribute, Funktoren // Bsp.: Algeb. Konzepte & Zahlendatentypen // operator overloading in python
#* Abstrakte Datentypen, Typspez. // Required Interface vs. Offered Interface // Adapter & Typattribute, Funktoren // Bsp.: Algeb. Konzepte & Zahlendatentypen // operator overloading in python
<!------------->
<!------------->
# [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012) - [[Gliederung der Vorlesung#Graphen und Graphenalgorithmen|(detailliertere Beschreibung)]]
# Kap.: [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012) - [[Gliederung der Vorlesung#Graphen und Graphenalgorithmen|(detailliertere Beschreibung)]]
#* Einführung // Graphendat., Adjazenzlisten & -matrizen // Gerichtete, ungerichtete, vollständige, planare, duale Graphen // Pfade, Zyklen // Tiefen- & Breitensuche // Zusammenhang, Komponenten // Gew. Graphen // Min. Spannbaum // Kürze. Wege, Best-first search (Dijkstra) // Most-Promising-first search (A*) // Prob. des H.-reisenden, exakte Alg. (erschöpf. Suche, Branch-and-Bound-Meth.) & Approx. // Erfüllbarkeitsprob., Darst. des 2-SAT-Prob.s durch gericht. Graphen, stark zusammenhängende Komponenten
#* Einführung // Graphendat., Adjazenzlisten & -matrizen // Gerichtete, ungerichtete, vollständige, planare, duale Graphen // Pfade, Zyklen // Tiefen- & Breitensuche // Zusammenhang, Komponenten // Gew. Graphen // Min. Spannbaum // Kürze. Wege, Best-first search (Dijkstra) // Most-Promising-first search (A*) // Prob. des H.-reisenden, exakte Alg. (erschöpf. Suche, Branch-and-Bound-Meth.) & Approx. // Erfüllbarkeitsprob., Darst. des 2-SAT-Prob.s durch gericht. Graphen, stark zusammenhängende Komponenten
<!------------->
<!------------->
Line 60: Line 60:
<!---#* Approximation von Geraden--->
<!---#* Approximation von Geraden--->
<!------------->
<!------------->
# [[Randomisierte Algorithmen]] (3. und 5.7.2012) - [[Gliederung der Vorlesung#Randomisierte Algorithmen|(detailliertere Beschreibung)]]
# Kap.: [[Randomisierte Algorithmen]] (3. und 5.7.2012) - [[Gliederung der Vorlesung#Randomisierte Algorithmen|(detailliertere Beschreibung)]]
#* Zufallszahlen, Zyklenlänge, Pitfalls // Zufallszahlengen.: linear congruential generator, Mersenne Twister // Random. vs. determ. Alg. // Las Vegas vs. Monte Carlo Alg. // Bsp. für Las Vegas: Random. 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)
#* Zufallszahlen, Zyklenlänge, Pitfalls // Zufallszahlengen.: linear congruential generator, Mersenne Twister // Random. vs. determ. Alg. // Las Vegas vs. Monte Carlo Alg. // Bsp. für Las Vegas: Random. 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)]]
# Kap.: [[Greedy-Algorithmen und Dynamische Programmierung]] (10. und 12.7.2012) - [[Gliederung der Vorlesung#Greedy-Algorithmen und Dynamische Programmierung|(detailliertere Beschreibung)]]
#* Prinz., Aufwandsred. in Entscheidungsbäumen // bereits bek. Alg.: min. Spannbäume nach Kruskal, kürz. Wege nach Dijkstra // Bsp.: Interval Sched. Prob. & Weighted Interval Sched. Prob. // Bew. der Optimalität beim Sched. Prob.: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dyn. Programmierung
#* Prinz., Aufwandsred. in Entscheidungsbäumen // bereits bek. Alg.: min. Spannbäume nach Kruskal, kürz. Wege nach Dijkstra // Bsp.: Interval Sched. Prob. & 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)]]
# Kap.: [[NP-Vollständigkeit]] (17. und 19.7.2012) - [[Gliederung der Vorlesung#NP-Vollständigkeit|(detailliertere Beschreibung)]]
#* die Klassen P & NP // NP-Vollständigkeit & Problemreduktion
#* die Klassen P & NP // NP-Vollständigkeit & Problemreduktion
<!------------->
<!------------->
# Reserve und/oder Wiederholung (24. und 26.7.2012)
# Kap.: Reserve und/oder Wiederholung (24. und 26.7.2012)


==Sonstiges==
==Sonstiges==
* [[Gnuplot| Gnuplot Kurztutorial]]
* [[Gnuplot| Gnuplot Kurztutorial]]

Revision as of 02:55, 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. Kap.: Einführung (17.4.2012) - (detailliertere Beschreibung)
    • Def. von Alg. & Dat., Geschichte // Fund. Alg. & Dat. // Python-Grundlagen
  2. Kap.: Container (19.4.2012) - (detailliertere Beschreibung)
    • Anford. von Alg. an Container // Einteilung der Container // Grundleg. Container // Sequenzen & Intervalle (Ranges)
  3. Kap.: 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. Kap.: Korrektheit (3. und 8.5.2012) - (detailliertere Beschreibung)
    • Def. von Korrektheit, Alg.-Spezifikation // Korrektheitsbew. vs. Test. // Vor- & Nachbed., Invar., Prog. by contract // test, exec. paths, unit test, exceptions & exept. handling in python
  5. Kap.: Effizienz (10. und 15.5.2012) - (detailliertere Beschreibung)
    • Laufzeit & Opt. // Laufzeit vs. Kompl. // Landausym. (O-, <math>\Omega</math>- & <math>\Theta</math>-Notation), Komplexitätsklassen // Bester, schlechtester, durchschn. Fall // Amorti. Kompl.
  6. Kap.: Suchen (22. und 24.5.2012) - (detailliertere Beschreibung)
    • Lin. & Bin. Suche in sort. Arrays // Medianprob. // Suchb., balanz. Bäume // selbst-balanz. Bäume, Rotationen // Komplex. der Suche
  7. Kap.: Prioritätswarteschlangen (29.5.2012) - (detailliertere Beschreibung)
    • Heap-Datenstruktur // Einfüge- & Löschoperat. // Heapsort // Kompl. des Heaps
  8. Kap.: Hashing und assoziative Arrays (31.5.und 5.6.2012) - (detailliertere Beschreibung)
    • Implem. assoz. Arrays mit Bäumen // Hashing & Hashfkten // Implem. assoz. Arrays als Hashtabelle mit lin. Verkettung bzw. mit offener Adressierung // Anwendung des Hashings zur String-Suche: Rabin-Karp-Algorithmus
  9. Kap.: Iteration versus Rekursion (12.6.2012) - (detailliertere Beschreibung)
    • Typen der Rekursion & ihre Umwandlung in Iteration // Auflösung rekurs. Formeln mittels Master- & Substitutionsmeth.
  10. Generizität (14.6.2012) - (detailliertere Beschreibung)
    • Abstrakte Datentypen, Typspez. // Required Interface vs. Offered Interface // Adapter & Typattribute, Funktoren // Bsp.: Algeb. Konzepte & Zahlendatentypen // operator overloading in python
  11. Kap.: Graphen und Graphenalgorithmen (19. bis 28.6.2012) - (detailliertere Beschreibung)
    • Einführung // Graphendat., Adjazenzlisten & -matrizen // Gerichtete, ungerichtete, vollständige, planare, duale Graphen // Pfade, Zyklen // Tiefen- & Breitensuche // Zusammenhang, Komponenten // Gew. Graphen // Min. Spannbaum // Kürze. Wege, Best-first search (Dijkstra) // Most-Promising-first search (A*) // Prob. des H.-reisenden, exakte Alg. (erschöpf. Suche, Branch-and-Bound-Meth.) & Approx. // Erfüllbarkeitsprob., Darst. des 2-SAT-Prob.s durch gericht. Graphen, stark zusammenhängende Komponenten
  12. Kap.: Randomisierte Algorithmen (3. und 5.7.2012) - (detailliertere Beschreibung)
    • Zufallszahlen, Zyklenlänge, Pitfalls // Zufallszahlengen.: linear congruential generator, Mersenne Twister // Random. vs. determ. Alg. // Las Vegas vs. Monte Carlo Alg. // Bsp. für Las Vegas: Random. 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. Kap.: Greedy-Algorithmen und Dynamische Programmierung (10. und 12.7.2012) - (detailliertere Beschreibung)
    • Prinz., Aufwandsred. in Entscheidungsbäumen // bereits bek. Alg.: min. Spannbäume nach Kruskal, kürz. Wege nach Dijkstra // Bsp.: Interval Sched. Prob. & Weighted Interval Sched. Prob. // Bew. der Optimalität beim Sched. Prob.: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dyn. Programmierung
  14. Kap.: NP-Vollständigkeit (17. und 19.7.2012) - (detailliertere Beschreibung)
    • die Klassen P & NP // NP-Vollständigkeit & Problemreduktion
  15. Kap.: Reserve und/oder Wiederholung (24. und 26.7.2012)

Sonstiges

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