7. sada domácich zadaní - tréning na ŠVK

Najneskorší termín: 8.5.2018 (utorok) o 21:00.
Bodový limit: MAX(100% z bodov za sady 1-6, 15)

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 administrátorovi predmetu (Galčík) 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 do 3 dní po termíne.
  • Bez notifikačného e-mailu body do Moodle nebudú zapísané.

Rôzne úlohy

Prehľadávanie do šírky

Backtracking

Dynamické programovanie/backtracking

  • Klávesnica (8 bodov): https://palma.strom.sk/SVK2016/SVK-B/
    • dôležite je si uvedomiť, že každé písmeno slova môže reprezentovať rôzne pozície kurzora na klávesnici
  • Záhradka (8 bodov): https://palma.strom.sk/SVK2016/SVK-D/
    • náročnejšie dynamické programovanie
  • 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í?
  • Kartičky I (5 bodov): https://palma.strom.sk/SVK2010/E1/
    • keďže počet kartičiek je nanajvýš 20, zafunguje aj rozumný backtracking
  • Hamburger I (5 bodov): https://palma.strom.sk/SVK2010/C1/
    • sú možné rôzne prístupy (napr. aj dynamické programovanie)
  • Veľký vlakový problém 2 (5 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 bisekcie
  • Festivalové leto I (4 body - do 29.4.2018): 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 (10 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 (7 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)
  • Výlet (6 bodov): https://palma.strom.sk/SVK2015/SVK-V/
    • backtracking
  • Parašutisti (8 bodov): https://palma.strom.sk/SVK2015/SVK-P/
    • dynamické programovanie: označme si B[j, k] ako indikátor toho, či je možné zachrániť j-teho parašutistu (j-teho v zozname parašutistov) a pritom do okamihu jeho záchrany sme stratili presne k parašutistov (z predošlých j-1 parašutistov, ktorí vyskočili).
    • čln je na začiatku na pozícii 0
  • TyBer (5 bodov): https://palma.strom.sk/SVK2017/SVK-T/
    • označme si R[J] - maximálny dosiahnuteľný príjem v okamihu, keď je auto na zastávke J zastavilo, aby z neho vystúpil pasažier, alebo prechádza zastávkou J prázdne.

Grafové algoritmy

Grafové algoritmy - ohodnotené grafy

  • Most (12 bodov): https://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é.

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: