Scalable Algorithms (ITI)

Algorithmen 1

Dozent: Thomas Bläsius

Übungsleiter: Maximilian Katzmann, Marcus Wilhelm

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_1730917&client_id=produktiv

Ablauf

Wöchentliche Termine:

Die Ausgabe der Übungsblätter erfolgt jeweils Mittwochs, bei einer Bearbeitungsdauer von 1 Woche bis zum darauf folgenden Mittwoch um 14:00. Die Abgabe erfolgt über ILIAS unter 'Tutoriumsgruppen' in der Gruppe des jeweiligen Tutors.

Klausur

  • Die Hauptklausur findet am 1. September statt. Klausurbeginn ist um 8:00 Uhr; seid also am besten um 7:40 Uhr vor Ort.
  • Eine Zuteilung wer in welchem Hörsaal schreibt, findet ihr in dieser Liste.
  • Die Bearbeitungszeit beträgt 2 Stunden.
  • Als Hilfsmittel ist ein Spickzettel erlaubt. Ein Spickzettel besteht aus einem A4 Blatt auf dem die Vor- und Rückseite beliebigen Inhalt enthalten darf.
  • Altklausuren sind hier verfügbar. Die Klausur dieses Semester wird sicher nicht deckungsgleich mit den Altklausuren sein. Dennoch sollten diese gut geeignet sein, um sich in Vorbereitung auf die Klausur mit dem Stoff vertraut zu machen.
  • Die Klausur vom Sommersemester 2022 findet ihr hier, eine Version mit Lösungen hier.
  • Die Nachklausur wird am 24.3.2023 stattfinden.

Zusatztutorien

Vor der Klausur werden zusätzliche Tutorien angeboten, bei denen Stoff aus der Vorlesung wiederholt und Übungsaufgaben bearbeitet werden. Eine Anmeldung ist nicht nötig.

Pro Woche werden zwei Tutorien stattfinden. Der Termin am Montag wird zur Wiederholung und als Fragestunde genutzt, am Mittwoch werden wir vornehmlich gemeinsam Aufgaben bearbeiten. Jede Woche wird einem Themenblock gewidmet sein.

Termine
  • Montags: 09:45 - 11:15, 50.34 Raum -102
  • Mittwochs: 09:45 - 11:15, 50.34 Raum -102
Woche Montag Mittwoch Themen
1 01.08.2022 03.08.2022 Beweise, O-Notation, Rekurrenzen, Amortisierte Analyse
2 08.08.2022 10.08.2022 Grundlegende Datenstrukturen, Hashing, Union-Find
3 15.08.2022 17.08.2022 Sortieren, Suchbäume, Heaps
4 22.08.2022 24.08.2022 Breitensuche, Kürzeste Wege, Minimale Spannbäume
5 29.08.2022 31.08.2022 Tiefensuche, Dynamsiche Programmierung
Materialien
  1. Woche 1: Folien Aufgaben Lösung (aktualisiert 15.08. 22:00)
  2. Woche 2: Folien Aufgaben (aktualisiert 10.08. 11:45) Lösung
  3. Woche 3: Folien Aufgaben (aktualisiert 22.08. 09:00) Lösung (aktualisiert 29.08. 10:50)
  4. Woche 5: Folien Aufgaben Lösung (aktualisiert 31.08. 15:00)

Digitale Sprechstunde

Die digitalen Sprechstunden finden via Twitch statt. Wir werden immer etwas vorbereitet haben, das den Stoff aus der Vorlesung übt bzw. wiederholt. Darüber hinaus ist Raum für Fragen (sowohl inhaltlicher als auch organisatorischer Natur). Wenn es konkrete Wünsche gibt, was nochmal wiederholt werden soll, dann können die gerne auch vorab an uns herangetragen werden.

3.8. um 14 Uhr

Hier beschäftigen wir uns insbesondere mit der Frage, wie man in einem Graphen alle Dreiecke findet. An dem Beispiel werden wir sehen, wie uns theoretische Überlegungen zu einem effizienten Algorithmus führen können. Dabei beschäftigen wir uns insbesondere mit der O-Notation, mit verschiedenen Graphdatenstrukturen und mit der Umsetzung der Algorithmischen Idee in Pseudocode.

Hier der Link zum genannten Git-Rep: https://github.com/thobl/triangle-counting

24.8. um 14 Uhr

Da die Klausur näher rückt wird hier hauptsächlich Platz für Fragen sein. Zusätzlich werden wir uns eher kleinere Aufgaben anschauen, bei denen wir insbesondere auf die Unterscheidung zwischen relevanten und irrelevanten Details eingehen. Falls ihr Wünsche für Themen habt, dann könnt ihr uns die auch gerne vorab zukommen lassen.

Materialien:

30.8. um 17:30 Uhr

Dieser Termin ist ausschließlich zur Beantwortung von Fragen gedacht. Die Fragen können gerne spontan im Chat gestellt werden oder vorab via Discord/Mail. Fragen zu spezifischen Aufgaben am besten schon vorab stelle, da diese spontan ggf. nicht so gut beantwortbar sind. Unspezifische Fragen der Form “Kannst du nochmal XY erklären?” sind natürlich auch ok.

Aufzeichnungen & Transkript

Die Lehrveranstaltung wird automatisch aufgezeichnet und im Ilias hochgeladen. Zusätzlich gibt es die Aufnahmen auch beim Lecture Translator. Dort wird die Veranstaltung automatisiert live transkribiert und übersetzt. Außerdem kann man sich die Aufzeichnungen dann später mit Untertiteln ansehen.

Termine

Woche Montag Mittwoch (Übungsblatt(ab/aus)gabe)
1 18.4.22: Feiertag 20.4.22: VL 1
2 25.4.22: VL 2 27.4.22: Übung 1
3 2.5.22: VL 3 4.5.22: VL 4
4 9.5.22: VL 5 11.5.22: Übung 2
5 16.5.22: VL 6 18.5.22: VL 7
6 23.5.22: VL 8 25.5.22: Übung 3
7 30.5.22: VL 9 1.6.22: VL 10
8 6.6.22: Pfingstmontag 8.6.22: Vorlesungsfrei
9 13.6.22: VL 11 15.6.22: Übung 4
10 20.6.22: VL 12 22.6.22: VL 13
11 27.6.22: VL 14 29.6.22: Übung 5
12 4.7.22: VL 15 6.7.22: digitale Sprechstunde
13 11.7.22 VL 16 13.7.22 Übung 6
14 18.7.22 VL 17 20.7.22 VL 18
15 25.7.22 VL 19 27.7.22 Zusammenfassung, Ausblick, etc

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
  8. Kürzeste Wege - Dijkstras Algorithmus: mit Klicks, ohne Klicks
  9. Kürzeste Wege - negative Kanten und APSP: mit Klicks, ohne Klicks
  10. Binärer Heap: mit Klicks, ohne Klicks (aktualisiert: 22.8.)
  11. Sortierte Folgen und Suchbäume: mit Klicks, ohne Klicks
  12. (2, 3)-Bäume - Implementierung: mit Klicks, ohne Klicks
  13. Tiefensuche - Brücken finden: mit Klicks, ohne Klicks
  14. Tiefensuche auf gerichteten Graphen: mit Klicks, ohne Klicks
  15. Minimale Spannbäume: mit Klicks, ohne Klicks
  16. Union-Find: mit Klicks, ohne Klicks
  17. Dynamische Programmierung: mit Klicks, ohne Klicks
  18. Generische Optimierungsmethoden: mit Klicks, ohne Klicks
  19. Average-Case Analyse, Zusammenfassung, Ausblick 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 & Master-Theorem mit Klicks, ohne Klicks (aktualisiert 10.08. 20:00)
  2. Blatt2-Aufgabe1-algOne & Amortisierte Analyse mit Klicks, ohne Klicks (aktualisiert: 03.08. 8:00)
  3. Sorting & Hashing mit Klicks Ohne Klicks
  4. Graphen mit Klicks ohne Klicks (inkl. Aktualisierung zu in-trees: es wird auch kreisfreiheit oder zusammenhang (Pfad zur Wurzel von jedem Knoten) benötigt)
  5. Suchbäume und Suche in Graphen mit Klicks mit ohne Klicks
  6. Starker Zusammenhang mit DFS, strukturelle Induktion mit Klicks ohne Klicks
  7. Average-Case Analyse, Zusammenfassung, Ausblick mit Klicks ohne Klicks

Übungsblätter

Die Übungsblätter werden mittwochs ab 14:00 Uhr hier verfügbar sein. Die Lösungen können dann bis zum darauffolgenden Mittwoch um 14:00 Uhr 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.

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

Tutorien

Eine Übersicht der angebotenen Tutorien gibt es hier. Die Anmeldung erfolgt über https://www.informatik.kit.edu/tutorieneinteilung/.

Pseudocode

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

Online-Veranstaltung am 6.7.

Am 6.7. ist der Audimax wegen einer Veranstaltung belegt. Daher weichen wir an dem Tag auf ein Online-Format aus. Hier die wichtigsten Informationen zum Ablauf:

  • Als Plattform verwenden wir Twitch.
  • Start ist wie üblich 14 Uhr.
  • Anders als in der Vorlesung geht es hier nicht um die Vermittlung neuen Stoffs.
  • Wir werden ein paar Fragen/Aufgaben vorbereitet haben, die darauf abzielen schon behandelte Themen nochmal besser zu verstehen.
  • Ihr könnt uns vorab via Discord (gerne einfach in #general) Themen mitteilen, die ihr euch hier wünschen würdet. Am besten rechtzeitig, damit wir da noch drauf reagieren können ;-).
  • Außerdem werden wir natürlich versuchen die live aufkommenden Fragen zu beantworten (um am Chat teilnehmen zu können ist ein Twitch-Account nötig).

Notizen aus der Online Vorlesung