Neue Startseite: Difference between revisions

From Alda
Jump to navigationJump to search
(Hoffentlich akzeptable Minimierung des Skriptbereiches (detailliertere Beschreibung auf anderer Seite))
No edit summary
Line 6: Line 6:


===Organisation===
===Organisation===
*[[Übungsaufgaben]]
*[[Klausur und Nachprüfung]]
*[[Klausur und Nachprüfung]]
*[[Leistungsnachweise]]
*[[Leistungsnachweise]]
Line 15: Line 16:


<!------------->
<!------------->
# ===[[Einführung]]=== (17.4.2012) - [[Gliederung der Vorlesung#Einführung|(detailliertere Beschreibung)]]
# [[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
<!------------->
<!------------->
Line 69: Line 70:
<!------------->
<!------------->
# Reserve und/oder Wiederholung (24. und 26.7.2012)
# 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.
# [[Media:Übung-1.pdf|Übung]] (Abgabe 24.4.2012) und [[Media:Uebung-1-Musterloesung.pdf|Musterlösung]]
#* Python-Tutorial // Sieb des Eratosthenes // Wert- und Referenzsemantik
#* Dynamisches Array
# [[Media:Uebung-2.pdf|Übung]] (Abgabe 3.5.2012) und [[Media:Uebung-2-Musterloesung.pdf|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
# [[Media:Uebung-3.pdf|Übung]] (Abgabe 10.5.2012) und [[Media:Uebung-3-Musterlösung.pdf|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
# [[Media:Uebung-4.pdf|Übung]] (Abgabe '''Montag''' 21.5.2012) <!------------ und [[Media:Musterloesung_4.pdf|Musterlösung]] ---->
#* Theoretische Aufgaben zur Komplexität // Amortisierte Komplexität von array.append() // Optimierung der Matrizenmultiplikation
# [[Media:Uebung-5.pdf|Übung]] (31.5.2012) <!------ und [[Media:muster_blatt5.pdf|Musterlösung]] ----> // Implementation und Analyse eines Binärbaumes // Anwendung: einfacher Taschenrechner
<!------------
# [[Media:Übung-6.pdf|Übung]] (Abgabe 5.6.2012) und [[Media:muster_blatt6.pdf|Musterlösung]]
#* Treap-Datenstruktur: Verbindung von Suchbaum und Heap // Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File  [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/die-drei-musketiere.txt die-drei-musketiere.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) // Suche mit linearer Komplexität
<!------------
# [[Media:Übung-7.pdf|Übung]] (Abgabe 12.6.2012) und [[Media:muster_blatt7.pdf|Musterlösung]]
#* Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration
<!------------
# [[Media:Übung-8.pdf|Übung]] (Abgabe 19.6.2012) und [[Media:muster_blatt8.pdf|Musterlösung]]
#* Elementare Graphenaufgaben: Aufstellen von Adjazenzmatrizen und Adjazenzlisten, planare Graphen // Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche
<!------------
# [[Media:Übung-9.pdf|Übung]] (Abgabe 26.6.2012)
#* Fortgeschrittene Graphenaufgaben: Erzeugen einer perfekten Hashfunktion, Routenplaner (Dazu benötigen Sie das File  [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/entfernungen.txt entfernungen.txt]. Die Zeichenkodierung in diesem File ist Latin-1.)
<!------------
# [[Media:Übung-10.pdf|Übung]] (Abgabe 3.7.2012) und [[Media:loesung_blatt10.pdf|Musterlösung]] sowie schöne [[Media:ballungsgebiete.pdf|Visualisierung der Ballungsgebiete]] von Thorben Kröger
#* Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Problem des Handelsreisenden (Eine <font color=red>neue Version</font> der Datei [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/entfernungen.txt entfernungen.txt] ist verfügbar. Dank an Sven Ebser, Joachim Schleicher und Thorben Kröger für Hilfe bei der Verbesserung der Datei.)
<!------------
# [[Media:Übung-11.pdf|Übung]] (Abgabe 10.7.2012)
#* Erfüllbarkeitsproblem, Anwendung: Heim- und Auswärtsspiele im Fussball (Dazu benötigen sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/bundesliga-paarungen-08-09.txt bundesliga-paarungen-08-09.txt].) // Randomisierte Algorithmen: RANSAC für Kreise (Dazu benötigen sie das File [http://klimt.iwr.uni-heidelberg.de/mip/people/ukoethe/download/noisy-circles.txt noisy-circles.txt].)
<!-------------
# [[Media:Übung-12.pdf|Übung]] (<font color=red>Achtung: Abgabe bereits am Mittwoch, 16.7.2012</font>)
#* Greedy-Algorithmen und Dynamische Programmierung
<!---------------->


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

Revision as of 03:38, 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 Alg. & Dat., Geschichte // Fund. Alg. & Dat. // Python-Grundlagen
  2. Container (19.4.2012) - (detailliertere Beschreibung)
    • Anford. 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., Invar., Prog. by contract // test, exec. paths, unit test, exceptions & exept. handling in python
  5. 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. 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. Prioritätswarteschlangen (29.5.2012) - (detailliertere Beschreibung)
    • Heap-Datenstruktur // Einfüge- & Löschoperat. // Heapsort // Kompl. des Heaps
  8. 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. 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. 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. 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. 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. NP-Vollständigkeit (17. und 19.7.2012) - (detailliertere Beschreibung)
    • die Klassen P & NP // NP-Vollständigkeit & Problemreduktion
  15. Reserve und/oder Wiederholung (24. und 26.7.2012)

Sonstiges

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