Aufgabenstellung WS 08/09

Moderator: Praktikum: Algorithmen

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Aufgabenstellung WS 08/09

Beitrag von Prof. Karsten Weihe » 22. Okt 2008 15:36

Hallo allerseits,

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 :oops: ). 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. :wink:

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? 8)


======


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. :twisted:

---

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

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung WS 08/09

Beitrag von MisterD123 » 22. Okt 2008 15:56

ich dacht bei dem dateiformat spontan, man könnte vielleicht ganz einfach n xml file machen, so nach dem motto

Code: Alles auswählen

<gitter sizex=.. sizey=.. sizez=..>
<terminalmenge>
 <sender x=.. y=.. z=..>
 <empfaenger x=.. y=.. z=..>
 <empfaenger x=.. y=.. z=..>
</terminalmenge>
<terminalmenge>
 ..
</terminalmenge>
</gitter>
sollte denke ich recht einfach zu parsen sein, explode und n bisschen substring, oder gibt doch garantiert n xml package für die meisten programmiersprachen.. für die ausgabe hab ich mir aber noch nix überlegt ;P
uml spezifikation für dateiformate.. öh wie sieht sowas aus? ;D oder wie war das gemeint?

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Re: Aufgabenstellung WS 08/09

Beitrag von Maradatscha » 26. Okt 2008 10:56

find ich in Ordnung so!
Wollen wir uns darauf festlegen?

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Aufgabenstellung WS 08/09

Beitrag von MisterD123 » 26. Okt 2008 11:12

es ist halt bei knotenzahlen in den millionen ein *ganz klein wenig* speicheraufwändig..

m_gaber
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 26. Okt 2004 15:09

Re: Aufgabenstellung WS 08/09

Beitrag von m_gaber » 27. Okt 2008 14:20

... klingt ganz gut.
speicherplatz denke ich ist kein problem.
eventuell wäre es noch ganz nett den einzelnen terminalmengen einen bezeichner mitzugeben.

ich schau mal ob ich auf die schnelle eine XML-Schema definition zusammengeschrieben bekomm

EisNerd
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 18. Nov 2005 19:54
Wohnort: Heppenheim

Re: Aufgabenstellung WS 08/09

Beitrag von EisNerd » 27. Okt 2008 15:16

So das xsd sollte soweit brauchbar sein.

Validator: http://www.w3.org/2001/03/webdata/xsv

@KW:
Wenn das für alle ok ist, sich also keiner beschwert, könnte man das auf die Homepage setzen?

/**
* see below!
*/
@Deprecated

Code: Alles auswählen

<?xml version="1.0" encoding="UTF-8"?>
<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema" 
  xmlns="http://algo.informatik.tu-darmstadt.de">

  <xsd:element name="grid">
    <xsd:complexType>
      <xsd:sequence>
	<xsd:element name="net" type="net" minOccurs="1" maxOccurs="unbounded"/>
      </xsd:sequence>
      <xsd:attribute name="size_x" type="xsd:integer" use="required"/>
      <xsd:attribute name="size_y" type="xsd:integer" use="required"/>
      <xsd:attribute name="size_z" type="xsd:integer" use="required"/>
      <xsd:attribute name="cost" type="xsd:integer" use="optional"/>
    </xsd:complexType>
  </xsd:element>
  
  <xsd:complexType name="net">
    <xsd:sequence>
      <xsd:element name="source" type="terminal" minOccurs="1" maxOccurs="1"/>
      <xsd:element name="sink" type="terminal" minOccurs="1" maxOccurs="unbounded"/>
      <xsd:element name="segment" type="segment" minOccurs="0" maxOccurs="unbounded"/>
    </xsd:sequence>
    <xsd:attribute name="cost" type="xsd:integer" use="optional"/>
  </xsd:complexType>
  
  <xsd:complexType name="terminal">
    <xsd:attribute name="pos_x" type="xsd:integer" use="required"/>
    <xsd:attribute name="pos_y" type="xsd:integer" use="required"/>
    <xsd:attribute name="pos_z" type="xsd:integer" use="required"/>
  </xsd:complexType>

  <xsd:complexType name="segment">
    <xsd:attribute name="pos_x" type="xsd:integer" use="required"/>
    <xsd:attribute name="pos_y" type="xsd:integer" use="required"/>
    <xsd:attribute name="pos_z" type="xsd:integer" use="required"/>
    <xsd:attribute name="orientation" type="orientation" use="required"/>
  </xsd:complexType>
  
  <xsd:simpleType name="orientation">
    <xsd:restriction base="xsd:char">
      <xsd:enumeration value="x"/>
      <xsd:enumeration value="y"/>
      <xsd:enumeration value="z"/>
    </xsd:restriction>
  </xsd:simpleType>
  
</xsd:schema>
Zuletzt geändert von EisNerd am 27. Okt 2008 16:41, insgesamt 1-mal geändert.
... und morgen gehts weiter.

patrik_s.stud.tu
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 12. Okt 2006 20:56

Re: Aufgabenstellung WS 08/09

Beitrag von patrik_s.stud.tu » 27. Okt 2008 15:36

also ich persoenliche finde, dass es ein riesen overhead ist!

ein einfacher file wuerde auch reichen! wie z.b.:

breite;hoehe;tiefe
[Menge]
x;y;z
x;y;z
x;y;z
...
[Menge]
x;y;z
...

wobei x,y,z zahlen fuer koordinaten sind und der erste tupel implizit die quelle ist.
man koennte auch [Menge] durch eine leere zeile ersetzen...

m_gaber
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 26. Okt 2004 15:09

Re: Aufgabenstellung WS 08/09

Beitrag von m_gaber » 27. Okt 2008 15:39

naja, es ist kaum zusätzlicher Aufwand, nur dass dir wenn du ein XML file hast damit mit einfachsten mitteln (bibliotheken) einen parser geschenkt bekommst (evtl lässt sich in java sogar ein xsd direkt in konstruktoraufrufe übersetzen, müsste man mal checken), während bei deinem format jeder einen eigenen parser schreiben müsste.

Gruß Michael

P.S. zumindest das erste Bild auf dieser seite sieht nach folgenden Arbeitsschritten aus:
1) XSD -> Java Klassen mittels Compiler
2) XML + Klassen -> Code mittels JAXB API

dann noch die restloichen methoden ausfüllen und du bist glücklich

EisNerd
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 18. Nov 2005 19:54
Wohnort: Heppenheim

Re: Aufgabenstellung WS 08/09

Beitrag von EisNerd » 27. Okt 2008 16:39

So geht das direkt durch xjc-2:

Code: Alles auswählen

xjc-2 -p de.tudarmstadt.informatik.algo.netmapping xml/grid.xsd -d src/
parsing a schema...
compiling a schema...
de/tudarmstadt/informatik/algo/netmapping/Direction.java
de/tudarmstadt/informatik/algo/netmapping/Grid.java
de/tudarmstadt/informatik/algo/netmapping/Net.java
de/tudarmstadt/informatik/algo/netmapping/ObjectFactory.java
de/tudarmstadt/informatik/algo/netmapping/Segment.java
de/tudarmstadt/informatik/algo/netmapping/Terminal.java
de/tudarmstadt/informatik/algo/netmapping/package-info.java
Hier das korrigierte Schema

Code: Alles auswählen

<?xml version="1.0" encoding="UTF-8"?>
<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema" 
  xmlns="http://algo.informatik.tu-darmstadt.de"
  targetNamespace="http://algo.informatik.tu-darmstadt.de">

  <xsd:element name="grid">
    <xsd:complexType>
      <xsd:sequence>
	<xsd:element name="net" type="net" minOccurs="1" maxOccurs="unbounded"/>
      </xsd:sequence>
      <xsd:attribute name="size_x" type="xsd:int" use="required"/>
      <xsd:attribute name="size_y" type="xsd:int" use="required"/>
      <xsd:attribute name="size_z" type="xsd:int" use="required"/>
      <xsd:attribute name="cost" type="xsd:int" use="optional"/>
    </xsd:complexType>
  </xsd:element>
  
  <xsd:complexType name="net">
    <xsd:sequence>
      <xsd:element name="source" type="terminal" minOccurs="1" maxOccurs="1"/>
      <xsd:element name="sink" type="terminal" minOccurs="1" maxOccurs="unbounded"/>
      <xsd:element name="segment" type="segment" minOccurs="0" maxOccurs="unbounded"/>
    </xsd:sequence>
    <xsd:attribute name="cost" type="xsd:int" use="optional"/>
  </xsd:complexType>
  
  <xsd:complexType name="terminal">
    <xsd:attribute name="pos_x" type="xsd:int" use="required"/>
    <xsd:attribute name="pos_y" type="xsd:int" use="required"/>
    <xsd:attribute name="pos_z" type="xsd:int" use="required"/>
  </xsd:complexType>

  <xsd:complexType name="segment">
    <xsd:attribute name="pos_x" type="xsd:int" use="required"/>
    <xsd:attribute name="pos_y" type="xsd:int" use="required"/>
    <xsd:attribute name="pos_z" type="xsd:int" use="required"/>
    <xsd:attribute name="orientation" type="direction" use="required"/>
  </xsd:complexType>
  
  <xsd:simpleType name="direction">
    <xsd:restriction base="xsd:string">
      <xsd:enumeration value="x"/>
      <xsd:enumeration value="y"/>
      <xsd:enumeration value="z"/>
    </xsd:restriction>
  </xsd:simpleType>
  
</xsd:schema>
Dateianhänge
grid.xsd.txt
wieder mit .txt Ergänzung...
(1.86 KiB) 59-mal heruntergeladen
... und morgen gehts weiter.

Benutzeravatar
H2k
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 27. Okt 2004 16:48
Wohnort: Langen
Kontaktdaten:

Re: Aufgabenstellung WS 08/09

Beitrag von H2k » 10. Nov 2008 22:38

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.
Soll die Benutzeroberfläche auch fünf- bis sechsstelligen Knotenzahlen "sinnvoll" darstellen können, oder reicht es wenn man 2-3-stellige Dimension darstellen kann.

patrik_s.stud.tu
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 12. Okt 2006 20:56

Re: Aufgabenstellung WS 08/09

Beitrag von patrik_s.stud.tu » 11. Nov 2008 09:10

Wir hatten gestern ein Gespraech mit Weihe aus dem hervorging, dass wir auch solche Knotenmengen 'sinnvoll' darstellen sollen. Insgesamt wird relativ viel Wert auf die Oberflaeche gelegt.
Mindestanforderungen: sinnvolle Darstellung von 5-6 stelligen Knotenmengen, eine rudimentaere Bedienung fuer die Uebersicht (Rotation, Translation, Selektierung von angezeigten Terminalmengen), einige Metriken fuer die Analyse

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Aufgabenstellung WS 08/09

Beitrag von Prof. Karsten Weihe » 11. Nov 2008 10:27

patrik_s.stud.tu hat geschrieben:Wir hatten gestern ein Gespraech mit Weihe aus dem hervorging, dass wir auch solche Knotenmengen 'sinnvoll' darstellen sollen. Insgesamt wird relativ viel Wert auf die Oberflaeche gelegt.
Ja, absolut!

Ich hoffe, das ist bei der Vorbesprechung herübergekommen!?


patrik_s.stud.tu hat geschrieben: Mindestanforderungen: sinnvolle Darstellung von 5-6 stelligen Knotenmengen, eine rudimentaere Bedienung fuer die Uebersicht (Rotation, Translation, Selektierung von angezeigten Terminalmengen),
Lassen Sie sich davon leiten, was Sie als Nutzer eines solchen Tools gerne haben möchten, damit die interaktive Edierung von Netzen möglichst bequem ist. Das wird später eine wesentliche Aufgabe für Sie sein, an den Endnutzer (unter Informatikern oft fälschlich "Dumm-User" o.ä. genannt) mitzudenken!

Wie schon mehrfach gesagt - und schon von einigen Kommilitonen genutzt: Ich biete an, dass wir lange vor der Endabnahme darüber reden, und ich erwarte sogar, dass Sie auf mich zukommen.

patrik_s.stud.tu hat geschrieben: einige Metriken fuer die Analyse
Nanu, was soll ich da als Mindestabnforderung vorgegeben haben :?: :shock: :wink:

Gruß,

KW

patrik_s.stud.tu
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 12. Okt 2006 20:56

Re: Aufgabenstellung WS 08/09

Beitrag von patrik_s.stud.tu » 11. Nov 2008 12:45

Naja es kam zumindest rueber, dass Metriken wie:
laengster Pfad
warum dieser laenger geworden ist
oder aehnliches als 'sinnvoll' betrachtet werden.

War jetzt aber nicht der Muss-Faktor^^

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Aufgabenstellung WS 08/09

Beitrag von Prof. Karsten Weihe » 11. Nov 2008 12:52

patrik_s.stud.tu hat geschrieben:Naja es kam zumindest rueber, dass Metriken wie:
laengster Pfad
warum dieser laenger geworden ist
oder aehnliches als 'sinnvoll' betrachtet werden.

War jetzt aber nicht der Muss-Faktor^^
Ok, ich denke, Sie werden mir zustimmen, dass wir besser sorgfältigst zwischen "als 'sinnvoll' betrachtet" und "Mindestanforderung" unterscheiden. :wink:

Gruß,

KW

Antworten

Zurück zu „Praktikum: Algorithmen“