RUB » LMI » Lehre » Datenstrukturen SS 2020

Datenstrukturen SS 2020

LVR-Nr: 150 322
Veranstaltung: Datenstrukturen
4-std.
Di, 14-16 Uhr
Do, 14-16 Uhr
Dozent: Maike Buchin
Übungsgruppen: Gruppe 1: Di, 10-12 Uhr, Bernhard Kilgus
Gruppe 2: Di, 12-14 Uhr, Daniel Pasler
Gruppe 3: Di, 12-14 Uhr, Bernhard Kilgus
Gruppe 3: Di, 12-14 Uhr, Leonie Ryvkin
Gruppe 5: Di, 16-18 Uhr, Leonie Ryvkin
Korrekteure: Justin Brenne, Timo Glaser

Aktuelles

  • Die Vorlesung und der Übungsbetrieb beginnen am 20. April.
  • Alle weiteren Informationen entnehmen Sie bitte dem Moodle, welcher ab 1.4.20 zur Verfügung stehen wird.

Informationen

Kommentar aus dem Vorlesungsverzeichnis

Für Studierende der Mathematik mit Nebenfach Informatik ist diese Vorlesung ein obligatorischer Bestandteil des B.Sc.. Bei Wahl des Schwerpunkts Informatik ist sie im B.Sc. zu empfehlen, da andere Vorlesungen auf ihr aufbauen. Weiterhin ist die Vorlesung in den Studiengängen "Angewandte Informatik" und "IT-Sicherheit" vorgesehen.

Nach einer Besprechung grundlegender Datentypen (wie Listen, Stacks, Queues und Bäume) werden zunächst Datenstrukturen diskutiert, die zur Repräsentation von Mengen geeignet sind und dabei bestimmte Mengenoperationen unterstützen (wie zum Beispiel Dictionaries, Priority Queues und UNION-FIND-Datenstruktur). Weiterhin gehen wir auf Repräsentationen von Graphen ein, behandeln diverse Graphalgorithmen (wie zum Beispiel Tiefen- und Breitensuche, kürzeste Wege, transitive Hülle, starke Komponenten und minimaler Spannbaum) sowie diverse Sortierverfahren (Mergesort, Heapsort, Quicksort, Bucketsort, Radixsort). Die Vorlesung soll die Fähigkeit schulen, bekannte Datenstrukturen professionell einzusetzen, neue Datenstrukturen bei Bedarf selbst zu entwerfen, die Korrektheit eines Algorithmus sauber zu begründen und seine Laufzeit zu analysieren.

Voraussetzungen

Die Kenntnis einer höheren Programmiersprache ist hilfreich, aber nicht im engeren Sinne erforderlich.

Literatur

Die Vorlesung orientiert sich an hauptsächlich an folgender Quellen:
Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen - Die Grundwerkzeuge. Springer. Das Buch ist über den OPAC der RUB innerhalb des Campusnetzes kostenlos erhältlich!

Weitere Literaturhinweise werden in der Vorlesung gegeben.

Klausur

Die Abschlussprüfung wird in Form einer Semesterabschlussklausur erbracht. Dies gilt für alle Studierende. An der Klausur teilnehmen kann nur, wer sich fristgemäß bei dem für sich zuständigen Prüfungsamt anmeldet. Bei Fragen hierzu wenden Sie sich direkt an Ihr zuständiges Prüfungsamt.

Die 150 minütige Klausur ist geplant für Donnerstag, den 16. Juli 2020, ab 14 Uhr in HNC 10 und 30 - vorbehaltlich der weiteren Entwicklung der Einschränkungen aufgrund von Covid-19. Als Hilfsmittel sind 3 handgeschriebene oder 2 maschinell beschriebene DIN A4-Seiten erlaubt.

Teilnahmeschein

Eine unbenotete Bescheinigung über eine erfolgreiche Teilnahme erhält, wer mindestens die Hälfte der Hausaufgabenpunkte erreicht, in den Übungen mindestens einmal vorrechnet und regelmäßig an den Übungen teilnimmt.

Kontakt