Home | english  | Impressum | Sitemap | KIT

Algorithmen I

Algorithmen I
Typ:
Semester: SS 2017
Zeit: 24.04.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)


26.04.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

03.05.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

08.05.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

10.05.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

15.05.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

17.05.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

22.05.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

24.05.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

29.05.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

31.05.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

07.06.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

12.06.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

14.06.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

19.06.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

21.06.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

26.06.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

28.06.2017
14:00 - 15:30 täglich
50.35 Fasanengarten-Hörsaal (HS a.F.) 50.35 Fasanengarten-Hörsaalgebäude

03.07.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

05.07.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

10.07.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

12.07.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

17.07.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

19.07.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

24.07.2017
15:45 - 17:15 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)

26.07.2017
14:00 - 15:30 wöchentlich
30.95 Forum Hörsaal (Audimax) 30.95 Hörsaal-Gebäude am Forum (AUDIMAX)


Dozent: Björn Kaidel
Prof.Dr. Jörn Müller-Quade
SWS: 4
LVNr.: 24500
BeschreibungDas Modul beinhaltet 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)
LiteraturhinweiseAlgorithms and Data Structures - The Basic Toolbox
K. Mehlhorn und P. Sanders
Springer 2008

Weiterführende Literatur

Algorithmen - Eine Einführung
T. H. Cormen, C. E. Leiserson, R. L. Rivest, und C. Stein
Oldenbourg, 2007

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

Algorithmen in Java. Teil 1-4: Grundlagen, Datenstrukturen, Sortieren, Suchen
R. Sedgewick
Pearson Studium 2003

Algorithm Design
J. Kleinberg and É. Tardos
Addison Wesley, 2005

Vöcking et al.
Taschenbuch der Algorithmen
Springer, 2008

LehrinhaltDieses Modul soll Studierenden grundlegende Algorithmen und Datenstrukturen vermitteln.

Die Vorlesung behandelt unter anderem:

  • Grundbegriffe des Algorithm Engineering
  • Asymptotische Algorithmenanalyse (worst case, average case, probabilistisch, amortisiert)
  • Datenstrukturen z. B. Arrays, Stapel, Warteschlangen und Verkettete Listen
  • Hashtabellen
  • Sortieren: vergleichsbasierte Algorithmen (z.B. quicksort, insertionsort), untere Schranken, Linearzeitalgorithmen (z.B. radixsort)
  • Prioritätslisten
  • Sortierte Folgen,Suchbäume und Selektion
  • Graphen (Repräsentation, Breiten-/Tiefensuche, Kürzeste Wege, Minimale Spannbäume)
  • Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
  • Geometrische Algorithmen
AnmerkungDer Dozent kann für gute Leistungen in der Übung Bonuspunkte für die Klausur vergeben, die bis zu 5% der Note ausmachen können. Diese Punkte gelten nur für die Hauptklausur im gleichen Semester und für den zugehörigen Nachschreibetermin. Danach verfallen die Punkte.
ArbeitsbelastungDer Gesamtarbeitsaufwand für dieses Modul beträgt ca. 180 Stunden (6 Credits). Die Gesamtstundenzahl ergibt sich dabei aus dem Aufwand für den Besuch der Vorlesungen und Übungen sowie den Prüfungszeiten und dem zeitlichen Aufwand, der zur Erreichung der Lernziele des Moduls für einen durchschnittlichen Studenten für eine durchschnittliche Leistung erforderlich ist.

Vorlesung (15 x 2 h 15 min) 33 h 45 min
Übung (15 x 45 min) 11 h 15 min
Tutorium (15 x 1 h 30 min) 22 h 30 min
Klausur 2 h

Vor- und Nachbereitung der Veranstaltungen 67 h 30 min
Klausurvorbereitung 45 h


Summe 182 h

ZielDer/die Studierende
  • 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.
PrüfungDie Erfolgskontrolle besteht aus einer schriftlichen Abschlussprüfung nach § 4 Abs. 2 Nr. 1 SPO im Umfang von 120 Minuten.

Die Modulnote ist die Note der Abschlussprüfung.