RakeSearch

RakeSearch

Ziel:	Suche orthogonale Paare diagonaler Lateinischer Quadrate
Kategorie:	Mathematik
Homepage:	http://rake.boincfast.ru/rakesearch/
Status:	produktiv
Projektadressen
Serverstatus:	RakeSearch
Forum:	RakeSearch Forum
SETI.Germany
Team-Statistik:	RakeSearch
Teambeitritt:	SETI.Germany beitreten
Forenthread:	SETI.Germany Forum
Workunits
RakeBeta (beta test)
Bildschirmschoner:
Checkpoints:
RakeSearch
Frist:	7 Tage
Download:	3,95 MB
Arbeitsspeicher:	1,60 MB
Betriebssysteme:
Bildschirmschoner:
Checkpoints:

Es werden orthogonale Paare diagonaler Lateinischen Quadraten der Ordnung 9 gesucht.

Ein Lateinisches Quadrat ist eine Tabelle der Größe n x n, derart mit n Elementen der Menge M gefüllt, dass jede Zeile und jede Spalte der Tabelle jedes einzelne Element von M genau einmal enthält. Die Kantenlänge (also n) des Quadrats entspricht der Ordnung.

Ein diagonales Lateinisches Quadrat ist ein Lateinisches Quadrat, auf dessen Diagonalen die Elemente der Menge M auch jeweils nur einmalig vorkommen.

Zwei Lateinische Quadrate werden als orthogonal bezeichnet, wenn sämtliche Kombinationen der jeweiligen Feldbelegungen beider Quadrate unterschiedlich sind.

Statistik (Stand: 20.03.2019 23:19:01)
Platzierung:	5
Punkte:	339.996.496
%-Anteil SG:	7.19
Status Scheduler:	aktiv
WUs bereit:	16.207
WUs in Arbeit:	41.437
Wir überholen:	Ars Technica - 3 BOINC Confederation - 4 XtremeSystems - 12 SETI.USA - 27
überholt SG:	-

Grundlagen

Ein Lateinisches Quadrat ist eine Tabelle der Größe n x n, derart mit n Elementen der Menge M gefüllt, dass jede Zeile und jede Spalte der Tabelle jedes einzelne Element von M genau einmal enthält. Die Kantenlänge (also n) des Quadrats wird Ordnung oder Rang genannt. Der berühmte Mathematiker Leonhard Euler (1707-1783) beschäftigte sich u.a. mit diesen Quadraten. Er verwendte dabei lateinische (und griechische) Buchstaben, daher der Name. Heute werden für die Elemente der Menge M meist Zahlen oder Farben verwendet.

Bei einem diagonalen Lateinisches Quadrat kommen die Elemente der Menge M nicht nur in den einzelnen Zeilen und Spalten, sondern auch auf beiden Diagonalen jeweils nur einmalig vor.

Beispiele diagonaler Lateinischer Quadrate der Ordnung 4,5,6 und 7 (Quelle: Präsentation des Projektes durch Natalia Nikitina, Eduard Vatutin, Oleg Zaikin und Maxim Manzyuk am 30. August 2017 bei BOINC Fast):

Zwei Lateinische Quadrate werden orthogonal genannt, wenn alle Kombinationen der jeweiligen Feldbelegungen beider Quadrate unterschiedlich sind; auf Englisch orthogonal diagonal Latin square = ODLS. Die quadratische Tabelle der beiden zusammengeführten diagonalen Lateinischen Quadrate nennt man dann Griechisch-lateinisches oder Eulersches Quadrat.

Beispiel eines Paares diagonaler Lateinischer Quadrate der Ordnung 7, die zudem orthogonal sind (Quelle: Präsentation des Projektes durch Natalia Nikitina, Eduard Vatutin, Oleg Zaikin und Maxim Manzyuk am 30. August 2017 bei BOINC Fast):

‎

Unter den Lateinischen Quadraten der Ordnung 4 gibt es genau ein orthogonales Paar:

Und in der Ordnung 5 wurden zwei gefunden:

(Quelle: Präsentation des Projektes durch Natalia Nikitina, Eduard Vatutin, Oleg Zaikin und Maxim Manzyuk am 30. August 2017 bei BOINC Fast)

Für Lateinische Quadrate der Ordnung 6 existiert kein OLDS. Die Suche nach OLDS der Ordnungen 7 und 8 wurde von der Gruppe bereits durchgeführt, erste Ergebnisse werden nach ihrer Aussage für die Veröffentlichung vorbereitet.

Ziel

Für die Suche nach ODLS der Ordnung 9 wurde das BOINC-Projekt "RakeSearch" entwickelt. Man rechnete ursprünglich mit circa 10.500 Jahren CPU-Zeit für die vollständige Suche, wobei sich diese Schätzung durch bereits beobachtete "fraktale Effekte" sowie die Optimierung der Applikation noch deutlich verringern kann.

Über CluBORun, einem Tool zur Verknüpfung von Volunteer Computing und bereits existierenden Computer-Clustern, beteiligt sich das Karelian Research Center an dem Projekt.

Projektbeginn und -fortschritt

Projektstart: 14. September 2017

Fortschritt des Projektes:
1. Dezember 2018: 43,7%

Ergebnisse

Nachdem in der Anfangsphase des Projektes die gefundenen orthogonalen Paare in einer tabellarischen Form veröffentlicht wurden, haben die Projektadministratoren im weiteren Verlauf eine grafische Darstellungsform entwickelt, wobei die gefundenen Quadrate als Knotenpunkte dargestellt werden, während die orthogonalen Beziehungen zwischen den Quadraten als Linien erscheinen. Dadurch entstehen oft sehr eindrucksvolle und manchmal ausgesprochen schöne Grafiken. Allerdings stellt diese Form nur eine mögliche Art der Visualisierung der Berechnungsergebnisse des Projektes dar.

Link zur tabellarischen Ergebnisdarstellung
Link zur grafischen Ergebnisdarstellung

Optimierte Anwendungen

Optimierte Anwendungen gibt es bereits seit relativ kurzer Zeit nach dem Projektstart, sie verringern in den meisten Fällen die benötigte Zeit pro WU um mehrere Stunden! Man beachte die Ausführungen dazu in diesem Forumsthread des Projekts, in dem auch der Link zu den betriebssystem- und CPU-abhängigen Downloads bei Github enthalten ist.

Badges

Es gibt mindestens vier verschiedene Sorten von Badges.

1. Badges entsprechend der Gesamtzahl der errechneten Credits. Motive sind Tiere aus Karelien.

Igel ^{5.000 Credits}	Fledermaus ^{10.000 Credits}	Flughörnchen ^{20.000 Credits}	Eichhörnchen ^{25.000 Credits}	Feldhase ^{60.000 Credits}	Wiesel ^{100.000 Credits}	Nerz ^{200.000 Credits}	Waschbär ^{300.000 Credits}

Ladoga-Ringelrobbe ^{7.500.000 Credits}	Fuchs ^{10.000.000 Credits}	Wolf ^{15.000.000 Credits}	Luchs ^{25.000.000 Credits}	Hirsch ^{50.000.000 Credits}	Elch ^{75.000.000 Credits}	Bär ^{100.000.000 Credits}	Vielfraß ^{150.000.000 Credits}

2. Badges entsprechend des Monats, in dem man ein ODLS gefunden hat. Motive sind Pflanzen und Schmetterlinge aus Karelien.

											Eberesche ^{Dezember 2017}

Moltebeere ^{Januar 2018}	Kiefer ^{Februar 2018}	Schneeglöckchen ^{März 2018}	Huflattich ^{April 2018}	Kätzchenweide ^{Mai 2018}	Storchschnabel ^{Juni 2018}	Lupine ^{Juli 2018}	Pfauenauge ^{August 2018}	Steinpilz ^{September 2018}	Gelbes Blatt ^{Oktober 2018}	Zitronen-Täubling ^{November 2018}	Kranbeere ^{Dezember 2018}

Schneeflocke ^{Januar 2019}	Himbeere ^{Februar 2019}	Preiselbeere ^{März 2019}

3. Badges für Top-Positionen hinsichtlich der durchschnittlichen Credits.

Top 25%	Top 5%

4. Sonderbadges.

Erster Fund eines ODLS-Paares im Projekt	Fund eines ODLS-Paares im Startmonat des Projekts	Fund während Jubiläum der Bestätigung der Poincaré-Vermutung

Quellen/Links

Folien der Präsentation des Projektes am 30. August 2017 bei BOINC Fast (englisch, PDF)
Wikipedia über das Lateinische Quadrat
Wikipedia über das Griechisch-lateinische Quadrat
Wikipedia über die Poincaré-Vermutung
Karelian Research Center (englisch)