wie angekündigt, möchte ich hier im Forum noch einmal die Projektaufgabe aus der heutigen Vorbesprechung zusammenfassen und dabei die algorithmische Problemstellung formaler spezifizieren.
Hier und auch auch ansonsten: Bitte nutzen Sie in erster Linie das Forum für Fragen, Anregungen, Kritik usw., damit alle Ihre Anfrage und meine Antwort bzw. die Diskussion darüber mitlesen können.
======
Algorithmische Problemstellung:
Gegeben sind vier positive ganze Zahlen, N1, N2, N3 und K, sowie für jedes i=1,...,K eine Zahl m. Für jedes i=1,...,K gibt es Koordinaten (Xsender, Ysender,ZSender) sowie für jedes j=1,...,m Koordinaten (XEmpfaenger[i,j],YEmpfaenger[i,j],ZEmpfaenger[i,j]) (Sie sind natürlich nicht an diese scheußliche, einfallslose Notation gebunden
). Koordinaten sind Werte im Bereich X=1,...,N1, Y=1,...,N2 und Z=1,...,N3. Intuitiv sind dies K Mengen von Terminalen in einem ungerichteten 3D-Gittergraphen, wobei jede Menge i ein Senderterminal und m Empfängerterminale hat.Gesucht ist für jedes i=1,...,K ein Steinerbaum S im Gittergraphen, der alle Terminale der i-ten Menge - Sender und Empfänger - miteinander verbindet. Für i<>j müssen S und S[j] knotendisjunkt sein.
Zu minimierende Zielfunktion: Für i=1,...K und j=1,...m sei D[i,j] die Anzahl der Kanten von S auf dem Weg vom Sender (i) zum Empfänger (i,j). Dann soll folgender mathematischer Ausdruck minimiert werden:
max { D[i,j] | i=1,...,K; j=1,...,m[i] }.
======
Aufgabenstellung des Praktikums: ein kleines Softwarepaket, das folgende Funktionalitäten bietet:
---
1. Einen Algorithmus für obiges Problem.
Der Algorithmus sollte einem auch bei fünf- bis sechsstelligen Knotenzahlen bei seiner Ausführung keine ausreichende Zeit bieten, um sich zwischendurch einen Kaffee zu holen.
Sie können den Algorithmus suchen (z.B. im Web) oder selbst algorithmisch kreativ sein oder beides miteinander verbinden.
Hinweis: Erfahrungsgemäß funktionieren Algorithmen hier nicht besonders gut, die durch kleine Modifikationen eine lange Liste von zulässigen Lösungen durchlaufen, also bspw Simulated Annealing, Evolutionsstrategien oder genetische Algorithmen. Zielführender sind wahrscheinlich konstruktive Algorithmen, die die Lösung Stück für Stück aufbauen (d.h. Kante für Kante, Pfad für Pfad, Baum für Baum, whatever). Auch Backtracking-Strategien sollten gut funktionieren, d.h. wenn sich der Algorithmus in eine unlösbare Situation verrennt, werden ein paar mitverantwortliche Platzierungen modifiziert, und der Algorithmus läuft von dieser modifizierten Situation aus weiter. Bewährt hat sich, dass man vorab diejenigen Pfade (nicht Bäume!) identifiziert und behandelt, bei denen obiges Maximum mit großer Wahrscheinlichkeit angenommen wird (das kann man mehr oder auch weniger raffiniert machen).
---
2. Graphikorientierte Benutzerschnittstelle
Sollte den Algorithmus visualisieren und auch animieren können und sollte interaktive Konstruktion von Beispielen erlauben (Achtung: Interaktion in einem 3D-Graphen ist kniffliger als man denkt).
---
3. Einfacher Zufallsgenerator für Beispiele (sonst wird es unbequem, große Beispiele zu konstruieren).
---
3. File I/O für Beispiele.
Prescht jemand vor mit einem Vorschlag für eine UML-Spezifikation?
======
Rahmenbedingungen:
1-2 Leute bearbeiten das Projekt gemeinsam, wobei es für Bearbeitung alleine Notenbonus gibt (Faustregel. mehr oder weniger zwei Notenstufen, also 0.6-0.7 einer Note).
Abgabefrist ist Anfang Vorlesungszeit SS 09. Kann bei Vorbringen nachvollziehbarer Gründe auch individuell verlängert werden.
Ich erwarte allerdings, dass Sie mindestens 1-2mal vor Abnahme auf mich zukommen und mit mir Ihre bisherigen und geplanten Arbeiten durchsprechen. Erster Termin sollte rund um Weihnachten sein. Für Absprache eines Termins einfach eine Email an mich.
======
Bestehen und Note:
Das Projekt ist bestanden, wenn die oben beschriebenen Funktionalitäten vorhanden sind und Fehlverhalten des Programms (z.B. Absturz) nur ausnahmsweise passiert, um 'mal wieder den Mythos des Vorführeffektes zu bestätigen. Will sagen: Die Abnahme sollte weitestgehend frei von Fehlverhalten des Pakets sein. Und natürlich müssen Sie zum Bestehen bei der Abnahme überzeugend vermitteln können, dass Sie das vorgestellte Ergebnis tatsächlich selbst entwickelt haben.
---
In die Gesamtnote fließen ein:
1. wie gut der Algorithmus ist (Laufzeit, Akkuratesse).
2. wie einfach und intuitiv die Benutzerschnittstelle ist (verständlich "für kleine Kinder und Vorstände" => optimal).
3. wie souverän Sie den Code erläutern können, wenn ich bei der Abnahme nachhake.
======
Die noten in den bisherigen Praktika waren (verdient!) eher unauffällig bis gut bis sehr gut, obwohl die Teilnehmer vorab auch nicht mehr wussten, also don't panic!
Gruß an alle,
KW
