|
|
| (19 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Vorlesung Algorithmen und Datenstrukturen ==
| | (Diese Varianten erfahren eventuell noch ein paar Modifikationen, falls der Professor die Neugestaltung der Startseite akzeptiert. |
| | Bitte schreibt auf der Seite "diskussion" (zweiter Tab auf der Seite), wie euch einzelne Varianten gefallen und welche Änderungen gewünscht werden.) |
|
| |
|
|
| |
|
| Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2012
| | [[mögliche neue Startseite - Variante 1]] |
|
| |
|
| Die Vorlesung findet '''dienstags''' und '''donnerstags''' jeweils um 14:15 Uhr in INF 227 (KIP), HS 2 statt.
| | [[mögliche neue Startseite - Variante 2]] |
|
| |
|
| === Klausur und Nachprüfung ===
| | [[mögliche neue Startseite - Variante 3]] (noch nicht fertig) |
| | |
| Die '''Abschlussklausur''' findet am Dienstag, dem 31.7.2012 von 9:30 bis 12:30 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!)
| |
| <!---
| |
| * '''[[Media:Prüfungsteilnehmer.pdf|Liste der Studenten]], die sich verbindlich zur Klausur angemeldet und die notwendige Übungspunktzahl erreicht haben.'''
| |
| * '''[[Media:Ergebnis-Klausur-23-07-2008.pdf|Ergebnis der Klausur vom 23.7.2008]]''' (anonymisiert)
| |
| * '''Scheine''' können ab 1.9.2008 im Sekretariat Informatik bei Frau Tenschert abgeholt werden.
| |
| * Die '''Wiederholungsklausur''' findet am 1.10.2008 um 9:00 Uhr im Seminarraum des [http://hci.iwr.uni-heidelberg.de/contact.php HCI, Speyerer Str. 4], statt.
| |
| * '''[[Media:Ergebnis-Klausur-01-10-2008.pdf|Ergebnis der Wiederholungsklausur vom 1.10.2008]]''' (anonymisiert)
| |
| --->
| |
| | |
| === 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.
| |
| <!-------
| |
| Im einzelnen können erworben werden:
| |
| * ein unbenoteter Übungsschein, falls jemand nicht an der Klausur teilnimmt bzw. die Klausur nicht bestanden wurde.
| |
| * ein benoteter Übungsschein (Magister mit Computerlinguistik im ''Nebenfach'', Physik Diplom)
| |
| * ein Klausurschein (Magister mit Computerlinguistik im ''Hauptfach'')
| |
| * ein Leistungsnachweis über 9 Leistungspunkte (B.A. Computerlinguistik - alte Studienordnung)
| |
| * ein Leistungsnachweis über 8 Leistungspunkte (B.Sc. Informatik, B.A. Computerlinguistik - neue Studienordnung)
| |
| * ein Leistungsnachweis über 7 Leistungspunkte (B.Sc. Physik).
| |
| --------->
| |
| | |
| === Übungsbetrieb ===
| |
| * Termine und Räume:
| |
| ** Mo 14:00 - 16:00 Uhr, INF 227 (KIP), Seminarraum 2.402 (Tutor: Sven Ebser [mailto:sven@ebsers.de sven AT ebsers.de])
| |
| ** Di 9:00 - 11:00 Uhr, INF 227 (KIP), Seminarraum 2.403 (Tutor: Christoph Koke [mailto:koke@kip.uni-heidelberg.de koke AT kip.uni-heidelberg.de])
| |
| ** Di 11:00 - 13:00 Uhr, INF 227 (KIP), Seminarraum 2.403 (Tutor: Kai Karius [mailto:kai.karius@googlemail.com kai.karius AT googlemail.com])
| |
| ** Mi 14:00 - 16:00 Uhr, INF 227 (KIP), Seminarraum 2.401 (Tutor: Stephan Meister [mailto:stephan.meister@iwr.uni-heidelberg.de stephan.meister AT iwr.uni-heidelberg.de])
| |
| * Die Übungsgruppen werden über <b>[https://www.mathi.uni-heidelberg.de/muesli/lecture/view/169 MÜSLI]</b> verwaltet. Dort erfolgt auch die <b>Anmeldung</b>.
| |
| <!------
| |
| * [[Media:Punktestand.pdf|aktueller Punktestand]] (PDF, anonymisiert, so aktuell, wie von den Tutoren an mich übermittelt -- UK)
| |
| ------->
| |
| * <b>[[Main Page#Übungsaufgaben|Übungsaufgaben]]</b> (Ü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 [http://de.neemoy.com/quizcategories/31/ 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]] (17.4.2012)
| |
| #* Definition von Algorithmen und Datenstrukturen, Geschichte
| |
| #* Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
| |
| #* Fundamentale Datenstrukturen: Zahlen, Container, Handles
| |
| #* Python-Grundlagen
| |
| <!------------->
| |
| # [[Container]] (19.4.2012)
| |
| #* Anforderungen von Algorithmen an Container
| |
| #* Einteilung der Container
| |
| #* Grundlegende Container: Array, verkettete Liste, Stack und Queue
| |
| #* Sequenzen und Intervalle (Ranges)
| |
| <!------------->
| |
| # [[Sortieren]] (24. und 26.4.2012)
| |
| #* 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]] (3. und 8.5.2012)
| |
| #* 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]] (10. und 15.5.2012)
| |
| #* 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]] (22. und 24.5.2012)
| |
| #* Lineare Suche
| |
| #* Binäre Suche in sortierten Arrays, Medianproblem
| |
| #* Suchbäume, balancierte Bäume
| |
| #* selbst-balancierende Bäume, Rotationen
| |
| #* Komplexität der Suche
| |
| <!------------->
| |
| # [[Prioritätswarteschlangen]] (29.5.2012)
| |
| #* Heap-Datenstruktur
| |
| #* Einfüge- und Löschoperationen
| |
| #* Heapsort
| |
| #* Komplexität des Heaps
| |
| <!------------->
| |
| # [[Hashing und assoziative Arrays]] (31.5.und 5.6.2012)
| |
| #* 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.2012)
| |
| #* Typen der Rekursion und ihre Umwandlung in Iteration
| |
| #* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
| |
| <!------------->
| |
| # [[Generizität]] (14.6.2012)
| |
| #* Abstrakte Datentypen, Typspezifikation
| |
| #* Required Interface versus Offered Interface
| |
| #* Adapter und Typattribute, Funktoren
| |
| #* Beispiel: Algebraische Konzepte und Zahlendatentypen
| |
| #* Operator overloading in Python
| |
| <!------------->
| |
| # [[Graphen und Graphenalgorithmen]] (19. bis 28.6.2012)
| |
| #* 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
| |
| <!------------->
| |
| <!---#* Repetition--->
| |
| <!---#* Orthogonale Zerlegung des Problems--->
| |
| <!---#* Hierarchische Zerlegung der Daten (Divide and Conquer)--->
| |
| <!---#* Randomisierung--->
| |
| <!---#* Optimierung, Zielfunktionen--->
| |
| <!---#* Systematisierung von Algorithmen aus der bisherigen Vorlesung--->
| |
| <!------------->
| |
| <!---# [[Analytische Optimierung]] (25.6.2008)--->
| |
| <!---#* Methode der kleinsten Quadrate--->
| |
| <!---#* Approximation von Geraden--->
| |
| <!------------->
| |
| # [[Randomisierte Algorithmen]] (3. und 5.7.2012)
| |
| #* 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]] (10. und 12.7.2012)
| |
| #* 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. und 19.7.2012)
| |
| #* die Klassen P und NP
| |
| #* NP-Vollständigkeit und Problemreduktion
| |
| <!------------->
| |
| # 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:Übung-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:Übung-5.pdf|Übung]] ('''neuer Abgabetermin''' 29.5.2008) und [[Media:muster_blatt5.pdf|Musterlösung]]
| |
| #* Implementation und Analyse eines Binärbaumes
| |
| #* Anwendung: einfacher Taschenrechner
| |
| <!------------
| |
| # [[Media:Übung-6.pdf|Übung]] (Abgabe 5.6.2008) 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.2008) 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.2008) 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.2008)
| |
| #* 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.2008) 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.2008)
| |
| #* 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.2008</font>)
| |
| #* Greedy-Algorithmen und Dynamische Programmierung
| |
| <!---------------->
| |
| | |
| == Sonstiges ==
| |
| * [[Gnuplot| Gnuplot Kurztutorial]]
| |
