7. sada domácich zadaní

Najneskorší termín: 1.5.2016 (nedeľa) o 21:00.
Bodový limit: 50% z bodov za sady 1-6

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, M. Opielovi 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é.

Rôzne úlohy

Prehľadávanie do šírky

Dynamické programovanie/backtracking

  • Veľký vlakový problém 1 (4 body): http://palma.strom.sk/SVK2012/A1/
    • možných prístupov je veľa, v implementačne najjednoduchšom riešení je dôležité všimnúť si ohraničenie počtu sprievodcov - aký je počet všetkých možných rozdelení?
  • Kartičky I (5 bodov): http://palma.strom.sk/SVK2010/E1/
    • keďže počet kartičiek je nanajvýš 20, zafunguje aj rozumný backtracking
  • Hamburger I (5 bodov): http://palma.strom.sk/SVK2010/C1/
    • sú možné rôzne prístupy (napr. aj dynamické programovanie)
  • Veľký vlakový problém 2 (5 bodov): http://palma.strom.sk/SVK2012/A2/
    • taktiež je možných viacero prístupov...
    • dynamické programovanie, kľúčom je zovšeobecnený problém: P(n, k) - maximálny počet cestujúcich na jedného sprievodcu v prípade, kedy je prvých n vozňov rozdelených medzi k sprievodcov.
    • technika bisekcie
  • Festivalové leto I (6 bodov): http://palma.strom.sk/SVK2011/C/
    • nech n je počet festivalov
      • s využitím greedy algoritmu je úloha riešiteľná v čase O(n.log(n))
      • cez dynamické programovania je úloha riešiteľná v prípade jednoduchej implementácie v čase O(n2), pri máličko chytrejšej implementácii je možný aj čas O(n.log(n))
        • pre Palmu je akceptovateľný aj čas O(n2)
      • backtracking O(2n) nie je pre Palmu akceptovateľný, keďže n môže byť až 80
        • treba si uvedomiť, že ak n=80, potom máme 280 možných výberov festivalov (podmnožín množiny festivalov), ktoré treba overiť. Keďže log2(10) ~ 3.32, potom 280 ~ 1024. Ak uvažujeme procesor s frekvenciou 10 GHz = 1010 Hz (reálne majú do 3GHz), tak tento procesor nespraví viac ako 1010 operácií za sekundu. Ak by procesor dokázal v rámci jednej operácie spraviť jeden výber festivalov a aj overiť jeho správnosť (čo nedokáže), potrebovali by sme aspoň 1024 operácií a to znamená čas aspoň 1024/1010 = 1014 sekúnd. Keďže rok má 31536000 sekúnd a 31536000 <= 108, tak náš výpočet pri n=80 trval dlhšie ako 1014/108 = 106 rokov (slovom milión rokov na jednom procesore).
    • idea:
      • dynamické programovanie: ak viete, že nejaký festival je časovo posledný festival, ktorého sa zúčastnite v optimálnom výbere, čo viete povedať o zvyšných festivaloch v optimálnom výbere?
      • greedy: uvažujme festival, ktorý skončí ako prvý. Je pravdou, že tento festival je v nejakom optimálnom výbere?
  • Festivalové leto II (12 bodov): http://palma.strom.sk/SVK2011/D/
    • dynamické programovanie, treba sa inšpirovať úlohami, ktoré sa robili na cvičení a prednáške
  • Kartičky II (7 bodov): http://palma.strom.sk/SVK2010/E2/
    • keď počet kartičiek môže byť až 2000, backtrack nezafunguje. Treba však využiť, že čísla na kartičkách sú nanajvýš 100. A to dáva priestor na dynamické programovanie (treba sa inšpirovať úlohami, ktoré sa robili na cvičení a prednáške)
  • 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).

Bodovanie: Bodové hodnotenie uvedené v zátvorke je výsledkom predpokladanej náročnosti riešenia a implementácie úlohy. Vzhľadom na vysokú bodovú ponuku si vyhradzujeme právo zmeniť bodové hodnotenie (v závislosti od počtu úspešných riešení).

Vybrané testovacie vstupy: