Zkouška 21.6.

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.
Werkov
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 20. 1. 2010 11:33
Typ studia: Informatika Bc.

Zkouška 21.6.

Příspěvek od Werkov »

TMA (Theseus, Ariadna, Minotaurus)
Ve stručnosti. V bludišti jsou jsou tři postavy T, M a A. Bludiště je neorientovaný graf s maximálně 100 vrcholy. Každá z postav se chce dostat na své cílové pole (jsou různá navzájem i různá od startovních). Ale postavy se nesmí v žádném uzlu potkat, ba ani se nesmí potkat přes hranu (nesmí se vidět přes chodbu). Mezi vrcholy se postavy přesouvají synchronizovaně po minutách, tzn. v každé celé minutě je každá postava v nějaké místnosti. Má se rozhodnout, zda je možné, aby se každá postava dostala na své cílové pole, ale aby tam došla jen tak, že sen nikdo s nikým nepotká, jak je uvedeno výše. (Pokud postava do cíle dojde, může jej dočasně opustit, aby uvolnila cestu jiné, ale nakonec musí být každá postava ve svém domečku.)

Vstup:
(uzly grafu jou pojmenované, názvy startovních a cílových pozic známe)
Soubor s hranamy ve tvaru
<název uzlu 1>-<název uzlu 2>

Výstup:
-1 pokud to postavy nemůžou projít
<číslo> nejmenší možný čas, za který to postavy mohou projít

Poznámka:
Ubral jsem tomu zadání dost (vše) z jeho peotičnosti. Holan to měl skvěle vybájené - "Od té doby, co byla Ariadna ve věštírně, je nějaká divná, a tak ji Theseus nechce potkat." :-)
Omezení paměti 4 MB.
blejzzzzz

Re: Zkouška 21.6.

Příspěvek od blejzzzzz »

tak kdo má vzorové řešení? nechť ho nahlásí, ať taky něco odkážeme příštím generacím :D
Uživatelský avatar
iwtu
Matfyz(ák|ačka) level I
Příspěvky: 48
Registrován: 15. 3. 2010 21:54
Typ studia: Informatika Bc.

Re: Zkouška 21.6.

Příspěvek od iwtu »

Pokial je mi zname, tak je to iba prehladavanie stavoveho priestoru a neprechadzat stavy, v ktorych sme uz boli alebo ktorych je zle (deadlock). Nieco na principe Sokoban.
kubatop
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 15. 6. 2010 11:13
Typ studia: Matematika Mgr.

Re: Zkouška 21.6.

Příspěvek od kubatop »

iwtu píše:Pokial je mi zname, tak je to iba prehladavanie stavoveho priestoru a neprechadzat stavy, v ktorych sme uz boli alebo ktorych je zle (deadlock). Nieco na principe Sokoban.
Je to přesně tak. Pokusím se to trochu rozvést.

Místnosti si pro přehlednost očíslujeme. S názvy by se pracovalo špatně. A na základě vstupního souboru vytvořím nějakou reprezentaci grafu. Nejlepší je asi seznam sousedů pro každý vrchol.
Každý z hrdinů je po skončení kola (v celou minutu) vždy právě v jedné místnosti. Tedy pozici každého hrdiny můžeme popsat pomocí číslice od 1 do 100 (číslo místnosti), mám tři hrdiny. Tedy celkem mám 100^3 = 10^6 možných stavů, které mohou nastat. To je dost, ale ne tak moc, abych je nemohl všechny projít. Počáteční i koncový stav znám.
Budu prohledávat do šířky. Přitom si budu navíc udržovat trojrozměrné pole 100x100x100 booleanů, kde si o každém stavu (ona trojice čísel) zapamatuji, jestli jsem se do něj už dostal. Pokud bych chtěl přejít do nějakého stavy, tak tedy v O(1) snadno zjistím, jestli jsem ho už neprozkoumal nebo jestli jeho prozkoumání už není v plánu.
Skončím ve chvíli, kdy se dostanu do cílového stavu nebo až projdu všechny možné (fronta se vyprázdní).

Zbývá se ještě nějak vypořádat s paměťovou složitostí. Omezení 4MB je akorát hraniční. Na trojrozměrné pole všech stavů spotřebuji akorát 1MB. Uložení vlastního grafu bludiště je zanedbatelné. Stejně tak nějaké pomocné proměnné.
Zbývají tedy cca 3MB na frontu. Frontu při prohledávání do šířky bude lepší reprezentovat polem - při použití spojového seznamu přibývají navíc ukazatelé. Celkově může být ve frontě až 10^6 záznamů (třeba pro úplný graf), tedy potřebuji pole délky 10^6. Pro jeden záznam mi tedy zbývají 3B paměti, což je akorát na trojici čísel určující stav. Nemohu si tedy u stavu pamatovat, kolik minut už uplynulo (což by bylo také dost prostorově neekonomické, neboť číslo minuty je 1 až milion a spousta po sobě jdoucích stavů má toto číslo stejné). To vyřeším tak, že ve chvíli, kdy se dostanu do další minuty, si do fronty uložím nějaký speciální oddělovač. Třeba nějaký stav, který nemůže nastat. Pokud narazím na tento oddělovač, zvýším si centrální čítač kol.Zároveň vím, že všechny stavy jsou teď ze stejné minuty. Další ale budou až o minutu později, proto oddělovač znovu přidám na konec fronty. V každém okamžiku může být ve frontě jen jeden oddělovač, tedy na požadovanou maximální délku fronty to nemá vliv (rozmysli si, že to vyjde i pro úplný graf).

Časová složitost v mé implementaci vyšla O(M^6), kde M je počet místností. Pro M = 100 tak dostáváme řádově 10^12 operací. To je opět akorát tak na hranici. Procesor s frekvencí 1GHz vykoná 10^12 instrukcí přibližně za 20 minut. Musíme si ale uvědomit, že tato složitost odpovídá grafům se spoustou hran. Typické bludiště bude mít z každé místnosti třeba maximálně 10 chodeb. Pak lze složitost omezit na O(M^3). (Rozmysli si matematický trik.)
Odpovědět

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