Dotazy na castecnou shodu

D
Matfyz(ák|ačka) level I
Příspěvky: 32
Registrován: 20. 12. 2006 17:42

Dotazy na castecnou shodu

Příspěvek od D »

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?

Akosi mi tam chybaju pravdepodobnosti. Neviete niekto ako sa daju spocitat? Tu cenu dotazu som chcel spocitat ako 2^3 * P(Rok)
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

Mne prijde ze konkretne to spocitat nelze, je to 2^3 * cena dotazu na uplnou shodu (musim vyzkouset vsechny moznosti hashe ROKu ) ... co myslite?
Plug 'n' Pray.
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Příspěvek od Hugo »

Ona je tam presne popsana jenom prumerna cena dotazu (s tema pravdepodobnostma).
Ja bych mu na to odpovedel podobne, jak o cene dotazu pise ve skriptech.
Ze je potreba pri vyhodnocovani projit 2^3 krat vice stranek.
Naposledy upravil(a) Hugo dne 7. 1. 2007 20:03, celkem upraveno 1 x.
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

Nevím už kde sem to viděl, ale mám takovej pocit že už někde jo: Cena dotazu = kolik stránek musím prohledat když znám určité atributy, tedy pro NAZEV je to 2^(3+4) musím tedy prohledat 128 stránek, jestli to tam není. Snad jen nekecám a opravdu to tak je :roll:
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

Dawe píše:Nevím už kde sem to viděl, ale mám takovej pocit že už někde jo: Cena dotazu = kolik stránek musím prohledat když znám určité atributy, tedy pro NAZEV je to 2^(3+4) musím tedy prohledat 128 stránek, jestli to tam není. Snad jen nekecám a opravdu to tak je :roll:
No spis 128 * vic nez kdybys mel zadany vsechno ? Nebo se v tehle prikladech implicitne predpoklada jediny pristup na disk pro vyhledani prvku?
Plug 'n' Pray.
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

No podle mě máš dáno, že jestliže máš kus adresy 10?? tak je daný, že to musíš najít někde na 1000,1001,1010,1011 a nikde jinde ne?
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

Dawe píše:No podle mě máš dáno, že jestliže máš kus adresy 10?? tak je daný, že to musíš najít někde na 1000,1001,1010,1011 a nikde jinde ne?
No to jo ... ale je dany, ze na prohledani 1000, 1001, 1010, 1011 potrebuju projit prave 4 stranky?
Plug 'n' Pray.
Uživatelský avatar
Dawe
Supermatfyz(ák|ačka)
Příspěvky: 360
Registrován: 12. 10. 2004 12:32
Typ studia: Informatika Mgr.
Bydliště: Doma a nebo na koleji

Příspěvek od Dawe »

Jo máš recht... už mi to secvaklo...
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

re

Příspěvek od Necroman »

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
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Uživatelský avatar
lavor
Matfyz(ák|ačka) level III
Příspěvky: 121
Registrován: 1. 2. 2005 20:39
Typ studia: Informatika Bc.
Bydliště: kolej 17.11., A1105
Kontaktovat uživatele:

Re: re

Příspěvek od lavor »

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 :lol:, mozno cosi na prednaske bolo ale urcite tiez len okrajovo
btw: nemohlo to byt na cviceni lebo je zato na skuske az 5 bodov :twisted:
Milujeme tých, čo nás odmietajú, odmietame tých, čo nás milujú.
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 »

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?
Uživatelský avatar
Hugo
Donátor
Donátor
Příspěvky: 233
Registrován: 2. 6. 2005 13:31
Typ studia: Informatika Mgr.
Bydliště: treti kontejner zleva
Kontaktovat uživatele:

Příspěvek od Hugo »

0.75 * 2^4 + 0.24 * 2^5 + 0.01 * 2^9 = 24.8
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 »

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..
Pavel J

Příspěvek od Pavel J »

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) ?
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

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 ;)
Plug 'n' Pray.
Odpovědět

Zpět na „2006“