SubsetSum@Home

[AL]

SubsetSum@Home

Kod [Zaznacz] Rozwiń

http://volunteer.cs.und.edu/subset_sum/

The Subset Sum problem is described as follows: given a set of positive integers S and a target sum t, is there a subset of S whose sum is t? It is one of the well-know, so-called "hard" problems in computing. It's actually a very simple problem, and the computer program to solve it is not extremely complicated. What's hard about it is the running time – all known exact algorithms have running time that is proportional to an exponential function of the number of elements in the set (for worst-case instances of the problem).

Over the years, a large number of combinatorial problems have been shown to be in the same class as Subset Sum (called NP-complete problems). But, depending on how you measure the size of the problem instance, there is evidence that Subset Sum is actually an easier problem that most of the others in its class. The goal of this project is to strengthen the evidence that Subset Sum is an easier hard problem.

Suppose we have a set of n positive whole numbers S whose maximum number is m. We will define the ratio n/m to be the density of the set and denote the sum of all elements in the set as ∑S. If you look at the list of sums produced by subsets of S, you notice that very few sums are missing if S is dense enough. In fact, it appears that there is an exact density threshold beyond which no sums between m and half the sum of S will be missing. Our preliminary experiments have led to the following hypothesis: A set of positive integers with maximum element m and size n > floor(m/2)+1 has a subset whose sum is t for every t in the range m < t < ∑S − m.

So here's where you can help. So far, we haven't been able to prove the hypothesis above. If you want to be really helpful, you can send us a proof (or show us where to find one in the research literature), and the project will be done. But if you want to be slightly less helpful and have more fun, you can volunteer your computer as a worker to see how far we can extend the empirical evidence. You will also be helping us figure out better ways to apply distributed computing to combinatorial problems.

SubsetSum@Home is based at the Computer Science Department of the University of North Dakota.

Drużynka

Projekt znaleziony kilka dni temu, ale dopiero dziś puścili pierwszą serię Wu i to od razu zarówno na Win jak i Lin.

[Troll81]

Dopięty :D

[patyczak]

Dopięty :D

ja również  :)

[andy101fah]

Reklama Teamu Poland na stronie głównej projektu.

[patyczak]

Pierwsza próbka przeliczona

Kod [Zaznacz] Rozwiń

Completed and validated 5,908.81 5,432.25 22.98 SubsetSum@Home v0.03
Athlon 3200+ winXP

Z tego co widzę do walidacji próbki potrzeba wyników z 3 klientów.

[Tomasz R. Gwiazda]

mnie nic nie pobralo :(

[patyczak]

mnie nic nie pobralo :(

Może poprawiają punktacje bo na razie jest trochę dziwna.

Kod [Zaznacz] Rozwiń

1404 777 24 Apr 2012 | 6:18:44 UTC 24 Apr 2012 | 8:03:02 UTC Completed and validated 6,135.78 5,211.48 31.40 SubsetSum@Home v0.03
1134 642 24 Apr 2012 | 6:19:59 UTC 24 Apr 2012 | 8:25:44 UTC Completed and validated 7,520.78 5,141.91 24.71 SubsetSum@Home v0.03

Core2Duo 2.4GHz WinXP

[TP]

Fajnie, że możecie liczyć ten projekt we własnej drużynie, bo Wasz kolega pozbawił Nas tej możliwości.... :bad:

[Pantarhei]

Fajnie, że możecie liczyć ten projekt we własnej drużynie, bo Wasz kolega pozbawił Nas tej możliwości.... :bad:

? ? ?

[Troll81]

? nie rozumiem twej wypowiedzi TP

[TP]

Proszę już tłumaczę:



Dzisiaj chciałem utworzyć w tym projekcie drużynę Polish National Team - no i mi wyskoczyło że nie da rady bo... już taka drużyna istnieje... a founderem jest kotfryc1 z B@P, który nawet nie liczy w drużynie, bo już jest w swojej, ale zablokował nam możliwość utworzenia własnej...

Dołączyłem i dałem requesta foundera.... i mam niesmak  :wacko:

[Pantarhei]

 To nieładnie z naszej strony, ale może da się to naprawić...

[Szopler]

Jaaasne i jeszcze podpisał się własnym nickiem... :facepalm2:

[Troll81]

chciałbym zauważyć ze założycielem nie jest kotfryc tylko kotfryc1. Niemniej jednak zbieżność jest dziwna. Jako że posiadasz konto na naszym forum napisz do kolegi kotfryc PW i wyjaśnij tę kwestię. Byłoby bardzo brzydko z jego strony gdyby taki numer wywinął....

[Troll81]

Ja juz do kolegi napisałem PW z prośba o wyjaśnienie

[TP]

Dzięki za zainteresowanie.

Ja ze swojej strony dodam, że napisałem do Admina tego projektu, z prośbą o przekazanie foundera... tylko nie wiadomo ile trzeba będzie czekać.... no i jaka będzie odpowiedź...

Link do usera

[KrzychuP]

Co to qrka ma być, pogięło go?  :wth:

chciałbym zauważyć ze założycielem nie jest kotfryc tylko kotfryc1.....

to niestety on, zerknij Trollu na BoincStats  :(
chyba, że ktoś się nieładnie bawi..

Pytanie: Można założyć konto w nowym projekcie o dowolnym nicku, jeśli jest on już używany przez kogoś innego w wielu innych projektach?

[Troll81]

tak można. Projekty nie komunikują się ze sobą...

w boincstats istnieja dwa kotfryce i jeden kotfryc1 czekam na odpowiedź.

[legis]

Dopięty

[TP]

Pytanie: Można założyć konto w nowym projekcie o dowolnym nicku, jeśli jest on już używany przez kogoś innego w wielu innych projektach?

Tak, ale i tak każdy user jest identyfikowany w bazie wszystkich projektów pod jednym Identyfikatorze między projektowym.

Także podszycie się pod kogoś odpada w sytuacji, gdy projekt łapie sam staty usera z innych projektów.+

Zawsze ktoś może się pod kogoś podszyć - no ale to jest karalne... i jednak trzeba się napracować...

[Szopler]

w boincstats istnieja dwa kotfryce i jeden kotfryc1 czekam na odpowiedź.

W BAM "Kotfryc" i "kotfryc" to jakieś "spady" z rozsynchronizowanych kont... aktywne jest tylko "kotfryc1"... :whistle:

[Troll81]

Czekam na odpowiedź kolegi...

[Troll81]

kolega kotfryc1 jest już u nas w teamie...

http://volunteer.cs.und.edu/subset_sum/show_user.php?userid=149

i jest jednocześnie founderem drużyny...

http://volunteer.cs.und.edu/subset_sum/team_display.php?teamid=45

z tego co pamiętam nie można być founderem jednej drużyny i członkiem innej. Może to jakiś fuckup bazy danych?

[ryszard.korczyk]

Z tego co się orientuje, kotfryc odsypia po nocce, więc pewnie wieczorem będzie dostępny.

[TP]

z tego co pamiętam nie można być founderem jednej drużyny i członkiem innej. Może to jakiś fuckup bazy danych?

Jak najbardziej można.

[AL]

z tego co pamiętam nie można być founderem jednej drużyny i członkiem innej. Może to jakiś fuckup bazy danych?

Jak najbardziej można.

Potwierdzam, jest to jak najbardziej możliwe.

[PoznanskaPyra]

Co to ma być? Mam nadzieję, że sprawa się wyjaśni. W ogóle głupia sytuacja  :shame:

[Krzysiak]

del

[Cyfron]

del

??

[sknd]

ale chora akcja :no:

[krzyszp]

Bez paniki Panowie, Kotfyc się pojawi, to się wyjaśni... Nie wieszajcie na nikim psów, dopóki nic nie wiadomo...
Sam mam ochotę zwrócić się do adminów o info na temat ip użytego do założenia tego konta...

[kotfryc]

Dobra możecie na mnie wieszać psy   |-? 
Właściwie chciałem sprawdzić jak wygląda kwestia tworzenia nowych zespołów, PNT nie było i kliknąłem  :facepalm2: Oczywiście że bym przekazał foundera, ale rano nie było komu i padłem po nocce w pracy.
Nie sądziłem, że tyle krzyku o  to będzie, wszak to nie domena internetowa i sprawę można załatwić jednym klikiem

Pytanie: Można założyć konto w nowym projekcie o dowolnym nicku, jeśli jest on już używany przez kogoś innego w wielu innych projektach?

Właśnie na podobne pytanie chciałem sobie odpowiedzieć ino nie odnośnie nicków (bo to już wiem) ale nazw zespołów.

Dzięki za zainteresowanie.
Ja ze swojej strony dodam, że napisałem do Admina tego projektu, z prośbą o przekazanie foundera... tylko nie wiadomo ile trzeba będzie czekać.... no i jaka będzie odpowiedź...

Admin był dużo szybszy ode mnie  :dunno:

TP przepraszam, jeśli w jakiś sposób mogę naprawić szkody powstałe w skutek mojej głupoty to pisz...  :shame:

PS napisałem moja głupota - proszę więc kolegów z PNT żeby nie oceniali całego zespołu przez pryzmat jednej osoby...

[Troll81]

No i się wyjaśniło.

[patyczak]

Nowa wersja aplikacji 0.04, jak na razie u mnie wszystkie zakończone WU oznaczone jako 'Validate error'.

[PoznanskaPyra]

Kod [Zaznacz] Rozwiń

1827 880 229 24 Apr 2012 | 19:48:48 UTC 24 Apr 2012 | 21:08:15 UTC Completed, waiting for validation 3,924.88 3,874.61 pending SubsetSum@Home v0.04
1826 879 229 24 Apr 2012 | 19:48:48 UTC 24 Apr 2012 | 21:08:15 UTC Completed, waiting for validation 3,916.15 3,866.97 pending SubsetSum@Home v0.04

Kod [Zaznacz] Rozwiń

1827 880 229 24 Apr 2012 | 19:48:48 UTC 24 Apr 2012 | 21:08:15 UTC Validate error 3,924.88 3,874.61 --- SubsetSum@Home v0.04   :(

[legis]

mnie nic nie pobralo :(

Może poprawiają punktacje bo na razie jest trochę dziwna.

Kod [Zaznacz] Rozwiń

1404 777 24 Apr 2012 | 6:18:44 UTC 24 Apr 2012 | 8:03:02 UTC Completed and validated 6,135.78 5,211.48 31.40 SubsetSum@Home v0.03
1134 642 24 Apr 2012 | 6:19:59 UTC 24 Apr 2012 | 8:25:44 UTC Completed and validated 7,520.78 5,141.91 24.71 SubsetSum@Home v0.03

Core2Duo 2.4GHz WinXP

Kod [Zaznacz] Rozwiń

1827 880 229 24 Apr 2012 | 19:48:48 UTC 24 Apr 2012 | 21:08:15 UTC Completed, waiting for validation 3,924.88 3,874.61 pending SubsetSum@Home v0.04
1826 879 229 24 Apr 2012 | 19:48:48 UTC 24 Apr 2012 | 21:08:15 UTC Completed, waiting for validation 3,916.15 3,866.97 pending SubsetSum@Home v0.04

Kod [Zaznacz] Rozwiń

1827 880 229 24 Apr 2012 | 19:48:48 UTC 24 Apr 2012 | 21:08:15 UTC Validate error 3,924.88 3,874.61 --- SubsetSum@Home v0.04   :(

2540   1236   211   24 Apr 2012 | 21:46:39 UTC   24 Apr 2012 | 22:56:27 UTC   Completed and validated   3,864.36   3,831.81   26.95   SubsetSum@Home v0.04

poprawili punktację

[Troll81]

taki urok młodych projektów....

[TP]

Admin był dużo szybszy ode mnie  :dunno:

TP przepraszam, jeśli w jakiś sposób mogę naprawić szkody powstałe w skutek mojej głupoty to pisz...  :shame:

PS napisałem moja głupota - proszę więc kolegów z PNT żeby nie oceniali całego zespołu przez pryzmat jednej osoby...

Przeprosiny przyjęte  :parrrty:

Temat zamknięty - admin zrobił "porządek".

Pozdrawiam i wysokich wyników życzę.

:ahoy:

[Troll81]

I wzajemnie Tomku

[PoznanskaPyra]

Kod [Zaznacz] Rozwiń

1826 879 229 24 Apr 2012 | 19:48:48 UTC 24 Apr 2012 | 21:08:15 UTC Completed and validated 3,916.15 3,866.97 21.01 SubsetSum@Home v0.04 :arrr: