** Deadline von Phase III auf 19.4 geändert nach Beschluss der Hochschulleitung; “Alle Abgabefristen für Abschluss-, Seminar-, Studien- und Hausarbeiten werden um die Dauer der Bibliotheksschließung - nach aktuellem Stand der 19. April 2020 - pauschal verlängert.” **
Im Rahmen dieses Programmierprojektes wird in Gruppen von jeweils 2-3 Personen ein webbasierter Routenplaner implementiert.
Das Projekt verläuft in 3 Phasen, jede Gruppe muss nach Ende einer Phase die entsprechende Aufgabe fertiggestellt haben, um weiter am Programmierprojekt teilnehmen zu dürfen.
Gruppen
Teilnehmer melden sich für die Lehrveranstaltung im C@mpus an, was automatisch auch zu einer Anmeldung im Iliaskurs führt. Die Gruppeneinteilung wird von den Studenten selbstständig organisiert. Teilnehmer, die bis zum 20.11 keine Gruppe gefunden haben, melden sich dann per Mail und werden dann in Gruppen eingeteilt.
Hardware
In dieser Veranstaltung werden Sie mit etwas größeren Datenmengen zu tun haben. Falls ihr Rechner weniger als 8GB RAM zur Verfügung hat, könnte es für die größeren Datensätze problematisch werden. Die Poolrechner im Informatikgebäude haben ausreichend RAM.
Formalien
Im C@mpus muss zusätzlich der Prüfungstermin bei Funke angemeldet werden. Die Lehrveranstaltung ist nicht benotet, es gibt nur Bestehen und Nichtbestehen.
Für alle Phasen:
Beim Test für die Abnahme wird eine VM mit dem Image Ubuntu 18.04 aus der bwCloud verwendet (Ubuntu 18.04, 8GB RAM). Als Student haben Sie die Möglichkeit, in der bwcloud eine solche VM zu nutzen. Allerdings hat eine solche mit VM nur 1 GB RAM was aber ausreicht um auf den kleineren Graphen zu testen und damit die Laufzeit für den Deutschlandgraph zu extrapolieren. Java und Mavenversion richten sich danach welche in den Standardpaketquellen gegeben ist. Das Programm darf nur Bibliotheken aus den Standardpaketquellen benutzen.
Eine Abgabe
- muss im Ilias hochgeladen werden. Entweder muss es als zip hochgeladen werden oder auf ein privates git-repository auf dem Uni-Github verweisen und ac120129 als Collaborator hinzugefügt werden.
- muss einfach von der Konsole kompiliert und gestartet werden können, dazu muss es entweder einfache Skripte wie “build.sh” geben oder ein automatisiertes Build-System wie maven verwendet werden.
- darf keinen kompilierten Code enthalten, also keine .class oder .jar Dateien
- ein README enthalten, welches
- die Übersetzung in der Konsole auf dem Zielsystem erklärt
- die Benutzung erläutert
- muss kleiner als 1MB sein
Zeit- und Platzanforderungen beziehen sich immer auf den Deutschland-Datensatz
- Implementierung muss auf einem Rechner mit 8GB RAM lauffähig sein
- Bei Algorithmen für die eine Laufzeitanforderung besteht, müssen benötigte Laufzeiten auf der Konsole ausgegeben werden.
Phase I (Deadline 20.12.2019)
Erstellung der Routenplanungskomponente;
- Kriterien für das Bestehen:
- Für den eingelesenen Graphen müssen Längen- und Breitengrad jeweils als double-Genauigkeit, d.h. 8 Byte abgespeichert werden
- Die folgenden beiden Zeitanforderungen müssen eingehalten werden.
- Einlesen des Deutschland-Graphen darf maximal 2 Minuten dauern
- Korrekte Berechnung eines one-to-all Dijkstra darf nicht mehr als 20 Sekunden dauern
- Die Implementierung muss es erlauben, sowohl Start-Ziel-Anfragen zu stellen, als auch Dijkstra von einem Knoten zu allen anderen Knoten zu berechnen sowie danach Distanzen vom Startknoten abzufragen
- Desweiteren muss es die Möglichkeit geben, eine Datei mit Start-Ziel-Anfragen einzulesen und die Distanzen auszugeben (siehe bereitgestellte .que bzw. .sol Dateien): .que/.sol-Dateien; Aufruf z.B. mit ./myBenchmarker bw.fmi bw.que; die Ausgabe muss dann genau bw.sol entsprechen, d.h. ein Diff-Befehl sollte Gleichheit der Dateien ergeben.
Phase II (Deadline 31.01.2020)
Lokalisierung mit partitionierender Hilfsdatenstruktur
- Das Aufbauen der Hilfsdatenstruktur darf nicht länger als 10 min dauern.
- Das Finden der nächsten Nachbarn mit der Hilfsdatenstruktur darf im Schnitt nicht länger als 10 ms dauern. (weniger als 1 ms ist machbar) Zum Vergleich: Die iterative Variante benötigt auf dem Zielsystem ca. 70 ms.
Phase III (19.04.2020)
Erstellung der Webclientkomponente und Webserverkomponente.
Es reicht aus wenn das Program lokal testbar ist, d.h. “localhost:8080” im Webbrowser, z.B. Firefox, einzutragen ist.
Optional: Um den tileserver von Openstreetmap zu entlasten können Sie stattdessen den FMI-eigenen mit https://tiles.fmi.uni-stuttgart.de/{z}/{x}/{y}.png verwenden.
Treffen
Das vierte und letzte Treffen für den Start von Phase III findet am 7.2 um 15:45 in V38.03 statt.