Algorithmen und Datenstrukturen

Grundstudium
SS 2009
Vorlesung: Di, 14-16, Do, 12-14, Prof. Martin Hofmann
Übung: Di, 10-12, 12-14, Fr 10-12, 12-14, 14-16, 16-18, Andreas Abel, Roland Axelsson und Team
Schein: ja
SWS: 3 Vorlesung + 2 Übung
Klausur: 18.7.2009, 13-15, A140, A240, B201, M218 Hauptgebäude


Aktuelles

Organisatorisches

Die Vorlesung findet an den folgenden 21 Terminen statt: 21.04., 23.04., 28.04., 30.04., 05.05., 12.05., 14.05., 19.05, 26.05., 28.05., 04.06., 09.06., 16.06., 23.06., 25.06., 30.06., 02.07., 07.07., 09.07., 14.07., 16.07.

  Tag Zeit Ort Beginn Dozent
Vorlesung Di 14.15 - 15.45 B 138 (Theresienstr. 39) 21.04.09 Martin Hofmann
  Do 12.15 - 13.45 B 138 (Theresienstr. 39) 23.04.09 Martin Hofmann 
Übung Di 10.15 - 11.45 B 046 (Theresienstr. 39) 28.04.09 Paola Maneggia
  Di 12.15 - 13.45 B 039 (Theresienstr. 39) 28.04.09 Thomas Manhardt
  Fr 10.15 - 11.45 B 039 (Theresienstr. 39) 24.04.09 Andreas Abel/ Roland Axelsson
  Fr 12.15 - 13.45 B 039 (Theresienstr. 39) 24.04.09 Julien Oster
  Fr 14.15 - 15.45 B 039 (Theresienstr. 39) 24.04.09 Bastian Gebhardt
  Fr 16.15 - 17.45 B 039 (Theresienstr. 39) 24.04.09 Sarah Breining
Klausur 18.07. 13.00 - 15.00 A140, A240, B201, M218 (Hauptgebäude)    
Nachholklausur 08.10. 11.00 - 13.00 B101, B201, M218 (Hauptgebäude)    

Für Studierende der Informatik im Grundstudium
Vorkenntnisse Grundkenntnisse in Informatik
Schein gilt für Diplomvorprüfung im Haupt- oder Nebenfach Informatik und für den Bachelorstudiengang
Scheinerwerb Weiteres wird noch bekanntgegeben.

Nachholklausur

Die Modulprüfung findet in Form einer ersten Semestralklausur am Ende der Vorlesungszeit (am 18.07.2009) Semesters sowie einer Nachklausur am Ende des Semesters (am 08.10.2009) statt.

Prüfungsstoff

Alles, was in der Vorlesung und in den Übungen behandelt wurde, ist prüfungsrelevant. Das schließt Flüsse in Netzwerken mit ein.

Ablauf

Datum: Donnerstag, 8. Oktober 2009
Einlass: 10:40 Uhr bis 11:00 Uhr s.t., danach wird niemand mehr in die Prüfungsräume eingelassen.
Prüfungszeit: 11:00 Uhr s.t. bis  13:30 Uhr.
Gebäude: Hauptgebäude, Geschwister-Scholl-Platz 1, U-Bahn U3/U6 Haltestelle "Universität".
Raum: Verteilung über die Räume nach Anfangsbuchstaben des Familiennamens, wie er bei der Anmeldung angegeben ist:
A - L Hörsaal B 201 (2.OG)
M - Z Hörsaal B 101 (1.OG)
Hinweis: Listen mit den Hörsaalnummern hängen ab ca. 10:30 Uhr vor den Prüfungsräumen aus. Falls Sie das Gebäude nicht gut kennen, ist es ratsam, einige Tage vorher die genaue Lage Ihres Prüfungsraums zu erkunden. Wenn Sie erst unmittelbar vor der Klausur nach dem Raum suchen, ist die Gefahr groß, dass Sie sich verspäten und nicht mehr mitschreiben können.

Erforderliche Unterlagen

  1. gültiger Immatrikulationsnachweis für dieses Semester
  2. gültiger Personalausweis oder Pass mit Lichtbild
  3. Schreibzeug

Eigenes Papier ist nicht erforderlich und darf für die Prüfung nicht benutzt werden.

Die Klausur findet ohne Hilfsmittel statt. Insbesondere sind keine schriftlichen Unterlagen, keine Taschenrechner oder andere Rechner, keine Mobiltelefone oder andere Kommunikationsmittel erlaubt.

Wenn Sie am Tag der Klausur nicht auf Ihr Handy verzichten können, deponieren Sie es für die Dauer der Prüfung in einem der Schließfächer im Durchgang neben Hörsaal A 140 (1.OG) oder im Durchgang neben Hörsaal A 240 (2.OG). Für diese Schließfächer wird eine 2-Euro-Münze als Pfand benötigt. Auch Taschen lassen Sie besser im Schließfach, aber bitte nicht die Ausweise.

Inhalt

Die Vorlesung führt in grundlegende Algorithmen und Datenstrukturen ein, welche in fast allen Gebieten der Informatik und verwandten Disziplinen Anwendung finden. Wir lehnen uns eng an das Lehrbuch von Cormen et al. an, das in mehreren Präsenzexemplaren in der Bibliothek vorhanden ist.

Gliederung

  • Einführung
    • Sortieren durch Einfügen
    • Sortieren durch Mischen
    • O-Notation
    • Lösen asymptotischer Rekurrenzen
  • Sortier- und Suchverfahren
    • HeapSort
    • QuickSort
    • Sortieren in Linearzeit
    • Selektion
  • Datenstrukturen
    • Hashtabellen
    • Binäre Suchbäume
    • Disjunkte Mengen
  • Entwurfsprinzipien
    • Dynamische Programmierung
    • Greedy Algorithmen
    • Amortisierungs-Analyse
  • Graphalgorithmen
    • Minimale Spannbäume
    • Kürzeste Wege
    • Flüsse in Netzwerken

Literatur

siehe bitte hier


Valid HTML 4.01!
Andreas Abel
Last modified: Tue Aug 4 15:25:10 CEST 2009
Valid CSS!