Algorithmen und Datenstrukturen

Termine

Mi, Fr 10:00 - 11:30, Turing-HS

1. Vorlesung: Mi. 15.10.2008

Übungen

Siehe Übungen zu Algorithmen und Datenstrukturen.

Klausur

Die Klausur findet am Mittwoch 11.02.2009 von 10:00 bis 11:30 in den Hörsälen Turing und Zuse statt.

Jeder, der die Vorraussetzungen erfüllt ist automatisch zur Klausur angemeldet. Sollten Sie nicht teilnehmen wollen, so müssen Sie sich bis zum 08.02.2009 beim Dozenten abmelden!

Inhalt

ADS Plan 0809

1 Algorithmen und Programmierung

Algorithmusbegriff
Darstellung von Algorithmen
Beschreibung von Programmiersprachen
Java imperativ
Korrektheit und Test
Effizienz

2 Entwurf und Analyse von Algorithmen

Einfache Algorithmentypen
Schrittweise Verfeinerung
Divide & Conquer
Das Scanline Prinzip

3 Datenstrukturen und Datentypen

Überblick
Klassen und Objekte
ADT
Listen und ihre Implementierung
Interfaces
Parametrisierte Typen
Funktionen höherer Ordnung
Java für ADT
Java funktional

4 Programmierparadigmen

Funktional
Imperativ
OOP

5 Sortierverfahren

Elementare Sortierverfahren
Sortieren durch Mischen
Quicksort

6 Bäume, Suchbäume

Bäume
Suchbäume
AVL-Bäume
2-3-4 Bäume

7 Hashverfahren

Offene Hashtabellen
Kollisionsauflösung in der Tabelle

8 Suchen in Texten

Boyer-Moore
Reguläre Ausdrücke

9 Prioritätswarteschlangen

Heap
Heapsort

10 Systematisches Probieren

Backtracking
Branch & Bound
Greedy

Literatur

T.Cormen, C.Leiserson, R.Rivest: Introduction to Algorithms, MIT Press / McGraw Hill
H.-P. Gumm, M.Sommer: Einführung in die Informatik, Addison-Wesley
T.Ottmann, P.Widmayer : Algorithmen und Datenstrukturen, Spektrum Verlag 2002
M.A. Weiss, Data Structures and Algorithm Analyis, Pearson
J. Wolff v. Gudenberg : Algorithmen, Datenstrukturen, Funktionale Programmierung, eine praktische Einführung mit Caml Light, Addison-Wesley, Bonn, 1996

Werkzeuge

Caml
Caml Light
Java Development Kit: JDK-6
Die Entwicklungsumgebung Eclipse

Bei Fragen wenden Sie sich bitte an Gregor Fischer.