[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ů.

[Zk] 20.1.2009

Příspěvekod Osiris » 20. 1. 2009 18:01

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
Osiris
Supermatfyz(ák|ačka)
 
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Bydliště: Praha
Typ studia: Informatika Mgr.

[Zk] 21.1.2009

Příspěvekod Myshaak » 21. 1. 2009 15:36

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!!"
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
 
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Bydliště: Tanvald / Troja A820
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvekod Osiris » 21. 1. 2009 16:00

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
Osiris
Supermatfyz(ák|ačka)
 
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Bydliště: Praha
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvekod Myshaak » 21. 1. 2009 16:05

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!!"
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
 
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Bydliště: Tanvald / Troja A820
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvekod Osiris » 21. 1. 2009 16:16

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
Osiris
Supermatfyz(ák|ačka)
 
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Bydliště: Praha
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvekod Myshaak » 21. 1. 2009 16:51

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!!"
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
 
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Bydliště: Tanvald / Troja A820
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvekod Osiris » 21. 1. 2009 17:03

jj :twisted: Pokud člověk nedostane nějaký těžký důkaz, tak to dá.
Osiris
Osiris
Supermatfyz(ák|ačka)
 
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Bydliště: Praha
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvekod malvoj » 24. 1. 2009 20:39

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).
malvoj
Matfyz(ák|ačka) level I
 
Příspěvky: 8
Registrován: 10. 5. 2006 11:47
Typ studia: Informatika Mgr.

Re: [Zk] 20.1.2009

Příspěvekod jirka_v » 29. 1. 2009 00:22

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.
jirka_v
Matfyz(ák|ačka) level I
 
Příspěvky: 18
Registrován: 20. 6. 2007 13:20

Re: [Zk] 20.1.2009

Příspěvekod Lado » 29. 1. 2009 12:05

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.
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ěvekod peterblack » 1. 2. 2013 10:01

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.


viewtopic.php?f=206&t=8375
tady je to stranka 41 dole
peterblack
Matfyz(ák|ačka) level III
 
Příspěvky: 153
Registrován: 10. 12. 2006 19:26


Zpět na TIN066 Datové struktury I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník