Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Erdosovi brojevi

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Ostalo - ozbiljno -> Čistilište
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
Naya
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 11. 09. 2011. (13:43:39)
Postovi: (F)16
Spol: žensko
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 18:16 ned, 3. 8. 2014    Naslov: Erdosovi brojevi Citirajte i odgovorite

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 :(

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

Dakle nemam pojma. Sram me. Pomoć. :oops:
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



_________________
Crying: acceptable at funerals and the Grand Canyon.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 23:55 sri, 6. 8. 2014    Naslov: Re: Erdosovi brojevi Citirajte i odgovorite

[quote="Naya"]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 :([/quote]

[url=http://en.wikipedia.org/wiki/Erd%C5%91s_number#Definition_and_application_in_mathematics]Erdősev broj[/url] 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).

[quote="Naya"]Drugi zadatak glasi "Develop a parallel algorithm for efficiently inverting a trillion-by-trillion matrix".[/quote]

Vjerojatno neki divide-and-conquer baziran na [url=http://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion]blokovskom invertiranju[/url].

Primijetimo da trilijun realnih brojeva dvostruke preciznosti "pojede" barem 8TB memorije (ovisno o [url=http://en.wikipedia.org/wiki/Trillion]interpretaciji rijec "trilijun"[/url], 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 [url=http://www.top500.org/blog/an-83000-processor-supercomputer-can-only-match-1-of-your-brain/]ovaj text od prije godinu dana[/url], zakljucujemo da se najbrza racunala danas vrte na nekih 10 petaFLOPSa. Neka je to udeseterostruceno do danas (a nije), imamo 100 petaFLOPSa, [url=http://en.wikipedia.org/wiki/FLOPS]sto iznosi[/url] [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 [i]floating point[/i] 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 [i]vague[/i] velicina) mi daje naslutiti da je rijec o shali. Naime, ako je rijec o [i]long scale[/i] 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 [url=http://en.wikipedia.org/wiki/Age_of_the_universe]procijenjene starosti Svemira[/url]. Mozda "efikasno" u smislu teorije, ali nikako ne i korisno. :)
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



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Ostalo - ozbiljno -> Čistilište Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan