Einleitung

IT-Technologien bestimmen immer weitere Bereiche unseres Lebens. Die Entwicklung schreitet immer schneller voran. Was gestern aktuell war, ist heute oft schon völlig veraltet. Gibt es da nichts von Substanz und Dauer? Was dem Außenstehenden als amorphe Lawine von immer neuen Tricks und technischem Schnickschnack vorkommt, hat aber tatsächlich schon einen soliden wissenschaftlichen Kern: die Informatik.

Algorithmen und Datenstrukturen sind das Herz der Informatik, der ewig junge Klassiker mit seinen unvergänglichen Wahrheiten und Strategien. Sie helfen immer wieder, aus einer Geschäftsidee ein funktionierendes Produkt zu machen. Hier gibt es nichts, das in ein paar Jahren schon veraltet oder irrelevant ist. Hier können Sie Wissen, Können und Kreativität kombinieren und die Basis für eine erfolgreiche IT-Karriere legen, eine Karriere, die oft genug und nicht ohne Grund mit einem Vorstellungsgespräch beginnt, das Algorithmen und Datenstrukturen zum Thema hat.

Algorithmen und Datenstrukturen sind nicht nur nützlich. Je länger Sie sich mit ihnen beschäftigen, umso mehr können Sie entdecken und umso mehr Spaß haben Sie mit ihnen. Egal ob spezialisierter Wissenschaftler, mit beiden Beinen in der Praxis stehender Software-Entwickler oder Hobby-Programmierer, jeder kann hier eine spannende Ecke finden und dort Algorithmen und Datenstrukturen auf seine Art kultivieren. Was will man mehr. Das Nützliche ist auch noch schön.

Schönheit ist allerdings manchmal etwas spröde und nicht immer sieht man sie auf den ersten Blick. Das gilt auch für Algorithmen und Datenstrukturen. Sie haben ihre spezielle Notation, den Pseudocode, ihre spezielle Sprache und Terminologie, die man kennen und akzeptieren muss.

Der Einstieg gleicht oft einem Sprung in sehr tiefes Wasser. Zur Vorbereitung könnten Sie Schwimmübungen an Land machen. Das ist nicht das Ziel in diesem Buch. Es soll schon ins Wasser gehen, abstrakte Themen und spröder Pseudocode werden nicht vermieden. Im Gegenteil, wir machen auf Dinge aufmerksam und diskutieren ausführlich Themen, die in der akademischen Literatur gerne mal ganz knapp abgehandelt werden und welche die explizite Einsteigerliteratur eher vermeidet. Sie werden sehen, so spröde ist das alles gar nicht.

Über dieses Buch

Fünf plus drei ergibt acht. Das nennt man Rechnen. Es ist sehr allgemein: Fünf plus drei Sofas, Elefanten, Kaninchen ergibt acht Sofas, Elefanten, Kaninchen. Das macht das Rechnen so nützlich. Viele Aufgaben können in Rechenaufgaben umgewandelt werden und als Rechenaufgaben gelöst werden. Man modelliert das Problem in Form von Zahlen und löst es dann in der Zahlenwelt. Das ist so weit verbreitet und allgemein üblich, dass eine stilisierte Kurznotation für solche Aufgaben entwickelt wurde und schon in der Grundschule gelehrt wird: .

Das gleiche Prinzip des Modellierens des Realen in abstrakten Datenwelten, um es dort mit bewertbaren Verfahren lösen zu können, ist das Grundthema von Algorithmen und Datenstrukturen. Es gibt eine Flut von Erkenntnissen, die in einer beeindruckenden akademischen Tradition aufbereitet wurden und dargelegt werden. Nichts davon ist veraltet, aber wir wollen es gelegentlich mal von einem anderen Blickwinkel aus betrachten und laden Sie ein, uns bei diesem Wechsel der Perspektive zu begleiten.

Informatik war einmal ein recht esoterisches Gebiet. Wer sich vor etlichen Jahren akademisch mit Algorithmen und Datenstrukturen beschäftigte, hatte in der Regel einen soliden mathematischen Hintergrund und war gewohnt, Dinge in der Sprache der Mathematik zu modellieren. Kompetenzen in der Software-Entwicklung waren dagegen weniger weit verbreitet. Einfache Programme, in denen die Daten in Arrays hin- und hergeschoben wurden, das war das Übliche.

Heute ist die Situation eher umgekehrt. Statt mathematischer gehören heute eher softwaretechnische Abstraktionen, wie die Objektorientierung, zum weitverbreiteten Wissens- und Kenntnisstand. Die Programmiersprachen haben sich weiterentwickelt und erlauben es, Programme in einer Notation zu schreiben, die vor Jahren als reiner Pseudocode angesehen worden wäre. Konzepte der funktionalen Programmierung sind von fortgeschrittenen Spezialveranstaltungen ins Grundstudium gewandert.

Mit diesem Buch wollen wir Ihnen eine Tür zu der klassischen Thematik der Algorithmen und Datenstrukturen öffnen. Dinge, die nicht so selbstverständlich sind, wie manche Spezialisten denken, werden ausführlich behandelt: Was ist und warum verwendet man Pseudocode, was ist der Unterschied zwischen einem Datenmodell und einer Datenstruktur und so weiter.

Persistente Datenstrukturen und die Beschreibung von Datenstrukturen als algebraische Datentypen sind nicht wirklich neu, aber heute sind sie keine Spezialthemen mehr und möglicherweise sind sie Ihnen, lieber Leser, auch schon begegnet. Glücklicherweise steckt ein einfaches und klares Konzept dahinter und Sie werden hier sehen, dass es sich gut zur Beschreibung von Datenstrukturen einsetzen lässt.

Und dann sind da noch die Kaninchen, Bauarbeiter, Vampire und so weiter. Speziell die kleinen Hobbler haben unser Verständnis der Algorithmen und Datenstrukturen ganz wesentlich gefördert und geprägt. Wir möchten sie Ihnen nicht vorenthalten.

Selbstverständlich wurden alle Bestimmungen des Tierschutzgesetzes beachtet. Bei der Arbeit an diesem Buch ist kein Tier zu Schaden gekommen und alle Mitwirkenden haben ihren Beitrag freiwillig und in artgerechter Weise geleistet.

Törichte Annahmen über den Leser

Wir nehmen an, dass Sie, lieber Leser, jemand sind, der sich für Algorithmen und Datenstrukturen interessiert und tiefer in diese Materie eindringen möchte. Die Behandlung der Thematik in der gängigen Spezialliteratur ist Ihnen aber gelegentlich zu akademisch, zu trocken und zu weit entfernt von ihren sonstigen Erfahrungen.

Sie haben erste Erfahrungen in der Software-Entwicklung und brauchen keine weitere Einführung in die Programmierung oder jemanden, der Ihnen eine bestimmte Programmiersprache als das Maß aller Dinge erklärt. Sie möchten sich die akademische Behandlung von Algorithmen und Datenstrukturen erschließen und suchen einen Einstieg in diese spannende Materie, der Ihre Erfahrungen respektiert und sie mit der akademischen Behandlung des Stoffs verbindet.

Vielleicht haben Sie auch als Studierende das Fach Algorithmen und Datenstrukturen belegt. Die Klausur rückt näher, der Stoff ist widerspenstig. Die üblichen Erklärungen scheinen sich in erster Linie an die bereits Eingeweihten zu richten. Sie suchen nach einem Zugang zu diesem schwierigen Thema, der wirklich von außen nach innen führt.

Wie dieses Buch aufgebaut ist

Algorithmen und Datenstrukturen für Dummies ist in vier Teile gegliedert und jeder Teil hat seinen Schwerpunkt. Es ist nicht notwendig, das Buch systematisch von vorne nach hinten durchzulesen. Wir ermuntern dazu, nach der Lektüre von Teil I eigene Schwerpunkte zu setzen und auch mal hin- und herzuspringen. Wie bei allen etwas komplexeren Wissensgebieten muss man auch hier die einzelnen Puzzleteile mal von dieser mal von jener Seite betrachten, bis dann schließlich alles an seinen Platz fällt und das große Ganze sichtbar wird.

Der Stoff kann und wird üblicherweise insgesamt entweder nach Problembereichen (Sortieren, Traversieren etc.) oder nach algorithmischen Techniken (Teilen und Herrschen, Gier etc.) gegliedert. Zwischen beiden Themenbereichen gibt es viele Querbezüge, sodass sich das Gesamtbild erst nach und nach erschließen lässt. Wir lösen dies, indem wir die Thematik in Teil III von der problemorientierten Seite und in Teil IV von der Seite der algorithmischen Techniken her betrachten. In Teil I werden dazu die Grundlagen gelegt. Teil II vertieft und erweitert diese Grundlagen mit den ersten Beispielen.

Neben den beiden üblichen Themenbereichen algorithmische Techniken und Problemstellungen haben wir zwei weitere Querschnittthemen: Datenmodell und Datenstruktur und imperative und funktionale Algorithmen, die sich durch viele Kapitel ziehen. Sie werden in der Literatur meist knapper behandelt, als es ihrer Bedeutung entspricht.

Teil I Grundbegriffe

In Teil I geht es um die Grundlagen: Algorithmen und Datenstrukturen. Was ist das und wie beschreibt und bewertet man es? Was ist ein Algorithmus, wie beschreibt man ihn in Pseudocode und wie wird seine Effizienz bewertet? Was ist eine Datenstruktur, welche Arten gibt es und wie beschreibt man sie?

Teil II Algorithmen in den Gärten der Strukturen

In diesem Teil geht es um das Zusammenspiel von Datenmodellen, Datenstrukturen und Algorithmen. Listen, Bäume und Graphen sind Datenmodelle. Sie liefern ihre jeweils spezifischen Problemstellungen, die mit Algorithmen und Datenstrukturen gelöst werden. Datenstrukturen und Algorithmen arbeiten dabei Hand in Hand.

Teil III Probleme und ihre Lösungen

Hier nehmen wir einen problemorientierten Standpunkt ein. Es beginnt mit Sortieren und dem Packen eines Rucksacks. Hier werden schon algorithmische Techniken angesprochen. Dann geht es um die Speicherung von Mengen. Datenabstraktionen als Hülle um Algorithmen und ihre Datenstrukturen werden...