Fórum studentů MFF UK

od mk » 4. 1. 2008 20:27

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 P_q. Cize P₁ bude pravdepodobnost, ze sa budeme pytat len na 1.atribut, P₂ bude pravdepodobnost, ze sa budeme pytat len na 2.atribut a napr. P₁₃ 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 P₁, P₂, P₃ a vsetky ostatne pravdepodobnosti (P₁₂, P₂₃, P₁₃, P₁₂₃, P_empty) polozime rovne nule, pretoze tie sa nebudu vyskytovat.

od **Trupik** » 6. 2. 2007 10:37

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.

od **Návštěvník** » 6. 2. 2007 09:36

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.

od **gofry** » 23. 1. 2007 10:12

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.

od **gASK** » 23. 1. 2007 09:37

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)

od **christyna** » 23. 1. 2007 09:33

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?

od **twoflower** » 14. 1. 2007 13:36

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)...

od **twoflower** » 14. 1. 2007 09:47

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

od **Tuetschek** » 14. 1. 2007 00:08

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

od **Pavel J** » 13. 1. 2007 23:41

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) ?

od **twoflower** » 13. 1. 2007 18:27

Hugo píše:0.75 * 2^4 + 0.24 * 2^5 + 0.01 * 2^9 = 24.8

Ahaa, diky!

Ac v zadani vyslovne uvedeno "Predpokladejme dotazy pouze na jeden atribut", pocital jsem samozrejme prumernou cenu dotazu, jako kdybychom mohli specifikovat vice atributu.

K tomu jeste jeden dotaz: kdyz bych mel zadano, ze pri dotazech muzu specifikovat vice atributu, tak pri pocitani prumerne ceny dotazu mam zahrnovat i "nulovy" dotaz, tj. dotaz, kde nespecifikuji zadny atribut?

Podle skript by to jit melo, ale na druhou stranu se mi to moc nezda, tak nevim..

od **Hugo** » 13. 1. 2007 18:17

0.75 * 2^4 + 0.24 * 2^5 + 0.01 * 2^9 = 24.8

od **twoflower** » 13. 1. 2007 18:07

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?

od **lavor** » 11. 1. 2007 12:26

Necroman píše:Měl bych dotaz, nemáte někdo zápisky ze cvičení či prednášky, kde se prováděl výpočet na částečnou shodu? Nějak jsem to asi prospal a nic moc o tom nevím. Jakékoliv příspěvky ocením, (třeba skeny ze sešitu ). dík moc

no ak takeho cloveka najdes, tak bude prvy kto to ma

, mozno cosi na prednaske bolo ale urcite tiez len okrajovo
btw: nemohlo to byt na cviceni lebo je zato na skuske az 5 bodov

od **Necroman** » 11. 1. 2007 11:20

Měl bych dotaz, nemáte někdo zápisky ze cvičení či prednášky, kde se prováděl výpočet na částečnou shodu? Nějak jsem to asi prospal a nic moc o tom nevím. Jakékoliv příspěvky ocením, (třeba skeny ze sešitu

). dík moc

Fórum studentů MFF UK

Dotazy na castecnou shodu

Odeslat odpověď

Rozšířit náhled Přehled tématu: Dotazy na castecnou shodu

Re: Dotazy na castecnou shodu

Re: Dotazy na castecnou zhodu

Re: Dotazy na castecnou zhodu

Re: re

re