[Zk] 24.1.2008

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ů.
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

[Zk] 24.1.2008

Příspěvek od Necroman »

Na zkousce se nas seslo cca 15 lidi, v S7. Otazky zadaval hezky odpredu, u kazdeho pri zadani stravil asi tak dve vteriny... Slysel jsem jen neco-strom, neco-halda, neco-strom, rekl bych, ze klasicky nahodny vyber z otazek, co je uveden na wiki. Taktez bylo dnes vyvraceno pravidlo, ze prvni rada dostava hashovani, dnes byli v prve rade dva a ani jeden nehashoval.
Nez dosel ke mne, tak kolega vlevo mel A-sort, vpravo (a,b) stromy a ja dostal k narozeninam Externi hashovani :shock: .

Asi po peti minutach to dva lide zabalili.

O tom jsem si ze zapisku pamatoval vseho vsudy, ze Insert a Delete ma amortizovane 6 operaci a Member 3, bez tuseni, proc tomu tak je a jak to vlastne funguje :roll: . Potom jsem si lehce vzpomenul na kohosi zapisky, kde ukazoval postup vkladani pro binarni cisla... zapatral jsem v pameti na Zemlickova cvika z OZD a rozepsal jsem mu tam se vsim vsudy Rozsiritelne hashovani a ono to bylo ono :). potom tam ze mne lamal patnact minut vzorce a odvozeni zavislosti velikosti adresare proti velikosti stranky na ukladani zaznamu s tim, ze to je to hlavni a dal mi za tri s tim, ze jsem mel na vic...
Good luck ostatnim.
macbeth ve vlaknu predtermin píše:Ta almighty teta na prvej prednaske hovorila, ze ak si myslime, ze sa na to budeme ucit 3 alebo 4 dni, tak ze sa mylime :)
jakepak 3 az 4, ucil jsem se na to od uterka :lol: . Myslim, ze na dvojku, pokud clovek nedostane hashovani, se to za dva dny poradneho uceni da celkem v pohode zvladnout, zejmena pokud si clovek vetsinu latky probral uz ve slozitosti.
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: [Zk] 24.1.2008

Příspěvek od rastik »

Koľko času mám počítať, že skúška zaberie?
WOW
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 14. 6. 2005 11:16
Typ studia: Informatika Mgr.

Re: [Zk] 24.1.2008

Příspěvek od WOW »

Necroman píše: jakepak 3 az 4, ucil jsem se na to od uterka :lol: . Myslim, ze na dvojku, pokud clovek nedostane hashovani, se to za dva dny poradneho uceni da celkem v pohode zvladnout, zejmena pokud si clovek vetsinu latky probral uz ve slozitosti.
Ja nevim, proc tady zbytecne matete lidi!!! :evil: Copak se daji datovky naucit za 2 dny??? :shock: Tak v tom pripade jsi asik borec, protoze ja to ani za 2 dny cele neprectu. To jdou mozna tak site, kdyz 2 dny nebudete spat... Ja uz mam datovky za sebou a ucil jsem se je aspon 6 dni, a to celkem poradne! Ze slozitosti mi to pripada stejne tak pouze s nazvama nadpisu. A kdyz vynechas hashovani, tak jsi vynechal ucivo vic jak za pulku semestru!!!

jenom tak pro info a tak good luck pro ostatni :wink:
MIKI
Matfyz(ák|ačka) level III
Příspěvky: 186
Registrován: 10. 12. 2004 22:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: [Zk] 24.1.2008

Příspěvek od MIKI »

WOW píše:Ja nevim, proc tady zbytecne matete lidi!!! :evil: Copak se daji datovky naucit za 2 dny??? :shock: Tak v tom pripade jsi asik borec, protoze ja to ani za 2 dny cele neprectu. To jdou mozna tak site, kdyz 2 dny nebudete spat...
No ked si to tak zoberies, naucis sa ku kazdemu definicie + vety a nejaky dokaz (volitelne) :D z najcastejsie sa opakujucich temat, co ti staci snad na 3 bez podrobnejsieho chapania => skusis 3x a da ti to docela slusnu pravdepodobnost, ze dotanes akurat to co vies aspon na tu 3.... ale ako vravim ja, taketo principy treba dodrzovat iba v casovej nudzi alebo casoch beznadeje! :twisted:

Podla vlastnej skusenosti za 2 dni sa to nejak neda stihnut cele aspon na 2.
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Re: [Zk] 24.1.2008

Příspěvek od Necroman »

MIKI píše:No ked si to tak zoberies, naucis sa ku kazdemu definicie + vety a nejaky dokaz (volitelne) :D z najcastejsie sa opakujucich temat, co ti staci snad na 3 bez podrobnejsieho chapania => skusis 3x a da ti to docela slusnu pravdepodobnost, ze dotanes akurat to co vies aspon na tu 3.... ale ako vravim ja, taketo principy treba dodrzovat iba v casovej nudzi alebo casoch beznadeje! :twisted:

Podla vlastnej skusenosti za 2 dni sa to nejak neda stihnut cele aspon na 2.
Samotne stromy a haldy+trideni se podle me opravdu da naucit na slusnou uroven za dva dny, pokud clovek umi latku ze slozitosti. Na to doporucuji ta tridilna skripta, Stromy maji 50 stranek, haldy+trideni 40 stranek. Cte se to jak pohadka a pokud si to clovek jeden den precte, zopakuje na tom vycucu, co daval na forum Tuetschek, a druhy den nauci dukazy + projde jeste jednou, tak se to da.

Samozrejme, naucit se poradne hashovani, to chce urcite vice casu, tam jsem tak maximalne vedel principy a nejaky ty vzorce, dukazy tezko.

...a jak mi radil znamy, co tedka dela diplomku v 5. rocniku, na datovky je nejlepsi jit poprve s tim, ze clovek umi dobre stromy a haldy a doufat, ze to dostane :)
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: [Zk] 24.1.2008

Příspěvek od hippies »

Ano, stromy a haldy se vzasade daj za jedno odopledne festoveho uceni, jak funguji ruzna hesovani (krom univerzalniho, tomu kloudne nerozumim do dnes) za dalsi odpoledne, ale podstata tohohle predmetu je v tech dukazech a to chce aspon 2 dny aby si to clovek zazil. Je ale fakt, ze jsem to delal loni a slozitos az letos, delat to zaroven tomu urcite dost pomuze.
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ů..
WOW
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 14. 6. 2005 11:16
Typ studia: Informatika Mgr.

Re: [Zk] 24.1.2008

Příspěvek od WOW »

Necroman píše:Samotne stromy a haldy+trideni se podle me opravdu da naucit na slusnou uroven za dva dny, pokud clovek umi latku ze slozitosti. Na to doporucuji ta tridilna skripta, Stromy maji 50 stranek, haldy+trideni 40 stranek. Cte se to jak pohadka a pokud si to clovek jeden den precte, zopakuje na tom vycucu, co daval na forum Tuetschek, a druhy den nauci dukazy + projde jeste jednou, tak se to da.
hippies píše:Ano, stromy a haldy se vzasade daj za jedno odopledne festoveho uceni, jak funguji ruzna hesovani (krom univerzalniho, tomu kloudne nerozumim do dnes) za dalsi odpoledne, ale podstata tohohle predmetu je v tech dukazech a to chce aspon 2 dny aby si to clovek zazil. Je ale fakt, ze jsem to delal loni a slozitos az letos, delat to zaroven tomu urcite dost pomuze.
Jaj, tak ja bohuzel asik nemam to IQ na urovni pres 200 a takovou pamet jako ostatni panove. Asi opravdu plati tvrzeni, ze "Matfyzakem se clovek uz rodi", coz neni muj pripad :lol:. Tudiz jsem vyrostl na pohadkach od Nemcove, Erbena a dalsich, a proto si vecer nedavam s chuti pohadku o Datovych strukturach... ehmm

Jiste, pravdepodobnost a statistiku jsem absolvoval take, takze taky vim, ze kdyz se naucim jednu otazku z te fury okruhu, tak mam REALNOU sanci ji dostat....

Takze kdyz se to vezme vsechno kolem a kolem... Nemam IQ pres 200, ani takovou pamet, ani nemam takove stesti, ze si vytahnu jedinou otazku z 20, kterou zrovna umim. Ale ja to magisterske studium taky dostuduju!!! :lol: :twisted: :lol:
...ale asi po svem... :D
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: [Zk] 24.1.2008

Příspěvek od hippies »

Nono, jestli te to uklidni, tak ja tu zkousku dal az na 2. pokus a za 3. (Prvni termin se trefil na to co jsem umel nejmin = neumel a sice universalni hesovani:D) ... 2. termin se zeptal na rozhodovaci stromy, ale ty jsem znal jen z umely inteligence (vazne jsem netusil, ze to tam nekde je) a tak jsem envedel co k tomu vlastne jako chce, tudiz se musel na kazde z toho zeptat:/

Jo a iq taky enmam 200, jen 172:P
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ů..
MIKI
Matfyz(ák|ačka) level III
Příspěvky: 186
Registrován: 10. 12. 2004 22:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: [Zk] 24.1.2008

Příspěvek od MIKI »

hippies píše:Jo a iq taky enmam 200, jen 172:P
Tak to uz si na matfyze podpriemer. :twisted:
Ale nic si z toho nerob.... Enstein mal tiez len okolo 160 a pozri kam to dotiahol.... a to ho ani na vysku nezobrali :D
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
Uživatelský avatar
langosh
Matfyz(ák|ačka) level II
Příspěvky: 96
Registrován: 28. 1. 2006 13:20
Typ studia: Informatika Mgr.
Bydliště: Bohnice
Kontaktovat uživatele:

Re: [Zk] 24.1.2008

Příspěvek od langosh »

Necroman píše: ...a jak mi radil znamy, co tedka dela diplomku v 5. rocniku, na datovky je nejlepsi jit poprve s tim, ze clovek umi dobre stromy a haldy a doufat, ze to dostane :)
Tak přesně na tohle jsem se spoléhal na tomhle termínu a dostal jsem univerzalni hašování :? .
Takže jdu zase v úterý. Teď alespoň to universalní hašování chápu, tak to snad nějak dopadne.
draracle
Matfyz(ák|ačka) level I
Příspěvky: 25
Registrován: 23. 9. 2004 13:21

Re: [Zk] 24.1.2008

Příspěvek od draracle »

Tez se pridam svou malou troskou, byt opozdene.

Sedel jsem prvni v prvni rade, protoze jsem si prisel pro hashovani se separovanymi retezci. Koubkova slova na uvitanou: "Cerveno-cerne stromy", me lehce zklamala. Toliko k teorii "prvni maj' hashovani"; uz na to moc nespolehat :wink:

Dokazal jsem logaritmickou vysku, nakreslil a posleze napsal v pseudokodu vyvazovani pro insert a delete. Slovne jsem jeste musel vypotit join a split. Po dvou a pul hodinach jsem odchazel (docela unaveny), tak tak jsem stihl odjezd na hory.

A jeste malou dousku k dobe uceni:
Jestli se to nekdo chce naucit, tak pet dni je minimum. Pro vyvarovani se stresu je lepsi si dat jeste tak den-dva rezervicku.
Naucit se jen stromy a haldy by mohlo fungovat, na to je dva dny az az. Ale bylo by lehce trapne, kdyby se na kazde zkousce vsichni hasheri zvedli a vzdali :lol:
Odpovědět

Zpět na „TIN066 Datové struktury I“