8. sada domácich zadaní

Najneskorší termín: 17.5.2015 (nedeľa) o 21:00

Cieľom tejto sady domácich zadaní je okrem samotných algoritmov vyskúšať si prostredie programátorskych súťaží PALMA a ŠVK.

Pri tejto sade sú body pridelené len riešeniam, ktoré Palma akceptovala. Čiastočné riešenia nie sú hodnotené. Preto namiesto skúšania všetkých úloh odporúčame zvoliť si stratégiu vybratia si nejakých úloh a dotiahnutia ich riešenia do zdarného konca.

Odovzdávanie úloh:

  1. zaregistrujte sa na stránke http://palma.strom.sk/?sub=13&type=personal pričom uveďte svoje skutočné meno a priezvisko,
  2. pozrite si poznámky k odovzdávaniu úloh v Jave:
  3. vyriešte niektoré zo zadaných úloh do stanovenému termínu,
  4. e-mailom oznámte F. Galčíkovi alebo M. Nikorovičovi svoj login (=prihlasovacie meno) a to, ktoré úlohy ste úspešne vyriešili - vďaka týmto údajom v Palme overíme, či úlohy boli skutočne vyriešené a zapíšeme body do Moodle.

Poznámky:

  • E-mailom zašlite len svoj login, NIE HESLO!
  • Rozhodujúci je čas odoslania riešenia cez systém Palma, nie odoslanie notifikačného e-mailu cvičiacim - tento e-mail môžete pokojne poslať aj po termíne.
  • Bez notifikačného e-mailu body do Moodle nebudú zapísané.

Úlohy na riešenie

  • Jednosmerky (4 bodov): http://palma.strom.sk/SVK2013/A/
    • grafové algoritmy pre neohodnotené orientované grafy (najkompaktnejší kód ale dáva jednoduchá úprava jedného z algoritmov pre ohodnotené grafy).
  • Výlet (6 bodov): http://palma.strom.sk/SVK2015/SVK-V/
    • backtracking
  • Parašutisti (8 bodov): http://palma.strom.sk/SVK2015/SVK-P/
    • dynamické programovanie: označme si B[j, k] maximálny počet bodov, ktoré možno získať v okamihu keď zachránime j-teho parašutistu (j-teho v zozname parašutistov) a do tejto chvíle sme stratili presne k parašutistov (z predošlých j-1 parašutistov, ktorí vyskočili).
  • Most (12 bodov): http://palma.strom.sk/SVK2014/Most/
    • prehľadávanie stavového priestoru - hľadá sa najkratšia cesta z východiskového stavu do cieľového stavu. Pozor, hrany v grafe modelujúcom stavový priestor sú orientované a ohodnotené.

Testovacie vstupy: Sada8.zip