Fórum studentů MFF UK

Máte někdo tušení, jak aspoň začít s řešením tohohle příkládku? Nějak vůbec nevím, kde začít a dle čeho navyšovat. Díky
Zadání: http://forum.matfyz.info/viewtopic.php?t=1885

rozhodne nebazirujou na detailech ale musi bejt videt ze vis jak bys to udelal.
jiank z tech peti tematovejch okruhu co tam mame napsat (postrehy, algoritmus, ds, atd atd) jsem mel jeden a pul a stejne, jelikoz jsem tam mel vsechno dulezity, tak to bylo za jedna.

No musí bejt jasný, jak bys to udělal. Aby z toho bylo vidět, že si uvědomuješ, jak konkrétně by se to napsalo, jak přesně by vypadaly datové struktury, aby z toho byla vidět složitost... Určitě nebazírujou na detailech, musí tam bejt to podstatný, to důležitý. Pokud nějakou důležitou věc ohledně řešení budeš vědět akle nenaúpíšeš ji tam, tak to není dobré. Já osobně jsem popsal asi 6 těch velkejch stránek a musel jsem si během toho ořezávat tužku, ale myslím, že jsem to psal zbytečně moc podrobně. Každopádně káš 2 hpdiny času, to toho člověk stihne napsat dost, mě by byla stačila hodka a půl.
Na písemku jsem se neučil. Na ústní jsem se učil z poznámek a ze slajdů co má topfer na stránkách, a co se týče těch stromů a takovejch těch datovejch struktur, tak na to jsem kouk v Algovision.

Mohli byste někdo, kdo už má tuhle zkoušku za sebou napsat z čeho jste se učili, atp? Hlavně moc nechápu, jak moc podrobně to musí být u té písemné části rozebrané. Jestli stačí napsat např. teď si vygeneruju stavový prostor, a prohledávám do hloubky, nebo tam bazírujou na detailech?

DÍK

U Topfera to asi možný je... když zvoráš ten algoritmus, tak budeš muset bojovat o 3 (pokud nepůjdeš rovnou)... ale to jsem tak slyšel... já byl u Holana

Lidi, dá se na téhle zkoušce vyletět?

Kdybyste někdo náhodou chtěli brát moc vážně to řešení, co jsem tam napsal, tak to neděleljte, není dobře ... Ale kdyby se to kapánek předělalo, tak to bude fungovat dobře. A mohlo by to mít ještě mnohem menší složitost, jelikož je mnoho tahů, kdy se vlastně nic neděje.

Him píše:HonzaK: jak se dela to vytvareni haldy v lin. case? jen se pridavaji prvky a nic se nedela? Dik

Dela se to, jak to Holan nazval, "ucetnickym trikem":
Vyjde se z toho, ze pri reprezentaci haldy temer uplnym bin. stromem se velka cast vrochlu nachazi bud v posledni hladine (tj. jsou to listy), nebo predposledni hladine - celkem to vzhledem k exponencialnimu rustu poctu vrcholu vzhledem k hladinam dela n/2 vsech vrcholu, ktere se uz vemou, ze jsou na svem miste, tj. cas na jejich umisteni je 0 (pri reprezentaci polem to odpovida druhe polovine pole). Dale se vezmou vrcholy, ktere tvori zbytek predposledni hladiny a cast predpredposledni - tech je n/4 a na vlozeni kazdeho z nich potrebujeme max 1 prohozeni (s nejakym vrcholem, ktery uz v hlade je). Pak se vezme dalsich n/8 vrcholu (na umisteni kazdeho z nich potrebujeme max 2 prohozeni), pak n/16 atd.

Tedy celkem je potrebny cas: 0*n/2 + 1*n/4 + 2*n/8 + ... coz je O(n)

Takze tak nejak...

Myslím, že ta halda v lin. čase spočívá v tom, že se staví odspoda (takže u heapsortu odzadu)

HonzaK: jak se dela to vytvareni haldy v lin. case? jen se pridavaji prvky a nic se nedela? Dik

Ja jsem byl na ustnim dneska, zkousel me Holan.
Nejdriv si vzal k ruce moji pisemku a mel jsem mu popsat, jak jsem to resil - v prubehu popisu do toho obcas vstoupi, aby se na neco zeptal, pripadne
aby uvedl protipriklad a take si prubezne procita, co je v pisemce skutecne napsano (aby nekdo nepopisoval jine reseni, nez napsal do pisemky ), urcite je dobre zminit se o slabinach zvoleneho algoritmu (minimalne tak zkousejiciho pripravite o poteseni z ukazani prikladu, na kterem vase reseni selze), mne to, ze jsem si chyby a slabiny uvedomoval, pricetl k dobru.
Po analyze pisemky se prejde k teorii, konkretne me se zeptal na haldu - tak jsem mu popsal reprezentaci bin. stromem a polem, pak chtel ukazat nejaky konkretni priklad a na nem demonstrovat insert a delete minima, dale se ptal na trideni haldou (tj. heapsort) - princip, casova narocnost...
Jeste se ptal na to, jak postavit haldu v linearnim case, ale to uz jen tak bokem.
Celkove bych ustni hodnotil jako prijemnejsi cast zkousky (oproti pisemce), spise se tam da vase celkove hodnoceni zlepsit, nez zhorsit (teda aspon takovy pocit jsem mel ja)

Písemnou část jsem dělal přímočaře s jednoduchou heuristikou: místo zkoušení všech 10! pořadí jsem zkoušel jen max. po N (např. 4) nejbližších spisovatelích a z toho v každém kroku šel k prvnímu nejvýhodnějšímu. Töpferovi se řešení líbilo (prý by hodnotil 1-), ale heuristiku komentoval tak, že je v podstatě zbytečná, že 10! možností se projít dá... Takže i to nejpřímočařejší zkoušení všech možností asi projde. Taky navrhoval rozdělit situaci podle intervalů, kdy na veletrhu žádný spisovatel není (což bude většina času) a zkoušet pořadí po částech zvlášť.

Na ústní se ptal na vnitřní/vnější třídění, grafové algoritmy... no nic překvapivého, všechno je v sylabu. Často chtěl odvodit složitost.

Bol uz niekto na ustnej casti skusky? Kto vas skusal a co sa pytal? Nech vieme, ake otazky su tento rok v oblube

Mně to taky přišlo jako dost brutální... jenže ono není... stačí to dobře nahlédnout - a je to za chvíli. To nahlédnutí se mi nepodařilo - důvod je ten, že neumím násobit dvěma...

No prijdes tam rano v 9, zkousejici si te odskrne, pak si vemes papir, nekam se posadis.
Za chvili rekne zadani prikladu s tim, ze se muzes ptat a on ti to upresni. Pokud se nezeptas, tak v programu nemuzes predpokladat, ze neco plati, takze lepsi se ptat. Jinak do zaverecny analyzy poznamenat, ze si predpokladal vstup omezenej treba jen na < 255 autobusu, nebo co ja vim. Pak napise zadani na tabuly a taky tam napise sablonu jak ma vypadat shrnovvaci papir - tj. papir na ktrej napises dekompozici ulohy, diskuzi o volbe algoritmu o prubehu resen atd atd. Po 2 hodinach odevzdas a po odevzdani se zapises na takovej pejpr co tam zkousejici ma. Sou tam dva sloupecky. Kazdej sloupecek ma 3 sekce - pro kazdej den jednu - a je dale clenenej podle hodin, kdy prijdes na ustni. Obecne se nevi, jestli pravej sloupec znamena, ze budes zkousenej Topferem, nebo Holanem.