Internet-Algorithmen (M-IAL) – Sommersemester 2014

Informationen zur Vorlesung

Vorlesungstermin

Montag, 10:15 bis 13:00 im Magnus-Hörsaal

Sprechstunden

Prof. Dr. Georg Schnitger
Hannes Seiwert, Raum 303, immer wenn im Büro anzutreffen

Material

Die Beamer Folien der Vorlesung stehen hier als PDF-Dateien zur Verfügung.
Sie werden im Laufe des Semesters ergänzt.

Videos zur Vorlesung können hier abgerufen werden.

Inhalt der Veranstaltung

Das Internet erfordert neue Modellbildungen, wie etwa das Streaming Data Modell in der Behandlung großer Datenmengen oder die Spieltheorie in der Modellierung egoistischer Benutzer. Desweiteren muss der Tatsache Rechnung getragen werden, dass komplexe Probleme wie das Routing von Paketen durch verteiltes, unkoordiniertes Rechnen bewältigt werden müssen. Die Veranstaltung führt in diese Modellbildungen ein und beschreibt algorithmische Lösungen wichtiger algorithmischer Probleme des Internets.

Der erste Teil ist Algorithmen zur Behandlung großer Datenmengen gewidmet. Hierzu gehören algorithmische Aspekte im Entwurf von Suchmaschinen wie auch die Lösung von Problemen im Streaming Data Modell. Desweiteren werden Hashing-Verfahren (verteiltes Hashing, Bloom-Filter) für Web-Anwendungen vorgestellt.

Im zweiten Teil werden algorithmische Fragestellungen behandelt, die sich vorwiegend im Internet Routing ergeben. Hierzu gehören etwa der Entwurf von Erasure Correcting Codes, die Untersuchung von Queueing-Strategien im Hinblick auf universelle Stabilität, die Analyse von Mechanismen zur End-to-End Congestion Control sowie die Begegnung von Denial-of-Service Attacken.

Der letzte Teil der Veranstaltung behandelt die algorithmische Spieltheorie, um das Verhalten egoistischer Benutzer des Internet im Kontext knapper Ressourcen, wie etwa Rechenzeit und Routing Kapazität, zu modellieren. Dazu werden fundamentale algorithmische Probleme der Spieltheorie, wie etwa die Bestimmung von Nash- Gleichgewichten oder der Entwurf von Auktionen, untersucht.

Literatur

D. Easley, J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World". Cambridge University Press, 2010 -- elementar

Informationen zur Übung

Die Teilnahme an den Übungen und das Bearbeiten der Übungsaufgaben wird für eine erfolgreiche Prüfung unbedingt empfohlen.

Um Bonuspunkte für die Prüfung gutgeschrieben zu bekommen, muss im Tutorium vorgerechnet worden sein (sofern die Gegebenheiten es zulassen).

Kopierte oder plagiierte Lösungen werden für jeden Betroffenen nicht bewertet; jedem „Wiederholungstäter“ werden keinerlei Bonuspunkte für die Prüfung angerechnet.

Übungstermin

Mittwoch, 14:15 bis 16:00 in NM 103

Übungsaufgaben

Die gelösten Blätter sind vor der Vorlesung abzugeben. Alternativ ist eine frühere Abgabe im Briefkasten gegenüber von Raum 303 möglich.

Prüfung

Am Ende des Semesters werden mündliche Prüfungen als Modulabschlußprüfung angeboten. Die in den Übungen erzielten Punkte verbessern das Resultat der mündlichen Prüfung um maximal zwei Notenschritte, falls die Prüfung bestanden wird. Z.B. kann die Note von 2.0 auf 1.3 verbessert werden bzw. von 2.3 auf 1.7. Werden weniger als 100% der anrechenbaren Übungspunkte erreicht, wird die Note entsprechend anteilsmäßig verbessert.