Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 No zadani si doslova nepamatuju, ale aspon napisu co tam tak zhruba bylo: 1) castecna shoda - zadany 3 atributy + kolik bytu z adresy zabiraji a mela se spocitat cena dotazu, pokud byly dva tributy pevne zadany, tj. 2^to co zabiral ten treti 2) Indexsekvencni soubor se strankama preteceni na konci, nejak zhodnotit jak muze dopadnout INSERT a jeho cenu 3) hashovani, k mod n, zadano jak vypada tabulka. otazka do jake stranky spadne zadany klic a kolik stranek se musi precist, hint: je tam zadano, kolik zaznamu se vejde do jedne stranky... 4) faginovo hashovani nebo-li externi. cena delete kdyz je adresar v pameti a cena v nejhorsim pripade kdyz je adresar na 2 strankach na disku 5) Insert do redudantniho B-stromu, zase nejake ceny a mnozstvi potrebnych bufferu 6) Litwinovo hashovani - kam jednotlive zaznamy prijdou 7) dane cetnosti znaku, vytvorit k nim hufmanuv a S-H kod a porovnat je ktery je lepsi (byly ruzny, ale kvalitativne stejny) 8) Veta, zakodovat pomoci BTSW. ---------- Pisemka byla temer stejna jako ostatni pisemky, zajimavy byl jen priklad c.1: Cormackovo hashovani, napsat jak vypada tvar hashovaci funkce Hi(K,r) pro r=4, a najit takove i, aby Hi(K,4) byla perfektni pro hodnoty klicu 501, 503, 510, 512. ---------- Bylo celkem 7 ukolu. 1) Mame 2B adresy a celkem tri atributy, p1=0.6, p2=0.3, p3=0.1. a) Spoctete nejlepsi rozlozeni jednotlivych bitu z adresy. jestli si dobre vzpominam tak to vyslo 7,5,4 b) Spoctete prumernou cenu dotazu pri tomto ohodnoceni. neco pres 1300 2) Mame Faginovno hasovani, kde adresar je rezidentne v pameti a) kolik je treba alokovat bufferu na INSERT 2 - slo by i s jednim, ale je to zbytecna prace navic b) jaka je nejhorsi I/O pri INSERTU 3 c) adresar je na disku, jak se zmeni pocet I/O, kdyz ukazatel ma 4B, velikost stranky 1KB 6 d) pocet hasovanych bitu z adresy je 8, kolik muze byt maximalne stranek po 1KB, ktere jsme schopni naadresovat. 2^8 e) jaky nejvetsi soubor jste schopni v tomto pripade ulozit? 256 KB 3) Deleni B stromu 4) Mame Litwinovo hasovani, prave vznikla stranka s poradovym cislem jedna. a) kolikata expanze probiha? prvni b) rozdelte prvky mezi stranky jen bylo treba vedet podle ktery bitu se ma delit, ale rikal, ze je to stejne jedno, jestli 1. nebo posl. 5) definujte B-deleni prostoru 6) Mame dany cetnosti 1,1,1,1,3,3,3,3,9,9 a) zkonstruujte Huffmanuv kod b) vysvetlete, co je to sourozenecka vlastnost 7) Mame danu zpravu Prsi, cely den prsi. Cely se chveji. Den co den prsi. A prsi, prsi, prsi. Zakodujte intervalovym kodovanim. Nevedeli jsme, co to je, artmeticky to nebylo, tak rikal, ze je to nejaky specialni BSTW a stacilo mu to. Tot vse, bylo to celkem na 24 bodu, 24-22 jedna, 21-18 dva, 16-17 tri, <15 bye, ale byli jsme tam tri na leto, ja mel 21,5, pak bylo 20,5 a 20. Dal nam vsem jednicky. ---------- 1) Dotazy na castecnou shodu v hasovani. Primarni soubor se tremi atributy (N, RN, R), kterym odpovida postupne 4, 9 a 3 bity v klici. Adresa stranek je dlouha 2B. Jaka je cena dotazu na castecnou shodu s atributy N a R? (2) 2) Index-sekvencni soubor s oblasti preteceni, organizovanou jako spojaky zachovavajici usporadani a strategii "posunuti". Blokovaci faktor je 4. Nejaka stranka primarniho souboru je uz plna a navic pokracuje v oblasti preteceni dvema zaznamy, z nichz kazdy je obsazeny v jiz zaplnenem bloku. a) Do teto primarni stranky se ma vlozit zaznam K a spocitat pocet diskovych I/O operaci - udelat diskusi podle hodnoty K. (2) b) Kolik k tomu potrebujeme nejmene bufferu (alokovat v RAM). (1) 3) Hashujeme pomoci fce k mod 11, b=3. Kolize se resi strategii "Umisti na nejblizsi volne misto". a) Kam bude umisten klic 46 (1) b) Popiste co je potreba udelat pri Delete(12) (2) +-----+ | 0|K1| | 1|12| | 2|K3| | 3| | | 4| | | 5| | | 6| | | 7| | | 8|K4| | 9|K5| |10|K6| +-----+ 4) Rusime zaznam v souboru organizovanem podle rozsiritelneho hashovani s adresarem ve dvou strankach disku. a) Kolik bufferu (= stranek) je treba alokovat ve vnitrni pameti? (1) b) Kolik I/O operaci je treba v nejhorsim pripade (zkracuje se adresar)? (1) 5) Uvazujme posledni dve vrstvy v redundantnim B-stromu, ktery ma 3 urovne. 3 7 21 23 | 9 11 14 15 21 a) Pridejte prvek 10 (1) b) Kolik bufferu je treba alokovat ve vnitrni pameti? (1) c) Kolik I/O operaci je treba pro operaci INSERT v nejhorsim pripade? (1) 6) Litwinova metoda stepeni stranek. Pridali jsme 4. stranku (ma cislo 3). a) Kolikata skoncila expanze? (1) b) Necht ve strance 1 jsou zaznamy 1001111, 1111011, 1010101, 1000001, 1110111. Provedte dalsi expanzi, tj. rozdelte do stranek. (2) 7) Mejme znaky s cetnostmi 1 1 1 2 2 3 3 3 8 9. a) Zkonstruhujte S-F kod. (2) b) Navrhnete prefixovy kod se stejnou prumernou velikosti kodoveho slova, ktery neni Huffmanuv. (2) 8) Zakodujte BSTW kodovanim (bez ohledu na interpunkci a velikost pismen) : Prsi, cely den prsi. Cely se chveji. Den co den prsi. A prsi, prsi, prsi. (2). --------- dneska byla pis z OZD, zadani nejasne, zmatecne. Neni to asi vsechno a taky to neni uplne presne, ale here we are: 1. Cena dotazu-castecna shoda-zadany dve polozky ze tri rozdeleni (3, 9, 4), ty 3, 4 byly zadany takze podle me je to 2^9 2.Hash-kolize na na nejblizsi volne misto, Jakysi udaj b=3(nobody knows nobody sees) 3.Index-sekv. soubour - preteceni s posuvem(taky netusim,cotoje), kolik potrebuju I/O, kolik potrebuju bufferu 4.B-strom rozdelit uzel a pocet I/O a bufferu 5.a)Zakodovat Shanno-Fanno b)najit prefix kod se stejnou delkou slova,ale ne Huff 6.Zakodovat pomoci Interval. kodovani-Zemle konstatovala,zesme to nedelali a dal tam BSTW(ze by to bylo tim,ze zkousi nekdo jinej,nez prednasi?) 7.Mazani ve Faginovi: adr je ve 2 str. kolik na to potrebuju IO, bufferu mikolas ---------- 1) dotaz na castecnou shodu pro pravdepodobnosti 0.6 0.3 0.1 a) optimalni delky signatur (3) b) prumerna cena dotazu (2) 2) rozsiritelne hasovani. adresar podle hornich 4 bitu. a) kolik bufferu v RAM na INSERT (1) b) kolik I/O operaci (1) c) velikost adresare pro adresy 4B (1) d) velikost stranky je 2K, adresar na disku. jak se zmeni odpoved b) (1) e) max. velikost souboru s timto adresarem. (1) 3)B-strom INSERT (2) (nemusel se pridat novy koren, cisla si napamatuju) 4) Grayuv kod a) definice (1) b) kod pro 3 bity (2) c) nejaky shluky pro 10tku (2) (graye jsem vynechal) 5) Huffmanuv strom pro 1,1,1,1,3,3,3,3,9,9 nakreslit (2) 6) prumerna delka slova z 5tky (2) 7) BSTW zakoduj: a chalupu a chalupu dostane od taty od taty (2) 8) porovnat prum delku kodoveho slova u huffmana a bstw. (2) chtel tam slyset, ze huffmn je obecne lepsi, bstw muze na urcitym vzorku prekvapit. --------- BTW: snad u vsech mailu ktere se vztahovaly k pisemce z OZD s Pokornym byla dole poznamka "Pokorny je opravdu hodny" .. snad na tom bude neco pravdy ;)