Algorithmen und Datenstrukturen
Vorlesung, Sommersemester 2006
Aktuelle Hinweise
- Übersicht der Klausurbonuspunkte
Bitte prüfen Sie Ihre Bonuspunkte. Bei Unstimmigkeiten wenden Sie sich an Werner Sandmann. - Formelsammlung (aus den Klausuren im SS 2005 und WS 2005/06)
- Klausurtermin: 11. August (ohne Gewähr, nach <link verwaltung_organe verwaltung studium_lehre pruefungen aktuelles_aus_den_pruefungsaemtern pruefungsterminplan_bachelormasterdiplom intern>Terminplan des Prüfungsamtes)
- Übungsgruppeneinteilung
- Informationen zum Übungsbetrieb und zur Klausur.
Organisatorisches
- Termin: Montag, 14-16 Uhr, F135
- Dozent: Prof. Dr. Udo Krieger
Lesen Sie bitte unbedingt die Informationen zum Übungsbetrieb und zur Klausur.
Allgemeines
Einordnung
- Bachelor Angewandte Informatik: Informatik, Pflichtbereich 2. Fachsemester
- Bachelor Wirtschaftsinformatik: Informatik, Wahlpflichtbereich
- Diplom Wirtschaftsinformatik: Grundzüge der Informatik, Pflichtbereich
Voraussetzungen
Vorausgesetzt werden Kenntnisse der Vorlesungen "Einführung in die Informatik" (inklusive zugehöriges Java-Praktikum) von Prof. Wirtz, "Mathematik für Informatiker" (inklusive Rechnerübungen) von Prof. Mendler und der Wirtschaftsmathematik von Dr. Dobbener.
Beachten Sie auch die Vorlesung "Anwendungsorientierte Wahrscheinlichkeitsrechnung", deren Besuch parallel zu "Algorithmen und Datenstrukturen" wir dringend empfehlen!
Inhalt
Die Vorlesung führt in die grundlegenden Techniken des effizienten Algorithmenentwurfes und ihre Umsetzung durch Datenstrukturen ein. Ziel der Vorlesung ist die Vermittlung theoretischer Kenntnisse (Was zeichnet effiziente Verfahren aus? Welche Algorithmen und Datenstrukturen verbergen sich dahinter? Wie kann man den Aufwand in Komplexitätsmaße fassen? Wie wird ein Algorithmus analysiert?) und praktischer Fähigkeiten (Wie analysiert man ein Problem? Wie bildet man es auf effiziente Algorithmen und Datenstrukturen ab? Wie implementiert man den Algorithmus und die Datenstrukturen durch ein lauffähiges Programm? Java in den Übungen! Wie testet man den Code und seine Effizienz?)
Die Vorlesung beginnt mit den Grundlagen der Analyse von Algorithmen. Es werden mathematische Grundlagen behandelt wie Abschätzungen, exakte und abstrahierte Laufzeit, asymptotische Notationen, Abschätzungen für den schlechtesten Fall (worst case) und den Mittelwert (average case), Abschätzungen bei typischen Verfahren wie Rekursion, insbesondere das Mastertheorem. Zudem werden die grundlegenden Datenstrukturen Felder, Stacks, Queues, Listen und Skiplisten sowie Graphen und Bäume behandelt. Weitere Themen sind interne Sortierverfahren durch Vergleiche (Bubblesort, Mergesort, Quicksort, Heapsort), untere Schranken für interne Sortierverfahren, Sortieren in linearer Zeit, externes Sortieren, Selektieren, Verwaltung dynamischer Mengen mittels Hashverfahren und Suchbäumen, insbesondere höhenbalancierte Bäume (AVL-Bäume). Schließlich werden grundlegende Algorithmen auf Graphen behandelt, z.B. für kürzeste Wege (Dijkstra) oder minimale Spannbäume.
Vorlesungsfolien
werden hier vorlesungsbegleitend zur Verfügung gestellt.
Kapitel 1:
- Kapitel 1 - Teil 1 Einführung
- Kapitel 1 - Teil 2 Leistungsanalyse
- Kapitel 1 - Teil 3 Rekursionsgleichungen
Kapitel 2:
- Kapitel 2 - Teil 1 Grundlegende Datenstrukturen
- Kapitel 2 - Teil 2 Listen-Mengen
- Kapitel 2 - Teil 3 Skiplisten
Kapitel 3:
- Kapitel 3 - Teil 1 Einführung in Sortierverfahren
- Kapitel 3 - Teil 2 Einfache Sortierverfahren
- Kapitel 3 - Teil 3 Sortieren durch Mischen
- Kapitel 3 - Teil 4 Sortieren durch rekursives Teilen
- Kapitel 3 - Teil 5 Effizienz des Sortierens
- Kapitel 3 - Teil 6 Externe Sortierverfahren
- Kapitel 3 - Teil 7 Selektieren
Kapitel 4:
- Kapitel 4 - Teil 1 Hash-Verfahren: Grundlagen
- Kapitel 4 - Teil 2 Offene Hash-Verfahren
Kapitel 5:
- Kapitel 5 - Teil 1 Bäume: Grundlagen und Anwendungen
- Kapitel 5 - Teil 2 Binäre Bäume, Heapsort
- Kapitel 5 - Teil 3 Suchbäume
- Kapitel 5 - Teil 4 Höhenbalancierte Bäume
Kapitel 6: Entwurfsmethoden für Algorithmen
- Kapitel 6 - Teil 1 Entwurfsmethoden für Algorithmen, Implementierung von Algorithmen
- Kapitel 6 - Teil 2 Graphen und Graphalgorithmen
- Kapitel 6 - Teil 3 Kürzeste Wege und Transitive Hüllen
Vorlesungsfolien bilden nur ein Gerippe. Sie ersetzen nicht den Besuch der Vorlesung und das Lesen der Literatur und sind allein nicht ausreichend für ein gutes Verständnis des Stoffes und die Fähigkeit der Anwendung.
Literatur
Die Vorlesung orientiert sich teilweise an
- Christel Baier: Skript zur Vorlesung "Informatik IV - Algorithmen und Datenstrukturen", Universität Bonn, SS2004. [PDF]
Empfohlene Bücher
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition, 2001.
- Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics - A Foundation for Computer Science, Addison-Wesley, 2nd edition, 1994.
- Ralf Hartmut Güting, Stefan Dieker: Datenstrukturen und Algorithmen, Teubner, 3. Auflage, 2004.
- Cornelia Heinisch, Frank Müller, Joachim Goll: Java als erste Programmiersprache, Teubner, 4. Auflage, 2005.
- Jon Kleinberg, Eva Tardos: Algorithm Design, Addison-Wesley, 2005.
- Donald E. Knuth: The Art of Computer Programming, Volume I-III, Addison-Wesley, 1969-1973.
- Peter Pepper: Programmieren mit Java, Springer, 2004.
- Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen, dpunkt, 3. überarbeitete Auflage, 2006.
- Robert Sedgewick: Algorithmen in Java, Pearson Studium, 3. Auflage, 2003.