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

Najneskorší termín: 16.5.2022 (pondelok) o 13: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:
  3. vyriešte niektoré zo zadaných úloh do stanovenému termínu,

Poznámky:

  • Body budú do moodle zapísané až po uplynutí termínu. Budete vyzvaní, aby ste e-mailom oznámili svoj login.
  • Za vyriešenú úlohu máte plný počet bodov, za nevyriešenú nula. Komentáre nie sú nutné. Code review nebude (ak by ste predsa nevedeli s úlohou pohnúť, môžeme sa vybraným úlohám venovať na cvičeniach na konci semestra).
  • Pre študentov opakujúcich tento predmet: ak ste úlohu vyriešili minulý rok, body za ňu nedostanete. Napriek tomu ju môžete riešiť v rámci prípravy na záverečný test. Ak by ste mali výrazne zúženú ponuku na získanie bodov, vieme sa individuálne dohodnúť na nejakých ďalších úlohách.

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 8.5.2022): 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)
  • 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í).