Preliminary knowledgegrundlegende Kenntnisse in Programmierung AbstractAlgorithmen 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. ContentsIn 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- LA-Info-GyGe-Ba-2023 > Pflichtbereich Informatik > (2nd Semester, Compulsory) Modul "Datenstrukturen und Algorithmen"
- Mathe-Ba-2021 > Software Engineering > (1st-6th Semester, Compulsory) Modul "Datenstrukturen und Algorithmen"
- SE-Ba-2023 > Pflichtbereich > Pflichtbereich II: Programmierung und Entwicklung > (1st-2nd Semester, Compulsory) Modul "Datenstrukturen und Algorithmen"
- TechMathe-Ba-2021 > Pflichtbereich > (1st-6th Semester, Compulsory) Modul "Datenstrukturen und Algorithmen"
- WiInf-Ba-2023 > Kernstudium > Pflichtbereich II: Informatik > (1st-2nd Semester, Compulsory) Modul "Datenstrukturen und Algorithmen"
|