Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼

Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Algorithmen und Datenstrukturen

Professor Ulf Leser

Die Vorlesung behandelt klassische Themen aus den Bereichen Algorithmen und Datenstrukturen. Betrachtet werden z.B. die Komplexität von Algorithmen, Sortieren, Suche in Listen, Prioritätswarteschlangen, Suchbäume und grundlegende Graphalgorithmen. 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 Montag (Änderung), den 12.4.2021, statt.

Die Vorlesung wird durch eine Übung begleitet. Die Einschreibung in AGNES sowie die Kommunikation erfolgt ausschließlich über die Übungen; eine Einschreibung in die Vorlesung ist nicht möglich und nicht nötig.

Voraussetzungen

Voraussetzung für den Besuch sind gute Kenntnisse in Java (z.B. Modul Grundlagen der Programmierung), in theoretischer Informatik (z.B. Modul Einführung in die Theoretische Informatik) sowie gute Schulkenntnisse in Mathematik.

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 stehen noch nicht fest. Es steht auch noch nicht fest, ob die Klausur in Präsenz oder online geschrieben werden wird.

Anrechnung

Das Modul kann angerechnet werden für:

  • Monobachelor Informatik (typischerweise im zweiten Semester, 9 SP)
  • Monobachelor INFOMIT (typischerweise im zweiten Semester, 9 SP)
  • Monobachelor IMP (typischerweise im vierten 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 Folien werden hier jeweils nach der Vorlesung als PDF erhältlich sein. Slides are English, but the lecture will be held in German.

Die Vorlesung wird live über ZOOM gehalten und nicht aufgenommen. Wir werden aber zu fast allen Vorlesungen pre-recorded Videos bereitstellen. Diese wurden von Prof. Meyerhenke in 2020 aufgenommen (Danke). Die Inhalte sollten praktisch deckungsgleich zur aktuellen Vorlesung sein. Sollten Ihnen Unterschiede auffallen, bitte ich um Nachricht. Wir machen die Videos jeweils nach der betreffenden Vorlesung im Moodle Kurs verfügbar. Sie können nicht lokal gespeichert werden.

  • Einführung
  • Komplexität und O-Notation
  • (Abstrakte) Datentypen
  • MaxSubArray - ein Problem, viele Lösungen
  • Listen: Arrays und Linked Lists
  • Sortieren: Einfache Verfahren und untere Schranke
  • Merge Sort und Quick Sort
  • Radix Sort und Bucket Sort
  • Suchen und Selektieren
  • Selbst-Organisierende Listen
  • Amortisierte Analyse (von SOLs)
  • Priority Queues
  • (Overflow) Hashing
  • Open Hashing
  • Suchbäume
  • AVL-Bäume (Achtung: Wir machen AVL Bäume, das Video von Prof. Meyerhenke behandelt Rot-Schwarz-Bäume)
  • Graphen - Einführung
  • Kürzeste Pfade mit Dijkstra
  • All Pairs shortest Paths: Transitive Hülle und Floyd-Warshall
  • Minimal Spanning Trees
  • Strongly Connected Components und Kosaraju's algorithm

Interessante Links