Rectilinear Crossing Number

Aus SETI.Germany Wiki

Homepage	http://dist.ist.tugraz.at/cape5/
Forum	http://dist.ist.tugraz.at/cape5/forum_index.php
Kurzbeschreibung	Rectilinear Crossing Numbers (RCN / oder auch Cape5) ist das derzeit aktive Distributed Computing Projekt des Instituts für Softwareentwicklung der TU Graz. Es werden Probleme der rechnerischen und kombinatorischen Geometrie untersucht. Ausführlichere deutsche Projektbeschreibung hier.
Betriebssysteme
WU-Größe & Laufzeit	Workunit-Größe & Laufzeit
Bildschirmschoner	vorhanden
Checkpointing	vorhanden
Serverstatusabfrage	RCN
Status	Beta
Teamstatistik	Rectilinear Crossing Numbers BOINCStats BOINCSynergy SETI.Germany-Statistikseiten
Team beitreten	JOIN SETI.Germany
Team-Founder	RealSanta
Projekt-Thread im SG-Forum	http://board.setigermany.de/forumdisplay.php?f=38

[bearbeiten] Laufzeiten

[bearbeiten] Das Rectilinear Crossing Number Projekt (RCN)

Bei diesem Mathematik-Projekt aus dem Bereich der kombinatorischen Geometrie beschäftigt man sich mit der Suche nach der kleinsten Anzahl von Kreuzungen eines Graphen von n-Punkten mit geraden Linien als Kanten. Dabei sollen keine drei Punkte auf einer gemeinsamen Linie liegen.

Für eine kleine Anzahl von Punkten ist dieses Problem, was u.a. in der Optimierung von Transportproblemen und z.B. auch im Print-Layout eine Rolle spielt, relativ leicht auflösbar. Nachfolgende Grafik verdeutlicht das z.B. für 5 Punkte

Für größere Punktmengen ist es aber sehr schwer, die beste Konfiguration zu ermitteln, da die Anzahl der kombinatorisch verschiedenen Arten, diese Punkte anzuordnen, exponentiell wächst. Zum Beispiel gibt es für n=11 Punkte bereits 2.334.512.907 verschiedene Möglichkeiten.

Hier die Ergebnisse der Kreuzungszahlen:

K(12) = 153, K(13) = 229, K(14) = 324, K(15) = 447, K(16) = 603 und K(17) = 798

K(19) = 1318 und K(21) = 2055

Im Dezember des Jahres 2006 ist es schließlich gelungen, mit einer weltweiten Computerkapazität von 10.000 CPU-Stunden pro Tag auch die Kreuzungszahl für Graphen mit 18 Knoten zu berechnen. Sie beträgt, wie im Januar 2007 rechnerisch bestätigt worden ist, 1029.

Das Projekt RCN berechnet daher zurzeit den Graph für n=20.

Dabei ist aktuell (Anfang Juli 2009) die W7er-Serie beendet worden und die W8er-Serie am Start ...

[bearbeiten] verfügbare Anwendungen

Aktuell sind die TCAPE Crossing Number-Apps "tcape-crossing 5.63" für Win, "5.59" für Linux und "5.61" Mac. Eine 64bit-Version wird seit 03.März 2008 neben Linux ("5.53") nun auch für Windows angeboten ("5.54")! Die maximale Laufzeit beträgt im Moment für die Serie W8 24h.

Ein Bildschirmschoner (Grafik) ist seit 24.01.2008 integriert! (wurde projektseitig aber wieder temporär akti- bzw. deaktiviert)

[bearbeiten] Einige interessante Links von der Projektseite

• Projekt-Webseite: http://dist.ist.tugraz.at/cape5/
• RCN-Forum hier auf SG: http://board.setigermany.de/forumdisplay.php?f=38
• Das RCN-Forum: http://dist.ist.tugraz.at/cape5/forum_index.php