Rectilinear Crossing Number - Wir haben Team hier
- Ersteller indiana_74
- Erstellt am
indiana_74
Moderator
☆☆☆☆☆☆
Das Rectilinear Crossing Number Projekt
http://dist.ist.tugraz.at/cape5/
Viele Fragen der rechnerischen und kombinatorischen Geometrie basieren auf endlichen Punktmengen in der euklidschen Ebene. Etliche Probleme aus der Graphentheorie passen ebenfalls in dieses Schema, bei dem Kanten auf gerade Linien beschränkt werden. Eine typische Frage ist das prominente Problem der Rectilinear Crossing Number (das z.B. mit Transportproblemen und der Optimierung von Print-Layouts in Zusammenhang steht): Was ist die kleinste Anzahl von Kreuzungen, die der vollständige Graph von n Punkten aufweist, wenn die Kanten als gerade Linien gezeichnet werden? Dazu gilt die Annahme, daß keine drei Punkte auf einer gemeinsamen Linie liegen.
Es ist leicht zu sehen, daß wir vier Punkte so anordnen können, daß keine Kreuzung von Linien entsteht. Für fünf Punkte zeigt die Abbildung verschiedene Arten, sie anzuordnen. Das sind alles verschiedene Order Types (Goodman und Pollack, 1983). Wenn man fünf Punkte in konvexer Lage anordnet, dann ergeben sich fünf Kreuzungen. Das beste was man tun kann ist, den Graph so anzuordnen, daß man nur eine Kreuzung erhält. Es gibt keinen Weg, den vollständigen Graphen von fünf Punkten ohne Kreuzungen zu zeichnen, auch nicht wenn man Kurven als Kanten erlauben würde. Übrigens, es ist leicht, die Anzahl der Kreuzungen zu maximieren: Man plaziert einfach alle n Punkte auf einem Kreis und erhält so die Maximalanzahl von (n über 4) Kreuzungen.
Fuer größere Punktmengen ist es sehr schwer, die beste Konfiguration zu ermitteln. Der Hauptgrund ist die Anzahl der kombinatorisch verschiedenen Arten, diese Punkte anzuordnen. Sie wächst nämlich exponentiell. Zum Beispiel gibt es für n=11 Punkte bereits 2.334.512.907 verschiedene Moeglichkeiten.
Die bemerkenswerte Jagd auf Crossing Numbers des vollständigen Graphen wurde in den 60er Jahren von R. Guy eröffnet. Bis zum Jahr 2000 waren nur Werte fuer n<=9 bekannt. Im Jahr 2001 wurde das Problem fuer n=10 geloest und im Jahr 2004 fuer n=11. Das Hauptziel des gegenstaendlichen Projekts ist die Verwendung ausgekluegelter mathematischer Methoden (abstrake Order-Type-Erweiterung), um die Rectilinear Crossing Number fuer kleine Werte von n zu bestimmen. Bis jetzt waren wir erfolgreich für n <= 17. Aus jüngsten (noch nicht einmal veröffentlichten) Forschungsergebnissen weiß man die Rectilinear Crossing Number für n=19 und für n=21. Daher ist das spannendste Problem zur Zeit die Bestimmung des richtigen Wertes für n=18, was das Hauptziel dieses Projekts ist.
Unser Team
Unser Team bei diesem Projekt ist noch ein sehr junges Team (3 Mitglieder) und dem entsprechend liegen wir bei den Platzierungen auch noch ziemlich weit hinten.
RAC = Platz 87
Top Credit = Platz 85
Da aber das gesamte Projekt noch sehr jung ist, ist der Abstand zum führenden Team nur etwa 213.000 Credits und damit nicht in unerreichbarer Ferne.
Wer sich also für das Team interessiert oder einfach unser Team ein wenig unterstützen möchte, kann hier
Mitglied im Team werden: http://dist.ist.tugraz.at/cape5/create_account_form.php?teamid=249
Das passende Signaturbanner gibt es auch schon!
http://dist.ist.tugraz.at/cape5/
Viele Fragen der rechnerischen und kombinatorischen Geometrie basieren auf endlichen Punktmengen in der euklidschen Ebene. Etliche Probleme aus der Graphentheorie passen ebenfalls in dieses Schema, bei dem Kanten auf gerade Linien beschränkt werden. Eine typische Frage ist das prominente Problem der Rectilinear Crossing Number (das z.B. mit Transportproblemen und der Optimierung von Print-Layouts in Zusammenhang steht): Was ist die kleinste Anzahl von Kreuzungen, die der vollständige Graph von n Punkten aufweist, wenn die Kanten als gerade Linien gezeichnet werden? Dazu gilt die Annahme, daß keine drei Punkte auf einer gemeinsamen Linie liegen.
Es ist leicht zu sehen, daß wir vier Punkte so anordnen können, daß keine Kreuzung von Linien entsteht. Für fünf Punkte zeigt die Abbildung verschiedene Arten, sie anzuordnen. Das sind alles verschiedene Order Types (Goodman und Pollack, 1983). Wenn man fünf Punkte in konvexer Lage anordnet, dann ergeben sich fünf Kreuzungen. Das beste was man tun kann ist, den Graph so anzuordnen, daß man nur eine Kreuzung erhält. Es gibt keinen Weg, den vollständigen Graphen von fünf Punkten ohne Kreuzungen zu zeichnen, auch nicht wenn man Kurven als Kanten erlauben würde. Übrigens, es ist leicht, die Anzahl der Kreuzungen zu maximieren: Man plaziert einfach alle n Punkte auf einem Kreis und erhält so die Maximalanzahl von (n über 4) Kreuzungen.
Fuer größere Punktmengen ist es sehr schwer, die beste Konfiguration zu ermitteln. Der Hauptgrund ist die Anzahl der kombinatorisch verschiedenen Arten, diese Punkte anzuordnen. Sie wächst nämlich exponentiell. Zum Beispiel gibt es für n=11 Punkte bereits 2.334.512.907 verschiedene Moeglichkeiten.
Die bemerkenswerte Jagd auf Crossing Numbers des vollständigen Graphen wurde in den 60er Jahren von R. Guy eröffnet. Bis zum Jahr 2000 waren nur Werte fuer n<=9 bekannt. Im Jahr 2001 wurde das Problem fuer n=10 geloest und im Jahr 2004 fuer n=11. Das Hauptziel des gegenstaendlichen Projekts ist die Verwendung ausgekluegelter mathematischer Methoden (abstrake Order-Type-Erweiterung), um die Rectilinear Crossing Number fuer kleine Werte von n zu bestimmen. Bis jetzt waren wir erfolgreich für n <= 17. Aus jüngsten (noch nicht einmal veröffentlichten) Forschungsergebnissen weiß man die Rectilinear Crossing Number für n=19 und für n=21. Daher ist das spannendste Problem zur Zeit die Bestimmung des richtigen Wertes für n=18, was das Hauptziel dieses Projekts ist.
Unser Team
Unser Team bei diesem Projekt ist noch ein sehr junges Team (3 Mitglieder) und dem entsprechend liegen wir bei den Platzierungen auch noch ziemlich weit hinten.
RAC = Platz 87
Top Credit = Platz 85
Da aber das gesamte Projekt noch sehr jung ist, ist der Abstand zum führenden Team nur etwa 213.000 Credits und damit nicht in unerreichbarer Ferne.
Wer sich also für das Team interessiert oder einfach unser Team ein wenig unterstützen möchte, kann hier
Mitglied im Team werden: http://dist.ist.tugraz.at/cape5/create_account_form.php?teamid=249
Das passende Signaturbanner gibt es auch schon!
indiana_74
Moderator
☆☆☆☆☆☆
Etwas langweilig vielleicht aber dafür mit umso mehr Potential!
Beim RAC jetzt Platz 40
beim Top-Credit jetzt Platz 69
Der Dank hierfür geht vor allem an
Stephan G.
Nicht zu verachten ist auch die Tatsache, dass die WU´s hier extrem kurz sind.
Die längste die ich je hatte (auf einem XP 3000+) dauerte gerade mal 26 Minuten und brachte 9.5 Credits.
Meistens dauern die WU´s nur 2-3 Minuten und bringen im Schnitt 1-2 Credits.
Beim RAC jetzt Platz 40
beim Top-Credit jetzt Platz 69
Der Dank hierfür geht vor allem an
Stephan G.
Nicht zu verachten ist auch die Tatsache, dass die WU´s hier extrem kurz sind.
Die längste die ich je hatte (auf einem XP 3000+) dauerte gerade mal 26 Minuten und brachte 9.5 Credits.
Meistens dauern die WU´s nur 2-3 Minuten und bringen im Schnitt 1-2 Credits.
Zuletzt bearbeitet:
Ole
Grand Admiral Special
- Mitglied seit
- 25.01.2003
- Beiträge
- 10.319
- Renomée
- 218
1-2 Minuten WUs? Dann sollten wir da nicht crunchen. Das schiesst nur den Server über den Jordan.
Ausserdem sollen die Mathematiker mal schön alleine weiter in ihren eigenen kleinen Welt leben und irgendwelchen nicht nachvollziehbaren Problemchen hinterherhecheln.
Ausserdem sollen die Mathematiker mal schön alleine weiter in ihren eigenen kleinen Welt leben und irgendwelchen nicht nachvollziehbaren Problemchen hinterherhecheln.
indiana_74
Moderator
☆☆☆☆☆☆
unterstudienrat
Moderator (DC)
☆☆☆☆☆☆
Oder vielleicht doch, dann machen wir uns halt den Ruf, das wir Server zerschießen
, das wäre ja nicht der erste.8) Wir habe sozusagen schon etwas Erfahrung damit
Gruß
D.U.
P.S.: Hab mich dann mal angemeldet
- Mitglied seit
- 11.11.2001
- Beiträge
- 9.624
- Renomée
- 452
- Standort
- Bayern, am Rande des Wahnsinns
dito, ich hab mir mal ein paar auf meinen X2 gezogen, und gleich die erste war eine ausgesprochene Monster WU: http://dist.ist.tugraz.at/cape5/result.php?resultid=1550118 knapp 9800 Sek!
die anderen waren dafür mit teilweise unter 30 sek. fast schon ein witz
die anderen waren dafür mit teilweise unter 30 sek. fast schon ein witz
unterstudienrat
Moderator (DC)
☆☆☆☆☆☆
Beim RAC jetzt schon Platz 19
beim Top-Credit jetzt Platz 57
Und das nur einen Tag nachdem Indiana gemeldet hatte RAC Platz 40 und Top-Credit Platz 69.
Wage mir nicht vorzustellen, wenn wir hier tatsächlich ein Advents-Race machen, wie BOINC.be sich fühlen muß wenn wir von hinten angerauscht kommen
Gruß
D.U.
beim Top-Credit jetzt Platz 57
Und das nur einen Tag nachdem Indiana gemeldet hatte RAC Platz 40 und Top-Credit Platz 69.
Wage mir nicht vorzustellen, wenn wir hier tatsächlich ein Advents-Race machen, wie BOINC.be sich fühlen muß wenn wir von hinten angerauscht kommen
Gruß
D.U.
indiana_74
Moderator
☆☆☆☆☆☆
Wir haben bereits 10 Mitglieder
Los Leute, einer geht noch!
Heute ist der 11.11.
wo bleibt der 11´te 
Los Leute, einer geht noch!
Heute ist der 11.11. wo bleibt der 11´te
Ole
Grand Admiral Special
- Mitglied seit
- 25.01.2003
- Beiträge
- 10.319
- Renomée
- 218
Wir haben bereits 10 Mitglieder
Los Leute, einer geht noch!
wo bleibt der 11´te
Nee, geht leider nicht, da ich kein Konto erstellen kann.
Auf der HP steht irgendwas von "neuem Server". Hat es was damit zu tun? Und wer zur Hölle hat denen erzählt, dass wir den Server sprengen wollten?
Edit: Jetzt gehts doch. Sehr komisch das ganze...
unterstudienrat
Moderator (DC)
☆☆☆☆☆☆
Noch 1841 Punkte und wir klopfen bei guten Bekannten (Team Norway) an, mit viel Glück schaffen wir das bei der derzeitigen mit Anzahl an aktiven PC's (10 Stück) in den nächsten 12 Stunden.
Gruß
D.U.
Gruß
D.U.
unterstudienrat
Moderator (DC)
☆☆☆☆☆☆
Nanü nana,
Team Norway ist ja nur noch im Rückspiegel zu sehen
Beim RAC jetzt schon Platz 15
beim Top-Credit jetzt Platz 45
Gruß
D.U.
Team Norway ist ja nur noch im Rückspiegel zu sehen
Beim RAC jetzt schon Platz 15
beim Top-Credit jetzt Platz 45
Gruß
D.U.
indiana_74
Moderator
☆☆☆☆☆☆
Das geht ganz schön fix hier
The_Lynx
Commodore Special
so muss das sein^^
ich versuch heut noch ein bisschen überzeugungsarbeit per "stromrechnungsmehrbezahlung" bei meinem mitbewohner zu leisten, das er mir drei p4s "sponsort".
2,8; 3,0 u. 3,2ghz dürften doch als zusätzliche kavallerie genügen, oder?
mfg Roman
ich versuch heut noch ein bisschen überzeugungsarbeit per "stromrechnungsmehrbezahlung" bei meinem mitbewohner zu leisten, das er mir drei p4s "sponsort".
2,8; 3,0 u. 3,2ghz dürften doch als zusätzliche kavallerie genügen, oder?
mfg Roman
H2o-Cooler
Lt. Commander
Blöde Frage im anderen Tread ob ihr ein Team bei RCN habt - Klar wo eigendlich nicht
Ich werde euch vorübergehend mal unterstützen . Bei uns wird sowas nicht gecruncht.
Bei mir warten 3 PC´s auf Arbeit( X2 3800 - AM2 2800 Sempron - Sempron 2800 ( Sockel 7) )
Solange bei Spinhenge nix zu tun gibt schiebe ich euren lahmen Wagen mal mit an.
ob ihr ein Team bei RCN habt - Klar wo eigendlich nicht Ich werde euch vorübergehend mal unterstützen . Bei uns wird sowas nicht gecruncht.
Bei mir warten 3 PC´s auf Arbeit( X2 3800 - AM2 2800 Sempron - Sempron 2800 ( Sockel 7) )
Solange bei Spinhenge nix zu tun gibt schiebe ich euren lahmen Wagen mal mit an.
Ole
Grand Admiral Special
- Mitglied seit
- 25.01.2003
- Beiträge
- 10.319
- Renomée
- 218
Blöde Frage im anderen Tread
Ich werde euch vorübergehend mal unterstützen . Bei uns wird sowas nicht gecruncht.
Bei mir warten 3 PC´s auf Arbeit( X2 3800 - AM2 2800 Sempron - Sempron 2800 ( Sockel 7) )
Solange bei Spinhenge nix zu tun gibt schiebe ich euren lahmen Wagen mal mit an.
Lahmen Wagen? Na hör mal! Ausserdem: Sieh zu, dass Du deinen Hintern komplett rüberschwingst!
unterstudienrat
Moderator (DC)
☆☆☆☆☆☆
@Ole,
nimmst H2o nicht übel er wußte bis eben noch nicht das wir da ein Team haben.
Und was er wohl auch nicht mitbekommen hat, ist das wir in 2 Tagen ~30 Plätze gutgemacht haben
Aber mal was anderes, ich könnte wetten das er Dich bei RCN überholt bis es bei Spinhenge wieder losgeht
Lass ihm mit dem schwingen Zeit, er hat uns doch schon lieb gewonnen
Gruß
D.U.
nimmst H2o nicht übel er wußte bis eben noch nicht das wir da ein Team haben.
Und was er wohl auch nicht mitbekommen hat, ist das wir in 2 Tagen ~30 Plätze gutgemacht haben
Aber mal was anderes, ich könnte wetten das er Dich bei RCN überholt bis es bei Spinhenge wieder losgeht
Lass ihm mit dem schwingen Zeit, er hat uns doch schon lieb gewonnen
Gruß
D.U.
unterstudienrat
Moderator (DC)
☆☆☆☆☆☆
Andere Leute findes es gut, aber Du kannst beruhigt sein meine Längste hatte 18.000sec.13 sec für eine WU?? Naja vielleicht bessert sich das ja noch.
Gruß
D.U.
H2o-Cooler
Lt. Commander
Lahmen Wagen? Na hör mal! Ausserdem: Sieh zu, dass Du deinen Hintern komplett rüberschwingst!
NE NE ich bleibe nur Gast - wenn es bei Spinhenge wieder los geht bin ich weg.
Ole
Grand Admiral Special
- Mitglied seit
- 25.01.2003
- Beiträge
- 10.319
- Renomée
- 218
Aber mal was anderes, ich könnte wetten das er Dich bei RCN überholt bis es bei Spinhenge wieder losgeht
Da habe ich keine Zweifel. Ich crunche das nämlich nicht mehr. Ohne Checkpointing und vollkommen zufälliger Länge ist dieses Projekt für mich ziemlich sinnlos.
Hatte den Rechner ausnahmsweise heute Nacht an um den Kram zu Ende zu kriegen. Das passiert sonst garantiert nicht.
unterstudienrat
Moderator (DC)
☆☆☆☆☆☆
Beim RAC jetzt schon Platz 10
beim Top-Credit jetzt Platz 40
und 5 neue Mitchruncher, wobei der 5te sich noch nicht zu erkennen gegeben hat
Gruß
D.U.
beim Top-Credit jetzt Platz 40
und 5 neue Mitchruncher, wobei der 5te sich noch nicht zu erkennen gegeben hat
Gruß
D.U.
H2o-Cooler
Lt. Commander
Ole
Grand Admiral Special
- Mitglied seit
- 25.01.2003
- Beiträge
- 10.319
- Renomée
- 218
Na mit eiener solchen Einstellung kann das ja auch nix werden .![:]](https://www.planet3dnow.de/vbulletin/images/smilies/rolleyes.gif "Augen rollen (sarkastisch) :]")
Das ist mein normaler Rechner, der auch für andere Sachen genutzt wird. 24/7 läuft der wenn dann nur für die Kav..
Strom ist mir zu teuer um das Ding hier 24/7 heizen zu lassen; ausserdem beende ich den Boinc Client oft. Zum Beispiel fürs daddeln usw. und wenn er dann grad stundenlang an einer WU ohne Checkkpointing gecruncht hat, finde ich es ziemlich sinnlos sowohl das ganze Ergebnis wegzuschmeissen als auch dasselbe nochmal zu berechnen. Deswegen ist das Projekt halt nichts für mich.
- Mitglied seit
- 11.11.2001
- Beiträge
- 9.624
- Renomée
- 452
- Standort
- Bayern, am Rande des Wahnsinns
mal ganz davon abgesehen das ich dieses Projekt auch eher für ein "Spaßprojekt" halte, da ein praktischer Nutzen IMHO nicht zu erkennen ist, muss ich Ole zustimmen, ohne Checkpointing und gleichmäßigen WUs ist das ziemlich Witzlos, wenn man nicht wirklich 24/7 cruncht.
Deshalb: auch bei mir: Stop.
Deshalb: auch bei mir: Stop.
Ähnliche Themen
