Vorlesung "Algorithmische Mathematik: Graphen & Anwendungen"

Unser Alltag ist voll von Aufgabenstellungen, die durch Graphen und davon abgeleiteten Datenstrukturen modelliert werden können. Dies reicht von der Routenplanung in Navigationsgeräten und Abfragen bei Online-Fahrplänen über die Modellierung und Optimierung von Produktionsprozessen bis hin zu Suchalgorithmen im Internet. Im Rahmen dieser Vorlesung wollen wir uns einen einen Überblick über Graphen, Bäume und Netzwerke verschaffen. Diese Datenstrukturen werden wir zunächst modellieren, so dass wir einen einheitlichen mathematischen Formalismus verwenden können. Er ermöglicht es, wesentliche Eigenschaften wie zum Beispiel den (starken) Zusammenhang zu definieren und zu analysieren. Schliesslich sollen klassische Algorithmen zur Durchmusterung und zum Beispiel für die Bestimmung kürzester Wege und maximaler Flüsse diskutiert werden. Wesentlich ist hierbei, dass wir auch stets die Korrektheit und Komplexität der Algorithmen beweisen, so dass wir ein solides theoretisches Fundament für Algorithmen auf Graphen, Bäumen und Netzwerken erarbeiten.

Darüberhinaus werden wir immer wieder versuchen, in kurzen, ausblicksartigen Beispielen einen Eindruck von weiteren, aktuellen Anwendungen von Graphen zu erhalten. Diese können zum Beispiel im Bereich der graphbasierten linearen Löser, des Rankings bei Suchmaschinen, der Visualisierung über Spektren von Graphen, der optimalen Partitionierung von Ortsdiskretisierungen für High Performance Computing und der Repräsentationen für maschinelles Lernen auf Graphen liegen.

Im Rahmen der vorlesungsbegleitenden Übungen werden wir sowohl theoretische Aufgaben lösen als auch einige der besprochenen Algorithmen im Rechner umsetzen.

Bitte beachten Sie: Das Kursmaterial sowie weitergehende Informationen zu Übungsbetrieb, Examen, etc. wird über den ADAM-Workspace zur Vorlesung bereit gestellt.

Literatur

  • H. Harbrecht, M. Peters: „Skript zur Vorlesung Algorithmische Mathematik“, FS 2016 Basel.
  • H. Harbrecht: „Skript zur Vorlesung Algorithmische Mathematik“, WS 2007, SS 2008, Uni Bonn.
  • B. Korte, J. Vygen: „Kobinatorische Optimierung“, Springer 2012.
  • S. Hougardy, J. Vygen: „Algorithmische Mathematik“, Springer 2015.
  • D. Jungnickel: „Graphen, Netzwerke und Algorithmen“, 3. Auflage, BI-Wissenschaftsverlag, 1994.
  • N. Blum: „Algorithmen und Datenstrukturen“, 2. Auflage, Oldenbourg Verlag, 2013
  • Ch. Baier: „Skript zur Informatik IV – Algorithmen und Datenstrukturen“, SS 2006, Uni Bonn.
  • W. Küchling, A. Weber: „Einführung in die Informatik – Objektorientiert mit Java“, Springer, 2000.

Vorlesung, Skript und Tafelbild

  • Vorlesung Dienstags, 12:15-14:00 Uhr, Hörsaal 001 im Kollegienhaus (fast immer)
  • kein elektronisches Skript, aber viele Quellen (siehe oben)
  • Vorlesung wird mit elektronischem Tafelwerk auf Tablet gehalten
  • Tafelbild wird auf ADAM veröffentlicht (zeitnah, aber ohne Garantie, dass "rechtzeitig" für Vorlesungsnachbereitung)
  • Tafelbild nur zur Nachbereitung (keine Weitergabe, Veröffentlichung, etc. erlaubt)

Anonymisiertes Feedback

ADAM-Forum erlaubt anonymes Feedback der Studierenden. Konstruktive Kritik und "Lob & Tadel" sind jederzeit willkommen.

Übungsbetrieb

  • Assistent zur Vorlesung: Ilja Kalmykov, (ilja.kalmykov@unibas.ch)
  • Übung: Donnerstags 16:15-18:00 Uhr (Start in erster Vorlesungswoche)
  • Übungszettel:
    • Veröffentlichung: Dienstags auf ADAM
    • Abgabe: Dienstags, bis 14 Uhr in Briefkasten
    • Gruppenabgabe: feste Gruppen aus zwei Studierenden
    • Theorie-Aufgaben: Beweise, Algorithmen anwenden (Abgabe in Papierform)
    • Programmier-Aufgaben: Implementierung von Algorithmen (in MATLAB / C/C++ / Python) (Abgabeform: digital, mittels Email)

Voraussetzung zum Bestehen des Übungsmoduls

Alle nachfolgenden Bedingungen müssen erfüllt sein:

  1. 50% der Punkte aus den Theorie-Aufgaben
  2. 50% der Punkte aus den Programmier-Aufgaben
  3. Bestehen der Übungsklausur am Ende des Semesters

Hinweise zur Klausur zur Übung

Die Klausur zur Übung findet am 24.05.2018 in Hörsaal 102 im Kollegienhaus statt.

  • Klausurbeginn: ca. 16:30 Uhr
  • Bearbeitungszeit: 90 min.
  • Einlass ab 16:15 Uhr.
  • Bitte seien Sie 30 Minuten vor dem Klausurbeginn da, so dass ein stressfreier Einlass ab 16:15 Uhr gewährleistet ist.

Es gelten folgende Regelungen im Vorfeld der Klausur:

  • Jede(r) Studierende hat genau einen Versuch, um das Übungsmodul zu bestehen. Dies geschieht in der Regel durch das Bestehen der oben genannten Klausur (sowie jeweils der 50% aus den Theorie- und Praxis-Übungen). Die einzigen beiden Ausnahmen (bzgl. Klausur) von dieser Regel sind wiefolgt:
    • Personen, die krankheitsbedingt nicht zur Klausur erscheinen können, müssen dies durch ein ärztliches Attest nachweisen.
    • Personen, die am Klausurtag selber (24.05.) aus zwingenden Gründen, die durch Dritte vorgegeben werden (z.B. berufliche Gründe, unaufschiebbare externe Veranstaltung mit Anwesenheitspflicht), nicht erscheinen können, müssen einen schriftlichen Nachweis (mit Unterschrift) von der dritten Partei vorlegen, in dem die dritte Partei die zwingenden Gründe der Abwesenheit des Studierenden bestätigt.
    • Für beide Personengruppen wird sehr zeitnah zur Klausur eine mündliche Prüfung als Ersatz der schriftlichen Prüfung angeboten. Die Qualität der in der mündlichen Prüfung diskutierten Aufgabenstellungen wird dabei identisch zur schriftlichen Prüfung sein. Die in der mündlichen Prüfung diskutierten Aufgaben werden ebenfalls bepunktet. Das Bestehen / nicht Bestehen der Prüfung wird schliesslich nach dem selben Bewertungsschlüssel wie in der Klausur durchgeführt.
  • Stoffumfang: Der gesamte in der Übung bis zum Zeitpunkt der Klausur diskutierte Stoffumfang (und somit implizit der bis dahin in der Vorlesung diskutierte Stoffumfang). Dies gilt sowohl für die Theorie- als auch die Praxis-Aufgaben.
  • Es wird sicher eine oder mehrere Aufgaben zur Praxis, d.h. zum Programmieren, geben.
  • Die Klausur ist sicher bestanden, wenn Sie 50% der Gesamtpunktzahl erreicht haben.

Am Tag der Klausur bzw. während der Klausur gelten folgende Regeln:

  • Bringen Sie ihren Studierendenausweis oder, falls dieser nicht vorhanden ist oder kein Foto enthält, ihre(n) Identitätskarte/Personalausweis/Reisepass zur zweifelsfreien Identifikation mit.
  • Es sind keine Hilfsmittel wie Taschenrechner, Handys/Natels/Smartphones, Smartwatches, Lernmaterial u.ä. erlaubt.
  • An Ihrem Platz sind einzig Schreibmaterial, Getränke und Essen (in Klarsichtfolie) erlaubt.
  • Alle weiteren Arbeitsmaterialien, insbesondere Papier, wird gestellt.
  • Es dürfen nicht mehrere Personen gleichzeitig den Hörsaal verlassen.
  • Jeder Betrugsversuch führt zum unmittelbaren Nichtbestehen der Klausur.

Übungsblätter