Dotazy na castecnou shodu

Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Příspěvek od twoflower »

Tuetschek píše:
Pavel J píše:? Myslím tím, proč např. v prvním sčítanci (ten odpovídá tomu, že první atribut je specifikovaný a ostatní dva nejsou) nemám součin pravděpodobností

P(první atribut specifikován) * P(druhý atribut nespecifikován) * P(třetí atribut nespecifikován)

ale mám tam jen

P(první atribut specifikován) ?
Ja si taky myslim ze to ma byt spis takhle ... protoze jestli ne tak to mam blbe v pisemce ;)
Na druhou stranu, ten priklad ve skriptech je zrejme pocitany podle toho, jak to psal Hugo. Ja to v pisemce tedy taky delal jako ty...prijde mi to logictejsi, ale jak overit, co je spravne :-/
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Příspěvek od twoflower »

Tuetschek píše:
Pavel J píše:? Myslím tím, proč např. v prvním sčítanci (ten odpovídá tomu, že první atribut je specifikovaný a ostatní dva nejsou) nemám součin pravděpodobností

P(první atribut specifikován) * P(druhý atribut nespecifikován) * P(třetí atribut nespecifikován)

ale mám tam jen

P(první atribut specifikován) ?
Ja si taky myslim ze to ma byt spis takhle ... protoze jestli ne tak to mam blbe v pisemce ;)
Ted me jeste napadlo, ze zalezi, jestli je v zadani, zda se pri pocitani prumerne ceny dotazu uvazuji pouze dotazy na jeden atribut. Pokud ano, tak je logicke to pocitat jako to napsal Hugo (nebot to, ze je tam jeden atribut, uz automaticky implikuje, ze ty ostatni tam nejsou => nemusim tam pocitat s pravdepodobnostmi P(atribut nespecifikovan)), pokud ne, tak by to asi melo byt i s temi vsemi pravdepodobnostmi okolo.

Jak to tedy melo byt v pisemce? V zadani uvedene pravdepodobnosti jsou pro dotazy na jeden atribut, ovsem zjevne ma smysl pocitat (pro ucely te prumerne ceny) i s dotazy na vice atributu, nebot priklad takoveho dotazu byl v podotazce c)...
christyna
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 25. 1. 2006 18:31

Re: Dotazy na castecnou zhodu

Příspěvek od christyna »

D píše:Uvazujte soubor FILM(NAZEV,ROK,REZISER) ulozeny hashovaci fci do adresoveho prostoru stranek, tak aby bylo mozne realizovat dotazy na castecnou zhodu. Adresy stranek jsou dlouhe 2 Byte. Jednotlive atributy prispivaji do adresy retezci delky 9,3,4. Jaka je cena dotazu na castecnou zhodu s atributy NAZEV, REZISER?
Nemohl by nekdo tedy napsat, jak to ma presne byt?
gASK
Admin(ka) level I
Příspěvky: 635
Registrován: 9. 6. 2005 12:33
Typ studia: Informatika Mgr.
Bydliště: Konečně Vinohrady:)
Kontaktovat uživatele:

Re: Dotazy na castecnou zhodu

Příspěvek od gASK »

christyna píše: Nemohl by nekdo tedy napsat, jak to ma presne byt?
2^3 - musím prohledat všechny stránky, kde znám prvních 9 a poslední 4 bity adresy a 3 bity jsou neznámé.

Obecně je to "pavzorec" 2^(počet otazníků v dotazu)
When life gives you crap, make crap golems.
Uživatelský avatar
gofry
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 13. 1. 2006 23:41

Příspěvek od gofry »

Pavel J píše:
Hugo píše:0.75 * 2^4 + 0.24 * 2^5 + 0.01 * 2^9 = 24.8
Proč to není

(0.75*0.76*0.99) * 2^4 + (0.25*0.24*0.99) * 2^5 + (0.25*0.76*0.01) * 2^9

? Myslím tím, proč např. v prvním sčítanci (ten odpovídá tomu, že první atribut je specifikovaný a ostatní dva nejsou) nemám součin pravděpodobností

P(první atribut specifikován) * P(druhý atribut nespecifikován) * P(třetí atribut nespecifikován)

ale mám tam jen

P(první atribut specifikován) ?
Ty by si vlastne mal chcieť počítať

Kód: Vybrat vše

P(non[B&C])*(počet stránok, ktoré musím prehľadať, ak nemám zadané ani B ani C)
P(non[B&C]) znamená pravdepodobnosť, že atribúty B a C nie sú špecifikované. Nepliesť si to s nejakým logickým výrazom.
Ale zrejme

Kód: Vybrat vše

P(non[B&C]) = P(A)
Čiže pravdepodobnosť, že atribúty B a C nebudú špecifikované sa rovná pravdepodobnosti, že atribút A špecifikovaný bude.
A zároveň

Kód: Vybrat vše

(počet stránok, ktoré musím prehľadať, ak nemám zadané ani B ani C) = (2^db)*(2^dc)
Platí tiež, že (tento krok už v skriptách nie je)

Kód: Vybrat vše

(2^db)*(2^dc) = 2^(d-da)
Vo finále teda

Kód: Vybrat vše

P(non[B&C])*(počet stránok, ktoré musím prehľadať, ak nemám zadané ani B ani C) =  P(A)*2^(d-da).
d - počet bitov signatúry záznamu
da, db a dc - počet bitov signatúr jednotlivých atribútov

Podobne počítaš v ostatných prípadoch, tj.

špecifikované: B
nešpecifikované: A, C

špecifikované: C
nešpecifikované: A, B

Výsledný vzorec by teda mohol vyzerať takto:
Obrázek
Q - množina dotazov so špecifikovaným jedným atribútom.
To ale zjavne vyzerá príliš jednoducho, preto sa pán Pokorný rozhodol, že to do skrípt trošku zašifruje.
Návštěvník

Příspěvek od Návštěvník »

twoflower píše:Pocital jste nekdo tenhle priklad ze skript (na strance 46)?

Uvazujme soubor s atributy JMENO, POVOLANI, VZDELANI. Predpokladejme dotazy pouze na jeden atribut s pravdepodobnosti P(Jmeno) = 0.75, P(Povolani) = 0.24, P(Vzdelani) = 0.01. Necht je d = 9.

Rozdeleni bitu (5, 4, 0) mi vyslo stejne, jen se nemuzu dopocitat k te uvedene prumerne cene dotazu 24.8 stranek.

Zkousel jste to nekdo?
Ja neviem kde robim chybu, pretoze podla toho vzorca co ma na stranke by sa d1 malo rovnat.
(9 - (log0.75+log0.24+log0.01))/3 + log2(0.75)
a neviem ci mam blbu kalkulacku co nevie pocitat logaritmy ale ta prva cast mi nevyjde 6.03 ale 3.91 a celkovo mi to vyjde 3,78.
Uživatelský avatar
Trupik
Matfyz(ák|ačka) level III
Příspěvky: 251
Registrován: 3. 1. 2005 14:45
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od Trupik »

Pjm = 0,75
Ppo = 0,24
Pvz = 0,01
d = 9
(vsechny logaritmy maji zaklad 2)
---------------
E:=(9-log(Pjm)-log(Ppo)-log(Pvz))/3=6.03
E + log(Pjm) = 5.62
E + log(Ppo) = 3.98
E + log(Pvz) = -0.61
---------------
posledni vysledek vysel zapone (protoze dotazy na Pvz jsou velmi nepravdepodobne). Takze nebudu uvazovat Pvz a spocitam znova E.

EDIT: taky je potreba upravit Pjm a Ppo:
Pjm := Pjm / (1-Pvz)
Ppo := Ppo / (1-Pvz)

E2 := (9-log(Pjm)-log(Ppo))/2 = 5.73
E2 + log(Pjm) = 5.32
E2 + log(Ppo) = 3.68

Rozdeleni tedy bude <djm, dpo, dvz> = <5,4,0> bitu

Prumerna cena dotazu se spocita jako
suma (pravdpodobnost na dany typ dotazu * pocet stranek, ktere se budou muset prohledat)

P = Pjm * 2^(d-djm) + Ppo * 2^(d-dpo) + Pvz * 2^(d-dvz) =
= 0.75 * 2^(9-5) + 0.24 * 2^(9-4) + 0.01 * 2^(9-0) = 24.8

Pokud neco pisu blbe, tak me opravte, jinak skritpa rekl bych nelzou.
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz

Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
mk
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 15. 6. 2006 10:20

Re: Dotazy na castecnou shodu

Příspěvek od mk »

Podla mna tie pravdepodobnosti netreba brat tak komplikovane.

Mame mnozinu dotazov Q, ktoru chapem ako potencnu mnozinu mnoziny [n] (kde n=3 je pocet atributov).
Kazdemu prvku(dotazu) q z tejto mnoziny priradime pravdepodobnost Pq. Cize P1 bude pravdepodobnost, ze sa budeme pytat len na 1.atribut, P2 bude pravdepodobnost, ze sa budeme pytat len na 2.atribut a napr. P13 bude pravdepodobnost, ze sa budeme pytat prave na 1. a 3. atribut.

Ak predpodkladame, ze sa budeme pytat len na jeden atribut, tak mame dane pravdepodobnosti P1, P2, P3 a vsetky ostatne pravdepodobnosti (P12, P23, P13, P123, Pempty) polozime rovne nule, pretoze tie sa nebudu vyskytovat.
Odpovědět

Zpět na „2006“