Datenstrukturen und Algorithmen

Die Vorlesung bietet eine Einführung in die Konstruktion von Datenstrukturen und Algorithmen. Ziele sind das Kennenlernen und Vergleichen alternativer Implementierungen für abstrakte Datentypen, die Analyse der Korrektheit und des Zeit- und Speicherbedarfs und das Kennenlernen und Anwenden von Entwurfsparadigmen für Algorithmen

Stoffplan

Lineare Datentypen

• ADT Liste
• ADT Stack
• ADT Queue

Bäume

• Definition und Eigenschaften
• ADT Tree
• Sequentielle Darstellung
• Verkette Darstellung

Anwendungen für Bäume

• Prioritätswartenschlangen und Heaps
• Suchbäume
• AVL-Bäume
• Rot-Schwarz-Bäume

Graphen

• Definition und Eigenschaften
• Implementation von Graphen
• Knotendurchlauf
• Topologisches Sortieren
• Minimale spannende Bäume
• Kurzeste Pfade in gerichteten Graphen

Datenstrukturen zur Darstellung von Mengen

• Implementation von Tabellen als lineare Listen
• Implementation von Tabellen mit Zugriff über Hashfunktion
• B+-Bäume

Sortierung von Mengen

• Elementare Sortierverfahren
• Effektive Sortierverfahren für Felder
• Optimales Sortieren
• Sortieren mit linearer Komplexität

Ãœbungsbetrieb

Die Übungen sind für keinen Studiengang verpflichtend und zählen nicht als Studienleistung. Die Studienleistung wird mit dem bestehen der Klausur erbracht. Der Übungsbetrieb ist eine Vorbereitung auf die Klausur und als solche ermöglicht er auch das Erlangen eines Klausurbonus. Dieser Bonus ist nur für die im anschließenden Wintersemester angebotene Klausur anrechenbar.

Die wöchentlich herausgegebenen Übungen sind in den Übungsgruppen oder in der Vorlesung abzugeben. Der Abgabezeitraum ist auf den Übungsblättern angegeben. Die korrigierten Übungen werden in den Übungsgruppen wieder zurückgegeben.

Klausur

(Bei Fragen bitte an mklein(at)welfenlab.de wenden.)

Klausurtermin Sommersemester: 22.08.2014 um 14 Uhr (90 Minuten) in VII 201.

Klausurtermin: 17.03.2014 um 14 Uhr (90 Minuten) in E415(Audimax, Nachnamen A-M), E214 (Großer Physikhörsaal, N-Z). Die genaue Raumaufteilung wird noch bekannt gegeben.

Allgemeine Hinweise: Bitte eigenes Papier / Stifte mitbringen. Jede Aufgabe sollte auf eine eigene Seite geschrieben werden (das hilft ungemein beim korrigieren). Es gibt insgesamt 7 Aufgaben. Der ungefähre Aufbau der Klausur ist wie die Probeklausur die im StudIP zu finden ist.

Erlaubte Hilfsmittel: Ein beidseitig beschriebens DinA4 Blatt (auch gern bedruckt). Keine Taschenrechner! 

Themen: Grundsätzlich sind alle Themen die in der Vorlesung und in der Übung behandelt wurden auch Klausurrelevant. Es gibt ein paar Ausnahmen:

• Dynamische Programmierung wird nicht abgefragt
• Das Einfügen / Löschen und die Rekonstruktion eines Rot-Schwarz Baumes wird nicht abgefragt, jedoch soll die Rot-Schwarz Eigenschaft bekannt sein.
• Persistente Datenstrukturen werden nicht abgefragt.
• Die Abstrakten Datentypen für Prioritätswarteschlangen, Bäume und Graphen werden, wenn sie abgefragt werden, gegeben. Das bedeutet aber nicht, dass man nicht wissen muss welche Operationen es bei den Datentypen gibt (wie. z.B. das Maximum / Minimum löschen beim der Prioritätswarteschlange). Man muss nur nicht die genauen Namen und Prä/Postkonditionen auswendig können.

Klausureinsicht: 26.03.2014 von 10-12 Uhr im F435 (Stahlbausaal). Um die Wartezeiten zu verkürzen sollten Studenten mit Nachnamen A-M von 10-11 Uhr zur Einsicht kommen, Studenten mit Nachnamen N-Z von 11-12 Uhr. Bei Problemen mit diesem Termin bitte unbedingt vorher bei mklein(at)welfenlab.de melden! 

Nachschreibklausur: Es gibt keinen zweiten Prüfungstermin im Wintersemester, auch wenn man sich dafür anmelden kann. Es gibt erst im Sommersemester 2014 eine Nachschreibeklausur