| | Informatik IISommersemester 2008
Typ : | Kursvorlesung | SWS : | 4 SWS Vorlesung + 2 SWS Übung | ECTS : | 8
| Veranstalter : | Prof. Dr. Thomas Ottmann | Betreuer : | Khaireel Mohamed
Christine Maindorfer
| AKTUELL : |
Die Klausureinsicht findet am 6.10.08, 14-16 Uhr, im Gebäude 051, Raum 03-26 statt.
| Vorlesung : | Montags: 14:00 - 16:00 Uhr (wöchentlich)
Donnerstags: 11:00 - 13:00 Uhr (wöchentlich)
Ort: HS 00-026 Geb. 101
| Sprache : | Deutsch
| Klausur : | Teilnahmevoraussetzungen:
- mind. 50% der sowohl theoretischen als auch der praktischen Übungen pro Übungsblatt bearbeitet
- Regelmäßige Teilnahme an den Tutoraten (es darf maximal 3 mal gefehlt werden)
| Voraussetzungen : | Vorausgesetzt werden Kenntnisse aus der Vorlesung Informatik I | Literatur : | Algorithmen und Datenstrukturen von Prof. Dr. Thomas Ottmann und Prof. Dr. Peter Widmayer erschienen in der 4. Auflage im Spektrum-Verlag. Zusätzliche Multimediamaterialen zu dem Buch und der Vorlesung finden sich hier.
|
|
|
|
LerninhaltIm Einzelnen wurden folgende Themen behandelt:
Formale Eigenschaften von Algorithmen, Korrektheit, Effizienz, Zeit- und Platzbedarf, Groß-O Notation, Omega-Notation; best, worst, average, amortized-worst-case Analyse von Algorithmen; Divide & Conquer u.a. Entwurfsverfahren; Elementare Datenstrukturen, Liste, Stapel, Schlange; Skiplisten als Beispiel einer randomisierten Struktur; Sortierverfahren: elementare, Heapsort, Quicksort, Radixsort; Suchverfahren: lineare, exponentielle Suche; Hashverfahren, insbesondere offene Hashverfahren; Bäume, natürliche Suchbäume, Durchlaufreihenfolgen; Balancierte Bäume, AVL-Bäume, B-Bäume; Union-Find-Strukturen u.a. Datenstrukturen;
Graphen.
LernzieleDas selbständige Entwickeln und Implementieren von Algorithmen, die Beherrschung der dazu erforderlichen Datenstrukturen und Entwurfsverfahren, und ein Verständnis für die Wechselwirkung zwischen beiden. Die Verbindung der Fähigkeit zur Formulierung von Verfahren mit Hilfe von abstrakten Datentypen, der Fähigkeiten zum Programmieren in höheren Sprachen, und die schrittweise Umsetzung der abstrakt formulierten Verfahren in lauffähige Programme. Die Fähigkeit, die Effizienz von Algorithmen, insbesondere ihren Zeit- und Platzbedarf mit mathematischen Methoden zu analysieren und so die Qualität von verschiedenen Algorithmen zur Lösung von Problemen beurteilen zu können.
|
