Veranstaltungen
Lecture
Datenstrukturen und Algorithmen
- Name in diploma supplement
- Data Structures and Algorithms
- Organisational Unit
- Networks and Communication Systems
- Lecturers
- Prof. Dr.-Ing. Amr Rizk
- Cycle
- summer semester
- SPW
- 2
- Language
- German
- Participants at most
- no limit
- Participants
Preliminary knowledge
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.
Contents
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
Literature
- 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