7. sada domácich zadaní

Najneskorší termín: 3.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:
   • http://palma.strom.sk/java/
   • Odovzdávanie úloh a ukážkové zdrojové kódy
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é.

Rôzne úlohy

• Testovacia úloha: http://palma.strom.sk/PAZ1bS3/S0U1/
  • nebodovaná úloha na vyskúšanie Palmy...
• Prefixový sufix (2 body): http://palma.strom.sk/SVK2011/B/
  • jednoduchá úloha "na rozbehnutie"
• Reakcie (6 bodov): http://palma.strom.sk/SVK2012/B/
  • toto nie je úloha na nič konkrétne (nejaký algoritmus alebo princíp - treba porozmýšľať - možno nad tým, ako by ste riešili túto úlohu v reálnom svete)

Prehľadávanie do šírky

• Kravička (12 bodov): http://palma.strom.sk/SVK2011/A/
  • náročnejší variant prehľadávania do šírky (sú však možné aj iné prístupy)

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 binárneho vyhľadávania (pozor, nie binárne vyhľadávanie v usporiadanom poli)
• 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 2⁸⁰ možných výberov festivalov (podmnožín množiny festivalov), ktoré treba overiť. Keďže log₂(10) ~ 3.32, potom 2⁸⁰ ~ 10²⁴. Ak uvažujeme procesor s frekvenciou 10 GHz = 10¹⁰ Hz (reálne majú do 3GHz), tak tento procesor nespraví viac ako 10¹⁰ 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ň 10²⁴ operácií a to znamená čas aspoň 10²⁴/10¹⁰ = 10¹⁴ sekúnd. Keďže rok má 31536000 sekúnd a 31536000 <= 10⁸, tak náš výpočet pri n=80 trval dlhšie ako 10¹⁴/10⁸ = 10⁶ 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)

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:

• Sada7.zip