Zkouška Pergel/Holan 26.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.
M_vys
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 4. 6. 2017 20:30
Typ studia: Informatika Bc.

Zkouška Pergel/Holan 26.6.

Příspěvek od M_vys »

Myslím, že to byla nová úloha.

Zadání:

Ve městě jsou ulice ohodnocené délkou a nebezpečností. Úkolem je najít co nejbezpěčnější cestu mezi dvěma místy ve městě. Nebezpečnost cesty závisí pouze na nebezpečnosti nejnebezpečnější ulice po cestě a pokud je víc stejně nebezpečných cest, chceme tu nejkratší. Je zaručeno, že aspoň jedna cesta existuje.

Vstup:

seznam ulic: odkud, kam, bezpečnost (ve tvaru 2^31 - # prepadeni), délka
start a cíl cesty

křižovatek <= 1000
pamět: 1GB


Výstup:
nebezpečnost nejbezpečnější cesty výpis ulic kterýma prochází zase odkud, kam


Byla jsem u Pergela, mojí písemku předtím očividně nečetl, chtěl po mě abych stručně shrnula svoje řešení.
Řešila jsem to tak, že jsem si seřadila hrany podle nebezpečnosti a postupně odebírala ty nejhorší (když jich bylo víc stejně nebezpečných odebrala jsem všechny) a zkoumala, jestli start a cíl jsou v té samé komponentě. Potom už nebyly, přidala jsem poslední potřebný našla nejkratší cestu pomocí Dijkstry. Vůbec se neptal na podrobnosti, reprezentaci čehokoliv nebo jak bych zkoumala ty komponenty, případně co složitost nebo paměť. Jen po mě chtěl ukázat jednu větu na papíře a řekl to vypadá věrohodně.
Z ústní mi dal dynamické programování a ptal se jaký znám použití, uzávorkování násobení matic je prý jeho nejoblíbenější.

Osobně jsem z toho měla smíšené pocity, Pergel vypadal, že to chce mít hlavně rychle za sebou (to jsem byli dva), taky to vypadalo že by se v tom i vrtal, ale říkal, že tohle řešení ještě neviděl, takže mi věří, že to tam všechno je. Ani u ústní se v tom moc nevrtal, potom řekl že jsem mu všechno řekla, algoritumus byl taky v pořádku, ale že na jedničku se mu to nezdá a dal mi dvojku. Já byla ráda že to mám za sebou, ale příde mi, že je to hodně o jeho náladě a pocitu.
kamen
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 28. 6. 2017 05:07
Typ studia: Informatika Bc.

Re: Zkouška Pergel/Holan 26.6.

Příspěvek od kamen »

Zkoušku jsem dělal u Holana, docela podrobně chtěl vysvětlit, jak jsem postupoval. Já jsem si seřadil hrany podle bezpečnosti a binárně vyhledal takovou bezpečnost, při které když použiju jen bezpečnější hrany bude start i cíl v různých komponentách souvislosti. Sice je to méně efektivní než nahoře uvedený algoritmus, ale říkal, že se mu to líbí a dal mi za 2. Pak chtěl jen vysvětlit jak funguje Dijkstra a to bylo vše.
Odpovědět

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