Veranstaltungen
Vorlesung
Datenstrukturen und Algorithmen
- Name im Diploma Supplement
- Data Structures and Algorithms
- Anbieter
- Networks and Communication Systems
- Lehrperson
- Prof. Dr.-Ing. Amr Rizk
- Turnus
- Sommersemester
- SWS
- 2
- Sprache
- deutsch
- maximale Hörerschaft
- unbeschränkt
- Hörerschaft
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