[AI-announce] Abschlussarbeit Seminaroptimierung

[Christopher Wolf]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hallo,

anbei eine Ausschreibung für eine Bachelor- oder Masterarbeit. Es soll
die Zuteilung von Themen zu Studierenden für die ITS-Seminare
untersucht werden.

Die ITS-Seminare werden seit 2 Semestern über eine gemeinsame
Web-Plattform vergeben (https://svhgi.nds.rub.de/). Ziel ist zum einen
eine bessere Auslastung der Seminare, zum anderen aber auch eine
gerechte Verteilung der Themen an alle Studierenden.

Zu diesem Zweck wird derzeit ein randomisierter Algorithmus verwendet,
der aus ca. 10.000 möglichen Zuordnungen die bestmögliche auswählt.
Wenngleich er relativ rasch konvergiert und das Ergebnis sicher
brauchbar ist (die meisten Studierenden erhalten entweder ihre Erst-
oder zumindest ihre Zweitwahl; es bleiben nur wenige Plätze unbesetzt)
ist nicht a priori klar, dass das Ergebnis auch /optimal/ ist. Dies
ist insbesondere deshalb zweifelhaft, da unsere Seminarwahl eine Reihe
von Nebenbedingungen enthält, die das Finden einer optimalen Zuteilung
vermutlich NP-vollständig oder zumindest NP-hart machen.

Im Rahmen dieser Abschlussarbeit soll versucht werden, den aktuellen
Zuteilungsalgorithmus zu verbessern. Insbesondere bieten sich folgende
Strategien aus der diskreten Optimierung an:
 * Greedy-Initialisierung (aktuell machen wir dies randomisiert)
 * Hill-Climbing (lokale Optimierung nach der Initialisierung)
 * Hill-Climbing mit Tauschen (erlaubt Übergang zwischen zwei gleich
optimalen Lösungen)
 * Simmulated Annealing (wie Hill-Climbing, aber mehr Freiheiten beim
Tauschen)
 * Genetische Optimierung (auf Permutationen, dann Greedy-Zuteilung)
 * Berechnung des optimalen Flusses in einem Netzwerk

Sehr schön wäre auch herauszuarbeiten, welcher Komplexitätsklasse
unser Problem angehört. In jedem Fall soll das Ergebnis in das
aktuelle Seminarverteilungssystem einfließen. Daher ist das Erstellen
von geeigneten Test- und Benchmarkfällen obligatorisch; dito eine
lückenlose Dokumentation des Programmcodes sowie der verwendeten
Algorithmen.

Sinnvolle Vorkenntnisse:
 * Programmierung, evtl. in PHP
 * Komplexitätstheorie, wie z.B. aus Diskreter Mathematik

Bei Interessse senden Sie mir bitte folgende Informationen zu,
bevorzugt als PDF:
 a) ein kurzes Motivationsschreiben (5-10 Zeilen - eMail genügt!)
 b) Ihren aktuellen Notenspiegel
 c) Angabe zum geplanten Zeitraum (z.B. ab jetzt Vollzeit, ab Dezember
in Teilzeit, ...)
 d) Ihren Studiengang & der angestrebte Typ der Arbeit (z.B.
Bachelorarbeit oder Masterarbeit - eMail genügt!)

Je nach Antwort zu (a-d) verschiebt sich der Fokus entsprechend: Als
Arbeit aus der Mathematik stünden eher die Algorithmen und deren
Optimalität im Vordergrund, als Arbeit aus der ITS wäre auch eine
Untersuchung über die sichere und verlässlichen Kommunikation zwischen
den Teilkomponenten relevant.

Evtl. Rückfragen gerne an Stefan Hoffmann (stefan.g.hoffmann at rub.de)
oder mich.

Beste Grüße,
Christopher Wolf

- -- 
Dr Christopher Wolf
Room NA 5/69
WG LTS - Working Group
Long Term Security
Ruhr University Bochum
Tel: +49 234 32 23265
Fax: +49 234 32 14430
www.cits.rub.de
www.christopher-wolf.eu

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with undefined - http://www.enigmail.net/

iQEcBAEBAgAGBQJRY9iiAAoJEH3aD/+s49Tw/ecIAJvIRoYhQM3Wlip2ltnXKUBQ
eFNjsB+JdK252ZjLlrW3ApS/oFsNmp5ZkKxgPrMzT6p/k+7NTX7ybWpYJmLWTJbT
v8UR53a0sm1L49u3PLq748RLhxdDIrDwWYmpaWTsNzC7rexng7YDf7DZpBhdPovF
gwY3XnINTIIi720RI2y9/UihT59O4QqDSo1MOqS3RqUp8OZFsnOnRU77S/bcLS+U
8Zz9Ho+03xgwAi2No4hqrq2DIUcOv/Cp/J0/D3ztOOCTIjStxniTKKTBH4ooon+W
Fciod5om1msgu75D7DhpvusojBiasGSpECtJNlJqGqHMgY7BD0PqhaJydGMhyxI=
=0nu2
-----END PGP SIGNATURE-----