Algorithmen und Datenstrukturen (ADS)

Die Vorlesung vermittelt die grundlegenden Algorithmen insbesondere zum Suchen und Sortieren und deren zu Grunde gelegten Datenstrukturen, die innerhalb der heutigen Programmierung häufig eingesetzt werden. Die Lernenden sollen die vorgestellten Algorithmen kennen und insbesondere durch deren Aufwands- und Komplexitätsanalyse sensibel für die Entwicklung effizienter Programme werden.

Inhalt:

  • Programmiersprache: C++ und STL
  • Speichertechniken: sequentiell, gekettet, gestreut
  • Datentypen: Felder, lineare Listen (Stack, Queues, Priority Queues), sortierte lineare Listen und deren Speicherverwaltung, Bäume, Graphen
  • Methode der rekursiven Programmierung
  • Algorithmen zum Sortieren und deren Analyse:
    - interne Sortierverfahren:
    - elementare Verfahren, Shellsort, Quicksort, Heapsort u.a.
    - externe Sortierverfahren
  • Verfahren zum Suchen in großen Datenbeständen: Sequentielle Suche, binäre Suche, einfache binäre Suche, Hashing
  • Dynamische Datenstrukturen und deren Algorithmen: ausgeglichene, B- und B*-Bäume, Graphen (Darstellung, Traversierung und Anwendung (Dijkstra-Algorithmus))

Voraussetzungen:

  • Kenntnisse von GIP
  • C++

Prüfung:

  • Zulassungsvoraussetzung: erfolgreiche Teilnahme am Praktikum
  • Schriftliche Prüfung (180 Minuten)

Literatur:

  • Hilfsblätter und Übungsaufgaben
  • R. Sedgewick: Algorithmen in C++ - Teil 1-4, Addison Wesley, 2002
  • T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 2002.
  • M.A. Weiss: Data Structures and Algorithm Analysis in C++, Addison Wesley, 2005.
  • S.B. Lippman, J. Lajoie, B.Moo: C++ Primer, Addison Wesley, 2005.
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to algorithms, 2nd edition, MIT Press, 2001.

Literatur Algorithmen und Datenstrukturen

Algorithmen in C++. Teil 1-4
von Robert Sedgewick.
Addison-Wesley, Juli 2002.

Data Structures and Algorithm Analysis in C++
von Mark A. Weiss ,
Addison Wesley, 2005.
http://www.cs.fiu.edu/~weiss

Algorithmen und Datenstrukturen
von T. Ottmann und P. Widmayer,
Spektrum Akademischer Verlag, 2002.

Algorithmen und Datenstrukturen- Eine Einführung mit Java
von G. Saake, K.U. Sattler,
dpunkt.verlag, 2004.

Klassiker

Introduction to Algorithms
von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein,
MIT Press, September 2001. http://mitpress.mit.edu/algorithms/

Classic Data Structures in C++
von T.A. Budd,
Addison Wesley, 1994.

Data Structures and Algorithms
von A.V. Aho, J.E. Hopcroft, J.D. Ullman,
Addison Wesley, 1987.

Fundamental Algorithms – The art of computer programming
von Donald E. Knuth, Vol. 1-3.
Addison Wesley, 1997

C++ - Literatur

C++ Primer
von Stanley B. Lippman, Josee Lajoie, Barbara E. Moo,
Addison Wesley, 2005.

C++ Objektorientierte Programmierung
von Alexander Niemann, Stefan Heitsiek,
Deutsch, Vmi Buch, Februar 2005.

Object-oriented Programming in C++
von Robert Lafore,
Sams, Dezember 2001.

Die C++ Programmiersprache
von Bjarne Stroustrup,
Addison Wesley, 1998.