Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Kumulativne tabele

[es] :: Art of Programming :: Kumulativne tabele

[ Pregleda: 7691 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

belilav

Član broj: 40324
Poruke: 5
212.200.97.*



Profil

icon Kumulativne tabele30.11.2004. u 05:41 - pre 196 meseci
Mnogo puta sam cuo za pojam kumulativnih tabela, najcesce kad je tema razgovora bila takmicenja iz informatike za srednju skolu, mada i dan-danas ne znam sta je to i kako se koristi ?!

Unapred zahvalan
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+709 Profil

icon Re: Kumulativne tabele03.12.2004. u 10:18 - pre 196 meseci
Vidim da niko ne odgovara, pa ću probati ja: koliko sam upoznat, kumulativne tabele ne postoje kao neki poseban pojam u programiranju. Verovatno se jednostavno misli na tabele (matrice) u kojima se drže neki kumulativni podaci, koje se verovatno koriste u nekim algoritmima.
 
Odgovor na temu

JogyII

Član broj: 29257
Poruke: 623
*.absolutok.com.



Profil

icon Re: Kumulativne tabele03.12.2004. u 11:10 - pre 196 meseci
kumulativne tabele???
pa znam za izracunavanje kumulativnih vrednosti koje se koristi u poslovnom softwer-u uglavnom za preglede i izvestaje (najcesce u nizovima, tabelama ...), ali nikada nisam cuo za "kumulativne tabele", dali ste sigurni da to nije opet neki srbizam na delu?

So Long, and Thanks for All the Fish


 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.bankerinter.net.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Kumulativne tabele04.12.2004. u 21:37 - pre 196 meseci
Kumulativne tabele jesu pojam u programiranju (struktura podataka) i nisu srbizam definitivno (cumulative tables, i Ameri ih tako zovu ;)). U svakom slucaju, problem koje resavaju je sledeci:
Imas niz od n elemenata i nad njime vrsis 2 operacije: jedna je povecaj (i, x), sto znaci povecaj i-ti element za x, a druga je Sum (i), koja treba da vraca zbir prvih i elemenata niza. Trivijalni algoritmi bi radili jednu operaciju u O (1), a drugu u O (n), ili nesto maaalo bolje. Primenom kumulativnih tabela, obe operacije vrse se u O (log n). To ti je otprilike pojamno sta znace kumulativne tabele, u sustini i idejno nisu teski algoritmi, a pogotovu sami kodovi koji su 3-4 reda svega. Ako te interesuje kako funkcionisu i kako izgleda kod, kazi da ti napisem, ako te ne interesuje, da se ne smaram da kucam, posto sam na dialup trenutno :(:(:(.
Poz

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

belilav

Član broj: 40324
Poruke: 5
*.vdial.verat.net.



Profil

icon Re: Kumulativne tabele06.12.2004. u 01:08 - pre 196 meseci
IsrkiboyI

Velika hvala.Ovaj uvod u kumulativne tabele sam znao otprilike i informativno.
Naravno da me zanima kako funkcionisu i kako izgleda kod, takodje mozes da upotrebis neki konkretan problem.
 
Odgovor na temu

JogyII

Član broj: 29257
Poruke: 623
*.absolutok.com.



Profil

icon Re: Kumulativne tabele06.12.2004. u 08:22 - pre 196 meseci
Citat:
IsrkiboyI: Kumulativne tabele jesu pojam u programiranju (struktura podataka) i nisu srbizam definitivno (cumulative tables, i Ameri ih tako zovu ;)). U svakom slucaju, problem koje resavaju je sledeci:
Imas niz od n elemenata i nad njime vrsis 2 operacije: jedna je povecaj (i, x), sto znaci povecaj i-ti element za x, a druga je Sum (i), koja treba da vraca zbir prvih i elemenata niza. Trivijalni algoritmi bi radili jednu operaciju u O (1), a drugu u O (n), ili nesto maaalo bolje. Primenom kumulativnih tabela, obe operacije vrse se u O (log n). To ti je otprilike pojamno sta znace kumulativne tabele, u sustini i idejno nisu teski algoritmi, a pogotovu sami kodovi koji su 3-4 reda svega. Ako te interesuje kako funkcionisu i kako izgleda kod, kazi da ti napisem, ako te ne interesuje, da se ne smaram da kucam, posto sam na dialup trenutno :(:(:(.
Poz
da koliko vidim obicno izracunavanje kumulativnih vrednosti, ali hvala nisam znao da se to zove "cumulative tables"

bilo bi lepo i da dobijemo ove algoritme ako budes imao vremena, ja znam samo za onu najprostiju verziju sa loop-om (a(n+1)=a(n)+v(n+1))
moze i link na net-u



So Long, and Thanks for All the Fish


 
Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.bankerinter.net.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..


Profil

icon Re: Kumulativne tabele06.12.2004. u 11:06 - pre 196 meseci
Pa ovako:
Znaci, imamo niz i treba da vrsimo operacije add (int x, int val) koje dodaju x-tom elementu vrednost val, i sum (int x) koja vraca sumu prvih x clanova niza. Dakle, najprostiji algoritmi koji bi nam pali na pamet za ovaj problem su npr da u jednom nizu pamtimo vrednosti samog niza, koje se unose, i da ih stoga add bude slozenosti O (1), a da sabiramo obicnom for petljom, sto bi bilo O (n), za sum f-ju. Ili mozemo u a [ i ] da pamtimo zbir od a [1] do a [ i ], pa da sum bude u O (1), ali bi add bilo u O (n), jer bi morali da povecavamo sve od a [ i ] do a [n]. E, slozenost O (log n) za obe f-je se postize primenom kumulativnih tabela, i to je "as good as it gets". Dakle, imamo niz tree, od n elemenata. (primetimo da je indexiranje od 1 do n, a ne od 0 do n - 1). E sad, svaki broj znamo da moze da se predstavi kao zbir stepena dvojke. Pa onda i svaka ovakva suma moze da se predstavi kao zbir odredjenih "podsuma". Kakvih ? Pa, ovako, ako treba da recimo nadjemo sum (i), mi cemo to radimo na sledeci nacin: sabiramo tree [ i ] sve dok i nije nula, a posle svakog sabiranja broju i "izbrisemo" najdesniju jedinicu u binarnom zapisu (pretvorimo je u 0). To ce reci da je recimo sum (13) = tree [13] + tree [12] + tree [8]. Slozenost ovog koraka bi bila O (log n), jer broj ima O (log n) cifara u binarnom zapisu. E sad ostaje jos kako da pamtimo vrednosti tako da u tree [13] bude a [13], u tree [12] bude a [9..12] i u tree [8] bude bas a [1..8]. U sustini, u tree [ i ] treba da bude a [k + 1..i] gde je k prvi broj manji od i koji je deljiv sa vecim stepenom dvojke nego i. To ce reci da je npr za sve neparne brojeve i tree [ i ] = a [ i ]. Npr tree [6] = a [5] + a [6], jer je 4 prvi manji od 6 da je deljiv sa vise od . Dakle, kad treba da updete-ujemo tree, tj da odradimo add, radicemo obrnuto nego za sum. Za add (x, val) dodacemo val u tree [x], pa u tree [k], gde je k prvi sledeci broj veci od x koji je deljiv sa vecim stepenom dvojke nego x, pa u tree [r], r prvi veci od k, da je "vise" deljiv sa dvojkom nego k, itd. Treba se malo potruditi da se sve ovo razume, a kad se ukapira, ono sto je vise nego lepo je kod koji je izuzetno jednostavan (treba obratiti paznju na operacije nad bitovima koje raditi gore opisane radnje):

Code:

int sum (int x)
{
    int tempsum;
    if (x == 0)
        return 0;
    tempsum = 0;
    while (x > 0)
    {
        tempsum +=  tree [x];
        x &= x - 1;
    }
    return tempsum;
}


Code:

void add (int x, int val)
{
    int temp;
    do
    {
        tree [x] += val;
        if (x == 0)
            break;
        temp = x;    //  Ovo je u sustini isto sto i
        temp &= -x;    //  x = x + x & (-x), ali ja    
        x += temp;    //  vise volim da pisem ovako
    }
    while (x <= n);
}

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.neobee.net.



Profil

icon Re: Kumulativne tabele03.04.2005. u 22:09 - pre 192 meseci
Evo, mozda i ovo nekom pomogne :)

http://www.cs.ubc.ca/local/rea...95/spe/vol24/issue3/spe884.pdf
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

[es] :: Art of Programming :: Kumulativne tabele

[ Pregleda: 7691 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.