Modulcode:	infEAlg-01a
Englische Bezeichnung:	Introduction to algorithms
Modulverantwortliche(r):	Priv.-Doz. Dr. Frank Huch
Turnus:	jedes Jahr im SS (SS22 SS23 SS24)
Präsenzzeiten:	3V 2PÜ
ECTS:	7
Workload:	45 Std. Vorlesung, 30 Std. Präsenzübung, 135 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-G (BSc Inf (21)) 2F-BSc-Inf (2F-BSc Inf (21)) BSc-WInf-G (BSc WInf (21)) VWL (Export) EcoQuantFin (Export)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-Math-A infEInf-01a

Kurzfassung:

Programmierung ist ein - wenn nicht der - zentrale Bestandteil der Informatik. Insofern muss ein an einer "grundlagen- und methodenorientierten Ausbildung" ausgerichteter Informatikstudiengang großen Wert darauf legen, die wichtigen Aspekte der Programmierung zu beleuchten. Einer dieser Aspekte umfasst den effizienten Umgang mit großen Daten. Grundlegende Kenntnisse darüber und in diesem Zusammenhang verwendete Methoden werden vermittelt.

Lernziele:

Die Studierenden

• kennen die unterschiedlichen Komplexitätsklassen nach Landau und können diese auch formal abgrenzen
• können Algorithmen analysieren und ihre Komplexität bestimmen
• können das Prinzip Teile-und-Herrsche anwenden um Probleme effizienter, möglichst mit logarithmisch Laufzeit oder einem logarithmischen Faktor zu lösen
• können dynamische Datenstrukturen mit Hilfe von Klassen und Objekten implementieren
• verstehen effiziente Datenstrukturen zum Speichern und späteren Abfragen großer Datenmengen und können sie implementieren bzw. erweitern
• verstehen amortisierte Laufzeiten und können sie analysieren
• können gelernte Datenstrukturen bezüglich ihres Einsatzes in Anwendungen vergleichen und beurteilen
• können Probleme mit Hilfe von Backtracking lösen
• haben das Prinzip der dynamischen Programmierung verstanden und können es Probleme anwenden, die den Beispielen des Moduls ähneln

Lehrinhalte:

• Laufzeitanalyse von Algorithmen, Best-, Worst- und Average-Case
• Landau-Notation
• unterschiedliche Sortierenverfahren und deren Vergleich
• untere Schranke für vergleichsbasierte Sortierverfahren
• Realisierung dynamischer Datenstrukturen mit Klassen und Objekten
• Suchbäume und AVL-Balancierung
• Prioritätslisten mittels Heaps
• Übersetzung Rekursion in Iteration + Keller
• dynamische Arrays, Hashmaps
• Graphen und einfache Graphalgorithmen
• Backtracking
• Kürzeste-Wege-Suche
• Abstrakte Datentypen
• Huffman-Codierung
• Dynamische Programmierung

Nach der anschaulichen Einführung einer Datenstruktur oder eines Algorithmus erfolgt eine schrittweise Realisierung als Python-Programm, welche häufig in den Übungen fortgesetzt wird. Darüber hinaus werden die Algorithmen bzgl. ihre Laufzeit experimentell verglichen und bzgl. ihres Laufzeitverhaltens analysiert.

Weitere Voraussetzungen:

Prüfungsleistung:

Klausur

Als Prüfungsvorleistung müssen 50% der Punkte in den Hausaufgaben erreicht werden.

Lehr- und Lernmethoden:

Tafelvorlesung, Beamerpräsentation mit Programmierung

Verwendbarkeit:

Literatur:

• Norbert Blum: Algorithmen und Datenstrukturen: eine anwendungsorientierte Einführung, Oldenbourg 2004.
• Donald E. Knuth: The Art of Computer Programming. Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley 1997. Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley 1998.
• Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen, Springer Vieweg 2017. Online-Version

Verweise:

Kommentar: