IB002 - 3. sada domácich úloh
Úloha je určená pre študentov sem. skupín IB002/11, IB002/12. Každý, kto má tuto skupinu riadne zapísaný, je povinný odovždat' vypracovane obidva príklady. Studenti, ktorí nepatria do týchto skupín možu ulohu odovždat' a maju narok na opravenie, nie vsak na bonusove body.
Termín odovzdania: 21.5. do 5:21
Zposob odovzdania: elektronicky do odovždavarne v ISe (pdf dokument formatu A4) alebo papierovo na cvičeniach A. Pančíka. Nezabudnite i v elektronickej veržii uviest' meno a ÚCO.
Vypracovanie ako dvojica: Úlohy je možne vypracovat' ako dvojica. Dvojica odovždýva len jedno rieSsenie podpýísanýe oboma menami. Body dostanuý obaja ž dvojice. KaSždýy prýíklad je hodnotenyý samostatne, je teda moSžnýe vytvorit' roždielne paýry pre prvyý a druhyý prýíklad.
Hodnotenie: Za výborne vypracovane riesenia môžete žískat' až 2 bod ža príklad. Za neodovždany príklad, ža riesenie, ktore je extremne nedostatocne (prýždny papier) a ža opisovanie naopak 2 body ža prýklad strýacate.
Príklad 1
□ Jožko dostal hlad a poprosil Anicku, aby mu isla spravit' sendvic. Anicka sa spociatku ždrýhala, pretože je emancipovana žena, ale potom jej Jožko sl'ubil, že ža každý krok do kuchyne jej žaplatí korunu. Napíste algoritmus pre Jožka, ktorý najde najkratsiu cestu do kuchyne, aby musel AniScke platit' Sco najmenej.
Plan ich obrovskeho výkendoveho domu mame vo forme grafu (V, E), kde vrcholy reprežentuju miestnosti a hrany priamy prechod medži nimi. Hodnotiaca funkcia k : E — N urcuje pocet krokov, ktore žaberie prechod medži miestnosťami. Anicka s Jožkom su v obývacke j G V, kuchyna je ožnacený k G V.
Príklad 2
□ Mýrio prehl'adýva žamok, v ktorom je niekde uväžnený princežný. Nevedel ju nikde najst', ale nakoniec natrafil aspon na mapu. Je to stvorcový siet', kde sý steny ožnacene X a vsetky ostatne polia ako o. Ked' sa na plan požrel, hned' mu bolo jasne, preco este princežnu nenasiel. V žamku sa nachadžaju aj miestnosti, do ktorých sa normýlne nedostane, pretože nemajuý Sžiadny vchod. Princežnaý musýí teda byt' v jednej ž nich. NapýíSste Mýariovi algoritmus, ktoryý žistýí presnyý poScet takyýchto tajnyých miestnostýí.
Plýn ma rožmery n x n. Môžete tiež predpokladať, že vsetky okrajove polia na plane sý ožnaScenýe o. Nežabudnite urScit' Scasovuý žloSžitost' algoritmu.