Datenstrukturen und Algorithmen (SS 2019)

Aktuelles:
Die Noten der zweiten Klausur sind nach RWTH Online übertragen worden.

Wichtige Informationen zum Übungsbetrieb

Die Tutorien finden donnerstags statt. Dort werden Tutoriumsaufgaben vorgerechnet und eine kleine Präsenzübung ("Minitest") am Ende des Tutoriumstermins geschrieben. Abgaben sind in Gruppen von 2-3 Studierenden erlaubt. Bei der Anmeldung im Übungssystem ist es möglich, eine andere Person anzugeben, mit der man präferiert in das gleiche Tutorium zugewiesen werden möchte.

Für die Klausur sind zwei Zulassungsbedingungen zu erfüllen. Sie müssen einerseits mindestens 50% der erreichbaren Punkte in den wöchentlich erscheinenden und in den Tutorien abzugebenden Abgaben erreichen. Das erste Übungsblatt erscheint am 11. April auf dieser Website. Weiterhin sind mindestens 50% der Punkte in den wöchentlichen Präsenzübungen zu erreichen. Sollten Sie die Vorlesung in einem Studiengang belegen, welcher nicht Informatik ist, können diese Zulassungsbedingungen für Sie möglicherweise entfallen. Überprüfen Sie dazu bitte Ihre fachspezifische Prüfungsordnung und informieren Sie sich im Zweifelsfall bei dem/der für Sie zuständigen Fachstudienberater*in.

F.A.Q.

  • Ich kann mich nicht zur zweiten Klausur anmelden. Was kann ich tun?
    Das Problem ist uns bekannt. Wir werden die Anmeldung ab dem 26. August freischalten.
  • Was ist klausurrelevant?
    Der gesamte Vorlesungsstoff ist klausurrelevant mit Ausnahme der algorithmischen Geometrie und Textalgorithmen.
  • Ich habe mich für die Globalübung angemeldet, bekomme allerdings angezeigt, dass dies nicht erfolgreich war. Ist das schlimm?
    Erst einmal nicht. Die Anmeldung exisitert, damit wir die Noten und Zulassungen nach RWTH Online übertragen können. Die Globalübung kann unabhängig von einer Anmeldung besucht werden.
  • Ich habe ein CES oder Erstsemestertutorium bekommen, obwohl ich das nicht bin. Ist das schlimm?
    Das ist nicht schlimm und gewollt um die Tutorien gleichmäßig auszufüllen.
  • Ich habe nicht das Tutorium bekommen, was ich haben wollte. Kann man da was machen?
    Es besteht die Möglichkeit im Übungssystem mit Studenten aus anderen Tutorien zu tauschen.
  • In RWTH Online ist ein Lehramtstutorium angegeben, gibt es eines?
    Nein.
  • In RWTH Online ist ein gruppenübergreifender Termin angegeben, was hat es damit auf sich?
    Ignorieren Sie bitte diesen Termin.
  • Gibt es einen Moodle-Raum?
    Nein. Die Übungsblätter werden auf dieser Website veröffentlicht.
  • Werden Lösungsvorschläge zu den Übungsaufgaben hochgeladen?
    Ja, auf dieser Website, i.d.R. bis Ende der Woche nach Abgabe.
  • Gibt es ein Skript zur Vorlesung?
    Nein.

Inhalt

Die Vorlesung stellt grundlegende Datenstrukturen und Algorithmen vor. Einerseits wird ein Katalog wichtiger Algorithmen detailliert vorgestellt, wobei Wert auf das intuitive Verständis des Algorithmus, die formalen Beweise seiner Korrektheit und auf die Analyse seiner Laufzeit und Gebrauch anderer Ressourcen gelegt wird. Andererseits werden allgemeine Techniken zum Entwurf neuer Datenstrukturen und Algorithmen vorgestellt.

Nach dem Genuss dieser Vorlesung sollen folgende wichtige Kenntnisse erworben worden sein: Die Fähigkeit, eine für ein Problem geeignete Datenstruktur aus einem grossen Katalog zu wählen und zu implementieren. Aktives, detailliertes Kennen der wichtigsten Algorithmen und Datenstrukturen sowie die Fähigkeit, geeignete Algorithmen in der Literatur zu finden. Selbstständiges Entwerfen und Analysieren neuer Datenstrukturen und Algorithmen anhand der wichtigsten Entwurfstechniken.

Ein grober Inhaltsüberblick sieht so aus:

  • Einführung
  • Suchen
  • Sortieren
  • Graphalgorithmen
  • Entwurfsparadigmen
Alle verwendeten Materialien wie zum Beispiel die in der Vorlesung verwendeten Folien und die Übungsblätter werden hier vorlesungsbegleitend zur Verfügung gestellt.

Vorlesungsfolien

Übungsblätter

Probeklausur

Klausuren 2019

Altklausuren von 2016

Globalübung

Hier finden Sie die Folien und Anschriften der Globalübung. Bitte beachten Sie, dass wir keinerlei Garantie auf die Korrektheit der handschriftlichen Notizen geben. Diese können formale und inhaltliche Fehler enthalten. Bitte sehen Sie die handschriftlichen Notizen als Bonus an, Korrekturen oder sonstige Aufarbeitungen werden von uns nicht mehr vorgenommen.

Literatur

Buch Introduction to Algorithms.
Buch Algorithmen und Datenstrukturen.
Buch Data Structures and Algorithms - The Basic Toolbox.
Zur Klausurvorbereitung und zum Aufarbeiten der meisten Inhalte der Vorlesung empfehlen wir folgende Kapitel aus dem obig genannten Buch Introduction to Algorithms (second edition):
2.1, 2.2, (2.3)
3.1
6
7.1, 7.2, (7.3), 7.4
8.1, 8.3
9.2, 9.3
10.1, 10.2
11.1, 11.2, 11.3
12
15.5
16.4
17.2, 17.3
18.1
22
23
24.1, 24.2, 24.3
25.2
26.1, 26.2, 26.3
(C.1), (C.2)
(geklammerte Kapitelbezeichnungen) haben dabei weniger Gewicht als ungeklammerte Bezeichner.