Main Page: Difference between revisions

From Alda
Jump to navigationJump to search
 
(269 intermediate revisions by 32 users not shown)
Line 1: Line 1:
== Getting started ==
== Vorlesung Algorithmen und Datenstrukturen ==
 
 
apl. Prof. Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2020
 
Die Vorlesung findet '''dienstags''' um 14:15 Uhr und '''donnerstags''' um 16:15 Uhr online auf Discord und Twitch statt. Die Links haben in Müsli angemeldete Teilnehmer per Email erhalten.


* [http://meta.wikimedia.org/wiki/Help:Editing Wiki Editierhilfe] (Wiki-Syntax usw.)
=== Klausur und Nachprüfung ===
* [http://www.mediawiki.org/wiki/Manual MediaWiki Manual] (für Administratoren)
* [[Sandbox]] (zum ungefährlichen Ausprobieren von Änderungen)


== Vorlesung Algorithmen und Datenstrukturen ==
Der Termin der '''Abschlussklausur''' steht noch nicht fest.
<!--Die '''Klausur 1''' findet am Donnerstag, dem 20.7.2017 von 13:00 bis 14:30 Uhr im Großen Hörsaal Chemie (INF 252) statt. <b>Bitte melden Sie sich in [https://muesli.mathi.uni-heidelberg.de/lecture/view/707 MÜSLI] für die Klausur an.</b> Zur Klausur wird zugelassen, wer mindestens 50% der Übungspunkte erreicht und eine Aufgabe in der Übungsgruppe vorgerechnet hat. (Hinweis: Sie benötigen einen Lichtbildausweis, um sich bei der Klausur zu indentifizieren!)-->
<!---
* '''[[Media:2014-Klausur-1.pdf|Ergebnis der Klausur 1 vom 29.7.2014]]''' (anonymisiert)
Die '''Klausur 2''' findet am Mittwoch, dem 8.10.2014 von 10:00 bis 12:00 Uhr im Seminarraum des [http://hci.iwr.uni-heidelberg.de/contact.php HCI, Speyerer Str. 6], statt. Teilnahmeberechtigt sind diejenigen, die Klausur 1 nicht bestanden haben (bitte unbedingt per Email <b>anmelden!</b>) sowie diejenigen, die mich vorab informiert haben (Sie brauchen sich nicht nochmals anzumelden).
* '''[[Media:2014-Klausur-2.pdf|Ergebnis der Klausur 2 vom 8.10.2014]]''' (anonymisiert)
* '''[[Media:Prüfungsteilnehmer.pdf|Liste der Studenten]], die sich verbindlich zur Klausur angemeldet und die notwendige Übungspunktzahl erreicht haben.'''
* '''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 ===
<!---
* Wegen der großen Nachfrage haben wir zusätzliche Tutoren/Korrektoren eingestellt und die Gruppengröße auf 32 Teilnehmer erhöht. Bitte melden Sie sich im [https://www.mathi.uni-heidelberg.de/muesli/lecture/view/355 MÜSLI] an.
* Termine und Räume:
** Mo 14:00 - 16:00 Uhr, INF 501, R-102 (Tutor und Korrektor: Niels Buwen [mailto:buwen@stud.uni-heidelberg.de buwen AT stud.uni-heidelberg.de])
** Mo 16:00 - 18:00 Uhr, INF 288, HS6 (Tutor: Niels Buwen, Korrektor: Katrin Honauer [mailto:katrin.honauer@iwr.uni-heidelberg.de katrin.honauer AT iwr.uni-heidelberg.de])
** Di  9:00 - 11:00 Uhr, <b>neuer Raum:</b> INF 294, R-103 (Tutor und Korrektor: Marius Killinger [mailto:marius.felix.killinger@stud.uni-heidelberg.de marius.felix.killinger AT stud.uni-heidelberg.de])
** Di 11:00 - 13:00 Uhr, INF 294, R-102 (Tutor und Korrektor: Fynn Beuttenmüller: [mailto:f.beuttenmueller@gmx.de f.beuttenmueller AT gmx.de])
** Mi 14:00 - 16:00 Uhr, INF 294, R-113 (Tutor: Axel Wagner, Korrektor: Philipp Schubert [mailto:phil.jo.schubert@gmail.com phil.jo.schubert AT gmail.com])
** Mi 16:00 - 18:00 Uhr, INF 294, R-113 (Tutor und Korrektor: Axel Wagner: [mailto:axel.wagner@stud.uni-heidelberg.de axel.wagner AT stud.uni-heidelberg.de])
--->
* Die Übungsgruppen werden über <b>[https://muesli.mathi.uni-heidelberg.de/lecture/view/1171 MÜSLI]</b> verwaltet.
* Übungsblätter werden auf [https://moodle.uni-heidelberg.de/course/view.php?id=2239 Moodle] veröffentlicht.
<!------
* [[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 Korrektor.
* 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.


Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2008
=== Prüfungsvorbereitung ===


'''[[Organisatorisches]]''' (9.4.2008)
Zur Hilfe bei der Prüfungsvorbereitung hat Andreas Fay [http://de.neemoy.com/quizcategories/31/ Quizfragen] erstellt.
* Die Vorlesung findet '''mittwochs''' um 11:15 Uhr in INF 227, HS 2 und '''donnerstags''' um 11:15 Uhr in INF 308, HS 2 statt.
------->
* Übungsbetrieb
=== Literatur ===
* Scheinbedingungen, Credit points
* Klausurtermin


'''[[Main Page#Übungsaufgaben|Übungsaufgaben]]'''
* 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''' (als [http://kogs.informatik.uni-hamburg.de/~koethe/VL-Algorithmen-und-Datenstrukturen-ss08-Overview.pdf PDF] mit Übungsthemen)
=== Gliederung der Vorlesung ===
(Termine werden nach und nach aktualisiert)
<!------------->
<!------------->
# [[Einführung]] (9.4.2008)  
# [[Einführung]] (21. und 23.4.2020)  
#* Definition von Algorithmen und Datenstrukturen, Geschichte
#* Definition von Algorithmen und Datenstrukturen, Geschichte
#* Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
#* Fundamentale Algorithmen: Konstruktoren, Kopierfunktionen, swap.
#* Fundamentale Datenstrukturen: Zahlen, Container, Handles
#* Fundamentale Datenstrukturen: Zahlen, Container, Handles
#* Python-Grundlagen
#* Python-Grundlagen
<!------------->
<!------------->
# [[Container]] (10.4.2008)
# [[Container]] (28.4.2020)
#* Anforderungen von Algorithmen an Container
#* Abstrakte Datentypen und algebraische Spezifikation
#* Einteilung der Container
#* Grundlegende Container: Array, Stack, Queue, assoziatives Array
#* Grundlegende Container: Array, verkettete Liste, Stack und Queue
#* Sequenzen und Intervalle (Ranges)
<!------------->
<!------------->
# [[Sortieren]] (16. und 17.4.2008)
# [[Sortieren]] (some day in 2020)
#* Spezifikation des Sortierproblems
#* Spezifikation des Sortierproblems
#* Selection Sort
#* Selection Sort und Insertion Sort
#* Merge Sort
#* Merge Sort
#* Quick Sort und seine Varianten
#* Quick Sort und seine Varianten
#* Vergleich der Anzahl der benötigten Schritte
#* Anzahl der benötigten Vergleiche
#* Laufzeitmessung in Python
<!------------->
<!------------->
# [[Korrektheit]] (23. und 24.4.2008)
# [[Korrektheit]] (29.4. und 6.5.2014 -- ab hier altes Datum)
#* Definition von Korrektheit, Algorithmen-Spezifikation
#* Definition von Korrektheit, Algorithmen-Spezifikation
#* Korrektheitsbeweise versus Testen
#* Korrektheitsbeweise versus Testen
Line 46: Line 88:
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python
#* Ausnahmen (exceptions) und Ausnahmebehandlung in Python
<!------------->
<!------------->
# [[Effizienz]] (24. und 30.4.2008)
# [[Effizienz]] (8. und 13.5.2014)
#* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
#* Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
#* Laufzeit versus Komplexität
#* Laufzeit versus Komplexität
#* Komplexitätsklassen
#* Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
#* Bester, schlechtester, durchschnittlicher Fall
#* Bester, schlechtester, durchschnittlicher Fall
#* Amortisierte Komplexität
#* Amortisierte Komplexität
<!------------->
<!------------->
# [[Suchen]] (7. und 8.5.2008)
# [[Suchen]] (15. und 20.5.2014)
#* Binäre Suche in sortierten Arrays
#* Sequentielle Suche
#* Suchbäume
#* Binäre Suche in sortierten Arrays, Medianproblem
#* balancierte Bäume
#* Suchbäume, balancierte Bäume
#* selbst-balancierende Bäume, Rotationen
#* selbst-balancierende Bäume, Rotationen
#* Komplexität der Suche
#* Komplexität der Suche
<!------------->
<!------------->
# [[Prioritätswarteschlangen]] (14.5.2008)
# [[Sortieren in linearer Zeit]] (22.5.2014)
#* Permutationen
#* Sortieren als Suchproblem
#* Bucket Prinzip, Bucket Sort
<!------------->
# [[Prioritätswarteschlangen]] (27.5.2014)
#* Heap-Datenstruktur
#* Heap-Datenstruktur
#* Einfüge- und Löschoperationen
#* Einfüge- und Löschoperationen
Line 66: Line 113:
#* Komplexität des Heaps
#* Komplexität des Heaps
<!------------->
<!------------->
# [[Dictionaries]] (15.5.2008)
# [[Assoziative Arrays]] (3.6.2014)
#* Implementation mit Bäumen
#* Datenstruktur-Dreieck für assoziative Arrays
#* Hashing
#* Definition des abstrakten Datentyps
#* Implementation als Hashtabelle
#* JSON-Datenformat
#* Realisierung durch sequentielle Suche und durch Suchbäume
<!------------->
<!------------->
# [[Iteration versus Rekursion]] (21.5.2008)
# [[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
#* Typen der Rekursion und ihre Umwandlung in Iteration
#* Iteratoren
#* Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
<!------------->
<!------------->
# [[Generizität]] (28.und 29.5.2008)
# [[Generizität]] (17.6.2014)
#* Abstrakte Datentypen, Typspezifikation
#* Abstrakte Datentypen, Typspezifikation
#* Required Interface versus Offered Interface
#* Required Interface versus Offered Interface
Line 82: Line 136:
#* Operator overloading in Python
#* Operator overloading in Python
<!------------->
<!------------->
# [[Graphen und Graphenalgorithmen]] (4. bis 12.6.2008)
# [[Graphen und Graphenalgorithmen]] (24.6. bis 10.7.2014)
#* Einführung
#* Einführung
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
#* Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
#* Gerichtete und ungerichtete Graphen
#* Gerichtete und ungerichtete Graphen
#* Vollständiger Graph
#* Vollständige Graphen
#* Planare Graphen, duale Graphen
#* Pfade, Zyklen
#* Pfade, Zyklen
#* Tiefensuche und Breitensuche
#* Tiefensuche und Breitensuche
#* Zusammenhang, mehrfacher Zusammenhang, Komponenten
#* Zusammenhang, Komponenten
#* Gewichtete Graphen
#* Gewichtete Graphen
#* Minimaler Spannbaum
#* Minimaler Spannbaum
#* Kürzeste Wege, Best-first search (Dijkstra)
#* Kürzeste Wege, Best-first search (Dijkstra)
#* Most-Promising-first search (A*)
#* 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
<!------------->
<!------------->
# [[Prinzipien des Algorithmenentwurfs]] (18.6.2008)
<!---#* Repetition--->
#* Repetition
<!---#* Orthogonale Zerlegung des Problems--->
#* Orthogonale Zerlegung des Problems
<!---#* Hierarchische Zerlegung der Daten (Divide and Conquer)--->
#* Hierarchische Zerlegung der Daten (Divide and Conquer)
<!---#* Randomisierung--->
#* Randomisierung
<!---#* Optimierung, Zielfunktionen--->
#* Optimierung, Zielfunktionen
<!---#* Systematisierung von Algorithmen aus der bisherigen Vorlesung--->
#* Systematisierung von Algorithmen aus der bisherigen Vorlesung
<!------------->
<!------------->
# [[Analytische Optimierung]] (19.6.2008)
<!---# [[Analytische Optimierung]] (25.6.2008)--->
#* Methode der kleinsten Quadrate
<!---#* Methode der kleinsten Quadrate--->
#* Approximation von Geraden
<!---#* Approximation von Geraden--->
<!------------->
<!------------->
# [[Randomisierte Algorithmen]] (25. und 26.6.2008)
# [[Randomisierte Algorithmen]] (10. und 15.7.2014)
#* Zufallszahlen, Zyklenlänge, Pitfalls
#* Zufallszahlen, Zyklenlänge, Pitfalls
#* Zufallsverteilungen, Box-Muller Transformation
#* Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
#* Randomisierte vs. deterministische Algorithmen
#* Randomisierte vs. deterministische Algorithmen
#* Las Vegas vs. Monte Carlo Algorithmen
#* Las Vegas vs. Monte Carlo Algorithmen
#* Beispiel für Las Vegas: Randomisiertes Quicksort
#* Beispiel für Las Vegas: Randomisiertes Quicksort
#* Beispiele für Monte Carlo: randomisierte Integration, randomisierter Primzahltest
#* Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems
#* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit
#* RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)
<!------------->
<!------------->
# [[Greedy-Algorithmen]] (2.7.2008)
# [[Greedy-Algorithmen und Dynamische Programmierung]] (17.7.2014)
#* Prinzip
#* Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
#* Bedingung für Optimalität
#* bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
#* Beispiele für Greedy-Algorithmen
#* 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
<!------------->
<!------------->
# [[Dynamische Programmierung]] (3. und 9.7.2008)
# [[NP-Vollständigkeit]] (22.7.2014)
#* die Klassen P und NP
#* NP-Vollständigkeit und Problemreduktion
<!------------->
<!------------->
# [[Erschöpfende Suche]] (10. und 16.7.2008)
# Wiederholung (24.7.2014)
#* Beispiele: u.a. Problem des Handlungsreisenden
#* Exponentielle Komplexität, NP-Vollständigkeit
#* Approximation bei NP-vollständigen Problemen
<!------------->
# [[Quantum computing]] (17.7.2008)


== Übungsaufgaben ==
== Übungsaufgaben ==


(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 10:00 Uhr per Email bei dem jeweiligen Übungsgruppenleiter.
(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 17.4.2008)
<i>Die Übungsaufgaben sind zur Zeit nicht freigeschaltet.</i>
 
<!------
# [[Media:Uebung-1.pdf|Übung]] (Abgabe 29.4.2014) und [[Media:muster_blatt1.pdf|Musterlösung]]
#* Python-Tutorial
#* Python-Tutorial
#* Sieb des Eratosthenes
#* Sieb des Eratosthenes
#* Wert- und Referenzsemantik
#* Wert- und Referenzsemantik
<!-------------------->
#* Freitag der 13.
# Übung (Abgabe 24.4.2008)
#* Dynamisches Array
#* Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von Problemgröße)
# [[Media:Uebung-2.pdf|Übung]] (Abgabe 6.5.2014) und [[Media:muster_blatt2.pdf|Musterlösung]]
#* Entwicklung eines effizienten Algorithmus: Bruchfestigkeit von Gläsern
#* Sortieren: Implementation und Geschwindigkeitsvergleich (Diagramme in Abhängigkeit von der Problemgröße)
<!-------------------->
#* Zelluläre Automaten
# Übung (Abgabe 2.5.2008)
# [[Media:Uebung-3.pdf|Übung]] (Abgabe 13.5.2014) und [[Media:muster_blatt3.pdf|Musterlösung]]
#* Experimente zur Effektivität von Unit Tests
#* Manuelles Debuggen
#* Einführung in Unit Tests
#* 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 20.5.2014) und [[Media:muster_blatt4.pdf|Musterlösung]]
# Übung (Abgabe 8.5.2008)
#* 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]] (Abgabe 27.5.2014) und [[Media:muster_blatt5.pdf|Musterlösung]]
# Übung (Abgabe 15.5.2008)
#* Implementation und Analyse eines Binärbaumes
#* Implementation und Analyse eines Binärbaumes
#* Anwendung: einfacher Taschenrechner
#* Anwendung: einfacher Taschenrechner
<!-------------------->
# [[Media:Uebung-6.pdf|Übung]] (Abgabe '''Donnerstag''' 5.6.2014) und [[Media:muster_blatt6.pdf|Musterlösung]]
# Übung (Abgabe 23.5.2008)
#* Treap-Datenstruktur: Verbindung von Suchbaum und Heap
#* Treap-Datenstruktur: Verbindung von Suchbaum und Heap
#* Anwendung: Worthäufigkeiten
#* Anwendung: Worthäufigkeiten (Dazu benötigen Sie die Files [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/die-drei-musketiere.txt die-drei-musketiere.txt] und [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/stopwords.txt stopwords.txt]. Die Zeichenkodierung in diesen Files ist Latin-1.)
<!-------------------->
#* BucketSort
# Übung (Abgabe 29.5.2008)
# [[Media:Uebung-7.pdf|Übung]] (Abgabe 12.6.2014) und [[Media:muster_blatt7.pdf|Musterlösung]]
#* Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Auflösung rekursiver Formeln, Umwandlung von Rekursion in Iteration
#* 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.)
# Übung (Abgabe 5.6.2008)
# [[Media:Uebung-8.pdf|Übung]] (Abgabe 19.6.2014) und [[Media:muster_blatt8.pdf|Musterlösung]]
#* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen, Benutzer-definierte Zahlentypen
#* Übungen zu Rekursion und Iteration: Fibonaccizahlen, Koch-Schneeflocke, Komplexität rekursiver Algorithmen, Umwandlung von Rekursion in Iteration
<!-------------------->
# [[Media:Uebung-9.pdf|Übung]] (Abgabe '''Dienstag''' 1.7.2014) und Musterlösung für [[Media:muster_blatt9-1+3.pdf|Aufgaben 1 und 3]] sowie für [[Media:muster_blatt9-2.pdf|Aufgabe 2]]
# Übung (Abgabe 12.6.2008)
#* Übungen zur Generizität: Sortieren mit veränderter Ordnung, Iterator für Tiefensuche
#* Elementare Graphenaufgaben (Adjazenzlisten aufschreiben, Beweis e <= 3n-6 für planare Graphen, Zyklen eines vollständigen Graphen)
#* Graphenaufgaben: Weg aus einem Labyrinth, Erzeugen einer perfekten Hashfunktion (Dazu benötigen Sie den Artikel [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5566 <i>"An optimal algorithm for generating minimal perfect hash functions"</i>] sowie das File  [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json]. Die Zeichenkodierung in diesem File ist UTF-8.)
#* Implementation einer Graphklasse
# [[Media:Uebung-10.pdf|Übung]] (Abgabe 8.7.2014) und Musterlösung für [[Media:muster_blatt10-1.pdf|Aufgabe 1]] sowie für [[Media:muster_blatt10-2.pdf|Aufgabe 2]]
#* Iteratoren für Tiefensuche und Breitensuche
#* Fortgeschrittene Graphenaufgaben: Routenplaner (Dazu benötigen Sie wieder das File  [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json]. Die Zeichenkodierung in diesem File ist UTF-8.) und Bildverarbeitung (Dazu benötigen Sie 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-11.pdf|Übung]] (Abgabe 15.7.2014)  
# Übung (Abgabe 19.6.2008)
und [[Media:muster_blatt11.pdf|Musterlösung]] sowie schöne [[Media:ballungsgebiete.pdf|Visualisierung der Ballungsgebiete]] von Thorben Kröger
#* Anwendung: Weg aus einem Labyrinth
#* Fortgeschrittene Graphenaufgaben 2: Clusterung mittels minimaler Spannbäume, Seam Carving (Dazu benötigen Sie wieder die Files [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/entfernungen.json entfernungen.json] und [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/pgm.py pgm.py] aowie das Bild [http://hci.iwr.uni-heidelberg.de/Staff/ukoethe/download/coast.pgm coast.pgm].)
#* Anwendung: Erzeugen einer perfekten Hashfunktion
# [[Media:Uebung-12.pdf|Übung]] (Abgabe 22.7.2014)
<!-------------------->
#* 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].)
# Übung (Abgabe 26.6.2008)
#* Bonusaufgaben: indirektes Sortieren und Prüfungswiederholung
#* Anwendung: Routenplaner
#* 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].)
#* Beispiele für Divide and Conquer: pow-Funktion
# [[Media:Bonusuebung.pdf|Übung (Bonus)]] (<font color=red>Achtung: Abgabe bereits am Dienstag, 24.7.2014</font>)
#* Beispiel für Methode der kleinsten Quadrate: Approximation von Kreisen
#* Greedy-Algorithmus
<!-------------------->
#* Weg durch einen Graphen
# Übung (Abgabe 3.7.2008)
#* Wiederholungsaufgaben für die Klausur
#* Naiver (deterministischer) und randomisierter Primzahltest, Laufzeitvergleich
--->
#* RANSAC für Kreise
 
<!-------------------->
== Sonstiges ==
# Übung (Abgabe 10.7.2008)
* [[Gnuplot| Gnuplot Kurztutorial]]
#* Theoretische und praktische Aufgaben zur dynamische Programmierung
* [[Git Kurztutorial]]
<!-------------------->
* [[neue Startseite|mögliche neue Startseite]]
# Übung (Abgabe 17.7.2008)
#* Sudoku-Löser

Latest revision as of 12:21, 23 October 2020

Vorlesung Algorithmen und Datenstrukturen

apl. Prof. Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2020

Die Vorlesung findet dienstags um 14:15 Uhr und donnerstags um 16:15 Uhr online auf Discord und Twitch statt. Die Links haben in Müsli angemeldete Teilnehmer per Email erhalten.

Klausur und Nachprüfung

Der Termin der Abschlussklausur steht noch nicht fest.

Übungsbetrieb

  • Die Übungsgruppen werden über MÜSLI verwaltet.
  • Übungsblätter werden auf Moodle veröffentlicht.

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

(Termine werden nach und nach aktualisiert)

  1. Einführung (21. und 23.4.2020)
    • Definition von Algorithmen und Datenstrukturen, Geschichte
    • Fundamentale Algorithmen: Konstruktoren, Kopierfunktionen, swap.
    • Fundamentale Datenstrukturen: Zahlen, Container, Handles
    • Python-Grundlagen
  2. Container (28.4.2020)
    • Abstrakte Datentypen und algebraische Spezifikation
    • Grundlegende Container: Array, Stack, Queue, assoziatives Array
  3. Sortieren (some day in 2020)
    • Spezifikation des Sortierproblems
    • Selection Sort und Insertion Sort
    • Merge Sort
    • Quick Sort und seine Varianten
    • Anzahl der benötigten Vergleiche
  4. Korrektheit (29.4. und 6.5.2014 -- ab hier altes Datum)
    • 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
  5. 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
  6. 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
  7. Sortieren in linearer Zeit (22.5.2014)
    • Permutationen
    • Sortieren als Suchproblem
    • Bucket Prinzip, Bucket Sort
  8. Prioritätswarteschlangen (27.5.2014)
    • Heap-Datenstruktur
    • Einfüge- und Löschoperationen
    • Heapsort
    • Komplexität des Heaps
  9. 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
  10. 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
  11. Iteration versus Rekursion (12.6.2014)
    • Typen der Rekursion und ihre Umwandlung in Iteration
    • Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
  12. 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
  13. Graphen und Graphenalgorithmen (24.6. bis 10.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
  14. Randomisierte Algorithmen (10. und 15.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)
  15. Greedy-Algorithmen und Dynamische Programmierung (17.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
  16. NP-Vollständigkeit (22.7.2014)
    • die Klassen P und NP
    • NP-Vollständigkeit und Problemreduktion
  17. Wiederholung (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.

Die Übungsaufgaben sind zur Zeit nicht freigeschaltet.


Sonstiges

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