Algorithmen und Datenstrukturen

Dieses Modul besteht aus einer Lehrveranstaltung.

Prüfungsordnung:  MI-BA-2017

Studienorganisation

Studiensemester:  2

Turnus:  Sommersemester, jährlich

Modultyp:  Pflichtveranstaltung

Lehrform:  Vorlesung/Labor

Art der Präsenzveranstaltung:  Vorlesung/Labor

Sprache:  Deutsch

Kompetenzen/Lernziele 

Sie kennen die mathematischen Konzepte Menge, Relation, Abbildung, Folge und Graph und können damit arbeiten. Sie können Verfahren zur Lösung von Problemen algorithmisch formulieren, und Sie sind in der Lage, die Zeitkomplexität eines Algorithmus zu analysieren. Des weiteren kennen Sie grundlegende Datenstrukturen wie Stack, Queue und Prioritätenliste und können diese geeignet einsetzen. 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 sind in der Lage, die algorithmische Schwierigkeit von Problemen einzuschätzen. Sie können fortgeschrittene Algorithmen und Datenstrukturen objektorientiert programmieren.

Die Veranstaltung führt die notwendigen Techniken der Informatik zur Analyse von Problemstellungen sowie des Entwurfs komplexer Systeme ein, die in allen Veranstaltungen der Themenkomplexe Mobile Anwendungen, Interaktive Systeme und des Themenkomplexes Medienprogrammierung genutzt werden.

Inhalte 

Grundlagen

  • Menge, Relation, Abbildung, Folge
  • Graph: gerichtet/ungerichtet, Pfad, Weg, Kreis, Teilgraph, Zusammenhang, Baum

Algorithmen

  • Begriff Algorithmus, Algorithmen im täglichen Leben
  • Algorithmus zur Darstellung von Zahlen zur Basis b
  • Euklidischer Algorithmus zur Berechnung des größten gemeinsamen Teilers
  • Sortieralgorithmen: Insertionsort, Quicksort, Mergesort, Heapsort
  • Graphenalgorithmen: Zusammenhangskomponenten, minimaler Spannbaum, kürzeste Wege
  • Zeitkomplexität von Algorithmen
  • Entwurfsmethoden
  • Algorithmisch schwierige Probleme
  • Komplexitätsklassen P und NP
  • Heuristische Verfahren für algorithmisch schwierige Probleme

Datenstrukturen

  • Array
  • Stack
  • Queue
  • Prioritätenliste
  • Verkettete Liste
  • Baum

In den begleitenden Übungen werden zunächst in kleineren Gruppen die mathematischen Grundlagen geübt. Später werden ausgewählte Algorithmen am Computer programmiert und hinsichtlich ihrer Laufzeiten verglichen.

Arbeitsaufwand

4 SWS, 5,0 Creditpoints (CP)

60 h Präsenzstudium, 90 h Eigenstudium

Prüfung

Art der Prüfung:  Prüfungsleistung

Prüfungsform:  K(2)

Literatur 

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

Voraussetzungen

Voraussetzungen lt. Prüfungs- und Studienordnung 

keine

empfohlene Voraussetzungen 

  • Programmierkenntnisse aus dem ersten Semester

Verantwortliche Dozenten

Modulverantwortliche(r):  Prof. Dr. Jan Christiansen

Dozent(in):  Prof. Dr. Jan Christiansen