Datenstrukturen und Algorithmen

Dozent: Dr. Arne Meier

Frequenz: jährlich im WS, empf. 3. Semester

Veranstaltungsart: Vorlesung und Übung (2V + 2Ü, 5 LP)

Prüfung: Klausur

Diese Vorlesung führt in die Konstruktion und Analyse von grundlegenden Datenstrukturen und Algorithmen ein. Ziele sind das Kennenlernen, Verstehen, Anwenden und Vergleichen alternativer Implementierungen für abstrakte Datentypen, das Analysieren von Algorithmen auf Korrektheit und auf Zeit- und Speicherbedarf sowie das Kennenlernen und Anwenden von Entwurfsparadigmen für Algorithmen.

Stoffplan:

• Landausymbole

• Stable Matchings, Felder und Listen, Gale-Shapley-Algorithmus

• Warteschlangen und Kellerspeicher, Bäume, Breitensuche, Tiefensuche

• Zusammenhangskomponenten, Topologisches Sortieren, Dijkstra-Algorithmus

• Prioritätswarteschlangen, Heaps

• Greedy-Paradigma, Intervall Scheduling, Minimale Spanbäume, Prim-Algorithmus

• Sortierverfahren (Insertionsort, Selectionsort, Mergesort, Quicksort, Timsort)

• Divide-and-Conquer-Paradigma, Optimalität von vergleichsbasierter Sortierverfahren, Inversionen

• Suchverfahren, Binäre Suche, Binäre Suchbäume, Durchmusterung von Graphen

• AVL- und Rot-Schwarz-Bäume, B/B*-Bäume

• Hashing, Kollisionsbehandlung, Double Hashing

• Dynamische Programmierung

Die Abschlussprüfung des Moduls ist eine schriftliche Klausur über 90 Minuten.

Termin

Die Prüfungstermine finden Sie im zentralen Webauftritt der Universität (siehe Link unten).

Anmeldung

Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten). Zur Teilnahme als Zulassungsauflage benötigen Sie keine Anmeldung. Bitte informieren Sie den Betreuer oder die Betreuerin des Übungsbetriebs im Anmeldezeitraum darüber.

Hilfsmittel

Es sind keine Hilfsmittel erlaubt. Sie benötigen kein eigenes Papier!

Klausurbonus

Die Modalitäten für das Erreichen eines Klausurbonus finden Sie im Foliensatz im Stud.IP.

Studienleistung

Die Modalitäten für das Erreichen der Studienleistung finden Sie im Foliensatz im Stud.IP.