Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Algorithm Engineering

Algorithmen und Datenstrukturen - Vorlesung

Sommersemester 2018
Professor Stefan Kratsch

Die Vorlesung behandelt klassische Themen aus den Bereichen Algorithmen und Datenstrukturen. Betrachtete Probleme sind z.B. Sortieren, Suchen in Strings, Listen, und Bäumen, Patternmatching und Wegesuchen in Graphen. Die verschiedenen Verfahren werden ausführlich dargestellt und in ihrer Komplexität analysiert. An ausgewählten Beispielen werden Korrektheitsbeweise durchgeführt. Durch die Vorlesung lernen Studierende grundlegende Algorithmen, effiziente Datenstrukturen und eine Reihe von Entwurfstechniken kennen und sind in der Lage, für ein gegebenes algorithmisches Problem verschiedene Lösungsansätze bzgl. ihrer Effizienz zu beurteilen und den am besten geeigneten Ansatz auszuwählen.

Die erste Vorlesung findet am Mittwoch, den 18.4.2018, statt.

Die Vorlesung wird durch eine Übung begleitet. Die Einschreibung in AGNES erfolgt ausschließlich über die Übungen.

Voraussetzungen

Voraussetzung für den Besuch sind gute Kenntnisse in Java.

Prüfungen und Klausureinsicht

Das Modul wird mit einer Klausur abgeschlossen. Voraussetzung zur Zulassung ist die Erreichung von mindestens 50% der Punkte in der Übung. Die Klausurtermine sind:

  • 30.7.2018 von 9:30 bis 12:00 (150 Minuten). Einlass 9:15.
  • 5.10.2018 von 9:30 bis 12:00 (150 Minuten). Einlass 9:15. (Nachklausur)

Ort der Klausur sind die beiden Räume 0'110 und 0'115 im ESZ.

Anrechnung

Das Modul (Vorlesung + Übung) kann angerechnet werden für

  • Monobachelor Informatik (typischerweise im zweiten Semester, 9 SP)
  • Monobachelor INFOMIT (typischerweise im zweiten Semester, 9 SP)
  • Kombibachelor Informatik, Kern- und Zweitfach (typischerweise im vierten Semester, 9 SP)

Literatur zur Vorlesung

  • Ottmann, Widmayer: Algorithmen und Datenstrukturen, Spektrum Verlag
  • Saake, Sattler: Algorithmen und Datenstrukturen (mit Java), dpunkt.Verlag
  • Sedgewick: Algorithmen in Java: Teil 1 - 4, Pearson Studium
  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press

Themen der Vorlesung

Die Vorlesung wird an der Tafel gehalten, folgt aber dem Inhalt der Folien aus dem letzten Jahr, welche hier verlinkt sind. Viele Inhalte der Folien folgen dem Buch von Ottmann und Widmayer, welches somit besonders gut zum Nach- oder Vorarbeiten geeignet ist.

Zusätzlich finden Sie im Moodle zur Vorlesung ein Pdf mit einem Überblick zu den Vorlesungsinhalten.

 

*: Organisatorisches aus dem Jahr 2017 ist natürlich nicht mehr zutreffend. Auch verwenden wir zum Einstieg leicht andere Beispiele, so dass die Folien hier eine komplementäre Einführung liefern.

Interessante Links