Rectilinear Crossing Number - Wir haben Team hier

indiana_74

Moderator
☆☆☆☆☆☆
Mitglied seit
24.02.2006
Beiträge
8.178
Renomée
481
Standort
in der Hauptstadt
  • SIMAP Race
  • QMC Race
  • RCN Russia
  • Spinhenge ESL
  • Docking@Home
  • BOINC Pentathlon 2011
  • BOINC Pentathlon 2012
  • BOINC Pentathlon 2013
  • BOINC Pentathlon 2014
  • BOINC Pentathlon 2015
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.

crossings.gif


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!
p3d_RCN.png
 
nix für ungut, danke @ indy für den Hinweis, aber das projekt hört sich ja super langweilig an.... *suspect*

Gruß,

Sysfried
 
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.*great*

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. :o
 
Zuletzt bearbeitet:
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. ;D ;)
 
1-2 Minuten WUs? Dann sollten wir da nicht crunchen. Das schiesst nur den Server über den Jordan.

Oder vielleicht doch, dann machen wir uns halt den Ruf, das wir Server zerschießen;D*suspect* , 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
 
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;D



Gruß

D.U.
 
Wir haben bereits 10 Mitglieder

Los Leute, einer geht noch!

*party2* *party* *party2* Heute ist der 11.11. *party* *party2* *party*

wo bleibt der 11´te ;D *rofl*
 
Wir haben bereits 10 Mitglieder

Los Leute, einer geht noch!

*party2* *party* *party2* Heute ist der 11.11. *party* *party2* *party*

wo bleibt der 11´te ;D *rofl*


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? ;D


Edit: Jetzt gehts doch. Sehr komisch das ganze...
 
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.
 
Nanü nana,
Team Norway ist ja nur noch im Rückspiegel zu sehen;D

Beim RAC jetzt schon Platz 15

beim Top-Credit jetzt Platz 45


Gruß

D.U.
 
Das geht ganz schön fix hier ;D
 
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
 
Blöde Frage im anderen Tread*suspect* ob ihr ein Team bei RCN habt - Klar wo eigendlich nicht ;D

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. ;D
 
Blöde Frage im anderen Tread*suspect* ob ihr ein Team bei RCN habt - Klar wo eigendlich nicht ;D

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. ;D


Lahmen Wagen? Na hör mal! Ausserdem: Sieh zu, dass Du deinen Hintern komplett rüberschwingst! ;)
 
@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;D
Lass ihm mit dem schwingen Zeit, er hat uns doch schon lieb gewonnen*buck*



Gruß

D.U.
 
13 sec für eine WU????? Naja vielleicht bessert sich das ja noch. :)
 
Aber mal was anderes, ich könnte wetten das er Dich bei RCN überholt bis es bei Spinhenge wieder losgeht;D


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. ;)
 
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*noahnung*



Gruß

D.U.
 
Na mit eiener solchen Einstellung kann das ja auch nix werden . :]

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.
 
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.
 
Zurück
Oben Unten