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

Participants

• SE-Ba-2023 > Pflichtbereich > Pflichtbereich II: Programmierung und Entwicklung > (1st-2nd Semester, Compulsory) Modul "Datenstrukturen und Algorithmen"