Grundlegende Algorithmen (WS 04/05)

Dozent:
Dr. Jens Ernst
Bereich:
3+2 SWS Vorlesung im Bachelorstudium Informatik (Pflichtvorlesung)
3+2 SWS Vorlesung im Aufbaustudium Informatik (Pflichtvorlesung)
3+2 SWS Vorlesung im Masterstudium Angewandte Informatik (Pflichtvorlesung)
3+2 SWS Vorlesung im Masterstudium Computational Science and Engineering (Pflichtvorlesung)
Zeit und Ort:
Do. 12:15 - 13:00, Hörsaal MI 00.06.011
Fr. 8:30 - 10:00, Hörsaal MI 00.04.011
Übung:
2 SWS Übung zur Vorlesung
Übungsleitung: Johannes Nowak
Hörerkreis:
Studierende im Bachelorstudium Informatik
Studierende im Aufbaustudium Informatik
Studierende im Masterstudium Angewandte Informatik
Studierende im Masterstudium Computational Science and Engineering
Voraussetzungen:
Elementare Grundkenntnisse in Informatik
Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen, Bioinformatik
Inhalt:
- Einführung
  Einführendes Beispiel: Fibonacci-Zahlen
  Das Modell der Registermaschine (RAM)
  Zeit- und Platzkomplexität
  Landau-Symbole
- Sortieralgorithmen
  Selection Sort
  Insertion Sort
  Merge Sort
  Heap Sort
  Quick Sort
  Untere Schranken für Sortieren
- Suchen
  Lineare, binäre, exponentielle Suche
  Binäre Suchbäume
  AVL-Bäume
  (a,b)-Bäume
- Graphalgorithmen
  Begriffe der Graphentheorie
  Speicherung von Graphen
  Traversieren von Graphen
  Kürzeste-Wege-Algorithmen
- Textalgorithmen
  Suchen in Texten
  Vergleichen von Texten bzw. Sequence Alignment
  Weiterhin geplant:
- Algorithmen zur Datenkompression
  Huffman-Encoding, Lempel-Ziv-Algorithmus, Kompression von Bilddaten
Änderungen an dieser Planung werden noch bekanntgegeben.
Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen
Klausurtermine und Ergebnismitteilungen:

Midterm/Mittelklausur: Freitag, 10.12.2004, 16:00, MW 2001
Einsichtnahme: Mittwoch, 22.12.2004, 13:00, 03.09.011b
Final/Endklausur: Mittwoch, 16.02.2005, 14:00, MI HS1
Einsichtnahme: Dienstag, 01.03.2005, 09:00-10:00, 03.09.011b
Wiederholungsklausur: Mittwoch, 13.04.05, 12:00, Hörsaal 0250 (Maschinenwesen)

Hilfsmittel: Ein eigenhändig handbeschriebenes Din A4-Blatt (Vorder- und Rückseite) mit beliebigem Inhalt.
Ansonsten keine Hilfsmittel.

Wichtig: Diese Ankündigung ist vorläufig. Es können sich noch Terminänderungen ergeben.
Bitte achten Sie auf aktuelle Ankündigungen an dieser Stelle!
Gesprächstermine für Vorlesungsteilnehmer
Für diese Veranstaltung wird allen Teilnehmern die Gelegenheit zu einem Einzelgespräch mit dem Dozenten oder der Übungsleitung gegeben. Dies erfolgt auf absolut freiwilliger Basis. Hierbei können Themen wie der aktuelle Punktestand bei den Hausaufgaben (->Klausurzulassung), Verständnisprobleme bzgl. Vorlesung/Übung besprochen und Feedback zu den Lehrveranstaltungen gegeben werden. Es werden zwei Termine angeboten, zu denen keine Voranmeldung nötig ist. Bitte haben Sie Verständnis, falls es zu Wartezeiten kommt.
Erster Termin: Montag, 17.01.05 (09:00 bis 11:00, 12:00 bis 15:00), Raum 03.13.060)
Zweiter Termin: Montag, 31.01.05 (09:00 bis 10:00, Raum 03.13.060)
Skript:
Kein Skript.

1. Vorlesung (pdf)
RAM-Beispielprogramm (3.Vorlesung, pdf)
Vorlesung 23.12.04 (pdf) (Die Qualität des Dokuments bitte ich zu entschuldigen.)
Theoretical Computer Science Cheat Sheet (von Steve Seiden, ACM Press, NY, pdf)

Literatur:
Die Vorlesung folgt in weiten Teilen dem Buch:
- Volker Heun.
  Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen.
  Vieweg, Braunschweig-Wiesbaden, 2003.
Vertiefendes und ergänzendes Material zur Vorlesung findet sich in:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
  Introduction to Algorithms.
  2. Auflage, MIT Press, Cambridge, MA, 2001.
- Uwe Schöning.
  Algorithmik.
  Spektrum Akademischer Verlag, Heidelberg, 2001.
- Robert Sedgewick.
  Algorithmen.
  2. Auflage, Pearson Education, München, 2002.
Sprechstunde:
nach Vereinbarung

Letzte Änderung: Jens Ernst am 24.06.2004