Tak ja se pomalu zacinam ucit na zkousku a budu tady mit obcas nejake dotazy
1) Litwin: "predpoklada se hasovaci funkce h(K), ktera pro libovolny klic vrati binarni cele cislo v dostatecnem rozsahu" (skripta). Ale my jsme nikdy zadnou hasovaci funkci neuvazovali, a vkladali jsme rovnou to, co prislo. Tak jak to je? A jak ma takova hasovaci funkce prosim vypadat, kdyz se kazdou chvili zvetsuji cisla stranek?
2) B stromy s promennou delkou zaznamu: B strom je definovany svou hodnotou m, jinak to neni B strom (skripta). Jake m je prosim u stromu s promennou delkou zaznamu? Rekneme, ze velikost bloku je 15.
Par drobnosti
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: Par drobnosti
-no treba v posledni pisemce byly normalne cisla v desitkovy soustave + hashovaci funkce, takze cislo ji vzal, prohnal hashovaci funkci a nakonec jsi to preved do binaru a podle toho zaradil do stranekMedved píše:1) Litwin: "predpoklada se hasovaci funkce h(K), ktera pro libovolny klic vrati binarni cele cislo v dostatecnem rozsahu" (skripta). Ale my jsme nikdy zadnou hasovaci funkci neuvazovali, a vkladali jsme rovnou to, co prislo. Tak jak to je? A jak ma takova hasovaci funkce prosim vypadat, kdyz se kazdou chvili zvetsuji cisla stranek?
-nekdy ale zase bejvalo zes dostal rovnou cisla v binaru a a zadnou funkci, takze jsi je jenom tak jak jsi je mel zaradil do stranek
->z toho vyplyva ze prevod do binaru se pouziva pouze pro zarazeni a nekdy byva podlozen i nejakou tou hashovaci funkci - mrkni na nejaky stary pisemky na studnici + reseny priklad na tohle je taky tady: http://forum.matfyz.info/viewtopic.php?f=386&t=2397
Re: Par drobnosti
Tak nejdriv jedna odpoved:
A ted otazka
3) Delete z B stromu. Puvodne jsem si myslel, ze kdyz mam B strom X1 a mazu prvek A, tak hledam takovy B strom X2, ze kdyz do nej pridam prvek A, dostanu strom X1, tedy proste inverzni operace. To ale neni pravda, protoze treba mazani z korene znamena, ze vezmu nejmensi vetsi v listech a vymenim. No takze ma otazka: dokaze nekdo definovat, jak spravne mazat v B stromech, aby to bylo vzdy korektni dle Zemlicky? Je mi jasny, ze ve skriptech je nakej algoritmus v PASCALu, ale nestiham ho trasovat. A ten stejny dotaz pro B* stromy.
Je to tak, ze muzeme uvazovat, ze kazdy zaznam je velikosti 1 a z toho pak nejake omezeni na m vyjde, ale neni to treba takto formalne brat.2) B stromy s promennou delkou zaznamu: B strom je definovany svou hodnotou m, jinak to neni B strom (skripta). Jake m je prosim u stromu s promennou delkou zaznamu? Rekneme, ze velikost bloku je 15.
A ted otazka
3) Delete z B stromu. Puvodne jsem si myslel, ze kdyz mam B strom X1 a mazu prvek A, tak hledam takovy B strom X2, ze kdyz do nej pridam prvek A, dostanu strom X1, tedy proste inverzni operace. To ale neni pravda, protoze treba mazani z korene znamena, ze vezmu nejmensi vetsi v listech a vymenim. No takze ma otazka: dokaze nekdo definovat, jak spravne mazat v B stromech, aby to bylo vzdy korektni dle Zemlicky? Je mi jasny, ze ve skriptech je nakej algoritmus v PASCALu, ale nestiham ho trasovat. A ten stejny dotaz pro B* stromy.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 10
- Registrován: 5. 2. 2007 20:55
- Typ studia: Informatika Bc.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Par drobnosti
Na prednasce jsme konkretni algoritmus mazani prvku z B-stromu neresili.Medved píše: 3) Delete z B stromu. Puvodne jsem si myslel, ze kdyz mam B strom X1 a mazu prvek A, tak hledam takovy B strom X2, ze kdyz do nej pridam prvek A, dostanu strom X1, tedy proste inverzni operace. To ale neni pravda, protoze treba mazani z korene znamena, ze vezmu nejmensi vetsi v listech a vymenim. No takze ma otazka: dokaze nekdo definovat, jak spravne mazat v B stromech, aby to bylo vzdy korektni dle Zemlicky? Je mi jasny, ze ve skriptech je nakej algoritmus v PASCALu, ale nestiham ho trasovat. A ten stejny dotaz pro B* stromy.
Na cvikach jsme si rikali, ze vysledek po DELETE dokonce nemusi byt vzdy jednoznacny (napr. zalezi jestli pri mazani z korene beres nejvetsi prvek z leveho ci nejmensi z praveho podstromu, apod.). Mel by snad stacit libovolny algoritmus, po kterem zustane nejaky B-strom (neobsahuje vymazany prvek).
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: Par drobnosti
ja se delete z Bstromu ucil tady:
http://cs.wikipedia.org/wiki/B_strom
je to par jednoduchych pravidel
pripadne v priloze mas muj prepis co jsem si delal na ADS1
http://cs.wikipedia.org/wiki/B_strom
je to par jednoduchych pravidel
pripadne v priloze mas muj prepis co jsem si delal na ADS1
- Přílohy
-
- bstrom.pdf
- (104.37 KiB) Staženo 332 x
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: Par drobnosti
Jestli se nepletu (je to uz davno:) ), tak delete z B stromu autori popsali nejak ve stylu "obdobne";) a u zkousky zemlickovy staci kdyz budes pouzivat konzistentni postup (vzdy nejmensi vetsi, vzdy nejvetsi mensi apod.) ale musi splnovat dve podminky - funguje na kazdem korektnim B-strome a ma pozadovanou slozitost.
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..