Das Modul "Grundlagen der Informatik 4: Algorithmen und Datenstrukturen" ist Pflicht für Studierende im Studiengang Web- und Medieninformatik. Die Wirtschaftsinformatiker dürfen es als Wahlpflicht-Modul belegen. Die W3L schlägt vor, es im vierten Semester nach GdI3 zu belegen. Nötig sind aber nur die Kenntnisse aus GdI2. Konkret sollte man gute Grundkenntnisse in objektorientierter Programmierung und in generischer Programmierung haben. Letzteres, weil die meisten Algorithmen im Kurs für generische Typen entwickelt werden. Wer sich auf diesen Kurs ein wenig vorbereiten will, sollte vor allem noch einmal das Kapitel zu generischer Programmierung aus GdI2 wiederholen.

Auf GdI4 hatte ich mich sehr gefreut, weil Kenntnisse im Bereich Algorithmen und Datenstrukturen zu meinem Bild von einem Informatiker gehören. Mathematik oder BWL sind Teil sehr vieler Studiengänge und viele Naturwissenschaftler und Ingenieure lernen programmieren. Aber Algorithmen sind für mich ein wesentlicher Teil dessen, was die Informatik als eigenständige Disziplin auszeichnet.

Ein bisschen hatte ich mich schon einmal mit dem Thema beschäftigt. Zu Schulzeiten hatte ich mal ein Buch über Algorithmen und Datenstrukturen, die damals noch in einer strukturierten Programmiersprache behandelt wurden. Hier ging es zum Beispiel um Sortieralgorithmen, Binärbäume und verkettete Listen. Als Schüler habe ich leider vieles nicht verstanden, obwohl ich das Thema sehr spannend fand. Nun wollte ich herausfinden, ob mir diese Konzepte inzwischen zugänglicher waren.

Schon im ersten Teil des Kurses gab es erste Überlegungen zur Korrektheit und Komplexität von Algorithmen. Überlegungen zur Komplexität bei wachsender Problemgröße ziehen sich durch den ganzen Kurs. Dies ist wichtig, um später für ein gegebenes Problem eine vorteilhafte Datenstruktur oder einen geeigneten Algorithmus auswählen zu können. Das zweite Kapitel handelte von Rekursion. Hier ging es darum, ein Verständnis dafür zu entwickeln, was beim rekursiven Methodenaufruf im Speicher passiert. Klassisches Fallbeispiel ist das Problem der Türme von Hanoi. Interessant war eine allgemeine Strategie, rekursive Algorithmen in iterative Algorithmen umzuwandeln. Oft ist der Algorithmus dann nicht mehr so übersichtlich und nachvollziehbar. Dafür verbessert sich die Laufzeit und der Speicherbedarf. Bis hier fand ich den Kurs noch recht trocken. Der Stoff war durchaus interessant aber nicht das, was ich erwartet hatte.

Das änderte sich im nächsten Kapitel, wo es um Suchalgorithmen ging. Im wesentlichen wurden hier die drei grundlegenden Strategien sequentielle Suche, binäre Suche und Hashing-basierte Suche behandelt. Der Kurs entwickelt die Codebeispiele in Java, weil das an der W3L die Lehrsprache ist. Aber ich habe rasch den Eindruck gewonnen, dass es in diesem Kurs eben nicht um Java sondern um ein Verständnis der Algorithmen und Datenstrukturen ging. Auch wenn immer wieder darauf verwiesen wird, was die Java-Klassenbibliothek schon fix und fertig anbietet. Denn natürlich wird man selten selbst die Algorithmen und Datenstrukturen aus dem Kurs implementieren. In der Regel wird man Bibliotheken benutzen, die sie zur Verfügung stellen. Sinn des Kurses ist eher, das man versteht, was man da benutzt und was das für Implikationen hat. Das macht sich auch ein wenig bei den Einsendeaufgaben bemerkbar. Ich hätte erwartet, hier vor allem Algorithmen implementieren zu müssen. Tatsächlich wurden viele Implementierungen im Lehrbuch schrittweise entwickelt. Oft ging es eher darum, diesen Code in kleinen Problemstellungen zu benutzen, ihn zu erweitern, zu ergänzen oder zu modifizieren.

Im nächsten Kapitel ging es um Sortierverfahren. Es zerfiel in zwei Teile. Im ersten Teil ging es um die sogenannten direkten Verfahren: - Sortieren durch direkte Auswahl

- Sortieren durch direktes Einfügen

- Sortieren durch direktes Austauschen

Diese Verfahren sind leicht zu verstehen aber sie sind langsam. Im zweiten Teil werden diese einfachen Verfahren schrittweise verbessert. Aus dem langsamen BubbleSort wird so z.B. der sprichwörtlich schnelle QuickSort-Algorithmus. HeapSort, QuickSort, ShellSort und MergeSort sind schon etwas schwieriger zu verstehen als die direkten Verfahren. Auch hier ist die Implementierung in Code das geringste Problem. Wichtiger ist, zu begreifen, wie auf der Datenstruktur (in der Regel ein Array) gearbeitet wird, wieviele Vergleiche und Tauschoperationen für große n anfallen, warum ein Verfahren terminiert und so weiter. Eine wichtige Frage ist auch immer wieder die sogenannte Stabilität eines Verfahrens. Hierbei geht es darum, ob sich die Reihenfolge von Elementen mit gleichem Schlüssel im Laufe des Sortierens ändern kann, oder ob sie "stabil" bleibt. Bei diesem Kapitel bedauerte ich nur, dass der BucketSort-Algorithmus nicht ausführlich vorgestellt wurde.

Im nächsten Kapitel ging es um Datenstrukturen. Hier wurden eigene Implementierungen von Feldlisten (ArrayList) und verketteten Listen, von Stapeln (Stack) und Schlangen (Queue), von Mengen (Set) und Abbildungen (Map) entwickelt. Hier wurden immer wieder Bezüge zu den Klassen hergestellt, die Java von Haus aus mitbringt. Es war für mich wirklich schön, zu begreifen, was ich bislang nur benutzt hatte, endlich zu verstehen, was "unter der Haube" passiert. Im Rest des Kapitels ging es um Bäume, um das Einfügen und Löschen in Bäumen und um ausgeglichene Bäume. Also darum, wie man Bäume reorganisieren kann, um zu verhindern, dass sie im schlimmsten Fall zur Liste entarten. Die verschiedenen Baumrotationen fand ich leider im Lehrbuch zu knapp erklärt, um sie nachvollziehen zu können. Zum Glück werden Algorithmen und Datenstrukturen in praktisch allen Informatik-Studiengängen gelehrt. Es war so kein Problem im Internet Skripte und Folien anderer Unis und FHs zu finden und da war dann schließlich auch eine Darstellung dabei, mit der auch ich gut zurechtkam.

Bis hier war ich mit dem Modul sehr zufrieden. Mit diesem Themen war dann wohl auch der Grundstock dessen abgehandelt, was zu einer einführenden Lehrveranstaltung "Algorithmen und Datenstrukturen" gehört. Von hier aus hätte es in verschiedene Richtungen weitergehen können. Die Autoren dieses Modul haben sich dafür entschieden, Algorithmen auf Texten zu behandeln. Konkret ging es um den KMP und den Boyer-Moore-Algorithmus. Dieses Kapitel ist mir sehr schwer gefallen. Ich war zunächst mit der Darstellung des Stoffes unzufrieden. Meine Suche nach alternativem Material, das verständlicher aufbereitet ist, blieb leider erfolglos. Möglicherweise haben die Autoren also ihr bestes getan und ich hatte hier einfach nicht den richtigen Dreh raus. Ich verstand die Algorithmen schon, aber nach ein bis zwei Tagen war alles wieder weg, während ich mich an den Rest des Stoffes gut erinnerte. Zum Glück kamen die Algorithmen auf Texten in der Präsenzklausur nicht dran.

Das letzte Kapitel handelte von kombinatorischen Algorithmen. Zunächst ging es um Backtracking. Damit kann man einige klassische Probleme lösen, zum Beispiel das Färben von Landkarten. Oder klassische Denksportaufgaben, die sich um das geschickte Positionieren von Springern oder Damen auf einem Schachbrett drehen. Schließlich wurde ein Constraint-Solver entwickelt. Dessen Funktionsweise konnte ich leider nicht in allen Details nachvollziehen, denn nun wurde es doch sehr komplex. Hier bewegt man sich schon in Richtung KI. Ich fand es irre spannend, dass dieses Thema im Kurs enthalten war, auch wenn es zum Glück nicht klausurrelevant war. Gerne hätte ich an dieser Stelle noch weiter gemacht, aber es passt eben nicht beliebig viel Stoff in ein Modul.

Mein Tutor hatte in diesem Modul einen einfach zu begreifenden Arbeitsrhythmus. Korrekturen kamen am Samstag, ganz gleich, wieviel man die Woche über eingereicht hatte. Ich konnte mein Arbeitsverhalten gut daran anpassen. Hilfestellung bei Problemen gab es schneller. Interessant für mich: Während in GdI1 noch sehr viel Wert auf einen sehr sauber strukturierten und expliziten Code gelegt wurde, ermutigte mich mein Tutor in GdI4, meinen Code kompakter zu schreiben, mehr Operationen in einer Zeile zusammen zu fassen. Meine Programme wurden so kürzer, waren aber auch nicht mehr ganz so leicht leserlich. Man erinnere sich: Dieser Kurs ist fürs 4. Semester vorgesehen. Da traut man den Studierenden schon einen dichteren Programmierstil zu.

Die Präsenzklausur lief für mich ziemlich gut. Anscheinend lag mir das Thema, denn ich konnte hier eines meiner besten Ergebnisse erzielen. In der Vorbereitung hatte ich mich auf die Grundkonzepte Suchalgorithmen, Sortierverfahren und Datenstrukturen konzentriert. Überraschend für mich: Java-Code musste ich nur wenig schreiben. Es wurde geprüft, ob man die Verfahren und Strukturen begriffen hatte, unabhängig von der Implementierung in einer bestimmten Programmiersprache. Ein Vorteil bei diesem Modul: Hier gibt es in der Regel ein eindeutiges "richtig" und "falsch", während es in anderen Modulen - nennen wir z.B. "Webdesign" - ein bisschen mehr Interpretationsspielräume gibt.

Was ich gerne noch gelernt hätte:

- Algorithmen zu Pfadsuche in Graphen

- etwas über genetische Algorithmen

- etwas über neuronale Netze

Am liebsten wäre mir, die W3L würde ein eigenes Modul "Künstliche Intelligenz" anbieten. Aber vielleicht passt das nicht zum Profil eines Studiengangs "Web- und Medieninformatik".

Im Kurs ist noch eine ganz knappe Einführung in die funktionale Sprache "Clojure" enthalten, letztlich ein Lisp-Dialekt auf der Java Virtual Machine. Auf dieses Kapitel war ich sehr neugierig, weil ich immer wieder höre, dass es sinnvoll ist, andere Programmierparadigmen kennen zu lernen. Nicht, um in exotischen Sprachen zu programmieren, sondern weil sich das Verständnis für Programmierung insgesamt entwickelt. Ich höre solche Aussagen einerseits mit einer gewissen Faszination und andererseits mit einer gewissen Skepsis. (Sie erinnern mich an die These, man müsse Latein lernen, weil man dann ... besser versteht/kann/lernt.) Jedenfalls wäre ich durchaus neugierig gewesen, eine lispoide Sprache zu lernen. Das Kapitel im Kurs GdI4 ist für diesen Zweck allerdings viel zu knapp. Ich verstehe also leider immer noch nicht, was genau den Reiz funktionaler Sprachen ausmacht. Gerne würde ich diesen Faden eines Tages wieder aufgreifen und zum Beispiel das legendäre "Structure and Interpretation of Computer Programs" von Abelson und Sussman durcharbeiten. Aber ich fürchte, während meines Fernstudiums werde ich die Zeit dazu nicht finden.