Algorithmen und Datenstrukturen 2

Lehrveranstaltung

Prüfungsordnung:  MI-BA-2011

Studienorganisation

Studiensemester:  2

Moduldauer:  2 Semester

Turnus:  Sommersemester, jährlich

Schwerpunkt:  Studienschwerpunkt Medien-Programmierung

Modultyp:  Pflichtveranstaltung

Lehrform:  Vorlesung/Labor

Sprache:  Deutsch

Kompetenzen/Lernziele 

Aufbauend auf der Kenntnis grundlegender Begriffe der Graphentheorie können Sie geeignete Sachverhalte mithilfe von Graphen modellieren. Sie kennen einige wichtige Sortieralgorithmen und Graphenalgorithmen. Sie kennen Entwurfsmethoden für Algorithmen und können diese anwenden. Sie sind in der Lage, die algorithmische Schwierigkeit von Problemen einzuschätzen. Sie können fortgeschrittene Algorithmen und Datenstrukturen objektorientiert programmieren.

Inhalte 

Vorlesung

  • Grundlagen
    • Graph: gerichtet/ungerichtet, Pfad, Weg, Kreis, Teilgraph, Zusammenhang, Baum
  • Algorithmen
    • Sortieralgorithmen: Quicksort, Mergesort, Heapsort
    • Graphenalgorithmen: Zusammenhangskomponenten, minimaler Spannbaum, kürzeste Wege
    • Entwurfsmethoden
    • Algorithmisch schwierige Probleme
    • Komplexitätsklassen P und NP
    • Approximationsverfahren
  • Datenstrukturen
    • Prioritätenliste
    • Verkettete Liste
    • Baum

Labor

In den begleitenden Übungen werden ausgewählte Algorithmen am Computer programmiert und hinsichtlich ihrer Laufzeiten verglichen.

Arbeitsaufwand

2 SWS, 2,5 Creditpoints (CP)

30 h Präsenzstudium, 45 h Eigenstudium

Prüfung

Art der Prüfung:  Prüfungsleistung

Prüfungsform:  K(2) oder SP(HA, Arb)

Literatur 

  • H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)
  • R. Sedgewick: Algorithmen in Java, Parts 1-4. 3. überarbeitete Auflage, Addison-Wesley (2003)
  • G. Saake und K.U. Sattler: Algorithmen und Datenstrukturen. 4. Auflage, dpunkt (2010)
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest und C. Stein: Algorithmen - Eine Einführung. 3. Auflage, Oldenbourg Verlag, (2010)

Voraussetzungen

Empfohlene Veranstaltungen 

Verantwortliche Dozenten

Modulverantwortliche(r):  Prof. Dr. rer. nat. Hans Werner Lang

Dozent(in):  Prof. Dr. rer. nat. Hans Werner Lang