Zkouška 26.5.2008

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
Návštěvník

Zkouška 26.5.2008

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

Název zadání: Knižní veletrh
* 10 spisovatelů rozdává na veletrhu autografy
* veletrh je čtvercová síť 20×20 políček
* o každé osobnosti víme, kdy přijde a jaká bude jejich trasa, tj. políčko, na kterém se zjeví a posloupnost písmen NSEWX (sever, jih, východ, západ, stát na místě) reprezentující jejich pohyb
* všechny časy dané "číslem kroku"
* autogram získám, když stojím ve stejný čas na stejném políčku jako nějaká osobnost, klidně může být více lidí na stejném místě, můžu získat víc autogramů najednou
* každý autogram má nějakou cenu
* program má naplánovat trasu, jak sebrat autogramy s co největší celkovou cenou

VSTUP: textový soubor, každá osobnost má jeden řádek:
* číslo kroku, kdy přijde
* políčko, na kterém začne
* trasa
* cena autogramu

VÝSTUP: textovýá plán trasy
* délka trasy
* cena nasbíraných autogramů
* políčko, kde začnu
* trasa

OMEZENÍ:
* 10 osobností
* veletrh má rozměry 20×20
* délka tras osobností <= 100
* osobnost může přijít v kroku od 1 do 5000
* paměť k dispozici: 27 MB
* cena autogramu je <= MAXINT/10

* priority řešení: 1. co největší cena, 2. nejkratší čas odchodu z veletrhu
* začínám v kroku 1
Brekeke

Re: Zkouška 26.5.2008

Příspěvek od Brekeke »

Hmm..ty jo..no ja to mel v 10!*100, takze socialni.... pochlubte se, kdo to ma nejak lip....
neoangin
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 4. 6. 2006 10:51
Typ studia: Informatika Bc.
Bydliště: Blava/Praha
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od neoangin »

Vsadil som na vrabca v hrsti: Popisal som "hladovy algoritmus" (to znamena - odchytavam autora s najcennejsim podpisom, ktory sa nachadza na veltrhu) s tym, ze som v diskusii napisal, ze by sa rozmymi modifikaciami a zlepseniami (napr. vyber startovacieho policka nielen podla casu objavenia prveho autora, ale aj podla ocenenia podpisu jednotlivych autorov; v pripade troch atutorov na vystavisti odchytit dvoch s memsimi podpismi, ktory vsak mozu mat sucet cien vacsi ako ten treti...) dali nachadzat lepise vysledky.

Ako ste ulohu riesili vy? Je niekto isty tym, ze ma optimalne riesenie? ;)
$ man woman
No manual entry for woman
vrtulex
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 20. 2. 2008 22:41
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od vrtulex »

10!*100? To by nebylo špatný... mě to vyšlo kolem 10!*10^20 v nejhorším případě... v průměrnym by to mělo být mnohem lepší (ořezávání)
Uživatelský avatar
Cabroušek
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 24. 1. 2008 23:16
Typ studia: Informatika Mgr.
Bydliště: Kladno
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od Cabroušek »

Já jsem to řešil tak, že jsem si nejprve vygeneroval stavový prostor veletrhu v poli 5 100 x 20 x 20, kdy každá matice 20 x 20 zachycuje stav veletrhu v jednom kroku. Mohu si to představit jako graf, kde z každé bodu matice 20x20 vede nejvýše pět hran do bodů následující matice 20 x 20. Vzhledem k paměťovému omezení není možné graf reprezentovat poitry a zůstaneme v tomto poli. Hrany mají váhu buď nula nebo váhu autogramů, které využitím této hrany získám.

To, kde je která osobnost si pamataju jako bity ve dvoubytovém integeru. Když je tam nula, nikdo tam není.

Samotnou cestu hledám průchodem pole do šířky, kdy heldám nejdelší (resp. nejhodnotnější cestu) v co nejmenším počtu kroků. U každého vrcholu vyzkouším všechny jeho následníky, když by se tím zvýšila jeho hodnota, zapíšu příslušný vrchol jako jeho předchůdce na cestě. U každého vrcholu si kromě osobností, které tam v tu chvíli jsou nebo nejsou pamatuju předchůdce na na nejdelší cestě. Aby mohl algoritmus řádně probíhat, je nutné si pamatovat i jaké osobnosti jsme na cestě potkali a jaké je momentální délka nejdelší cesty do každého z vrcholů - ale kdybych si tyto údaje pamatoval u každé z vrcholů, opět by došlo k překročení paměťového limitu. Stačí si pamatovat údaje ve dvou nesvrchnějších vrstách šířící se vlny (jde udělat třeba sudá - lichá).

Průchod do šířky končí nalezením bodu, kdy jsem potkal všechny osobnosti nebo dojde až dokonce. V poslední matici 20 x 20 vyberu vrcholy které mají nejvyšší délku cesty a procházím ty cesty pozpátku - z těchto cest vyberu tak, která kobnčí dříve (resp. dříver přestane růst) a to je ta správná.

Využil jsem vlastně celou možnou paměť 27 MB.

Časová složitost 5100 * 20^2 * 5
Uživatelský avatar
R.U.R.
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 25. 5. 2008 18:46
Typ studia: Informatika Ph.D.
Bydliště: Beroun
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od R.U.R. »

10! * 10 * 101, takže řádově 10^10 - není to zřejmě optimální, ale myslím, že je to celkem dobrý, když máš ještě o řád míň, tím líp ;-)

Všechny permutace pořadí spisovatelů, ve kterém je navštívím, a pro každou permutaci musím každého navštívit co nejdřív.
Permutací je 10!, každého spisovatele musím navštívit v některém z max. 101 kroků, kdy je na veletrhu, a spisovatelů je 10.

A samozřejmě se to dá hodně ořezat, ale nevymyslel jsem takový ořez, aby mi klesla složitost v nejhorším případě - leda bych to musel počítat nějak amortizovaně.
vrtulex
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 20. 2. 2008 22:41
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od vrtulex »

Cabroušek: nojo, takhle to asi půjde... ale nějak mě to tam nenapadlo... holt co naděláme, že?
Bimbosh

Re: Zkouška 26.5.2008

Příspěvek od Bimbosh »

Jo hele v pohode, ja to udelal obycejnou hloubkou ale s orezavanim, takze na slozitost se radsi ani neptejte. No na to, ze to slo dynamicky tak to asi hloubka nebude optimalni reseni... Kua...
Turista

Re: Zkouška 26.5.2008

Příspěvek od Turista »

Ten příklad mi přijde docela brutální - můžete prosím blíže specifikovat jak dlouho na to bylo, jak to celé probíhalo, jak vypadá ústní kolo a jaké bylo skóre zúčastněných? Snad toho nechci moc, jen krátký report. Díky moc!
FF

Re: Zkouška 26.5.2008

Příspěvek od FF »

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.
vrtulex
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 20. 2. 2008 22:41
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od vrtulex »

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...
neoangin
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 4. 6. 2006 10:51
Typ studia: Informatika Bc.
Bydliště: Blava/Praha
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od neoangin »

Bol uz niekto na ustnej casti skusky? Kto vas skusal a co sa pytal? ;) Nech vieme, ake otazky su tento rok v oblube :D
$ man woman
No manual entry for woman
Návštěvník

Re: Zkouška 26.5.2008

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

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.
HonzaK
Matfyz(ák|ačka) level II
Příspěvky: 71
Registrován: 28. 9. 2007 17:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zkouška 26.5.2008

Příspěvek od HonzaK »

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 :D ), 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)
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zkouška 26.5.2008

Příspěvek od Him »

HonzaK: jak se dela to vytvareni haldy v lin. case? jen se pridavaji prvky a nic se nedela? Dik
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
Odpovědět

Zpět na „PRG031 Programování II“