Praktikum 1

Moderator: Effiziente Graphenalgorithmen

Christian_
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 178
Registriert: 10. Apr 2009 16:30

Praktikum 1

Beitrag von Christian_ »

Hallo Herr Stille,

Ich habe ein paar Fragen zum Praktikum:
Könnten sie die MST Gewichte der großen Testgraphen veröffentlochen, damit ich vergleichen kann ob mein Graph korrekt it?
Ist es normal, dass man mit Java/JUNG 3/4 der Zeit zum einlesen des Graphen benötigt?
Dürfen wir davon ausgehen, dass das MST-Gewicht nicht größer als der Datentyp int ist?
Ist es in Ordnung, wenn wir Java7 verwenden?

Gruß
Christian
Zuletzt geändert von Christian_ am 15. Nov 2011 23:32, insgesamt 1-mal geändert.
Omnium rerum principia parva sunt. -Cicero

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: Praktikum 1

Beitrag von zimpfer »

MST1: 261159288
MST2: 1323900090
MST3: 1806814846

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Praktikum 1

Beitrag von Stille »

Guten Abend,
Christian_ hat geschrieben: Ist es normal, dass man mit Java/JUNG 3/4 der Zeit zum einlesen des Graphen benötigt?
Kommt drauf an, was man zum Einlesen verwendet. Ich würde Ihnen dringend empfehlen buffered readers zu verwenden. Andere Klassen sind teilweise extrem unperformant.
Christian_ hat geschrieben: Dürfen wir davon ausgehen, dass das MST-Gewicht nicht größer als der Datentyp int ist?
Siehe Antwort "MST Gewichte" oben.
Christian_ hat geschrieben: Ist es in Ordnung, wenn wir Java7 verwenden?
Wenn das salonfähig ist, habe ich nichts dagegen. Generell würde ich sagen: keine Betas, keine Prereleases, etc. Ist natürlich schwierig, da herstellerbedingt extrem unterschiedlich. Wichtig ist mir, dass Ihr Code in der vorgegebenen Laufzeit fehlerfrei läuft, und für uns einfach handhabbar ist.
Cicero hat geschrieben: Omnium rerum principia parva sunt.
Principiis obsta. (Ovid)
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Christian_
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 178
Registriert: 10. Apr 2009 16:30

Re: Praktikum 1

Beitrag von Christian_ »

Ok, diese werte habe ich auch
Omnium rerum principia parva sunt. -Cicero

Kai.S
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 10. Apr 2010 22:22

Re: Praktikum 1

Beitrag von Kai.S »

Hätte auch noch eine Frage:
Müssen wir Datenstrukturen aus den gegebenen Librarys verwenden, oder können wir auch eigene angepasste Strukturen schreiben?

Zusatz:
In der Aufgabe steht wir sollen in konstanter Zeit entscheiden können ob 2 Knoten zum selben blauen Baum gehören, und die Vereinigung so machen, dass die Laufzeit nicht über nlogn geht... Dürfen wir dann nicht in der Vorlesung angesprochene Datenstrukturen nutzen, die insgesamt deutlich bessere Laufzeiten hervorbringen, aber genau genommen keine konstante Zeit mehr bei der Entscheidung brauchen, sondern eher α(n)?

Zusatz2:
Dürfen wir wie es in den Beispieldaten der Fall ist davon ausgehen, dass die Knoten immer von 0 oder 1 an ohne Sprünge durchnummeriert sind?

Zusatz3:
Dürfen wir eine PriorityQueue Implementation benutzen oder müssten wir diese selbst implementieren? Und sollen wir einfüge/update/lösch-Operationen auf einem PriorityQueue als Zeit zum Sortieren anrechnen?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Praktikum 1

Beitrag von Stille »

Hallo,

entschuldigen Sie die späte Antwort, ich habe das Forum zwar abonniert, in regelmässigen Abständen setzt aber die Benachrichtigungsfunktion aus bis ich mich da aus und wieder eintrage, dann klappt es wieder.
Kai.S hat geschrieben:Hätte auch noch eine Frage:
Müssen wir Datenstrukturen aus den gegebenen Librarys verwenden, oder können wir auch eigene angepasste Strukturen schreiben?
Die Benutzung von Libraries ist optional.
Kai.S hat geschrieben: In der Aufgabe steht wir sollen in konstanter Zeit entscheiden können ob 2 Knoten zum selben blauen Baum gehören, und die Vereinigung so machen, dass die Laufzeit nicht über nlogn geht... Dürfen wir dann nicht in der Vorlesung angesprochene Datenstrukturen nutzen, die insgesamt deutlich bessere Laufzeiten hervorbringen, aber genau genommen keine konstante Zeit mehr bei der Entscheidung brauchen, sondern eher α(n)?
Sie meinen die Wurzelbäume? α(n) ist ja quasi konstant. Interessant wäre natürlich ein Vergleich der beiden angesprochenen Datenstrukturen.
Kai.S hat geschrieben: Zusatz2:
Dürfen wir wie es in den Beispieldaten der Fall ist davon ausgehen, dass die Knoten immer von 0 oder 1 an ohne Sprünge durchnummeriert sind?
Wenn es mit allen Testdatensätzen funktioniert, ist das ok.
Kai.S hat geschrieben: Zusatz3:
Dürfen wir eine PriorityQueue Implementation benutzen oder müssten wir diese selbst implementieren? Und sollen wir einfüge/update/lösch-Operationen auf einem PriorityQueue als Zeit zum Sortieren anrechnen?
In der Aufgabe steht genau, was Sie benutzen dürfen und was nicht. java.util.PriorityQueue<E> ist demnach z.B. benutzbar. Mit Sortieren ist hier nur das initiale Sortieren zu Beginn einiger Algorithmen gemeint, nicht PQ.insert/update/delete/etc...
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Kai.S
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 10. Apr 2010 22:22

Re: Praktikum 1

Beitrag von Kai.S »

Vielen Dank für die Antworten :)

Antworten

Zurück zu „Effiziente Graphenalgorithmen“