Ramsey@Home (beendet)

Aus Rechenkraft
Wechseln zu: Navigation, Suche
Logo
Man sieht: R(3,3) muss größer als 5 sein.

Das Projekt sucht neue untere Schranken für Ramsey Zahlen.

Es werden vollständige Graphen auf die Existenz von bestimmten Untergraphen untersucht. Die Existenz ist hierbei leicht zu zeigen. Die Frage, ab welcher Größe eines Graphen diese Untergraphen auftreten müssen ist schwerer und wird hier untersucht.

Gesucht wird eine bessere (also höhere) untere Schranke für die Ramsey-Zahl R(3,3,3,3,3).

Veranschaulichen wir R(3,3) einmal. R(3,3) ist anschaulich die Zahl von Leuten, die man auf eine Feier einladen muss, so dass sich immer mindestens 3 Leute untereinander kennen, oder mindestens 3 Leute untereinander nicht kennen.

  • R(3,3)>3, denn bei drei Leuten A,B,C können sich zum Beispiel nur A und B kennen
  • R(3,3)>4, denn bei vier Leuten A-D können sich z.B. nur A&B und C&D kennen. Es kennen sich hier 2 Leute untereinander nicht (z.B A&C und A&D), und 2 kennen sich
  • R(3,3)>5, denn es lässt sich eine Gruppe von 5 Leuten konstuieren (siehe Bild), so dass sich nur maximal 2 Leute gegenseitig kennen (rote Verbindungen) und maximal 2 Leute nicht kennen (blaue Verbindungen).
  • R(3,3)=6. Für jede beliebige Sechsergruppe existiert eine Untergruppe von mindestens 3 Leute, die sich untereinander kennen, oder eben nicht kennen. Das bedeutet für ein analoges Bild, dass man ein einfarbiges Dreieck findet (finden muss).

Betrachtet man statt R(3,3) jetzt R(3,3,3), so kann muss man sich das eine dritte Eigenschaft vorstellen, also z.B. hat gehört von. Für die Suche nach R(3,3,3,3,3) zwei weitere Eigenschaften. Das Projekt benutzt daher einen Zusammenhang zwischen solchen Eigenschaften in Graphen und summenfreien Mengen.

Ein Paper von Exoo zeigt R(3,3,3,3,3) >= S(5) + 2. Weiter zeigte Exoo, dass S(5) >= 160 gilt, woraus folgt R(3,3,3,3,3) >= 162. Das Projekt sucht jetzt also nach einer Verteilung der Zahlen 1-162 in 5 summenfreien Mengen. Die bisher beste Lösung kann man sich auf der Homepage anschauen.

Man benutzt hier eine heuristische Suche durch die möglichen 5162 Mengen, die auftreten können. Ein Bruteforce-Ansatz ist bei dieser Größe ausgeschlossen.

Siehe Satz von Ramsey.

Ende 2008 wurde das Projekt erstmal gestoppt, da man mit der bisherigen Anwendung keine wirklichen Fortschritte mehr machen konnte. Die Seite ist momentan nicht erreichbar.


Inhalt

Projektübersicht

InfoIcon.png Ramsey
Name Ramsey
Kategorie Mathematik
Ziel Minimieren von Ramsey Zahlen
Kommerziell   nein
Homepage ramseyathome.com/ramsey


 
United States01.gif    Dieses Projekt wird in Wisconsin, USA durchgeführt.


Projektstatus

InfoIcon.png Projektstatus
Status   beendet
Beginn 14.06.2008
Ende 2008

Projektlinks

Neuigkeiten (RSS-Feed)

Statistiken

Wo Übersicht Top Teams Top User
Projekt Home Page Top Teams Top User
BOINCstats.com Übersicht Top Teams Top User
BOINCsynergy.com: Der Service wurde eingestellt.
stats.free-dc.org Übersicht Top Teams Top User
allprojectstats.com: Der Service wurde eingestellt.

Clientprogramm

Betriebssysteme

Icon windows 16.png   Windows Checkbox 1.gif  
Icon windows 16.png   Windows 64bit Checkbox 1.gif  
Icon linux 16.png   Linux Checkbox 1.gif  
Icon linux 16.png   Linux 64bit Checkbox 1.gif  
Icon dos 16.png   DOS Checkbox 0.gif  
Icon macos 16.png   MacOS X Checkbox 1.gif  
Icon freebsd 16.png   BSD Checkbox 0.gif  
Icon solaris 16.png   Solaris Checkbox 0.gif  
Icon java 16.png   Java (betriebssystemunabhängig)  Checkbox 0.gif  

Client-Eigenschaften

Funktioniert auch über Proxy Checkbox 1.gif
Normal ausführbares Programm Checkbox 1.gif
Als Bildschirmschoner benutzbar Checkbox 1.gif
Kommandozeilenversion verfügbar Checkbox 1.gif
Personal Proxy für Work units erhältlich   Checkbox 0.gif
Work units auch per Mail austauschbar Checkbox 0.gif
Quellcode verfügbar Checkbox 1.gif
Auch offline nutzbar Checkbox 1.gif
Checkpoints Checkbox 1.gif

Dies und das

  • Im Herbst 2008 wurde entschieden keine Credits mehr zu vergeben. Dazu entschied sich der Projektbetreiber, nachdem er bis zu 80% seiner Zeit ins Creditsystem zu stecken.

Installation

Ramsey@Home (beendet) benutzt die BOINC-Infrastruktur. Die Anmeldung, Installation und Konfiguration sind auf der allgemeinen BOINC-Seite beschrieben.


Veröffentlichte Versionen

  • 20.09.2008: 1.12 erste MacOS X-Version
  • 17.09.2008: 1.03 erste Linux-Version

Die neuesten Anwendungen findet man hier.

Screenshots

Bisher zeigt der Client noch keine eigenen Grafiken bei der Berechnung an, die allgemeinen BOINC-Screenshots zeigen aber, wie der Client arbeitet. Wenn BOINC als Bildschirmschoner läuft, wird bei diesem Projekt das BOINC-Logo angezeigt.



Eigene Werkzeuge