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 2017
apl. Prof. Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2020


Die Vorlesung findet '''dienstags''' und '''donnerstags''' jeweils um 13:30 Uhr im Großen Hörsaal Chemie (INF 252) statt.  
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.-->
Der Termin der '''Abschlussklausur''' steht noch nicht fest.
Die '''Abschlussklausur''' findet am Dienstag, dem 27.7.2014 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!)
<!--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://www.mathi.uni-heidelberg.de/muesli/lecture/view/707 MÜSLI]</b> verwaltet.  
* Die Übungsgruppen werden über <b>[https://muesli.mathi.uni-heidelberg.de/lecture/view/1171 MÜSLI]</b> verwaltet.  
* Übungsblätter werden in der Regel mittwochs auf [https://elearning2.uni-heidelberg.de/course/view.php?id=15180 Moodle] veröffentlicht.
* Ü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]] (18. und 20.4.2017)  
# [[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]] (25.4.2017)
# [[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]] (27. bis 4.5.2017)
# [[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

  • 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