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 :-/Tuetschek píše:Ja si taky myslim ze to ma byt spis takhle ... protoze jestli ne tak to mam blbe v pisemcePavel 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) ?
Dotazy na castecnou shodu
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
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.Tuetschek píše:Ja si taky myslim ze to ma byt spis takhle ... protoze jestli ne tak to mam blbe v pisemcePavel 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) ?
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)...
Re: Dotazy na castecnou zhodu
Nemohl by nekdo tedy napsat, jak to ma presne byt?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?
-
- Admin(ka) level I
- Příspěvky: 635
- Registrován: 9. 6. 2005 12:33
- Typ studia: Informatika Mgr.
- Login do SIS: BUREJ3BM
- Bydliště: Konečně Vinohrady:)
- Kontaktovat uživatele:
Re: Dotazy na castecnou zhodu
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é.christyna píše: Nemohl by nekdo tedy napsat, jak to ma presne byt?
Obecně je to "pavzorec" 2^(počet otazníků v dotazu)
When life gives you crap, make crap golems.
Ty by si vlastne mal chcieť počítaťPavel J píše:Proč to neníHugo píše:0.75 * 2^4 + 0.24 * 2^5 + 0.01 * 2^9 = 24.8
(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) ?
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)
Ale zrejme
Kód: Vybrat vše
P(non[B&C]) = P(A)
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)
Kód: Vybrat vše
(2^db)*(2^dc) = 2^(d-da)
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).
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:
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.
Ja neviem kde robim chybu, pretoze podla toho vzorca co ma na stranke by sa d1 malo rovnat.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?
(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.
- 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:
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.
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!
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!
Re: Dotazy na castecnou shodu
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.
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.