Kommentare/ Inhalte:
Die
Entwicklung von Algorithmen zur Lšsung von Problemen mit dem Computer sind
zentraler Bestandteil der Informatik.
UnabhŠngig von einer spŠteren Ausrichtung in theoretischer, praktischer und anwendungsbezogener Informatik sind fundamentale Kenntnisse
in dem Prozess des Algorithmenentwurfs unabdingbar. Im Rahmen dieser
Veranstaltung werden Entwurfsprinzipien fŸr effiziente Algorithmen und Datenstrukturen
vermittelt. Dabei werden eine Reihe von grundlegenden Algorithmen und
Datenstrukturen vorgestellt, die zur Lšsung hŠufig auftretender Teilprobleme
komplexer Fragestellungen gewinnbringend eingesetzt werden kšnnen. Die
Veranstaltung gliedert sich wie folgt:
Rechnermodelle und
KomplexitŠtsma§e.
KomplexitŠtsanalyse von
iterativen und rekursiven Algorithmen.
Elementare Datenstrukturen:
Listen, Stapel, Schlangen, BŠume.
Algorithmen fŸr Suchen und
Sortieren.
Dynamische Datenstrukturen: Hashing, (balancierte) SuchbŠume.
Elementare Graphalgorithmen:
Durchlaufen von Graphen, kŸrzeste Wege.
Algorithmische Entwurfsmethoden
zur Lšsung schwieriger Probleme:
Dyn. Programmierung, Backtracking, Branch & Bound
Vorgehen:
Grundlagen und Faktenwissen im
Bereich Algorithmen und Datenstrukturen erwerben.
Sicherer Umgang mit
Entwurfsmethoden fŸr effiziente Algorithmen und Datenstrukturen
(Effizienzanalyse und Korrektheit) einŸben.
SelbststŠndiges kreatives
Entwickeln von Algorithmen und Datenstrukturen.
SelbststŠndiges Aneignen von
neuen Algorithmen, Datenstrukturen und Analysemethoden.
Literatur:
Die Vorlesung orientiert sich an dem
Lehrbuch von Cormen, Leiserson,
Rivest, Stein, welches sowohl in englischer als auch
deutscher Sprache verfŸgbar ist:
englisch: Introduction
to Algorithms, 2nd Edition, MIT Press 2001
deutsch: Algorithmen - Eine
EinfŸhrung, Oldenbourg Verlag, 2004
Das Buch ist sehr umfassend, in dieser Lehrveranstaltung werden nur AuszŸge daraus vermittelt.