Grundlagen: Algorithmen und Datenstrukturen
Fundamentals of Algorithms and Data Structures

Modul IN0007

Dieses Modul wird durch Fakultät für Informatik bereitgestellt.

Diese Modulbeschreibung enthält neben den eigentlichen Beschreibungen der Inhalte, Lernergebnisse, Lehr- und Lernmethoden und Prüfungsformen auch Verweise auf die aktuellen Lehrveranstaltungen und Termine für die Modulprüfung in den jeweiligen Abschnitten.

Basisdaten

IN0007 ist ein Semestermodul in Deutsch auf Bachelor-Niveau das im Sommersemester angeboten wird.

GesamtaufwandPräsenzveranstaltungenUmfang (ECTS)
180 h 75 h 6 CP

Inhalte, Lernergebnisse und Voraussetzungen

Inhalt

Das Modul behandelt zunächst die Grundlagen der Analyse von Effizienz bzw. Komplexität. Es werden grundlegende Begriffe, Komplexitätsmaße, die Landau-Symbole sowie verschiedene Maschinenmodelle eingeführt. Danach studiert das Modul grundlegende Datenstrukturen und algorithmische Probleme. - Datenstrukturen für Sequenzen: Untersucht werden dynamische Arrays, Listen, Stapel und Warteschlangen. Dabei wird jeweils die Komplexität der einzelnen Operationen hergeleitet. - Hashing: Im Kern werden Hashing mit Verkettung, universelles Hashing sowie verschiedenen Sondierverfahren vorgestellt. Das Modul behandelt optional perfektes Hashing und hash-basierte Algorithmen, zum Beispiel für das Problem des Mengendurchschnitts. - Sortieren: Das Modul wiederholt zunächst einfache Verfahren wie InsertionSort, SelectionSort und BubbleSort. Anschließend werden fortgeschrittene Verfahren wie MergeSort, HeapSort und QuickSort analysiert. Optional werden sortierbasierte Algorithmen, die untere Schranke für vergleichsbasiertes Sortieren, Rang-Selektion, RadixSort sowie externes Sortieren vorgestellt. - Prioritätswarteschlangen: Das Modul untersucht binäre Heaps und Binomialheaps. - Suchbäume: Das Modul behandelt binäre Suchbäume, AVL-Bäume und (a,b)-Bäume. - Graphalgorithmen: Das Modul studiert verschiedene Graphrepräsentation, Traversierungstechniken per DFS/BFS, die Berechnung von Zweifachzusammenhangskomponenten und starken Zusammenhangskomponenten, topologische Sortierung, die Berechnung von kürzesten Wegen und minimalen Spannbäumen. Optional werden Lösungsverfahren für das Traveling Salesman Problem (TSP) vorgestellt. Im Stoffspektrum des Moduls sind optional Datenkompressionverfahren (Huffman, Lempel-Ziv) und einfache Algorithmen für das Problem des Pattern Matchings vorgesehen.

Lernergebnisse

Die Teilnehmer beherrschen grundlegende Das Modul behandelt zunächst die Grundlagen der Analyse von Effizienz bzw. Komplexität. Es werden grundlegende Begriffe, Komplexitätsmaße, die Landau-Symbole sowie verschiedene Maschinenmodelle eingeführt. Danach studiert das Modul grundlegende Datenstrukturen und algorithmische Probleme. - Datenstrukturen für Sequenzen: Untersucht werden dynamische Arrays, Listen, Stapel und Warteschlangen. Dabei wird jeweils die Komplexität der einzelnen Operationen hergeleitet. - Hashing: Im Kern werden Hashing mit Verkettung, universelles Hashing sowie verschiedenen Sondierverfahren vorgestellt. Das Modul behandelt optional perfektes Hashing und hash-basierte Algorithmen, zum Beispiel für das Problem des Mengendurchschnitts. - Sortieren: Das Modul wiederholt zunächst einfache Verfahren wie InsertionSort, SelectionSort und BubbleSort. Anschließend werden fortgeschrittene Verfahren wie MergeSort, HeapSort und QuickSort analysiert. Optional werden sortierbasierte Algorithmen, die untere Schranke für vergleichsbasiertes Sortieren, Rang-Selektion, RadixSort sowie externes Sortieren vorgestellt. - Prioritätswarteschlangen: Das Modul untersucht binäre Heaps und Binomialheaps. - Suchbäume: Das Modul behandelt binäre Suchbäume, AVL-Bäume und (a,b)-Bäume. - Graphalgorithmen: Das Modul studiert verschiedene Graphrepräsentation, Traversierungstechniken per DFS/BFS, die Berechnung von Zweifachzusammenhangskomponenten und starken Zusammenhangskomponenten, topologische Sortierung, die Berechnung von kürzesten Wegen und minimalen Spannbäumen. Optional werden Lösungsverfahren für das Traveling Salesman Problem (TSP) vorgestellt. Im Stoffspektrum des Moduls sind optional Datenkompressionverfahren (Huffman, Lempel-Ziv) und einfache Algorithmen für das Problem des Pattern Matchings vorgesehen.

Voraussetzungen

IN0001 Einführung in die Informatik 1, IN0015 Diskrete Strukturen

Lehrveranstaltungen, Lern- und Lehrmethoden und Literaturhinweise

Lehrveranstaltungen und Termine

ArtSWSTitelDozent(en)Termine
VO 3 Grundlagen: Algorithmen und Datenstrukturen (IN0007) Dienstag, 14:00–16:00
Mittwoch, 13:15–14:15
UE 2 Tutorübungen zu Grundlagen: Algorithmen und Datenstrukturen (IN0007) Termine in Gruppen

Lern- und Lehrmethoden

Das Modul besteht aus einer Vorlesung und einer begleitenden Übungsveranstaltung. Die Inhalte der Vorlesung werden im Vortrag und durch Präsentation vermittelt. Studierende werden insbesondere durch die Lösung von Übungsblättern zur inhaltlichen Auseinandersetzung mit den Themen angeregt. Die Lösung der Übungsaufgaben wird in der Übungsveranstaltung besprochen. Zusätzlich erhalten die Studenten durch die Korrektur der Übungsblätter eine individuelle Rückmeldung über ihren Lernerfolg.

Medienformen

Folien, Tafelarbeit, Übungsblätter

Literatur

Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures - The Basic Toolbox. Springer, 2008. Vertiefendes und ergänzendes Material zur Vorlesung findet sich in folgenden Büchern: - Volker Heun: Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen. 2. Auflage, Vieweg, 2003. - Michael T. Goodrich, Roberto Tamassia. Algorithm Design - Foundations, Analysis, and Internet Examples. John Wiley & Sons, 2002. - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd edition, MIT Press, 2009. Deutsche Übersetzung: Algorithmen - Eine Einführung. 3. Auflage, Oldenbourg Verlag, 2010. - Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2005. - Uwe Schöning. Algorithmik. Spektrum Akademischer Verlag, 2001. - Robert Sedgewick, Kevin Wayne: Algorithms. 4th edition, Addison-Wesley, 2011. - Robert Sedgewick. Algorithms in Java, Parts 1-4. 3rd edition, Addison-Wesley, 2002. Deutsche Übersetzung: Algorithmen in Java, Teil 1-4. 3. Auflage, Pearson Education, 2003.

Modulprüfung

Beschreibung der Prüfungs- und Studienleistungen

Die Prüfungsleistung wird in Form einer Klausur erbracht. In dieser weisen Studierende anhand der gestellten Aufgaben nach, dass sie über fundamentale Kenntnisse im Bereich der Algorithmen und Datenstrukturen verfügen und diese erfolgreich bei der Lösung von Problemen anwenden können. Ferner demonstrieren Studierende beim Lösen der gestellten Aufgaben, dass sie die im Modul behandelten Datenstrukturen und grundlegenden algorithmischen Methoden beherrschen. Die Studierenden weisen nach, dass sie in begrenzter Zeit grundlegende algorithmische Probleme erkennen und analysieren können sowie Wege zu einer effizienten Lösung finden können.

Wiederholbarkeit

Eine Wiederholungsmöglichkeit wird am Semesterende angeboten.

Kondensierte Materie

Wenn Atome sich zusammen tun, wird es interessant: Grundlagenforschung an Festkörperelementen, Nanostrukturen und neuen Materialien mit überraschenden Eigenschaften treffen auf innovative Anwendungen.

Kern-, Teilchen-, Astrophysik

Ziel der Forschung ist das Verständnis unserer Welt auf subatomarem Niveau, von den Atomkernen im Zentrum der Atome bis hin zu den elementarsten Bausteinen unserer Welt.

Biophysik

Biologische Systeme, vom Protein bis hin zu lebenden Zellen und deren Verbänden, gehorchen physikalischen Prinzipien. Unser Forschungsbereich Biophysik ist deutschlandweit einer der größten Zusammenschlüsse in diesem Bereich.