Koucky 9.1.2015

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ů.
lefty
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 4. 8. 2011 09:16
Typ studia: Informatika Mgr.

Koucky 9.1.2015

Příspěvek od lefty »

Zkousejici rozdal papiry s otazkami, ktere vypadaly uplne stejne jako ty ukazkove na jeho webu. Obsah mych otazek byl take shodny, dostal jsem:
  • lina binomialni halda
  • exponencialni odhad fibonacciho cisel
U obou otazek chtel dukazy, u binomialni haldy se trochu vyptaval na algoritmus mergovani a jestli bych ho umel udelat bez setrideneho seznamu tech vnitrnich hald. Vymyslel jsem neco na zpusob prihradkoveho trideni. Take jsem udelal chybu v dukazu slozitosti delete-min, ale stoural do toho az jsem se opravil. Nakonec jsem odesel s jednickou a vsechny ty domaci ukoly mi byly k nicemu :D.

Hodne stesti!
Návštěvník

Re: Koucky 9.1.2015

Příspěvek od Návštěvník »

Prosim te, jak podrobne chce dukazy? Staci mu myslenka, naznak.. nebo je to puntickar? A z ceho ses ucil?
ips
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 10. 9. 2011 20:18
Typ studia: Informatika Bc.

Re: Koucky 9.1.2015

Příspěvek od ips »

Přišlo mi, že mu jde hlavně o pochopení. Já měl důkazy amortizovaných složitostí u líné binomiální haldy, měl jsem tam drobné nepřesnosti, to ale přešel naprosto bez mrknutí oka, jen mě na to upozornil. Položil potom ještě několik doplňujících otázek k těm potenciálům (jak se bude chovat join dvou hald z pohledu potenciálu, jak se bude chovat nějaká série operací na prázdné haldě) aby si ověřil, že rozumím tomu principu a jen jsem se nenaučil důkaz nazpaměť. Když viděl, že nějak reaguji, stačilo mu to a šel dál. Celkově bych zkoušku hodnotil jako jednu z těch pohodovějších, možná úplně nejpohodovějších na MFF, takže se fakt není čeho bát :).

Jinak jako materiál jsem používal ty ofocené poznámky na jeho webu, je tam jen pár míst kde mohl být trošku podrobnější (případně názornější), ale celkově je to parádní materiál.
Návštěvník

Re: Koucky 9.1.2015

Příspěvek od Návštěvník »

ips píše:Přišlo mi, že mu jde hlavně o pochopení. Já měl důkazy amortizovaných složitostí u líné binomiální haldy, měl jsem tam drobné nepřesnosti, to ale přešel naprosto bez mrknutí oka, jen mě na to upozornil. Položil potom ještě několik doplňujících otázek k těm potenciálům (jak se bude chovat join dvou hald z pohledu potenciálu, jak se bude chovat nějaká série operací na prázdné haldě) aby si ověřil, že rozumím tomu principu a jen jsem se nenaučil důkaz nazpaměť. Když viděl, že nějak reaguji, stačilo mu to a šel dál. Celkově bych zkoušku hodnotil jako jednu z těch pohodovějších, možná úplně nejpohodovějších na MFF, takže se fakt není čeho bát :).

Jinak jako materiál jsem používal ty ofocené poznámky na jeho webu, je tam jen pár míst kde mohl být trošku podrobnější (případně názornější), ale celkově je to parádní materiál.
Jen z jeho poznamek? To je super. Mel jsem v planu se z nich ucit. Je dobre vedet, ze jsou vice mene postacujici. Diky za zpravu.
Tommassino
Matfyz(ák|ačka) level I
Příspěvky: 35
Registrován: 10. 9. 2009 21:03
Typ studia: Informatika Mgr.

Re: Koucky 9.1.2015

Příspěvek od Tommassino »

Dneska (26.1.2015) jsem byl na zkoušce a dost mě překvapil hodnocením, protože ostatní tu mají zkoušku za pohodovou. Zkouška začala stejně, jak to tu ostatní popisují, mě ale pak postupně dal dvě další doplňující otázky (z těch otázek ze seznamu, takže jsem prakticky napsal dvě písemky). To mě docela překvapilo, protože v prvních dvou otázkách mu nic nevadilo (aspoň mi neřekl). Přestože v těch doplňujících otázkách jsem nějaké detaily sem a tam neměl úplně na sto procent, tak jsem čekal, že dostanu 1, rozhodně ty otázky byly mnou dost solidně zpracované, ale dal mi 2 s tím, že mu vadilo, že mám mezery v detailech. Nejspíš hodně kouká na to, jestli máte úkoly, já úkoly nedělal.

Vadily mu věci typu toho, že v důkazu složitosti splay jsem měl omylem nadefinovanou r(x) jako velikost podstromu, ne log velikosti, přestože pak v důkazu jsem používal log velikosti. Nebo třeba, že jsem mu lemma použitá v důkazu dokázal jen náznakem (prvních pár řádků důkazu). Kvůli tomu jsem prý měl tu celou otázku z jeho pohledu špatně... Když jsem mu říkal, že se mi nelíbí dvojka, tak mi nabídl další otázku, ale to sem se mu na to už vykašlal - přišlo mi, že mi prostě nechce dát za jedna... Rozhodně mi nepřišlo, že by mu stačily principy, chtěl velmi přesné důkazy a všechno dobře odůvodněné.

Takže - pokud nemáte úkoly, tak musíte na jedna umět materiály hodně dobře, s úkoly je to asi pohoda, jak tu ostatní popisují.

PS: měl jsem otázky: splay - operace, fibonacci - dolní odhad, doplňkové: splay - důkazy, ab-strom - operace, jo a učil jsem se primárně z jeho poznámek
david1
Matfyz(ák|ačka) level I
Příspěvky: 37
Registrován: 16. 2. 2009 18:00
Typ studia: Informatika Mgr.

Re: Koucky 9.1.2015

Příspěvek od david1 »

Ja mám podobný pocit, že síce je skúška pohodová z hľadiska vopred známych otázok a veľkosti látky na učenie, ale pokiaľ človek nemá spravené bonusové úkoly, tak sa veľmi ľahko môže zvrtnúť. Ak sa mu niečo nezdá, tak sa pýta dosť do detailov a zisťuje, či tomu človek rozumie. No a problém je, že aj keď nakoniec na všetky otázky odpoviete, tak vám akosi za 1 nechce skúšku uznať. Povedal by som, že skúška je presný opak prednášky, kde bolo veľa vecí akosi nejasne prejdených a práve tieto veci sú dôležite na skúške.
Odpovědět

Zpět na „TIN066 Datové struktury I“