[Zk] 20.1.2009

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

[Zk] 20.1.2009

Příspěvek od Osiris »

Koubek zadal každému otázku, několik lidí to vzdalo hned. Já jsem dostal Leftist haldu. Stačilo napsat definici + popsat operace a odcházel jsem s jedničkou v indexu :)

Hodně štěstí ostatním :wink:
Osiris
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

[Zk] 21.1.2009

Příspěvek od Myshaak »

Tak dneska nas tam bylo docela dost, snad vsech dvacet. :)

No, mel jsem dost stesti na otazku - cerveno-cerne stromy. Jupiii! Asi hodinu jsem psal. Dal jsem definici, odvozeni logaritmicke vysky a pak insert + delete s vyvazovanim. Delal jsem to rozborem pripadu, musim se neskrome priznat, ze jsem to fakt umel, takze jsem mel vsechny varianty a navic spravne. ;) Akorat me pak zaskocil otazkou, proc pri delete-vyvazovani uvazuju jen cerny vrchol v. Proc pry neni cerveny? To ve skriptech myslim nebylo a ze na to pry musim prijit. Odpoved: kdyby byl v obarveny cervene v (T,v) 3-pracialnim cc strome, tak ho staci prebarvit na cerno a je po problemu! ;)
Pak mi rekl o index a na dalsi stranku, kde jsem mel treba popsany join se uz ani nepodival. Takze huraaaa!

Jinak pan zkousejici je vazne v pohode. Teda ne v tom smylu, ze by snad znamkovani bylo mirne, ale u kazdeho se vzdy na 5 - 10 minut zastavi a pripadne da cas a sanci na dalsi promysleni (+co jsem si vsiml, tak na trojku nechce zadne prisernosti). Z toho ale vyplyva pomerene dlouha doba zkousky, myslim, ze ti posledni tam zakysnou na hodne dlouho....

Uceni: cca 3 dny lehciho uceni a 3 dny fest sroceni (tj. v mem pripade asi 7 hodin cisteho casu denne). Teprve posledni/predposledni den se zacal dostavovat efekt "Ahaaa! Ted uz je to jasny!". Zato jsem schroupal prakticky vse, vcetne univerzalniho a perfektniho hesovani (ktery jsem taky chtel dostat) - bez toho a bez "slozitych" dukazu se to snad da stihnout o den dva rychleji.

Tak hodne stesti!

__________________________________________

Uaaaa, 100. prispevek. To je dneska den! :D
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: [Zk] 20.1.2009

Příspěvek od Osiris »

6 dní učení? Proboha, a já se učil cca 8 hodin... v pondělí odpoledne a v úterý ráno před zkouškou... :shock: Já myslím, že tak cca 8-10 hodin je na tenhle předmět optimum...
Osiris
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvek od Myshaak »

Osiris píše:6 dní učení? Proboha, a já se učil cca 8 hodin... v pondělí odpoledne a v úterý ráno před zkouškou... :shock: Já myslím, že tak cca 8-10 hodin je na tenhle předmět optimum...
Wow! :shock: Proboha, tak to jsi vazne bouchac! :) Nee, tak samozrejme stromy & haldy jdou; a pokud nebude mit clovek pech na otazku, tak to na trojku za par hodin da, ale pochybuju, ze si za 8 hodin byt jen poradne prectes tu cast o hashovani :twisted:
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: [Zk] 20.1.2009

Příspěvek od Osiris »

No, lehčí důkazy u hashování jsem uměl z přednášky, prakticky je to víceméně cvičení na Binomické rozdělení, ale je pravda, že s univerzálním hashováním + perfektním bych měl potíže...
Osiris
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvek od Myshaak »

Osiris píše:No, lehčí důkazy u hashování jsem uměl z přednášky, prakticky je to víceméně cvičení na Binomické rozdělení...
To je taky pravda. No ona je vubec otazka, jak ke zkousce pristupovat, z hlediska "cena/vykon". Jestli tomu dat deset hodin s tim, ze kdyz nebudu mit smulu, tak nevyletim a se stestim na otazku dam za jedna, nebo tomu dat par dni navic (i kdyz celkove jsem se i ja do takovych 30 hodin cistyho casu urcite vesel) s tim, ze pak "temer jiste to dam a v nejhorsim pripade snad budu bojovat mezi dvojkou a trojkou". Ale tohle ma kazdy jinak a kazdemu neco jineho leze do hlavy... Ale co, hlavne, ze uz to mame za sebou, ne? 8)
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: [Zk] 20.1.2009

Příspěvek od Osiris »

jj :twisted: Pokud člověk nedostane nějaký těžký důkaz, tak to dá.
Osiris
malvoj
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 10. 5. 2006 12:47
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvek od malvoj »

otázka: srůstající hešování
chtěl vědět těch pět hešování jak jsou ve skriptech + jak se liší
další otázkyjak fungují algoritmy stačilo schématicky není nutné psát celý ten kód co to implementuje do posledního detailu
chtěl určitě slyšet, že očekávaná délka řetězce ve srůstajících hešováních je 3 s pomocnou pamětí 2 + co za význam pomocná paměť má (ve zkratce - pomáhá tomu aby se v tabulce neblokovalo zbytěčně místo - protože prvky samozřejmě obsazují mista pro prvky z jiné skupiny 0..m).
jirka_v
Matfyz(ák|ačka) level I
Příspěvky: 18
Registrován: 20. 6. 2007 14:20

Re: [Zk] 20.1.2009

Příspěvek od jirka_v »

malvoj píše:chtěl určitě slyšet, že očekávaná délka řetězce ve srůstajících hešováních je 3 s pomocnou pamětí 2
Tyhle konkretni hodnoty jsou primo nekde ve skriptech, nebo vyjdou po dosazeni do nekteryho z tech silenejch vzorcu? Nejak to tam nemuzu najit... Diky.
Lado
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 29. 1. 2007 11:42

Re: [Zk] 20.1.2009

Příspěvek od Lado »

jirka_v píše:
malvoj píše:chtěl určitě slyšet, že očekávaná délka řetězce ve srůstajících hešováních je 3 s pomocnou pamětí 2
Tyhle konkretni hodnoty jsou primo nekde ve skriptech, nebo vyjdou po dosazeni do nekteryho z tech silenejch vzorcu? Nejak to tam nemuzu najit... Diky.
Je to tam - zhrnute jednou vetou. Da sa to dost jednoducho prehliadnut, bohuzial.
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: [Zk] 20.1.2009

Příspěvek od peterblack »

Lado píše:
jirka_v píše:
malvoj píše:chtěl určitě slyšet, že očekávaná délka řetězce ve srůstajících hešováních je 3 s pomocnou pamětí 2
Tyhle konkretni hodnoty jsou primo nekde ve skriptech, nebo vyjdou po dosazeni do nekteryho z tech silenejch vzorcu? Nejak to tam nemuzu najit... Diky.
Je to tam - zhrnute jednou vetou. Da sa to dost jednoducho prehliadnut, bohuzial.
http://forum.matfyz.info/viewtopic.php?f=206&t=8375
tady je to stranka 41 dole
Odpovědět

Zpět na „TIN066 Datové struktury I“