Scalable Algorithms (ITI)

Algorithmen 1

Dozent: Thomas Bläsius

Übungsleitung: Maximilian Katzmann, Marcus Wilhelm, Wendy Yi

In dieser Vorlesung werden grundlegende Kenntnisse im Bereich Algorithmen und Datenstrukturen vermittelt. Ziel ist es, Fähigkeiten zu Verständnis und Lösung algorithmischer Probleme, sowie insbesondere deren Formalisierung, Kommunikation und Analyse zu erlernen.

Austausch findet vorrangig über Discord statt. Der Zugang ist verlinkt im ILIAS-Kurs: https://ilias.studium.kit.edu/goto.php?target=crs%5F2086671&client_id=produktiv


Eine Liste von Hochschulgruppen, die gerade aktiv neue Mitglieder suchen findet ihr hier.

Umfrage zum Studienstart

Mit einer 5-minütigen, anonymen Umfrage könnt ihr dazu beitragen den Studienstart am KIT zu verbessern! (Bitte nur 1x ausfüllen.)

Ablauf

Es gibt zwei Wöchentliche Termine für Vorlesung und Übung: Montags 15:45 und Mittwoch 14:00.

Zusätzlich gibt es Tutorien (genaue Liste folgt).

Woche Montag Mittwoch (Aus- und Abgabe von Übungsblättern)
1 2023-04-17: Vorlesung 1 2023-04-19: Vorlesung 2
2 2023-04-24: Übung 1 2023-04-26: Vorlesung 3
3 2023-05-01: Feiertag 2023-05-03: Vorlesung 4
4 2023-05-08: Vorlesung 5 2023-05-10: Übung 2
5 2023-05-15: Vorlesung 6 2023-05-17: Vorlesung 7
6 2023-05-22: Vorlesung 8 2023-05-24: Übung 3
7 2023-05-29: Pfingsten 2023-05-31: Pfingsten
8 2023-06-05: Vorlesung 9 2023-06-07: Vorlesung 10
9 2023-06-12: Vorlesung 11 2023-06-14: Übung 4
10 2023-06-19: Vorlesung 12 2023-06-21: Vorlesung 13
11 2023-06-26: Vorlesung 14 2023-06-28: Übung 5
12 2023-07-03: Vorlesung 15 2023-07-05: Vorlesung 16
13 2023-07-10: Vorlesung 17 2023-07-12: Übung 6
14 2023-07-17: Vorlesung 18 2023-07-19: Vorlesung 19
15 2023-07-24: Vorlesung 20 2023-07-26: Übung 7

Vorlesung

  1. Einführung - Multiplikation und O-Notation: mit Klicks, ohne Klicks
  2. Teile und Herrsche: mit Klicks, ohne Klicks
  3. Dynamische Arrays, amortisierte Analyse: mit Klicks, ohne Klicks
  4. Listen und binäre Suche: mit Klicks, ohne Klicks
  5. Sortieren - Mergesort, Quicksort, untere Schranke: mit Klicks, ohne Klicks
  6. Sortieren - Bucketsort, Radixsort, Word-RAM: mit Klicks, ohne Klicks
  7. Graphen und Breitensuche: mit Klicks, ohne Klicks

Lernziele, Literaturhinweise und Glossar

Zusätzliche Notizen mit den Lernzielen, Literaturhinweisen zu den einzelnen Vorlesungen und eine Glossar mit den wichtigsten Begriffen findet ihr hier. Hier auch nochmal das selbe Dokument aber mit Links zu den Folien ohne Klicks.

Übung

  1. Asymptotik, Pseudocode und Master-Theorem: mit Klicks, ohne Klicks (Update 24.04. 15:00)
  2. Algorithmenentwurf, amortisierte Analyse: mit Klicks, ohne Klicks
  3. Sortieren, Hashing: mit Klicks, ohne Klicks (Update 24.05. 9:45)

Übungsblätter

Die Übungsblätter werden mittwochs ab 14:00 Uhr hier verfügbar sein. Die Lösungen können dann bis Freitag 18:00 Uhr in der darauffolgenden Woche in Form eines PDFs online eingereicht werden. Dies erfolgt über ILIAS unter 'Tutoriumsgruppen' in der Gruppe des jeweiligen Tutors.

  • Es wird genau eine Abgabe pro Student erwartet.
  • Die Lösungen müssen mit gut sichtbar mit Namen und Matrikelnummer beschriftet sein.
  • Bei handschriftlichen Abgaben muss auf Lesbarkeit und ausreichend Platz für Korrekturanmerkungen gesorgt werden.
  • Achte darauf, effiziente Algorithmen zu formulieren, also solche mit möglichst geringer asymptotischer Laufzeit!
  • Wenn du die Korrekheit deines Algorithmus begründen oder dessen Laufzeit analysieren sollst, tue dies getrennt von der Beschreibung deines Algorithmus.
  • Gib Algorithmen nur in Pseudocode an anstatt sie in Worten zu beschreiben, falls dies explizit gefordert ist!
  • Falls nicht anders spezifiziert, bezeichnen wir mit „Graph“ einen einfachen, ungerichteten und ungewichteten Graphen.


Wer mindestens 50% aller Punkte erreicht, die auf den Übungsblättern vergeben werden, erhält einen Bonus von 0.3 Notenpunkten in der Abschlussklausur.

Pseudocode

Wir bieten die folgenden Richtlinien für das Schreiben von Pseudocode an, die zur Orientierung helfen können: Pseudocode Richtlinien

Tutorien

Über die Woche verteilt gibt es 31 Tutorien (siehe Liste). Diese dienen dem interaktiven Austausch über die Übungsblätter sowie aktuelle Themen aus Vorlesung und Übung. In den Tutorien werden außerdem die Übungsblätter abgegeben, korrigiert und besprochen.

Die Anmeldung zu den Tutorien erfolgt von Dienstag, den 18.04.2023, 18:00 Uhr bis Donnerstag, den 20.04.2023, 18:00 Uhr unter https://www.informatik.kit.edu/tutorieneinteilung/.