Scalable Algorithms (ITI)

Algorithmen 1

Dozent: Thomas Bläsius

Übungsleitung: Jean-Pierre von der Heydt, 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.

Regen Austausch zur Vorlesung gibt es auf Discord. Der Zugang ist im Ilias verlinkt.


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.)

Aktuell: Anmeldung zu Tutorien

Unter folgendem Link ist die Anmeldung zu den Tutorien möglich bis Freitag 19.4. um 12:00 Uhr: https://plus.campus.kit.edu/signmeup/procedures/SS2024/Alle/infotut

Anmeldung vergessen? falls du es nicht geschafft hast dich, regulär zu einem Tutorium anzumelden, schreib Marcus eine E-Mail mit Name, Matrikelnummer, ukuerzel und ggf. deinen Präferierten Tutoriumsterminen

Ablauf

Es gibt wöchentlich zwei Termine für Vorlesung und Übung: Montag 15:45 und Mittwoch 14:00.

Zusätzlich gibt es Tutorien.

Woche Montag Mittwoch
1 15.04. Vorlesung 1 17.04. Vorlesung 2
2 22.04. Vorlesung 3 24.04. Übung 1
3 29.04. Vorlesung 4 01.05. Maifeiertag
4 06.05. Vorlesung 5 08.05. Übung 2
5 13.05. Vorlesung 6 15.05. Vorlesung 7
6 20.05. Pfingsten 22.05. Pfingsten
7 27.05. Vorlesung 8 29.05. Übung 3
8 03.06. Vorlesung 9 05.06. Vorlesung 10
9 10.06. Vorlesung 11 12.06. Übung 4
10 17.06. Vorlesung 12 19.06. Vorlesung 13
11 24.06. Vorlesung 14 26.06. Übung 5
12 01.07. Vorlesung 15 03.07. Vorlesung 16
13 08.07. Vorlesung 17 10.07. Übung 6
14 15.07. Vorlesung 18 17.07. Vorlesung 19
15 22.07. Vorlesung 20 24.07. Ü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

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.

Algo-Code

Unter https://algo-code.iti.kit.edu findet ihr ein Tool, mit dem ihr die Fähigkeit trainieren könnt, eine algorithmische Idee tatsächlich umzusetzen. Das ist eine Fähigkeit, die man nicht lernen, sondern nur trainieren kann (im Sinne von: es hilft nicht viel, sich anzuschauen bzw erklären zu lassen, wie das geht; das muss man oft genug selber machen).

Die Seite wird zwar gerade noch entwickelt, es gibt noch viele Bugs und nicht so viele Levels, aber nützlich für das Training sollte sie trotzdem schon sein. Im Laufe des Semesters kommt sicher auch das eine oder andere Level dazu.

Übung

  1. Asymptotik, Pseudocode, amortisierte Analyse: mit Klicks, ohne Klicks
  2. Datenstrukturen / Amortisierte Analyse, Sortieren und Quicksort: mit Klicks, ohne Klicks

Übungsblätter

Die Übungsblätter werden mittwochs ab 15:30 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. Bitte beachtet die Hinweise auf den Übungsblättern!

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