Algorithmen und Datenstrukturen
Die Vorlesung Algorithmen und Datenstrukturen findet jedes Sommersemester statt und schließt an die Einführung in die Informatik an.
Inhalt
Hier ist ein grober Überblick der Vorlesung:
- Listen
- Dynamisch wachsende Felder & verkettete Listen
- Stacks & Queues
- Iteratoren
- Bäume
- Rekursives & nicht-rekursives Durchlaufen
- Syntax-Bäume mit einem recursive descent parser erstellen
- Suchbäume und balancierte Bäume (AVL-, 2-3-4-, Rot-Schwarz- und B-Bäume)
- Binäre Heaps
- Hash-Verfahren
- Graphen & Datenstrukturen für Graphen
- Algorithmen auf Graphen
- Suche in Graphen & topologisches Sortieren
- Minimale Spannbäume
- Kürzeste Wege & A*-Algorithmus
- Maximaler Fluss / minimaler Schnitt
- Dynamische Programmierung
- Suche in Texten
Für diese Vorlesung setzen wir voraus, dass Du mit den Konzepten aus EinfInf vertraut bist. Das gilt insbesondere für das Verständnis von Rekursion und asymptotischen Aufwand. Außerdem erwarten wir, dass Du Java einigermaßen flüssig beherrscht.
Wir werden fast alle besprochenen Algorithmen und Datenstrukturen in beispielhaft in Java implementieren. Sowohl die Übungen als auch der Programmierwettbewerb erfordern Programmierkenntnisse in Java.
Team
Wir freuen uns regelmäßig über deutlich mehr als 200 Teilnehmer an der Vorlesung. Deshalb arbeitet ein großes Team aus (teilweise studentischen) Übungsleitern und Tutoren zusammen am Gelingen der Vorlesung. – Ich bin dafür sehr dankbar!
Ebenfalls vielen Dank an die Helferinnen und Helfer von Acagamics, die den Programmierwettbewerb organisieren!
| Vorlesung und verantwortlich | Christian Rössl |
| Organisation des Übungsbetriebs | Thomas Wilde, Christian Braune |
| weitere Übungsleiter | NN, siehe Vorlesungsseite |
| Tutoren | NN, siehe Vorlesungsseite |
Organisation
Die Veranstaltung gliedert sich in Vorlesung, Übung und Tutorium. Für Übungen und Tutorien ist eine Anmeldung nötig. Informationen dazu gibt es in der ersten Vorlesung.
Vorlesungsseite
Wir verwenden für die Vorlesung einen eigenen Dienst
der nur während der Vorlesungszeit und nur für das jeweilige Sommersemester zur Verfügung steht. Dort findest Du nach der Anmeldung alle Materialien zur Vorlesung, und dort kannst Du Deine Lösungen zu den Übungsaufgaben elektronisch einreichen.
Wenn Du das Verfahren zur Anmeldung noch nicht kennst, klären wir das in der ersten Vorlesung.
Aus Gründen des Datenschutzes löschen wir Vorlesungsdaten und insbesondere Zugangsdaten nach jedem Semester. – Deshalb ist für jedes Semester eine neue Anmeldung nötig. Der Zugang z.B. aus EinfInf funktioniert nicht mehr!
Wir veröffentlichen in der ersten Vorlesungswoche bereits das erste Übungsblatt, in dem wir einige Begriffe aus der Vorlesung Einführung in die Informatik wiederholen!
Programmierwettbewerb
Ebenfalls ein Teil der Veranstaltung ist der Programmierwettbewerb: Hier musst Du in einer größeren Code-Basis mit definierten Schnittstellen einen Algorithmus entwickeln und implementieren.
Damit es nicht zu langweilig ist, dreht sich der Wettbewerb um ein Computerspiel.
Traditionell wird der Wettbewerb von einem Acagamics-Team organisiert. Wir freuen uns immer wieder über die liebevoll gestalteten Spiele! Vielen Dank dafür!
Überblick
| Semesterwochenstunden | 3h Vorlesung + 2h Übung + freiwilliges Tutorium |
| Programmierwettbewerb | freies Arbeiten, Teilnahme verpflichtend |
| Voraussetzungen | EinfInf (empfohlen), Java Programmierung |
| empfohlenes Semester | 2 (oder 3 bei Studienbeginn im Sommer) |
| offizielle Termine und Angaben | bitte im LSF suchen (Es ist leider kein permanenter Link möglich.) |
Literatur
Jede ältere Auflage tut es genauso gut!
Anders als EinfInf wird sich die Vorlesung weit weniger am Buch von Saake&Sattler orientieren. Einige Dinge übernehme ich z.B. explizit von Goodrich&Tamassia.
Das ist eine gute Übung, sich an englischsprachige Literatur zu gewöhnen!