Algorithmen I

  • Typ:
  • Semester: SS 2020
  • Zeit: 20.04.2020
    15:45 - 17:15 wöchentlich
    30.95 Forum Hörsaal (Audimax)
    30.95 Hörsaal-Gebäude am Forum (AUDIMAX)


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


  • Dozent:

    Prof. Dr.-Ing. Carsten Dachsbacher

    Alisa Jung
    Daniel Opitz
    Vincent Schüßler

  • SWS: 4
  • LVNr.: 24500

Alle weiteren Details und Termine finden Sie im ILIAS-Kurs.

 

===============================================

 

Die Nachklausur wird voraussichtlich am 16.03.2021 von 12:30 Uhr bis 14:30 Uhr im kleinen Zelt und im Redtenbacher Hörsaal stattfinden. Die Aufteilung nach Nachnamen auf Ort und gegebenfalls Einlasszeit wird rechtzeitig hier und im Ilias-Kurs bekannt gegeben.

Anmeldebeginn: 01.02.2021
Anmeldeschluss: 11.03.2021
Abmeldeschluss: 15.03.2021

 

================================================================================

 

Die Ergebnisse der Hauptklausur können Sie hier einsehen:

algo1_hk_ss2020_aushang_v2.pdf

Trotz der aktuellen Umstände möchten wir eine Klausureinsicht ermöglichen, es ist aber abzusehen, dass dies eine logistische Herausforderung wird. Daher möchten wir an Sie appellieren, die Einsicht bitte möglichst nur in wichtigen Fällen (z.B. nahe an der Bestehensgrenze) wahrzunehmen.

Die Einsicht wird elektronisch (per Video) mit Vergabe von Terminen (in der Regel 15 Minuten) stattfinden. Zur Vereinbarung eines Termins melden Sie sich bitte bis zum 16.11.2020 bei algo1-uebung-ss20@lists.kit.edu.

 

 

Die Hauptklausur wird am Samstag 26.09. von 9:00 Uhr bis 11:00 Uhr in der dm-Arena stattfinden.

Der Einlass erfolgt gestaffelt nach Nachnamen wie folgt:

  • 8:00 Uhr: A bis Hen*
  • 8:15 Uhr: Her* bis Q*
  • 8:30 Uhr: R* bis v*

Erscheinen Sie pünktlich zur Ihnen zugeteilten Einlasszeit am Ihnen zugeteilten Schalter (siehe letzte Seite in Informationen zur Hauptklausur in der dm-Arena.pdf) und bringen Sie eine ausgefüllte und ausgedruckte Corona-Erklärung mit (http://www.ciw.kit.edu/download/2020-05-06__Merkblatt_Klausuren_unter_Corona-Bedingungen.pdf letzte Seite).

Weitere Informationen finden Sie in folgendem Dokument: Informationen zur Hauptklausur in der dm-Arena.pdf.

 

Weitere Informationen zu Besonderheiten wegen Corona und zur Übung siehe weiter unten.

Beschreibung Das 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)
Literaturhinweise Algorithms 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

Lehrinhalt Dieses 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
Anmerkung Der 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.
Arbeitsbelastung Der 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

Ziel Der/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üfung Die 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.

Übung

Aktuelles

Der neue Abgabetermin für die Übungsblätter ist Freitags 13:00 im ILIAS.

 

Allgemein

Die Inhalte zur Vorlesung und Übung werden im Lauf der Vorlesungszeit im ILIAS hochgeladen.

ILIAS-Beitrittslink: https://ilias.studium.kit.edu/goto.php?target=crs_1085824_rcodeWdUJ7Ps4X3&client_id=produktiv

 

Übungstermine

Wir werden etwa alle zwei Wochen eine Übungseinheit als Aufzeichnung sowie die zugehörigen Folien als pdf ins ILIAS hochladen.

 

Übungsblätter

Wir werden freitags wöchentliche Übungsblätter im ILIAS hochladen. Die Bearbeitung ist freiwillig. Abgabetermin ist immer der darauffolgende Freitag 13:00 Uhr.

Bonuspunkte: Pro 6% der insgesamt erreichbaren Übungsblatt-Punkte gibt es einen Bonuspunkt für die Klausur, jedoch nicht mehr als 12 Bonuspunkte (von insgesamt 240 Punkten in der Klausur) bei >=72% aller Übungsblattpunkte. Bonuspunkte werden nur auf bereits bestandene Klausuren angerechnet.

Abgabe: Aufgrund der Corona-Situation erfolgt die Abgabe der Blätter ebenfalls im ILIAS digital als Scan der handschriftlichen Lösung. Wer keinen Scanner zur Verfügung hat, kann z.B. Apps wie "Microsoft Office Lens - PDF Scanner" verwenden, um mit dem Handy mit wenig Aufwand pdfs der Lösung zu erstellen.

 

Tutorien

Die Tutorien werden ab der zweiten Vorlesungswoche wöchentlich stattfinden, voraussichtlich als Videokonferenz, über welche Plattform steht noch nicht fest. Außerdem haben wir im ILIAS im Bereich "Tutorien" Gruppen für die Tutorien vorbereitet, die zur Kommunikation mit den Tutoren genutzt werden können. Für Fragen, die für alle (nicht nur innerhalb des Tutoriums) interessant sein könnten, gibt es außerdem das allgemeine Forum.