Zkouška 16. ledna 2008

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í.
Petr2

Zkouška 16. ledna 2008

Příspěvek od Petr2 »

Vážení,
přináším Vám report z dnešní zkoušky. Vše jak jsem byl schopen si zapamatovat, takže pokud mě někdo doplní budu jen rád :) .
Bodování je asi takové : 25-22 výborně; 21-19 velmi dobře; 18-16 dobře; 15 neprospěl
1. ) neredundantní B strom, odebrání prvku - nějak se to rozpadlo [ 3b ]
2. ) popište kdy je lepší HDD a kdy SSD (respektive flash paměti) [ 2b ]
3. ) hašování s částečnou shodou, dány čtyři atributy a pravděpodobnosti, rozdělení na bity za [ 2b ], cena dotazu [ 1b ] byl zadán atribut, střední cena dotazu [ 1b ]
4. ) Cormack [ 6b ] - bylo to rozděleno, na dvě části; hlavní úkol byl kdy to použijete, co si musíte rozmyslet, podle čeho si to budete rozmýšlet.
5. ) Fagin - šlo o to vložit záznam, rozpadala se jen stránka ne adresář - [ 2b ]
6. ) Něco na běhy, třídění - tady si to nepamatuju - [ 2b ]
7. ) K čemu je dobrý indexový soubor? (Během zkoušky dvakrát zdůraznil, že si máme pořádně tu otázku přečíst, protože většina odpovídá na něco jiného.) [ 2b ]
8. ) Kombinovaný index. Co to je, kdy to použít, jaké jsou s tím problémy / překážky (teď nevím přesně)? [ 3b ]
tož ogaři, někde mi tam chýbá 1b tak to někdo opravte
Dobrá rada na závěr kdo odevzdal dřív, tak to zpravidla dostal zpátky do ruky s tím, co má opravit :!: , takže ;-)
Hodně zdaru (nejen) u zkoušky z Odporných a Zrůdných Dat
Xerxes
Matfyz(ák|ačka) level I
Příspěvky: 37
Registrován: 23. 1. 2007 16:32
Typ studia: Informatika Bc.
Bydliště: Zlínský kraj / Kolej 17. listopadu
Kontaktovat uživatele:

Re: Zkouška 16. ledna 2008

Příspěvek od Xerxes »

Doplním, co si (snad) pamatuju:

3) Čtyři atributy s pravděpodobnostmi 1/2, 1/4, 1/6 a 1/12, adresa má 14 bitů.
a) Rozvrhnout schéma. [3b]
b) Cena dotazu na druhý atribut. [1b]
c) Průměrná cena dotazu. [1b]

4) Máme hotovou knihovnu na Cormacka.
a) Kdy je vhodné ji použít? [2b]
b) Jaké parametry bude třeba nastavit? [4b]

6) Máme 220 běhů, kolikacestné slévání použít, abychom to setřídili na 2 průchody?

Komentář:

1) Odebírání prvku v neredundantním B-stromu (m = 5), strom měl tři patra, prvek byl v krajním listu, sousední list byl na minimu -> sloučili se, rodič ale byl taky na minimu -> podtekl -> jeho soused měl 3 prvky, jeden mu tedy přes kořen půjčil.

3) Vyšlo to tuším po řadě 5, 4, 3 a 2 bity. Dotaz na druhý atribut má cenu 1024, průměrná cena dotazu byla cca 1195.

4) Cormack to sice byl, ale spíš teoretická okecávačka.

6) Řekl bych 15-cestné.

7) Tady Žemličkovi prý skoro všude chybělo, že indexovaný soubor slouží k ukládání dat (duh!). Ostatní charakteristiky ale chtěl taky...
Petr2 píše:tož ogaři, někde mi tam chýbá 1b tak to někdo opravte
Myslím, že 3a) bylo za tři, ale jistý si nejsem.
Petr2 píše:Dobrá rada na závěr kdo odevzdal dřív, tak to zpravidla dostal zpátky do ruky s tím, co má opravit :!: , takže ;-)
Lidi víceméně stáli řadu na to, aby jim to prohlédl a okomentoval, takže měl co dělat :cool:...

Jo a ještě říkal, že to začne opravovat až tak za týden, protože je někde pryč.
Uživatelský avatar
Yawgmoth
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 17. 5. 2007 20:09
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zkouška 16. ledna 2008

Příspěvek od Yawgmoth »

Xerxes píše: 6) Máme 220 běhů, kolikacestné slévání použít, abychom to setřídili na 2 průchody?
ona byla ta otázka zadaná trochu pochybně, bylo tam cosi jako "Abychom co nejlépe využili zdroje a použili maximálně 2 průchody." Ovšem co se považuje za nejlepší využití zdrojů ... Teoreticky pokud máme 220 běhů na 220 různých médiích ze kterých jsme schopni číst najednou tak se vyplatí 220 cestné třídění na jeden průchod :)

Ale taky jsem napsal 15...
Xerxes píše: Jo a ještě říkal, že to začne opravovat až tak za týden, protože je někde pryč.
tohle mě teda nepotěšilo :(
navstevnik

Re: Zkouška 16. ledna 2008

Příspěvek od navstevnik »

Yawgmoth píše: ona byla ta otázka zadaná trochu pochybně, bylo tam cosi jako "Abychom co nejlépe využili zdroje a použili maximálně 2 průchody." Ovšem co se považuje za nejlepší využití zdrojů ... Teoreticky pokud máme 220 běhů na 220 různých médiích ze kterých jsme schopni číst najednou tak se vyplatí 220 cestné třídění na jeden průchod :)

tohle mě teda nepotěšilo :(
Otazka je, co nazyvame zdroji. O tom, jestli mame urcity pocet medii nebo jen souboru nebyla v pismece zadna zminka, takze bych spise uvazoval o zdrojich jako filedeskriptorech, rezijni pameti...
Uživatelský avatar
Donarus
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 30. 9. 2007 12:40
Typ studia: Informatika Mgr.

Re: Zkouška 16. ledna 2008

Příspěvek od Donarus »

je prosim moje reseni 3ky spravne ? furt se v tom motam

Kód: Vybrat vše


pocet bitu = 14

			A	B	C	D
P daného jevu		1/2	1/4	1/6	1/12
log2 z dané P		-1	-2	-2,585	-3,585


d(jevu) = (#bitu - ( -1 -2 -2,585 -3,585 ))/n + (log2 z dané P)
	= 5,7925 + (log2 z dané P)

=>

d(A) = 4,7925 = cca = 5
d(B) = 3,7925 = cca = 4
d(C) = 3,2075 = cca = 3
d(D) = 2,2075 = cca = 3


rozdeleni(A,B,C,D) = (5,4,3,3)



dale cena jednotlivych dotazu uz je easy
cena A = 2^9 = 512
cena B = 2^10 = 1024
cena C = 2^11 = 2048
cena D = 2^11 = 2048


a prumerna cena dotazu je taktez easy
512*1/2 + 1024*1/4 + 2048*1/6 + 2048*1/12 = 256+256+341,333+170.666 = cca 1024





JiriD
Matfyz(ák|ačka) level I
Příspěvky: 44
Registrován: 2. 2. 2008 09:35
Typ studia: Informatika Bc.

Re: Zkouška 16. ledna 2008

Příspěvek od JiriD »

Donarus píše:je prosim moje reseni 3ky spravne ? furt se v tom motam
Postup máš správný, ale máš tam početní chybu.
Donarus píše: d(D) = 2,2075 = cca = 2
Navíc ti nevycházelo 14 bitů (5+4+3+3 = 15).

JInak je to dobře.
Wenn ich morgen meinem Gott gegenüberstehe, kann ich sagen:
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.

Und das wird er mir wohl verzeihen!
Odpovědět

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