Main Page: Difference between revisions
From Alda
Jump to navigationJump to search
No edit summary |
|||
(2 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester | apl. Prof. Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2020 | ||
Die Vorlesung findet '''dienstags''' und '''donnerstags''' | 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 === | === Klausur und Nachprüfung === | ||
Der Termin der '''Abschlussklausur''' steht noch nicht fest. | |||
Die ''' | <!--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) | * '''[[Media:2014-Klausur-1.pdf|Ergebnis der Klausur 1 vom 29.7.2014]]''' (anonymisiert) | ||
Line 42: | Line 42: | ||
** 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]) | ** 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:// | * Die Übungsgruppen werden über <b>[https://muesli.mathi.uni-heidelberg.de/lecture/view/1171 MÜSLI]</b> verwaltet. | ||
* Übungsblätter werden | * Ü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) | * [[Media:Punktestand.pdf|aktueller Punktestand]] (PDF, anonymisiert, so aktuell, wie von den Tutoren an mich übermittelt -- UK) | ||
Line 62: | Line 62: | ||
=== Gliederung der Vorlesung === | === Gliederung der Vorlesung === | ||
(Termine werden nach und nach aktualisiert) | |||
<!-------------> | <!-------------> | ||
# [[Einführung]] ( | # [[Einführung]] (21. und 23.4.2020) | ||
#* Definition von Algorithmen und Datenstrukturen, Geschichte | #* Definition von Algorithmen und Datenstrukturen, Geschichte | ||
#* Fundamentale Algorithmen: Konstruktoren, Kopierfunktionen, swap. | #* Fundamentale Algorithmen: Konstruktoren, Kopierfunktionen, swap. | ||
Line 69: | Line 70: | ||
#* Python-Grundlagen | #* Python-Grundlagen | ||
<!-------------> | <!-------------> | ||
# [[Container]] ( | # [[Container]] (28.4.2020) | ||
#* Abstrakte Datentypen und algebraische Spezifikation | #* Abstrakte Datentypen und algebraische Spezifikation | ||
#* Grundlegende Container: Array, Stack, Queue, assoziatives Array | #* Grundlegende Container: Array, Stack, Queue, assoziatives Array | ||
<!-------------> | <!-------------> | ||
# [[Sortieren]] ( | # [[Sortieren]] (some day in 2020) | ||
#* Spezifikation des Sortierproblems | #* Spezifikation des Sortierproblems | ||
#* Selection Sort und Insertion Sort | #* Selection Sort und Insertion Sort |
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
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)
- 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
- Container (28.4.2020)
- Abstrakte Datentypen und algebraische Spezifikation
- Grundlegende Container: Array, Stack, Queue, assoziatives Array
- 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
- 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
- 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 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
- 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)
- 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
- NP-Vollständigkeit (22.7.2014)
- die Klassen P und NP
- NP-Vollständigkeit und Problemreduktion
- 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.