Forum@DeGiorgi :: Pogledajte temu

through

[^/[Print]\]

Forum@DeGiorgi -> Čistilište

#1: Erdosovi brojevi Autor/ica: Naya,

Postano: 18:16 ned, 3. 8. 2014
—
Bok ljudi, trebam pomoć oko dva zadatka (od kojih eto jedan ima veze s erdosovim brojevima)

Zadatak glasi Improve my (Misha Collins’) Erdős number. Hint: it’s currently lower than 1000. Kako se može popraviti nečiji E. broj? Ne znam ga izračunati Sad

Drugi zadatak glasi "Develop a parallel algorithm for efficiently inverting a trillion-by-trillion matrix".

Dakle nemam pojma. Sram me. Pomoć. Embarassed

#2: Re: Erdosovi brojevi Autor/ica: vsego, Lokacija: /sbin/init

Postano: 23:55 sri, 6. 8. 2014
—

Naya (napisa):

Zadatak glasi Improve my (Misha Collins’) Erdős number. Hint: it’s currently lower than 1000. Kako se može popraviti nečiji E. broj? Ne znam ga izračunati Sad

Erdősev broj predstavlja "kolaborativnu udaljenost" dane osobe od Paula Erdősa. Unaprjedjuje se jednostavno.

Oznacimo Erdősev broj osobe [tex]X[/tex] s [tex]E(X)[/tex]. Dakle, Castiel (Misgha Collins od milja) ima Erdősev broj [tex]E(\text{Castiel})[/tex]. Bilo koja osoba [tex]P[/tex] takva da je [tex]E(P) < E(\text{Castiel})-1[/tex] moze s gospodinom Collinsom objaviti rad, pa ce njegov novi Erdősev broj postati [tex]E(P)+1 < E(\text{Castiel})[/tex]. Sve ostale osobe moraju same unaprijediti svoj Erdősev broj tako da zadovolji navedeni uvjet, pa onda objaviti rad s g. Collinsom (ako vec nisu).

Naya (napisa):

Drugi zadatak glasi "Develop a parallel algorithm for efficiently inverting a trillion-by-trillion matrix".

Vjerojatno neki divide-and-conquer baziran na blokovskom invertiranju.

Primijetimo da trilijun realnih brojeva dvostruke preciznosti "pojede" barem 8TB memorije (ovisno o interpretaciji rijec "trilijun", moze i daleko vise). Posto je ovdje rijec o matrici, pricamo o najmanje 8 trilijuna terbytea, te o broju operacija reda velicine trilijun na kvadrat, tj. [tex]10^{24}[/tex] (opet, uz "optimisticnu" definiciju rijeci "trilijun").

Uzmemo li ozbiljno ovaj text od prije godinu dana, zakljucujemo da se najbrza racunala danas vrte na nekih 10 petaFLOPSa. Neka je to udeseterostruceno do danas (a nije), imamo 100 petaFLOPSa, sto iznosi [tex]10^{17}[/tex] FLOPSa i potpuno je iskoristivo samo uz savrseno paralelni algoritam bez komunikacijskog gubitka medju procesorima (ideal koji bas i nije dostizan, no za neke probleme mu se moze doci jako blizu).

Summa summarum, vrlo optimisticna donja ograda trajanja invertiranja zadane matrice je [tex]10^{24-17} = 10^7[/tex] sekundi, tj. cca 116 dana, sve uz pretpostavku da te brojeve uopce uspijemo pohraniti negdje. Ovo pretpostavlja da ce nase invertiranje trositi tocno jednu floating point operaciju po svakom elementu matrice, sto je ogromno pretjerivanje. Cak i da uspijemo postici samo kvadratnu slozenost, ovo se mora mnoziti s nekim faktorom koji tesko da je reda velicine jednoznamenkastih prirodnih brojeva (dakle, sad vec pricamo o barem 1000 dana, tj. skoro 3 godine).

Sama nedorecenost zadatka ("trilijun" je vague velicina) mi daje naslutiti da je rijec o shali. Naime, ako je rijec o long scale trilijunu, onda ovih 116 dana raste na [tex]1.16 \cdot 10^{14}[/tex] dana, tj. [tex]3.17 \cdot 10^{11}[/tex] godina, sto je cca 30 puta vise od procijenjene starosti Svemira. Mozda "efikasno" u smislu teorije, ali nikako ne i korisno. Smile

Forum@DeGiorgi -> Čistilište

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.