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

Wöchentliche Termine:

• Montags 15:45, Audimax: Vorlesung
• Mittwoch 14:00, Audimax: abwechselnd Vorlesung oder Übung
• Tutorien, Anmeldung siehe https://www.informatik.kit.edu/tutorieneinteilung/

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.

• 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 findet am 24. März statt. Klausurbeginn ist um 8:00 Uhr; seid also am besten um 7:40 Uhr vor Ort.
• Anmeldung ist hier bis zum 18.08.2023 um 23:59 möglich.
• 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.
• Die Klausur vom Wintersemester 2023 findet ihr hier, eine Version mit Lösungen hier.

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.

• Montags: 09:45 - 11:15, 50.34 Raum -102
• Mittwochs: 09:45 - 11:15, 50.34 Raum -102

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 4: Folien Aufgaben Lösung
5. Woche 5: Folien Aufgaben Lösung (aktualisiert 31.08. 15:00)

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.

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

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:

• Die drei Fragen, die wir uns angeschaut hatten: question-list.pdf
• Der Beispielgraph zur ersten Frage: mssp-example-graph.pdf
• Die Notizen vom Stream: notes-24-8.pdf

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.

Dieser Termin kurz vor der Nachklausur ist hauptsächlich 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.

Die Notizen vom Stream findet ihr hier: notes-23-03-20.pdf.

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.

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. Hashing: mit Klicks, ohne Klicks
8. Graphen und Breitensuche: mit Klicks, ohne Klicks
9. Kürzeste Wege - Dijkstras Algorithmus: mit Klicks, ohne Klicks
10. Kürzeste Wege - negative Kanten und APSP: mit Klicks, ohne Klicks
11. Binärer Heap: mit Klicks, ohne Klicks (aktualisiert: 22.8.)
12. Sortierte Folgen und Suchbäume: mit Klicks, ohne Klicks
13. (2, 3)-Bäume - Implementierung: mit Klicks, ohne Klicks
14. Tiefensuche - Brücken finden: mit Klicks, ohne Klicks
15. Tiefensuche auf gerichteten Graphen: mit Klicks, ohne Klicks
16. Minimale Spannbäume: mit Klicks, ohne Klicks
17. Union-Find: mit Klicks, ohne Klicks
18. Dynamische Programmierung: mit Klicks, ohne Klicks
19. Generische Optimierungsmethoden: mit Klicks, ohne Klicks
20. Average-Case Analyse, Zusammenfassung, Ausblick mit Klicks ohne Klicks

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.

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

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.

• Übungsblatt 01
• Übungsblatt 02
• Übungsblatt 03
• Übungsblatt 04
• Übungsblatt 05
• Übungsblatt 06
• Übungsblatt 07
• Übungsblatt 08
• Übungsblatt 09
• Übungsblatt 10
• Übungsblatt 11
• Übungsblatt 12
• Übungsblatt 13
• Übungsblatt 14

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

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

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