empfohlenes Vorwissen

grundlegende Kenntnisse in Programmierung

Abstract

Algorithmen sind das Herzstück jeder Computeranwendung. Daher sollte jeder Informatiker ein fundiertes Wissen besitzen über (i) Strukturen, die eine effiziente Organisation und Abfrage von Daten ermöglichen, (ii) häufig verwendete Algorithmen und (iii) grundlegende Techniken zum Modellieren, Verstehen und Lösen algorithmischer Probleme.

Lehrinhalte

In der Vorlesung werden die Grundlagen zu Algorithmen und Datenstrukturen betrachtet. Der Kurs behandelt folgende Themen:

• Einführung: Begriffe, Maße, Landau Notation, Maschinenmodell, Einfache Programmanalyse
• Datenstrukturen für Sequenzen (Arrays, Listen, Stapel, Warteschlangen)
• Abstrakte Datentypen
• Hashing (Verkettung, universelles Hashing, Sondierverfahren)
• Algorithmische Prinzipien
• Sortieren (InsertionSort, SelectionSort, BubbleSort, MergeSort, HeapSort und QuickSort)
• Prioritätswarteschlangen (binäre Heaps, Binomialheaps)
• Suchverfahren und Suchbäume (binäre Suchbäume, AVL-Bäume, (a,b)-Bäume)
• Graphalgorithmen (Graphrepräsentation, Traversierung per DFS/BFS, Zweifachzusammenhangskomponenten, starke Zusammenhangskomponenten, topologische Sortierung, kürzeste Wege, minimale Spannbäume, TSP)
• Grundlagen verteilter Algorithmen, Grundzuüge der Nebenläufigkeit
• Optional: Optimierungsalgorithmen und Pattern Matching

Literaturangaben

• K. Mehlhorn, P. Sanders, M. Dietzfelbinger: Algorithmen und Datenstrukturen. Springer Verlag Berlin; Juli 2010
• Th.H. Cormen et al.: Algorithmen – eine Einführung. Oldenbourg 2007

Hörerschaft

• LA-Info-GyGe-Ba-2023 > Pflichtbereich Informatik > (2. Fachsemester, Pflicht) Modul "Datenstrukturen und Algorithmen"
• Mathe-Ba-2021 > Software Engineering > (1.-6. Fachsemester, Pflicht) Modul "Datenstrukturen und Algorithmen"
• SE-Ba-2023 > Pflichtbereich > Pflichtbereich II: Programmierung und Entwicklung > (1.-2. Fachsemester, Pflicht) Modul "Datenstrukturen und Algorithmen"
• TechMathe-Ba-2021 > Pflichtbereich > (1.-6. Fachsemester, Pflicht) Modul "Datenstrukturen und Algorithmen"
• WiInf-Ba-2023 > Kernstudium > Pflichtbereich II: Informatik > (1.-2. Fachsemester, Pflicht) Modul "Datenstrukturen und Algorithmen"