| Beschreibung: |
Das Modul beeinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:
- Ergebnisüberprüfung (Checkers) und Zertifizierung
- Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
- Grundbegriffe des Algorithm Engineering
- Effektive Umsetzung verketteter Listen
- Unbeschränkte Arrays, Stapel, und Warteschlangen
- Hashtabellen: mit Verkettung, linear probing, universelles Hashing
- Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
- Selektion: quickselect
- Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
- Sortierte Folgen / Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit
- Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)
- Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
Lernziele:
- kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, und die Korrektheits- und Effizienzanalyse,
- Implementierung, Dokumentierung und Anwendung,
- kann mit diesem Verständnis auch neue algorithmische Fragestellungen bearbeiten,
- wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,
- ist in der Lage, grundlegende Algorithmen zu analysieren und miteinander zu vergleichen,
- wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischen Herangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.
|
