2.2.1 Poˇcet z´aznam˚u v datab´azi
Podle poˇctu jednotliv´ych krit´eri´ı je moˇzn´e pˇribliˇznˇe urˇcit, kolik seznam˚u by mˇelo minim´alnˇe existovat, aby byly pokryty vˇsechny moˇznosti. Z tohoto ´udaje je pak moˇzn´e odhadnout probl´emy, kter´e by mohly nastat.
Krit´eria m˚uˇzeme rozepsat jako:
K1, K2, K3, K4....Kn, J1, J2, J −3, ..., Jn
Pro kaˇzd´e krit´erium Ki bude zvolen´a konkr´etn´ı hodnota krit´eria pˇredstavov´ana podmnoˇzinou nab´ızen´ych hodnot, tedyki ⊆Ki. Pokud je zn´am celkov´y poˇcet moˇznost´ı|Ki| krit´eria Ki, je celkov´y poˇcet moˇzn´ych hodnot tohoto krit´eria
2.2. Matematick´y model d´an celkov´ym poˇctem podmnoˇzin, tedy mohutnost´ı potenˇcn´ı mnoˇziny
2|Ki|
Pokud neuvaˇzuji vˇsechny podmnoˇziny, ale napˇr´ıklad jen podmnoˇziny ob-sahuj´ıc´ı 1...r moˇzn´ych hodnot, pak pouˇziji vzorec
|Ki| 1
+ |K2i|+ |K3i|+...+ |Kri|
Druh´a skupina krit´eri´ıJ1, J2, J3, ..., Jmpˇredstavuje takov´a, kde z nab´ızen´e mnoˇziny hodnot Ji mohu vˇzdy zvolit pouze jedinou, m´am tedy pˇresnˇe |Ji| moˇznost´ı. Tak celkov´y poˇcet moˇzn´ych kombinac´ı lze zapsat jako:
[ |K1i|+ |K2i|+ |K3i|+...+ |Kri|]∗ |J1| ∗ |J2| ∗ |J3| ∗...∗ |Jm|
T´ımto vzorce jsem schopen zjistit jak velk´y poˇcet seznam˚u je potˇreba k obs´ahnut´ı vˇsech moˇzn´ych kombinac´ı krit´eri´ı.
Je nutn´e ovˇsem poˇc´ıtat s t´ım, ˇze nˇekter´e zadan´e seznamy budou m´ıt stejn´a krit´eria a t´ım se zv´yˇs´ı poˇcet potˇrebn´ych seznam˚u pro obsaˇzen´ı vˇsech krit´eri´ı.
Tento probl´em popisuje Cupon collector problem.
Cupon collector problem se zab´yv´a ot´azkou, kolik je potˇreba zakoupit unik´atn´ıch pˇredmˇet˚u, abychom z´ıskali vˇsechny. Pˇr´ıkladem m˚uˇze b´yt zaku-pov´an´ı sbˇeratelsk´ych kartiˇcek, kter´e jsou prod´av´any v bal´ıˇck´ach po nˇekolika kart´ach. Karty jsou v tˇechto bal´ıˇcc´ıch n´ahodnˇe um´ıstˇeny. M˚uˇze se st´at, ˇze pˇri zakoupen´ı dvou bal´ıˇck˚u budou nˇekter´e karty stejn´e. ˇReˇsen´ım tohoto probl´emu mohou sbˇeratel´e urˇcit, kolik takov´ychto bal´ıˇck˚u budou muset koupit, aby z´ıskali celou kolekci. Jak vypl´yv´a z tohoto zdroje [1]
D´ıky tomuto probl´emu lze urˇcit, kolik seznam˚u je skuteˇcnˇe potˇreba pro naplnˇen´ı vˇsech krit´eri´ı. Pomoc´ı poˇctu moˇzn´ych kombinac´ı krit´eri´ı a pouˇzit´ı aproximaˇcn´ıho vzorce pro v´ypoˇcet tohoto probl´emu, kter´y je n´asleduj´ıc´ı,
E[X] =y(ln(y) + Γ) + 1/2
,se tento poˇcet potˇrebn´ych seznam˚u dozv´ım.
Do tohoto vzorce za y dosad´ım vypoˇcten´e ˇc´ıslo moˇzn´ych kombinac´ı krit´eri´ı.
Za Γ dosad´ım Euler-Mascherovu konstantu, kter´a je rovna pˇribliˇznˇe 0.577216.
Pro objasnˇen´ı jak je moˇzn´e, ˇze nˇekter´e seznamy budou stejn´e z pohledu matematiky, pouˇziji Narozeninov´y paradox.
Narozeninov´y paradox se zab´yv´a ot´azkou, pˇri jak´em poˇctu osob v m´ıstnosti je pravdˇepodobnost pro n´ahodn´e dvˇe osoby, aby mˇeli narozeniny ve stejn´y den.
Pokud napˇr´ıklad osob v m´ıstnosti je 23, tak pravdˇepodobnost, ˇze tento jev na-stane je rovna 50%. Tento paradox se vyuˇz´ıv´a napˇr´ıklad v bezpeˇcnosti. [2]
K z´ısk´an´ı pravdˇepodobnosti shody je pouˇzit opaˇcn´y numerick´y proces.
Nejprve vypoˇctu, jak´a je pravdˇepodobnost, ˇze vˇsechny seznamy jsou odliˇsn´e.
N´aslednˇe zbyl´a pravdˇepodobnost do 100%, je pravdˇepodobnost pro shodu ale-spoˇn dvou seznam˚u. V t´eto pr´aci budu uvaˇzovat jak´a je pravdˇepodobnost, ˇze shoda je 50%.
Prvn´ı je nutn´e vypoˇc´ıtat poˇcet moˇzn´ych dvojic seznam˚u. Pro tento v´ypoˇcet vyuˇziji n´asleduj´ıc´ı vzorec.
z=s∗(s–1)
kde s je poˇcet seznam˚u. D´ale vypoˇctu pravdˇepodobnost, ˇze jeden p´ar je unik´atn´ı. Za pomoci n´asleduj´ıc´ıho vzorce
p(t) =c∗(c–1)
Promnˇen´a c zde oznaˇcuje poˇcet vˇsech moˇzn´ych krit´eri´ı. ˇSance, ˇze vˇsechny seznamy budou unik´atn´ı, je:
p(u) =p(t)z
P(u) je pravdˇepodobnost, ˇze vˇsechny p´ary budou unik´atn´ı, jelikoˇz se snaˇz´ım zjistit poˇcet nutn´ych seznam˚u, pro urˇcitou pravdˇepodobnost. P(u) se bude rovna t´eto pravdˇepodobnosti. Jak jsem dˇr´ıve zm´ınil tato pravdˇepodobnost se bude rovnat 50%. Zn´am tedy p(u) a mohu si tak´e spoˇc´ıtat p(t). Z posledn´ıho vzorce spoˇc´ıt´am z, z dosad´ım do prvn´ıho vzorce a vypoˇctu s. S pak oznaˇcuje mnou hledan´y poˇcet seznam˚u, kter´y je potˇreba pro 50% pravdˇepodobnost, alespoˇn 2 stejn´ych seznam˚u.
Tuto anal´yzu nyn´ı aplikuji na pˇredpokl´adan´e poˇcty krit´eri´ı v aplikaci Ea-sypacking
Na pˇr´ıkladu aplikace EasyPacking se budu snaˇzit uk´azat, ˇze d´ıky uve-den´ym probl´em˚um nestaˇc´ı pouze urˇcit poˇcet kombinac´ı jednotliv´ych krit´eri´ı.
Je tak´e nutn´e uvaˇzovat jak pravdˇepodobn´e je, ˇze uˇzivatel´e zadaj´ı seznam se stejn´ymi krit´erii. Pro jednoduchost nebudu uvaˇzovat ve v´ypoˇctech, ˇze nˇekter´e destinace nebo aktivity jsou v´ıce vyuˇz´ıv´any.
2.2. Matematick´y model M˚uˇzu poˇc´ıtat, ˇze na svˇetˇe je pˇribliˇznˇe 200 st´at˚u. D´ale pro utvoˇren´ı pˇredstavy o poˇctu potˇrebn´ych seznam˚u uvaˇzujme 50 moˇzn´ych aktivit, kter´e uˇzivatel´e aplikace budou provozovat na sv´ych cest´ach. Posledn´ımi dvˇema krit´erii je vˇek a pohlav´ı. Pohlav´ı tvoˇr´ı dvˇe moˇznosti. Co se t´yˇce vˇeku, aplikace vyhled´av´a v rozsahu +-5 let od uˇzivatelem zadan´eho vˇeku. Pokud budu uvaˇzovat uˇzivatele v rozpˇet´ı vˇeku 10 – 60 let. Tedy uˇzivatele co jiˇz cestuj´ı a pouˇz´ıvaj´ı chytr´y telefon. Mˇelo by postaˇcit d´ıky intervalu +-5 let 6 z´aznam˚u, kter´e budou rov-nomˇernˇe rozm´ıstˇeny v intervalu 10-60 let.
Z pˇredeˇsl´e ´uvahy vych´az´ı n´asleduj´ıc´ı poˇcty jednotliv´ych krit´eri´ı
• 50 aktivit
• 200 st´at˚u
• 2 pohlav´ı
• 6 odliˇsn´ych vˇekov´ych kategori´ı
Nen´ı pravdˇepodobn´e, ˇze by uˇzivatel zaˇskrtl vˇsechny aktivity. Budu poˇc´ıtat s t´ım, ˇze rozumn´e ˇc´ıslo pro maxim´aln´ı poˇcet aktivit pro jednu cestu je 4. Takto se dostaneme, pomoc´ı dosazen´ı do dˇr´ıve zmiˇnovan´eho vzorce na
[ 501+ 502+ 503+ 504]∗200∗2∗6 = 602820000
D´ale se pouˇziji Cupon collector problem pro zjiˇstˇen´ı poˇctu potˇrebn´ych seznam˚u, tak aby byly vˇsechny krit´eria obs´ahnuta. Dosad´ım do pˇredeˇsl´eho vzorce.
602820000∗(ln(602820000) + 0.577216) + 1/2 = 1.2535247∗1010
Z pˇredeˇsl´eho v´ypoˇctu je vidˇet, ˇze pro naplnˇen´ı vˇsech krit´eri´ı je potˇreba pˇribliˇznˇe dvacetkr´at v´ıce z´aznam˚u.
Jak je vidˇet z v´ysledku v´ypoˇctu, takov´yto poˇcet z´aznam˚u je skoro nemoˇzn´e uchov´avat v datab´azi. Z´aroveˇn vyhled´av´an´ı v takov´em to objemu dat by bylo opravdu pomal´e. Je nutn´e omezit poˇcet tˇech nejvˇetˇs´ıch kriteri´ı. T´ım je jak destinace, tak aktivity.
Ohlednˇe destinac´ı m˚uˇzu poˇc´ıtat s t´ım, ˇze nˇekter´e destinace nejsou navˇstˇevov´any, napˇr´ıklad s ohledem na situaci v tˇechto zem´ıch. D´ale ne v kaˇzd´e destinaci lze prov´adˇet vˇsech 50 aktivit. Ovˇsem ani tento pˇredpoklad nesn´ıˇz´ı poˇcet seznam˚u dostateˇcnˇe.
M˚uˇzu ovˇsem ˇr´ıci, ˇze nˇejak´e seznamy budou velice podobn´e popˇr´ıpadˇe do-konce shodn´e. Pˇr´ıkladem m˚uˇze b´yt lyˇzov´an´ı v Alp´ach nebo dovolen´a u moˇre v jiˇzn´ı Evropˇe. Je tedy zbyteˇcn´e uchov´avat takto shodn´e seznamy. Bylo by tedy v´yhodn´e vytvoˇrit ”slovn´ık”spoleˇcn´ych destinac´ı a aktivit, kde je pˇredpoklad, ˇze seznamy budou stejn´e. Na z´akladˇe tohoto omezit poˇcet podobn´ych seznam˚u.