Ramsey@Home

• Domovská stránka projektu
• Stránka používateľa

Tím BOINC.SK

• Pridať sa k tímu BOINC.SK
• Tímové štatistiky

Projekt Ramsey@Home sa zaoberá Ramseyho teóriou. Základom tejto teórie je myšlienka hľadania usporiadania v náhodných konfiguráciách.

Typický výsledok v Ramseyho teórii začína s určitou matematickou štruktúrou, ktorá sa rozdelí na menšie časti. Otázka znie: aká veľká musí byť pôvodná štruktúra, aby aspoň jedna jej časť mala určenú zaujímavú vlastnosť?

Názorným príkladom je princíp holubníka: vieme, že n holubov býva v m priehradkach holubníka. Aké veľké má byť číslo n aby sme si boli istí že aspoň jedna priehradka obsahuje aspoň dvoch holubov?

Ďaľším príkladom je teorém o priateľoch a cudzincoch: na párty sa zabáva aspoň šesť ľudí. Každý pár sa navzájom buď pozná, alebo nie. V každom prípade sa dajú nájsť takí traja ľudia ktorí sa navzájom poznajú, alebo sú si úplne neznámi. Otázka môže znieť: koľko ľudí musí byť na párty, aby bola splnená podmienka:  traja ľudia sa navzájom poznajú, traja ľudia sa nepoznajú ale počuli o sebe, alebo traja ľudia sa ani nepoznajú ani o sebe nepočuli? Výsledok je R(3,3,3)=17.

Nájsť Ramseyho číslo začne byť zložitou úlohou, ak sa snažíme overiť každú jednu permutáciu. Ak na párty prišlo napr. 43 osôb (číslo 43 je najspodnejšou hranicou pre R(5,5)), dostaneme 903 vzťahov, z ktorých každý môže byť buď pozná sa alebo nepozná sa. Pre 43 osôb tak dostaneme  2⁹⁰³ možných permutácii.

Takýto brute-force spôsob hľadania Ramseyovho čísla by bol veľmi neefektívny, preto sa projekt rozhodol použiť techniku navrhnutú matematikom Geoffrey Exoom. Táto technika využíva vzťah medzi Ramseyho a Schurovým číslom. Schurove číslo S(n) popisuje koľko kladných celých čísiel môžeme rozdeliť na n skupín, pre ktoré platí že v žiadnej skupine neexistujú také čísla x,y,z   kde x+y=z.

Napríklad S(2)=4, pretože čísla 1-4 môžeme rozdeliť na

Skupinu 1:  1,4
Skupinu 2:  2,3

S(2)!=5, pretože 1+4=5 aj 2+3=5 (päťku teda nemôžeme umiestniť ani do jednej z dvoch skupín)

V predchádzajúcej fáze projekt skúmal rozloženie celých čísel 1-162 do 5 skupín.

Projekt je momentálne neaktívny.