7. sada domácich zadaní

Najneskorší termín: 23.4.2012 (pondelok) 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.

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 Ferovi Galčíkovi (skupiny A, E[xtra]) alebo Lacovi Mikešovi (skupiny B, C, D) 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.

Úlohy na riešenie

Prehľadávanie do šírky

  • Kravička (14 bodov): https://palma.strom.sk/SVK2011/A/
    • náročnejší variant prehľadávania do šírky (sú však možné aj iné prístupy)
  • Labyrint (14 bodov): https://palma.strom.sk/SVK2011/E/
    • variant prehľadávania do šírky (jednoduchší ako v prípade úlohe o kravičke), ak je jasné ako funguje prehľadávanie do šírky v 2D poli, treba spraviť len relatívne jednoduchú úpravu, ktorá zoberie do úvahy teleportovanie.

Backtracking

Dynamické programovanie

  • Festivalové leto I (7 bodov): https://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 (15 bodov): https://palma.strom.sk/SVK2011/D/
    • dynamické programovanie, treba sa inšpirovať úlohami, ktoré sa robili na cvičení a prednáške
  • Kartičky II (9 bodov): https://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)
  • Hamburger I (5 bodov): https://palma.strom.sk/SVK2010/C1/
    • sú možné rôzne prístupy (napr. aj dynamické programovanie)

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í).

Testovacie vstupy: Sada7.zip