7. sada domácich zadaní

Najneskorší termín: 24.4.2013 (streda) o 21:00, resp. 28.4.2013 (nedeľa) o 21:00 za 50% bodov.

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 (skupina A) 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.

Rôzne úlohy

Prehľadávanie do šírky

Dynamické programovanie/backtracking

  • Veľký vlakový problém 1 (4 body): https://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í?
  • Veľký vlakový problém 2 (10 bodov): https://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): 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 (12 bodov): https://palma.strom.sk/SVK2011/D/
    • 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í). Vyhradzujeme si tiež právo nehodnotiť riešenia, ktoré neboli akceptované cez Palmu.

Testovacie vstupy: Sada7.zip