01661 - Datenstrukturen 1

Persönliches, subjektives Kursfazit

Entweder man müht sich zunächst mit Datenstrukturen 1 ab, oder mit 1613 (imperative Programmierung). Beide Kurse behandeln Datenstrukturen, was für den Studienanfänger bereits eine kleinere Hürde ist. Hat man einen der Kurse bestanden und verstanden, fällt einem der jeweils andere dann leichter. Zumindest die betreffenden Kapitel.

Viel gibt es über diesen Kurs nicht zu sagen. Er gehört definitiv nicht zu den Einfachen und ist unter anderem aufgrund der Themenfülle und strenger Klausurkorrektur nicht zu unterschätzen. Man sollte die wichtigen Algorithmen (Bubble-, Heap-, Insertion-, Radix-, Bucket-, Merge-, Quick-, Selection- und Shellsort) inklusive Laufzeitanalyse und O-Notation kennen, sowie eine gegebene Folge mit ihnen auf Papier sorieren können. Dazu die Grundlegenden Datenstrukturen wie B- und AVL-Bäume und Operationen auf ihnen (Insert, Delete, Overflow- und Underflowbehandlung, ...), Entwurf von eigenen Strukturen mittels Algebra und ADT, Hashfunktionen und Kollisionsstrategien, sowie jede Stufe von Dijkstra auf Papier bringen.

Mir hat das folgende Buch bei den Algorithmen, der O-Notation und der mathematischen Datentypspezifikation sehr geholfen.

Literaturempfehlung

Siehe Literaturempfehlung im Widget. Das Buch von Saake/Sattler ist zwar ein Schinken, aber es behandelt alle Themen im Kurs und ist in vielen Teilen deutlich umfangreicher. Wer die Themen also aus einem anderen Blickwinkel betrachten möchte, was durchaus hilfreich ist, kann getrost zugreifen.

Klausur- und Organisatorisches

Stand SS 2010: Klausur ist nicht einfach. Mit der (vielleicht temporären) Umstrukturierung musste man 60% der Klausurpunkte erreichen um zu bestehen. Dafür konnte man bis zu 22% an Klausur-Zusatzpunkten durch die Einsendeaufgabe sammeln (Punkte Einsendeaufgabe mod 20. Hat man also 99% in der Einsendeaufgabe erreicht, bekommt man trotzdem nur 4 Klausurpunkte. Schlimmstenfalls holt man in allen EA 99%, bekommt aber nur 77% der möglichen Klausur-Zusatzpunkte).

Das war auch einer der Kritikpunkte vieler Mitstudenten, die die EA nicht bearbeiten konnten. Dafür konnte man sich bei freundlichen Mitstundenten auf ihre 100% Einsendeaufgaben mit draufschreiben und sich so durch die EA "schummeln". Ob es am Ende was gebracht hat (man musste im besten Fall nur noch 38% in der Klausur holen), ist ungewiss. Der Lehstuhl wollte so anscheinend die Leute davon abhalten unvorbereitet zur Klausur zu erscheinen und die Bestehensquote zu erhöhen. Hat wohl geklappt - dieses Semester scheint nur knapp die Hälfte zur Klausur angetreten zu sein, was den Bestehens-Schnitt deutlich gehoben hat 😉

Aber so wie es ausschaut, wird - aufgrund der vielen Kritik - davon abgewichen und das alte "Einsendeaufgaben Pflicht zur Klausurzulassung"-System wieder eingeführt.

Zur Klausurvorbereitung empfehle ich natürlich die alten Klausuren, sowie alle Sortieralgorithmen und Dijkstra bis zum Erbrechen auf Papier zu üben. Vor allem Dijkstra ist (wenn er dran kommt) ein echter Punktebringer, bei dem man sich jedoch schnell vermalen kann. Wenn man das gut und schnell kann, ist man schonmal ein gutes Stück weiter. Gleiches gilt für die Algebra und die ADT: eine von beiden kam bis jetzt in jeder Klausur dran. Auch das Hashing sollte man mehrmals auf Papier geübt haben.

Kursinhalt

Kurseinheit 1

Analyse von Algorithmen, Spezifikation von Datentypen durch Algebren und ADTs. Datentypen in Java, Arrays, Klassen, etc. Dynamische Datenstrukturen, Zeiger, Konzepte.

Kurseinheit 2

Sequenzen, Modelle, frist, last, append, rappend, concat, etc. Doppelt und einfach verkettete Listen, sowie Operationen auf diesen. Stacks, Queues, Abbildungen, Binäre Bäume, Einbettung, Allgemeine Bäume und Implementierungen.

Kurseinheit 3

Mengen, geordnete und ungeordnete Listen, Bitvektoren, Dictionaries,geschlossenes und offenes Hashing, Analyse, Kollisionsstrategien (quadratisches und lineares Sondieren, etc.), Hashfunktionen (Divisionsmethode, Mittel-Quadrat-Methode, etc). Binäre Suchbeume, AVL Bäume und Operationen auf diesen, Priority-Queues, Partitionen von Mengen.

Kurseinheit 4

Sortierverfahren: DAC (Merge + Quicksort), Find and Insert (Heap- und Baumsortieren), Fächersortierung (Radix und Bucketsort), Schranken für Sortierverfahren, Laufzeitanalyse und Beweise. Speicherdarstellung von Graphen und Durchlauf.

Kurseinheit 5

Graph-Algorithmen mit Dijkstra, Implementierung mit Adjazenzmatrik und Priority-Queues. Externes Suchen in B-Bäumen, Over- und Underflowbehandlung.

Buchempfehlung