© APSIS GmbH , Polling, 2001, 2002, 2003

Einleitung

Das Fach „Algorithmen und Datenstrukturen“ deckt „klassische Themen“ der Ausbildung von Informatikern ab. Es gibt viele Lehrbücher, die klassische Algorithmen (wie Sortierverfahren, usw.) und klassische Datenstrukturen (wie Reihungen, verkettete Listen, Bäume, usw.) mehr oder weniger verständlich vorstellen. Die meisten – insbesondere die besten – von ihnen wurden vor einiger Zeit geschrieben, deswegen verwenden sie typischerweise auch eine „klassische“ Programmiersprache (wie Algol, Pascal, C, o.ä.).

Java gehört dieser Reihe der Sprachen nicht an. Sie ist aber diejenige Programmiersprache, deren Wachstumsrate an Popularität wahrscheinlich alle andere übertrifft. Dies hat im wesentlichen zwei Gründe:

• die Plattformunabhängigkeit, die ihre Verwendung im Internet ermöglicht

• die Objektorientierung, die moderne Programmentwicklungstechniken und -paradigmen unterstützt.

Java wird sogar zunehmend als erste Unterrichtssprache verwendet, auch in den Informatikstudiengängen an der Tech­ni­schen Fachhochschule Berlin. So gibt es immer mehr Studenten, die noch keine andere Programmiersprache beherrschen. Um ihnen Algorithmen und Datenstrukturen unterrichten zu können, wurde dieses Lehrbuch entwickelt.

Es wendet sich an folgende Zielgruppen:

• Studenten von Informatikstudiengängen

• Schüler mit Leistungskurs Informatik

• Auszubildende in TI-Berufen mit Schwerpunkt Software

• Programmierer und

• Interessierte an anspruchsvollen Algorithmen

Es ist geeignet sowohl als Lehrmaterial für Vorlesungen und Kurse, wie auch fürs Selbst­studium.

Der Leser sollte möglichst die folgenden Voraussetzungen erfüllen:

• Erfahrung im Erstellen einfacherer Programme

• Kenntnisse der Programmiersprache Java

• insbesondere die Behandlung von Reihungen1 und Datenstrukturen, die durch Referenzen (Zeiger) miteinander verkettet sind

• nicht aber die Standardbibliotheken (nur rudimentär)

• und nicht die fortschrittlichen Mechanismen wie Polymorphie, Ausnahmebehandlung, abstrakte Klassen u.ä.

Zum Erlernen der Sprache Java wird zum Beispiel folgendes Lehrbuch empfohlen:

Solymosi, Schmiedecke: Programmieren mit Java
Vieweg Verlag 1999, ISBN 3-528-05697-5

Die meisten guten Bücher zum Thema Algorithmen und Datenstrukturen haben einen hohen akademischen Anspruch. Es gibt nur einige, die als Lehrbücher (z.B. als Begleitliteratur für Hochschulvorlesungen) geeignet sind. Die Mehrzahl von diesen ist jedoch für Universitätsstudiengänge entstanden. Für Fachhochschulen, wo dem theo­re­ti­schen Ansatz die Praxisrelevanz vorangestellt wird, sind sie oft zu anspruchsvoll. Die Informatikstudenten an Fachhochschulen sind weniger an mathematischen Beweisen als an verständlich formulierten Algorithmen interessiert.

Insbesondere wurde auf die Lesbarkeit der Programme in den meisten – hauptsächlich älteren – Lehrbüchern kein Gewicht gesetzt. In der Zwischenzeit wissen wir aber: Im allgemeinen ist das Lesen von Programmen deutlich schwerer als das Schreiben. Bei der Entwicklung der Beispielprogramme dieses Lehrbuchs wurde auf die Lesbarkeit Acht gegeben:

·         Wahl der Bezeichner

·         angemessene Kommentare

·         inhärente Strukturierung

·         konsequentes Druckbild (Einrückung, Klammerung, Schriftarten)

Hierdurch soll der Leser schneller den Sinn, den Ablauf und das Prinzip der Algorithmen erfassen können. Auch Studenten sollen sich daran gewöhnen, Programme mit hohem Lesbarkeitsgrad zu schreiben.

Beim Verfassen dieses Lehrbuchs wurden des weiteren folgende Ziele verfolgt.

1. Einige wichtige und bekannte Algorithmen (z.B. die Algorithmen Quicksort und Heapsort zum Sortieren von Reihungen, der Knuth-Morris-Pratt-Al­go­rith­mus zum Suchen einer Zeichenkette in einem Text, Baumdurchläufe, usw.) werden vorgestellt.

2. Der Leser soll dabei Erfahrungen sammeln, wie man Algorithmen schreiben und lesen und wie man den dynamischen Ablauf eines Algorithmus darstellen kann.

Einen Algorithmus kann man z.B. in natürlicher Sprache, in „Pseudocode“, als Ablaufdiagramm („Kästchen mit Pfeilen dazwischen“), als Nassi-Schnei­der­mann-Diagramm („geschachtelte Kästchen“), als Java-Programm, als Assembler-Programm usw. darstellen.

Einen Ablauf des Algorithmus kann man z.B. durch eine Folge von „Momentaufnahmen“ darstellen, oder durch spezielle Diagramme und Grafiken. Man kann einen solchen Ablauf auch an einer Tafel „mit Kreide und Schwamm“ oder auf einem Papier mit „Bleistift und Radiergummi“ vorführen. Zeichentrickfilme oder Computeranimationen sind auch sehr geeignet, ihre Herstellung ist aber meistens aufwändig.

3. Die Studenten von Lehrveranstaltungen dieses Fachs sollen auch üben, genau und verständlich über Algorithmen zu sprechen und zu schreiben. Sie sollen einige wichtige Fachbegriffe (z.B. Algorithmus, B-Baum, Halde, usw.) kennen lernen und in ihr aktives Vokabular aufnehmen. Insbesondere sollen sie sich auch mit der Komplexität von Algorithmen befassen und ein Verständnis für die Algorithmen-Klassen P und NP gewinnen.

4. Sie sollen theoretisch und praktisch etwas über das Verhältnis von (abstrakten) Algorithmen und (konkreter) Programmierung erfahren.

Vertrautheit mit abstrakten Algorithmen ist eine notwendige, aber keineswegs hinreichende, Voraus­setzung für „gute Programmierung im Alltag“.

Die in diesem Buch abgedruckten Beispielprogramme stehen im Internet unter der folgenden Adresse zur Verfügung:

http://www.tfh-berlin.de/~oo-plug/Ad

Fragen, Verbesserungsvorschläge und Kritik können an die folgende Adresse gesendet werden:

© APSIS GmbH , Polling, 2001, 2002, 2003