Main Page: Difference between revisions
From Alda
Jump to navigationJump to search
| Line 186: | Line 186: | ||
== Übungsaufgaben == | == Übungsaufgaben == | ||
(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei verspäteter Abgabe bis zu drei Tagen werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet. <!--Erreichbare Punkte (ohne Bonusaufgaben): 466.--> | |||
(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei Abgabe bis | |||
# [[Media: | # [[Media:Uebung-1.pdf|Übung]] (Abgabe 29.4.2014) | ||
#* Python-Tutorial | #* Python-Tutorial | ||
#* Sieb des Eratosthenes | #* Sieb des Eratosthenes | ||
#* Wert- und Referenzsemantik | #* Wert- und Referenzsemantik | ||
#* Freitag der 13. | |||
#* Dynamisches Array | #* Dynamisches Array | ||
# [[Media:Uebung-2.pdf|Übung]] (Abgabe 3.5. | <!----- | ||
# [[Media:Uebung-2.pdf|Übung]] (Abgabe 3.5.2014) und [[Media:Uebung-2-Musterloesung.pdf|Musterlösung]] | |||
#* Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von der Problemgröße) | #* Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von der Problemgröße) | ||
#* Entwicklung eines Gewinnalgorithmus für ein Spiel | #* Entwicklung eines Gewinnalgorithmus für ein Spiel | ||
#* Bonus: Dynamisches Array mit verringertem Speicherverbrauch | #* Bonus: Dynamisches Array mit verringertem Speicherverbrauch | ||
# [[Media:Uebung-3.pdf|Übung]] (Abgabe 10.5. | # [[Media:Uebung-3.pdf|Übung]] (Abgabe 10.5.2014) und [[Media:Uebung-3-Musterlösung.pdf|Musterlösung]] | ||
#* Experimente zur Effektivität von Unit Tests | #* Experimente zur Effektivität von Unit Tests | ||
#* Bestimmung von Pi mit dem Algorithmus von Archimedes | #* Bestimmung von Pi mit dem Algorithmus von Archimedes | ||
#* Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests | #* Deque-Datenstruktur: Vor- und Nachbedingungen der Operationen, Implementation und Unit Tests | ||
# [[Media:Uebung-4.pdf|Übung]] (Abgabe '''Montag''' 21.5. | # [[Media:Uebung-4.pdf|Übung]] (Abgabe '''Montag''' 21.5.2014) und [[Media:muster_blatt4.pdf|Musterlösung]] | ||
#* Theoretische Aufgaben zur Komplexität | #* Theoretische Aufgaben zur Komplexität | ||
#* Amortisierte Komplexität von array.append() | #* Amortisierte Komplexität von array.append() | ||
#* Optimierung der Matrizenmultiplikation | #* Optimierung der Matrizenmultiplikation | ||
# [[Media:Uebung-5.pdf|Übung]] (31.5. | # [[Media:Uebung-5.pdf|Übung]] (31.5.2014) und [[Media:muster_blatt5.pdf|Musterlösung]] | ||
#* Implementation und Analyse eines Binärbaumes | #* Implementation und Analyse eines Binärbaumes | ||
#* Anwendung: einfacher Taschenrechner | #* Anwendung: einfacher Taschenrechner | ||
# [[Media:Uebung-6.pdf|Übung]] (Abgabe '''Freitag''' 8.6. | # [[Media:Uebung-6.pdf|Übung]] (Abgabe '''Freitag''' 8.6.2014) und [[Media:muster_blatt6.pdf|Musterlösung]] | ||
#* Treap-Datenstruktur: Verbindung von Suchbaum und Heap | #* Treap-Datenstruktur: Verbindung von Suchbaum und Heap | ||
#* Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/die-drei-musketiere.txt die-drei-musketiere.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) | #* Anwendung: Worthäufigkeiten (Dazu benötigen Sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/die-drei-musketiere.txt die-drei-musketiere.txt]. Die Zeichenkodierung in diesem File ist Latin-1.) | ||
#* BucketSort | #* BucketSort | ||
# [[Media:Uebung-7.pdf|Übung]] (Abgabe 14.6. | # [[Media:Uebung-7.pdf|Übung]] (Abgabe 14.6.2014) und [[Media:muster_blatt07.pdf|Musterlösung]] | ||
#* Absichtliche Konstruktion von Kollisionen für eine Hashfunktion | #* Absichtliche Konstruktion von Kollisionen für eine Hashfunktion | ||
#* Übungen zum Assoziativen Array und zum JSON-Format: Cocktail-Datenbank (Dazu benötigen Sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/cocktails.json cocktails.json]. Die Zeichenkodierung in diesem File ist UTF-8.) | #* Übungen zum Assoziativen Array und zum JSON-Format: Cocktail-Datenbank (Dazu benötigen Sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/cocktails.json cocktails.json]. Die Zeichenkodierung in diesem File ist UTF-8.) | ||
# [[Media:Uebung-8.pdf|Übung]] (Abgabe 21.6. | # [[Media:Uebung-8.pdf|Übung]] (Abgabe 21.6.2014) und [[Media:muster_blatt8.pdf|Musterlösung]] | ||
#* Übungen zu Rekursion und Iteration: Fibonaccizahlen, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration | #* Übungen zu Rekursion und Iteration: Fibonaccizahlen, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration | ||
# [[Media:Uebung-9.pdf|Übung]] (Abgabe 28.6. | # [[Media:Uebung-9.pdf|Übung]] (Abgabe 28.6.2014) und [[Media:muster_blatt9.pdf|Musterlösung]] | ||
#* Planare Graphen: Aufstellen von Adjazenzmatrizen und Adjazenzlisten, obere Schranke für die Zahl der Kanten | #* Planare Graphen: Aufstellen von Adjazenzmatrizen und Adjazenzlisten, obere Schranke für die Zahl der Kanten | ||
#* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche | #* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche | ||
# [[Media:Uebung-10.pdf|Übung]] (Abgabe 5.7. | # [[Media:Uebung-10.pdf|Übung]] (Abgabe 5.7.2014) und [[Media:muster_blatt10.pdf|Musterlösung]] | ||
#* Fortgeschrittene Graphenaufgaben: Erzeugen einer perfekten Hashfunktion, Routenplaner (Dazu benötigen Sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json]. Die Zeichenkodierung in diesem File ist UTF-8.) | #* Fortgeschrittene Graphenaufgaben: Erzeugen einer perfekten Hashfunktion, Routenplaner (Dazu benötigen Sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json]. Die Zeichenkodierung in diesem File ist UTF-8.) | ||
# [[Media:Uebung-11.pdf|Übung]] (Abgabe 12.7. | # [[Media:Uebung-11.pdf|Übung]] (Abgabe 12.7.2014) und [[Media:muster_blatt11.pdf|Musterlösung]] sowie schöne [[Media:ballungsgebiete.pdf|Visualisierung der Ballungsgebiete]] von Thorben Kröger | ||
#* Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Bildverarbeitung mit Graphen (Dazu benötigen Sie wieder das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json] sowie die Files [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/cells.pgm cells.pgm] und [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/pgm.py pgm.py].) | #* Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Bildverarbeitung mit Graphen (Dazu benötigen Sie wieder das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json] sowie die Files [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/cells.pgm cells.pgm] und [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/pgm.py pgm.py].) | ||
# [[Media:Uebung-12.pdf|Übung]] (Abgabe 19.7. | # [[Media:Uebung-12.pdf|Übung]] (Abgabe 19.7.2014) und [[Media:muster_blatt12.pdf|Musterlösung]] | ||
#* Erfüllbarkeitsproblem, Anwendung: Heim- und Auswärtsspiele im Fussball (Dazu benötigen sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/bundesliga-paarungen-12-13.json bundesliga-paarungen-12-13.json].) | #* Erfüllbarkeitsproblem, Anwendung: Heim- und Auswärtsspiele im Fussball (Dazu benötigen sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/bundesliga-paarungen-12-13.json bundesliga-paarungen-12-13.json].) | ||
#* Randomisierte Algorithmen: RANSAC für Kreise (Dazu benötigen sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/noisy-circles.txt noisy-circles.txt].) | #* Randomisierte Algorithmen: RANSAC für Kreise (Dazu benötigen sie das File [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/noisy-circles.txt noisy-circles.txt].) | ||
# [[Media:Bonusuebung.pdf|Übung (Bonus)]] (<font color=red>Achtung: Abgabe bereits am Dienstag, 24.7. | # [[Media:Bonusuebung.pdf|Übung (Bonus)]] (<font color=red>Achtung: Abgabe bereits am Dienstag, 24.7.2014</font>) | ||
#* Greedy-Algorithmus | #* Greedy-Algorithmus | ||
#* Weg durch einen Graphen | #* Weg durch einen Graphen | ||
Revision as of 19:06, 16 April 2014
Vorlesung Algorithmen und Datenstrukturen
Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2014
Die Vorlesung findet dienstags und donnerstags jeweils um 14:15 Uhr in INF 288 (Mathematisches Institut), HS 1 statt.
Klausur und Nachprüfung
Der Termin der Abschlussklausur steht noch nicht fest.
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:
- Mo 14:00 - 16:00 Uhr, Raum wird noch bekanntgegeben (Tutor: Niels Buwen: buwen AT stud.uni-heidelberg.de)
- Mo 16:00 - 18:00 Uhr, INF 288, HS6 (Tutor: Niels Buwen: buwen AT stud.uni-heidelberg.de)
- Di 9:00 - 11:00 Uhr, INF 294, R-102 (Tutor: Fynn Beuttenmüller: f.beuttenmueller AT gmx.de)
- Di 11:00 - 13:00 Uhr, INF 294, R-102 (Tutor: Fynn Beuttenmüller: f.beuttenmueller AT gmx.de)
- Mi 14:00 - 16:00 Uhr, INF 294, R-113 (Tutor: Axel Wagner: axel.wagner AT stud.uni-heidelberg.de)
- Mi 16:00 - 18:00 Uhr, INF 294, R-113 (Tutor: Axel Wagner: axel.wagner AT stud.uni-heidelberg.de)
- 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 Ullrich Köthe auf Anfrage gerne einrichtet.
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
- 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
- Container (17.4.2014)
- Anforderungen von Algorithmen an Container
- Einteilung der Container
- Grundlegende Container: Array, verkettete Liste, Stack und Queue
- Sequenzen und Intervalle (Ranges)
- 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
- 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
- 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
- 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
- Sortieren in linearer Zeit (22.5.2014)
- Permutationen
- Sortieren als Suchproblem
- Bucket Prinzip, Bucket Sort
- Prioritätswarteschlangen (27.5.2014)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- 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
- 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
- Iteration versus Rekursion (12.6.2014)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
- 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
- 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
- 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)
- 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
- NP-Vollständigkeit (17.7.2014)
- die Klassen P und NP
- NP-Vollständigkeit und Problemreduktion
- Reserve und/oder Wiederholung (22. und 24.7.2014)
Übungsaufgaben
(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei verspäteter Abgabe bis zu drei Tagen werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.
- Übung (Abgabe 29.4.2014)
- Python-Tutorial
- Sieb des Eratosthenes
- Wert- und Referenzsemantik
- Freitag der 13.
- Dynamisches Array
