Es werden grundlegende Entwurfsmuster für Algorithmen sowie klassische algorithmische Probleme und Datenstrukturen behandelt. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. In die Graphentheorie wird kurz eingeführt.
Lernziel
Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen.
Inhalt
Es werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. Hierfür werden grundlegende Konzepte der Graphentheorie eingeführt.
Die Leistungskontrolle wird in jeder Session angeboten. Die Repetition ist ohne erneute Belegung der Lerneinheit möglich.
Prüfungsmodus
schriftlich 240 Minuten
Zusatzinformation zum Prüfungsmodus
Während des Semesters können durch aktive Mitarbeit Bonuspunkte erarbeitet werden. Am Ende des Semesters wird aus den Bonuspunkten eine Note für die Übungen berechnet. Die Note für die Übungen fliesst in die Endnote ein, sofern deren Berücksichtigung vorteilhaft ist. Die Endnote ist das Maximum aus der Note der Sessionsprüfung und dem gewichteten Mittel der Note für die Übungen (30%) und der Note der Sessionsprüfung (70%).
Die Bonuspunkte zählen auch für die Repetitionsprüfung oder den 1. Versuch im Sommer. Sobald die Lerneinheit neu gelesen wird, sind die Bonuspunkte aus dem Vorjahr nicht mehr anrechenbar.
Hilfsmittel schriftlich
Keine
Online-Prüfung
Die Prüfung kann am Computer stattfinden.
Falls die Lerneinheit innerhalb eines Prüfungsblockes geprüft wird, werden die Kreditpunkte für den gesamten bestandenen Block erteilt. Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.