Zadanie 7

Najneskorší termín: 13.5.2023 (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: http://palma.strom.sk/java/ a Odovzdávanie úloh a ukážkové zdrojové kódy
  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.
  • niektoré nové úlohy môžu byť pridané po skončení programátorskej súťaže ŠVK (17.4.2024)

Rôzne úlohy

  • Reakcie (5 bodov): https://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 (8 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)
  • Minimum (10 bodov): https://palma.strom.sk/SVK2023/M/
    • Prehľadávanie do šírky s pridanou informáciou o vzdialenosti. Štartovacích vrcholov môže byť v rade na začiatku viacero. Algoritmus je možné ukončiť pri nájdení prvého nálezu.

Backtracking

Dynamické programovanie/backtracking

  • Súčin (S1 – 5 bodov, S2 – 10 bodov, S3 – 6 bodov):
    • Verzia S1 (https://palma.strom.sk/SVK2023/S1/) – obmedzenia na veľkosť vstupu sú malé, klasický backtrack funguje. Body za S1 sú udelené iba ak je úloha riešená backtrackom (teda za riešenie pomocou dynamického programovania sú body len za úlohu S2).
    • Verzia S2 (https://palma.strom.sk/SVK2023/S2/) – dynamické programovanie s dvojrozmerným poľom. Hodnota D[i][j] hovorí, akú hodnotu môžeme dostať v i-tom kroku hry keď budeme uvažovať karty začínajúce od pozície j. Pri výpočte je potrebné rozhodovať sa, či nasledovná karta bude z ľavej časti (hodnota j sa zväčší o 1) alebo pravej (vtedy hodnota j ostáva). Pozícia ľavej karty je daná indexom j. Pozíciu pravej karty vieme vyrátať s použitím i a j (vieme koľko kariet je v i-tom kroku hry k dispozícii).
    • Verzia S3 (https://palma.strom.sk/SVK2023/S3/) – rekonštrukcia riešenia.
  • 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
  • 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 (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.2024): 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 log’_2_'(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?
    • IDEA 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

  • Jednosmerky (4 bodov): https://palma.strom.sk/SVK2013/A/
    • grafové algoritmy pre neohodnotené orientované grafy (najkompaktnejší kód ale dáva jednoduchá úprava jedného z algoritmov pre ohodnotené grafy).

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