Vorlesung (Halbmodul): Cake-cutting Algorithms
Sommersemester 2016
Allgemeines:
- Diese Veranstaltung kann im Master-Studiengang Informatik besucht
werden. Um an dieser Veranstaltung (und insbesondere an der Prüfung)
teilnehmen zu können, müssen Studierende im Bachelor-Studiengang
Informatik laut Prüfungsordnung die Veranstaltungen "Informatik
I" bis "Informatik IV" erfolgreich abgeschlossen haben.
Für Nebenfächler ist dies nicht erforderlich (außer die
Prüfungsordnung des Nebenfaches verlangt es doch).
- Außer dieser formalen Zugangsvoraussetzung sind keinerlei
spezielle Vorkenntnisse nötig. Es wird nur ein grundlegendes
Verständnis mathematischer und informatischer (z.B. algorithmischer)
Begriffe vorausgesetzt und ein Interesse an der gerechten Aufteilung
z.B. von Kuchen erwartet.
- Bitte tragen Sie sich auf der Website
CCC: Computational Complexity and Cryptology
für diese Vorlesung und die Übungsgruppe sowie für das Seminar
ein. Falls Sie nicht schon registriert sind, müssen Sie sich erst
registrieren. Wenn Sie bei der Anmeldung Ihre E-Mail-Adresse angeben,
wird Ihnen ein Passwort zugeschickt.
Zusätzlich müssen Sie sich im LSF anmelden, damit Sie sich später
beim Prüfungsamt für die Prüfung anmelden können.
Nur wer sowohl im LSF als auch im CCC angemeldet ist, kann die
Zulassung zur Prüfung erwerben und an der Prüfung teilnehmen.
Anmeldefrist: Sie müssen sich spätestens bis zum
22. April 2016 um 23:59 Uhr zu dieser Vorlesung (inklusive
Übungsgruppe) im CCC-System und im LSF angemeldet haben. Das ist eine
Ausschlussfrist. Wenn Sie sich bis dahin nicht angemeldet haben,
können Sie nicht an der Klausur teilnehmen.
- Dieses Halbmodul kann mit jedem anderen Halbmodul der Theoretischen
Informatik kombiniert werden.
Prüfung:
findet in Form einer schriftlichen Klausur
am Donnerstag, dem 14.07.2016, von 8:30 Uhr bis 10:00 Uhr im
Hörsaal 5D (Geb. 25.21) statt.
Bitte bringen Sie Ihren Personal- und Studentenausweis mit
zur Klausur. Falls der Platz auf den von uns ausgeteilten
Klausuren nicht reicht, sollten Sie sich auch eigene Blätter
mitbringen.
Erlaubte Hilfsmittel: Vorlesungsmitschriften, Bücher,
Übungsblätter, Gedächtnis.
Nicht erlaubte Hilfsmittel: Mobiltelefone und ähnliche
Kommunikationsgeräte, Kommiliton/inn/en, Taschenrechner.
Anmeldung: bis zwei Wochen (PO 2012) vor dem Klausurtermin beim
Akademischen Prüfungsamt bzw. über das Studierendenportal.
Hat man sich zur Klausur angemeldet, so kann man bis eine Woche vor
der Klausur noch zurücktreten, ohne dass dies als ein Fehlversuch
gewertet wird. Die Abmeldung von der Klausur muss über das
Akademische Prüfungsamt erfolgen. Bitte sagen Sie in diesem Fall
auch mir per E-Mail Bescheid.
Klausureinsicht:
findet am Freitag, dem 15.07.2016, von 10:00
Uhr bis 11:00 Uhr im Büro von Ann-Kathrin Selker (25.02.O1.33) statt.
Probeklausur:
findet am 23. Juni 2016 um 8:40 Uhr im Hörsaal
5H statt. Die Teilnahme ist freiwillig. Die Lösungen werden in den
Übungen besprochen. Hier können Sie das
pdf der Probeklausur.
herunterladen.
Nachprüfung:
findet als mündliche Prüfung statt
(individuelle Terminabsprache über E-Mail).
Übungen:
- Termine und Räume (voraussichtlich):
- Donnerstag von 10:30 Uhr bis 12:00 Uhr im Seminarraum 25.12.O1.51,
- Montag von 14:30 Uhr bis 16:00 Uhr im Seminarraum 25.13.U1.30.
Der Übungsbetrieb beginnt in der zweiten Semesterwoche mit einem
kurzen Tutorium am Donnerstag, dem 21.04.2016. Das erste Übungsblatt
wird in der dritten Semesterwoche (also am Montag, dem 25.04.2016, und
am Donnerstag, dem 28.04.2016) besprochen.
- Die Übungen werden betreut von Herrn
Daniel Neugebauer
und von Frau
Ann-Kathrin Selker.
- Für die Übungen sind die Aufgaben auf den Übungsblättern zu lösen.
Die Lösungen werden in den Übungen besprochen und es wird
eine aktive Beteiligung aller Studierenden erwartet (d.h.,
jeder muss zwei Mal in der Übung vorrechnen, und zwar nur solche
Aufgaben, deren schriftliche Lösung vorher abgegeben wurde). Fehlen
bei den Übungen oder der Vorlesung kann ebenso eine Nichtzulassung zur
Prüfung zur Folge haben wie eine zu inaktive Teilnahme an den Übungen.
- Die Übungsblätter können nach der Vorlesung am Donnerstag
hier von dieser Website heruntergeladen werden. Das erste Blatt
erscheint am 14.04.2016.
Bitte geben Sie Ihre bearbeiteten Übungsblätter jeweils eine Woche
später in dem entsprechend beschrifteten Übungsbriefkasten
(Geb. 25.13, Ebene 2) ab, also am Donnerstag bis 8:35 Uhr.
Empfohlene Literatur:
|
Jörg Rothe (ed.): "Economics and Computation: An
Introduction to Algorithmic Game Theory, Computational Social Choice,
and Fair Division", Springer-Verlag, 2015
Für die Vorlesung relevant ist:
- Chapter 7: "Cake-Cutting: Fair Division of Divisible
Goods", Claudia Lindner · Jörg Rothe, pp. 395 - 491
|
|
Jörg Rothe, Dorothea Baumeister, Claudia Lindner, and Irene
Rothe: "Einführung in Computational Social Choice: Individuelle
Strategien und kollektive Entscheidungen beim Spielen, Wählen und
Teilen", Spektrum Akademischer Verlag, 2011
Für die Vorlesung relevant ist:
- Kapitel 6: "Cake-Cutting: Aufteilung teilbarer
Ressourcen", Claudia Lindner · Jörg Rothe, pp. 233 - 321
|
Ergänzende Literatur:
- Jack Robertson and William Webb: "Cake-Cutting
Algorithms: Be Fair if You Can", A K Peters, 1998
- Steven J. Brams and Alan D. Taylor: "Fair Division:
From Cake-Cutting to Dispute Resolution",
Cambridge University Press, 1996
Skript:
Es gibt keins. Es gibt aber gute Literatur, siehe
oben. Meine Folien zur Vorlesung können Sie sich kapitelweise hier
herunterladen:
Diese werden im Laufe des Semesters ergänzt und sind auf Englisch.
ACHTUNG: Wer in Düsseldorf Informatik studiert und sich für
einen ein- oder zweisemestrigen Auslandsaufenthalt interessiert, oder
auch wer an einer ausländischen Hochschule studiert und ein oder zwei
Semester in Düsseldorf Informatik studieren möchte, kann sich über das
Internationale Austauschprogramm ERASMUS
informieren oder Herrn
Jun.-Prof. Dr. Kalman Graffi
persönlich ansprechen, der seit dem Sommersemester 2016 den
ERASMUS-Austausch für die Informatik koordiniert.