[Zk] 2008-01-16

Logické a fyzické schéma souboru, logický a fyzický záznam. Základní databázové operace. Hierarchie pamětí, magnetická páska, magnetický disk, RAID, jukebox. Halda, sekvenční soubor, index-sekvenční soubor, indexovaný soubor. Bitové indexy. Jednoduchá hašovací schemata. Perfektní hašování. Dynamické hašování, skupinové štěpení stránek. Hašovací schemata na částečnou shodu. B-stromy, B+-stromy. B*-stromy, (a,b)-stromy. Srovnání paralelního přístupu pomocí B-stromů a (a,b)-stromů. Struktury pro vícerozměrnou indexaci: VB-stromy, vícerozměrná mřížka. n-cestný algoritmus třídění.
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

[Zk] 2008-01-16

Příspěvek od Lukas Mach »

1. Skupinove stepeni

V zadani byly uz nakreslene 3 skupiny po 3 strankach, v nich nejake prvky + oblast preteceni se dvemi prvky. Podle toho, jak byly zahashovane se jeste nestepilo. Mel se vzit novy prvek (22), zahashovat hlavni hashovaci funkci (vyslo 4), dat do te stranky a protoze se jednalo o 19. pridany prvek (predtim v tabulce bylo 18 prvku), mela se rozstepit prvni skupina stranek prvni hashovaci funkci. Jeste celkem jednoduchy.

2. Castecna shoda pomoci hashovani

Zadane pravdepodobnosti a pocet bloku (16378). Podle poctu bloku maji adresy 14 bitu (= 2^14). Pravdepodobnosti vyhledavani podle jednotlivych atributu byly P_A = P_B = 0.4, P_C = 0.2. Melo se vypocitat, kolik ktery atribut dostane bitu (A => 5, B => 5, C => 4). Plus cena za vyhledavani podle atributu B a pak podle dvojice atributu A a C.

3. B-strom - insert a delete

Jednoducheasy.

4. Co je tercialni pamet

Jukeboxy magnetickych pasek (a podobne) a ze je to na data, ktera potrebujeme udrzovat, ale nepotrebujeme k nim pristupovat casto.

5. K cemu je vicerozmerna mrizka, kdy bychom ji meli pouzit.

Vyhledavani podle vice atributu.

6. Larson-Kajla

Pridat jeden prvek - ten samozrejme vytlacil ze stranky jiny, mela se zmenit signatura stranky a vytlaceny prvek zahashovat do dalsi stranky.

7. Jak v invertovanem souboru pro kolekci dokumentu hledat frazi.

Udrzovat si seznamy dokumentu, pozice, najit prunik dokumentu a zkontrolovat podle pozic, jestli jsou slova ve spravnem poradi + vedle sebe.
Naposledy upravil(a) Lukas Mach dne 16. 1. 2008 19:51, celkem upraveno 1 x.
For every epsilon, there is delta.
Where is my delta?
Sakuri
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 8. 1. 2007 20:45

Re: [Zk] 2008-01-16

Příspěvek od Sakuri »

Zadane pravdepodobnosti a pocet bloku (16378). Podle poctu bloku maji adresy 14 bitu (= 2^14). Pravdepodobnosti vyhledavani podle jednotlivych atributu byly P_A = P_B = 0.4, P_C = 0.2. Melo se vypocitat, kolik ktery atribut dostane bitu (A => 5, B => 5, C => 2). Plus cena za vyhledavani podle atributu B a pak podle dvojice atributu A a C.
Teda nevim, jestli nejde jen o preklep, ale ten treti atribut by mel dosta 4 bity? Prece ten soucet musi davat zase tech 14...
kavos
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 22. 1. 2006 14:57

Re: [Zk] 2008-01-16

Příspěvek od kavos »

Lukas Mach píše:
V zadani byly uz nakreslene 3 skupiny po 3 strankach, v nich nejake prvky + oblast preteceni se dvemi prvky. Podle toho, jak byly zahashovane se jeste nestepilo. Mel se vzit novy prvek (22), zahashovat hlavni hashovaci funkci (vyslo 4), dat do te stranky a protoze se jednalo o 19. pridany prvek (predtim v tabulce bylo 18 prvku), mela se rozstepit prvni skupina stranek prvni hashovaci funkci. Jeste celkem jednoduchy.
1) Jak se pozná, kdy se má přidat stránka? Pro úplnost dodávám, že v zadání bylo uvedeno L=2, tedy by se měla přidávat po každých dvou prvcích. Ale proč po 19. prvku a ne třeba po 20.?

2) a když se přidá stránka do 3×3, nemělo by se ještě reorganizovat?

Díky
ranger_86
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 16. 6. 2007 17:01

Re: [Zk] 2008-01-16

Příspěvek od ranger_86 »

Nevim jak vy, ale podle me mela prijit ta hodnota 22 (skupinove stepeni, pr1) do oblasti preteceni. Fakt je ten, ze podle skript a wiki se stepeni provadi po kazdych 2 operacich. Vyjimkou je zacatek behu. Na zacatku se vse plni tak dlouho, nez je nektera stranka naplnena, tehdy dochazi k prvnimu stepeni a pak v intervalech co 2 operace. Coz se ze zadani nedalo zjistit, jestli uz ma dojit ke stepeni ci nikoliv.
A u toho priklady s atributy a pravdepodobnostmi, nemusi byt nahodou adresa nasobkem 8 bitu ??? Jen myslenka
Sakuri
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 8. 1. 2007 20:45

Re: [Zk] 2008-01-16

Příspěvek od Sakuri »

1) Jak se pozná, kdy se má přidat stránka? Pro úplnost dodávám, že v zadání bylo uvedeno L=2, tedy by se měla přidávat po každých dvou prvcích. Ale proč po 19. prvku a ne třeba po 20.?
Ja jsem tu pisemku nevidela, takze muzu jen hadat - pokud na uplnem zacatku (coz nemusi odpovidat obrazku, ktery byl na pisemce - protoze tam muze byt znazorneny stav po x stepenich) byly tri skupiny po trech strankach, pak se pri vkladani prvnich prvku muselo stepit az po vložení 18. prvku (protoze prvni stepeni probiha az po Lxn vlozenich, kde n je pocet stranek). Takze si myslim, ze stepit by se melo po osmnactem prvku a pak vzdy po dalsich dvou - ted po 20., 22. atd. Takze podle me se po 19. prvku teda rozhodne stepit nic nemusi - otazka je, jestli nebylo treba stepit jeste predtim - pokud je pravda, ze to z obrazku vypadalo, ze se jeste nestepilo, melo se to udelat jeste pred vlozenim 19. prvku.... Ale jak rikam, nevidela jsem tu pisemku, takze vsechno bez zaruky:) Bylo zadano s a g?
Sakuri
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 8. 1. 2007 20:45

Re: [Zk] 2008-01-16

Příspěvek od Sakuri »

ranger_86 píše:Nevim jak vy, ale podle me mela prijit ta hodnota 22 (skupinove stepeni, pr1) do oblasti preteceni. Fakt je ten, ze podle skript a wiki se stepeni provadi po kazdych 2 operacich. Vyjimkou je zacatek behu. Na zacatku se vse plni tak dlouho, nez je nektera stranka naplnena, tehdy dochazi k prvnimu stepeni a pak v intervalech co 2 operace. Coz se ze zadani nedalo zjistit, jestli uz ma dojit ke stepeni ci nikoliv.
A u toho priklady s atributy a pravdepodobnostmi, nemusi byt nahodou adresa nasobkem 8 bitu ??? Jen myslenka
Na zacatku se neplni vsechno tak dlouho, nez se zaplni stranka, ale veme se pocatecni pocet stranek a ten se vynasobi L - tolik prvku muzes vlozit a pak musis stepit. Aspon tak nam to rikal Matous na cvicenich u skupinoveho stepeni...
dargor
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 15. 12. 2006 15:00

Re: [Zk] 2008-01-16

Příspěvek od dargor »

Sakuri píše:
Zadane pravdepodobnosti a pocet bloku (16378). Podle poctu bloku maji adresy 14 bitu (= 2^14). Pravdepodobnosti vyhledavani podle jednotlivych atributu byly P_A = P_B = 0.4, P_C = 0.2. Melo se vypocitat, kolik ktery atribut dostane bitu (A => 5, B => 5, C => 2). Plus cena za vyhledavani podle atributu B a pak podle dvojice atributu A a C.
Teda nevim, jestli nejde jen o preklep, ale ten treti atribut by mel dosta 4 bity? Prece ten soucet musi davat zase tech 14...
O jakem zakladu se pouzivaji logaritmy pri vypoctech tech bitu na jednotlive atributy?
Sakuri
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 8. 1. 2007 20:45

Re: [Zk] 2008-01-16

Příspěvek od Sakuri »

O jakem zakladu se pouzivaji logaritmy pri vypoctech tech bitu na jednotlive atributy?
O zakladu dva
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Re: [Zk] 2008-01-16

Příspěvek od Lukas Mach »

Sakuri píše:Teda nevim, jestli nejde jen o preklep, ale ten treti atribut by mel dosta 4 bity? Prece ten soucet musi davat zase tech 14...
Diky, melo to byt skutecne 4.
For every epsilon, there is delta.
Where is my delta?
michael111
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 14. 1. 2008 18:41
Typ studia: Informatika Bc.

Re: [Zk] 2008-01-16

Příspěvek od michael111 »

jejda....a ja som si myslel, ze to dnes uz konecne dam :(
siNm

Re: [Zk] 2008-01-16

Příspěvek od siNm »

uz su prve vysledky...
na to aka bola tazka pisomka to dopadlo celkom dobre :P :P :P :(
http://kocour.ms.mff.cuni.cz/~zemlicka/ ... /zk03.html
Odpovědět

Zpět na „DBI007 Organizace a zpracování dat I“