Datenstrukturen und Algorithmen
Data Structures and Algorithms

Die Veranstaltung stellt das Konzept der Abstrakten Datentypen vor, führt die wichtigsten Beispiele von Abstrakten Datentypen ein, und zeigt deren Anwendung/Handhabung im Rahmen der Behandlung von wichtigen grundlegenden Algorithmen.

Inhalte im Einzelnen:
- Algorithmenbegriff (Syntax, Semantik, Spezifikation)
- Algorithmenentwicklung (schrittweise Verfeinerung)
- Algorithmentheorie (Berechenbarkeit, Komplexität, Korrektheit)
- Wichtige Algorithmen (Suchen, Sortieren)
- Konzept der Abstrakten Datentypen (Spezifikation, Implementierung)
- Bedeutung von Vor- und Nachbedingungen
- Wichtige Abstrakte Datentypen (verkettete Listen, Keller, Schlangen, Mengen, Binärbäume, ausgewogene Bäume, B-Bäume, Hash-Tabellen, Graphen)
- Wichtige Klassen von Algorithmen (Divide-and-Conquer-Algorithmen, Such- und Sortieralgorithmen, Graphalgorithmen, Greedy-Algorithmen, Optimierungsalgorithmen)

Die Studierenden lernen den Algorithmenbegriff erläutern können und
Algorithmen durch schrittweise Verfeinerung entwickeln zu können. Sie sind in der Lage wichtige Komplexitätsklassen zu unterscheiden und damit die Komplexität eines Algorithmus abschätzen zu können. Die Studierenden beherrschen die die grundlegenden Datenstrukturen und können diese sinnvoll anwenden. Insbesondere sind ihnen die Unterschiede und die jeweiligen Vor- und Nachteile der Datenstrukturen bekannt und damit sind sie in der Lage die richtige Repräsentation für eine gegebene Umgebung auszuwählen und selbst zu implementieren.

- Robert Sedgewick: Algorithms, Addison Wesley, 1998
- Les Goldschlager, Andrew Lister: Computer Science - A Modern Introduction - Second Edition, Prentice Hall, 1987
- Bertrand Meyer: Object-Oriented Software Construction, Prentice Hall, 1997
- sowie andere Literatur zu diesem Thema gemäß Mitteilung in der Veranstaltung

This course teaches the concept of abstract data types. It introduces the fundamental abstract data types and
shows their use/handling within the scope of important classes of algorithms.

Contents in detail:
- Notion of an algorithm (syntax, semantics, specification)
- Development of algorithms (stepwise refinement)
- Theory of algorithms (computability, complexity, correctness)
- Important algorithms (searching, sorting)
- Concept of Abstract Data Types (specification, implementation)
- Significance of pre- and postconditions
- Important Abstract Data Types (linked lists, stacks, queues, sets, binary trees, balanced binary trees, B- trees, hash tables,graphs)
- Important classes of algorithms (divide and conquer, searching and sorting, graph algorithms, greedy, backtracking)

The students are able to explain the notion of algorithms have understood how to develop algorithms by stepwise refinement. They know important complexity classes and are able to estimate the complexity of an algorithm using these classes. The students are able to explain the concept of abstract data types and can enumerate and explain important abstract data types. They know the differences and the strengths and weaknesses of the different data types and therefore are able to choose and implement the most appropriate type in a given environment.

- Robert Sedgewick: Algorithms, Addison Wesley, 1998
- Les Goldschlager, Andrew Lister: Computer Science - A Modern Introduction - Second Edition, Prentice Hall, 1987
- Bertrand Meyer: Object-Oriented Software Construction, Prentice Hall, 1997
- sowie andere Literatur zu diesem Thema gemäß Mitteilung in der Veranstaltung