Studoši

imam pitanje za 24. zad
P(x,y) je matrica koju dobijemo kad izracunamo vjerojatnosti pojavljivanja brojeva iz zadane
P’(x,y) = P(x-1, y)
Kako dobijemo P’, tako da početnu tablicu pomaknemo i onda računamo vjerojatnosti iz te nove tablice, ili pomaknemo vec izracunatu matricu P

supernatural samo pomaknes onu pocetnu tablicu, odnosno matricu P

fmst ok, ali zar nije onda rjesenje u docsu krivo

supernatural ne znam na sto tocno mislis, ali mozda te buni sto nije napisana matrica P’. Ovo sto je u rjesenju je matrica pogreske predvidanja, odnosno apsolutne vrijednost razlike, i ona je dobra.

gama negdje se uzima (d+1)/2 za korak, mozda bi kod matrice 8×8 i 2×2, gdje je d=3, s onda bio (3+1)/2=2

fmst gdje si vidio da se uzima (d+1)/2 za odmak?

gama
btw ispravak netočnog navoda, Alen Duspara, lično je rekao da se uzima d kao najveći odmak, tako da bi za matricu 11×11 po tome odmak bio d=5, odnosno s=2

gama kod ORT pretrazivanja, ima u docsima, kod opisa ORT algoritama, dvije slike gdje je na jednoj uzet d, a na drugoj d+1

jel onda s=d/2 i kod ORT i kod LOG?

Charm fmst Prezentacija MAS-JK-3-5, slajdovi 21, 22, 23. Tamo se nalazi opisi postupka za 3SS, LOG i ORT. Za LOG i ORT su u oba slučaja uzeli s=d/2, tako da pretpostavljam da je to točno uvijek.

fmst a ako gledamo ovu s predavanja u kojoj je d=d/2 i stave nam da je krivo rješeno, imamo se na što pozvati, tako da biram tu opciju

gama Jel se sigurno kod neparnog d (npr. d=5) zaokružuje na manji broj dok se dijeli s 2. Jel za d=5 => d/2 = 2.5 onda uzimamo 2 il 3?

Dakle kako je napisao kolega Bobicki, ovo bi trebalo biti tako i stvar je riješena?
I koji je primjer s tim blokovima u docu riješen točno? (ako uopće postoji)

Miskina666 Alen Duspara kaže da se radi cjelobrojno dijeljenje, tako da je 2.

A kod racunanja broja operacija, jel racunamo sve operacije iako su neke od njih za isti blok?
npr. izracunali smo MAD za neki blok i u sljedecem koraku trebamo za taj isti blok ponovno izracunati MAD.

Hoce obje operacije uci u konacni zbroj operacija ili uzimamo samo jednu od takvih.

fmst Ako je suditi po slici koja opisuje ORT, onda ih ne bi trebali ponovo uzimati u obzir, jer dolje u broj točaka za proračun samo dosad neviđene stavljaju

na ovo mislim:

gama to ima smisla jer je to ona tocka u koju smo se pomaknuli, ali ono sto me zanima je sto ako nam je u jednom koraku ta tocka bila recimo gore, a u sljedecem koraku lijevo.

Rekao bih da biraš ono tako da ti u najgorem slučaju min prozor bude na rubovima.

Npr. ako imaš 8×8 prozor s 2×2 blokom, d ti je 3, uzimaš \lfloor \frac{d + 1}{2} \rfloor jer u slučaju da ti je minimum odmaknut 2 , onda sljedeći gledaš odmaknut za 1, a to će ti biti rub prozora pretraživanja. U slučaju kad bi imao 9×9 s 2×2 prozorom, onda ti je d = 4, i tad opet možeš dobiti rub prozora s početnim s = 2, sljedeći s će biti 1, i opet worst case scenarij je rub (s one kraće strane).

Tako da moj guess je da mora vrijediti svojstvo da \sum{s_i} \leq d_{min}, a pošto vrijedi da je s_{i + 1} = \lfloor \frac{s_i}{2} \rfloor , onda ti s_{-1} mora biti d + 1 ili manje, pa je tako s_0 = \lfloor \frac{d_{min} + 1}{2} \rfloor kako bi osigurali da pregledavamo cijeli prozor.

Ako se radi o slučaju da smijemo popunjavati nulama, onda bi izraz bio s_0 = \lfloor \frac{d_{min} + 1}{2} \rfloor + (d_{max} - d_{min}). Time ćemo dobiti da provjeravamo cijeli prozor i u najgorem slučaju (npr. kad imamo asimetrične d-ove), a ako izađemo iz prozora lako samo kažemo da su to nul-blokovi. Ovo bi bio slučaj kad blok ne bi bio centriran (npr. kad su dimenzije prozora i bloka paran i neparan broj).

Tj ovo je bar moja logika koja se bazira na tome da nema apsolutno nikakvog smisla imati veći prozor pretraživanja za ORT i LOG ako nećeš potencijalno iskoristiti sve vrijednosti. A ako se kaže da je s_0 = \lfloor \frac{d}{2} \rfloor, onda za 8×8, 2×2 slučaj nikad nećeš pregledati dalje od okoline 1 bloka, dakle prozor bi ti komotno mogao biti 4×4 i ne bi bilo razlike u rezultatima.

M̵̧̩͑̀͝î̶͍̉ć̴̝̾́̀o̶̺̟̣͂̽ A kako znas jel d/2 ili (d+1)/2? S obzirom da je u predavanjima d/2

fmst vjerujem da se ne uzima, pogledaj ovdje:

zamagljeni su, a ni nema smisla nešto ponovo računati kad već znaš rezultat

adrian7000 Može biti i jedno i drugo, ali d + 1 ti daje rezultate koji bolje iskorištavaju vrijednosti, tj. dolaze bliže prozora. A znaš da mora biti d + 1 ili manje zato što u suprotnom imaš (skoro) geometrijski niz \frac{d}{2}+1 + \frac{d}{4} + \frac{d}{8} + ... čija suma je veća od d (teži u d + 1 za neke d-ove), i onda nije zadovoljeno \sum{s_i} \leq d_{min}.

MOD EDIT: Obrisao sam ono s d + 3 i d + 2 jer sam našao protuprimjere (npr. 14×14, 2×2). Znači ipak je d + 1 maksimum.

gama sjećam se iz ispita kod proračuna koliko su ORT i LOG efikasniji - ne uzima se, dakle jednom kad je neki blok izračunat više ga se ne računa - bilo da nam on treba odmah u sljedećem koraku ili 10 koraka nakon