Rôzne otázky

Dostal som par e-mailov s otazkami, ktore su idealne na to, aby boli adresovane a aj zodpovedane (nielen mnou) na predmetovom fore.

Chcem sa opýtať či ak na záverečnom teste je zadaná úloha napr. Školský výlet (15 bodov, backtracking) tak vlastne sa vyžaduje aby bola úloha vyriešená backtrackingom? Alebo ak nájde iné efektívnejšie riešenie nemusí ho použiť.

Sposob riesenia ulohy uvedeny v zatvorke je odporucany sposob riesenia ulohy. Cielom je vam zjednodusit rozmyslanie o tom, aku techniku pouzit na vyriesenie ulohy. To, akym sposobom ulohu budete riesit, je len na vas. Kazde korektne a efektivne riesenie je akceptovane. Najprv k druhej casti "efektivne riesenie". Ak sa trebars rozhodnete riesit jednoduchu ulohu riesitelnu v polynomialnom case backtrackingom v exponencialnom case (napr. preto, ze toto je jedina vec, ktoru ovladate), nie je to uplne OK a prejavi sa to nizsim (mozno aj velmi nizsim) bodovym ohodnotenim. Dbat treba aj na pozadovanu casovu zlozitost. Napriklad pri ulohe o palindrome bolo specialne oznamene (uvedomil som si to az po vytlaceni zadani a preto to bolo riesene oznamom v uvode testu), ze sa vyzaduje riesenie v case O(n^2). Riesenia s horsou zlozitostou neboli akceptovane. Ak mate pochybnosti ako bude vase riesenie hodnotene, je lepsie sa spytat sa niekoho z dozorujucich kolegov.

Pristavim sa este pri prvej casti "korektne riesenie". Niekedy sa stava, ze studenti riesia ulohu uplne inym sposobom, ktory ale nezodpoveda zadaniu alebo najdu vlastne riesenie vlastnou metodou. Takato kreativita je fajn, no potom sa ocakava, ze svoje riesenie viete aj zdovodnit a vyargumentovat. Ste sice v prvom rocniku a teda zaklady z teoretickej informatiky nemate, no je obzvlast podozrive ak nejaky NP-tazky problem zriesite polynomialne nejakym greedy algoritmom. Totiz teoreticka informatika hovori, ze potom by ste vlastne dokazali P=NP, co je asi najvacsi otvoreny problem sucasnej informatiky a mnoho ludi veri, ze P!=NP. Netreba sa potom divit, ze dozorujuci kolegovia na vase riesenie nebudu pozerat prilis dovercivo.

Bola tu spomenuta uloha skolsky vylet. Ano, pre prakticke vstupy tuto ulohu islo riesit aj v pseudopolynomialnom case (=nie backtrackingom ale cez dynamicke programovanie). Riesenie cez dynamiku je urcite super a akceptovatelne - akurat pripominam, ze toto riesenie cez dynamiku by bolo PODSTATNE narocnejsie, nez vsetky dynamiky, co sme robili na PAZ1b (dokopy?).

Presne je to "Skladací meter". Skúšala som to naprogramovať, ale mám problém s jednou vecou.
Takže generovala som 0 a 1 pre kĺby toho metra a to nasledovne: 1-ak sa ohne, 0-ak sa neohne. Potom, ak sa kĺb ohol, odpočítala som od časť
od časti pred ňou a ak sa neohol, tak som pripočítala. Mám s tým však veľký problém, pretože to nie je dobrý prístup, ako som zistila.
Chcem sa len opýtať aký je vlastne "algoritmus" na zistenie celej dĺžky. Ja keď si to kreslím tak to vidím, ale neviem to premietnuť do nejakého vzorčeka pomocou matem. operácií . Idem na to vôbec dobre?

Ano, ides na to velmi dobre. Ak si nakreslis konkretne "ohnutie" je jednoduche vidiet celkovu dlzku. Ako by si ale dlzku zmerala v realnom svete? Nuz odpoved je jednoducha - zoberies jeden koniec (najlavejsi bod) a zmerias dlzku po druhy koniec (najpravejsi bod). Z toho vyplyva otazka: ako zistit najlavejsi a najpravejsi bod? Predpokladajme, ze ides meter skladat popri ciselnej osi (=popri inom klasickom meradle). Zacinas na pozicii 0. Prilozis jeden diel trebars dlzky 10. Koniec (dalsi klb) sa dostane na poziciu 10 (najlavejsi bod je 0, najpravejsi je 10). Ak teraz pridas dalsi diel bez ohybu dlzky 5, tak kedze klb je na pozicii 10, jeho koniec sa dostane na poziciu 15 (najlavejsi bod je 0, najpravejsi je 15. Ak teraz s ohybom pridame diel dlzky 8, co sa stane? Kedze klb je na pozicii 15, ohyb sposobi, ze sa koniec dielca dostane na poziciu 15-8 = 7. Pripominam, ze teraz je najlavejsi bod metra 0, najpravejsi 15 a koniec metra je na pozicii 8. Pridajme bez ohybu dielec dlzky 12. Predosly ohyb sposobil, ze bez ohybu znamena, ze sa posuvame smerom k zapornym cislam. Ak je teda teraz koniec metra na pozicii 8, po pridani dalsieho dielca sa dostavame na poziciu 8-12 = -4. Teraz je najlavejsi bod metra -4, najpravejsi 15 a koniec metra je na pozicii -4. Predpokladajme, ze nastane ohyb a pripajame dielec dlzky 5. Ohyb znamena zmenu smeru od zapornych cisel ku kladnym (poziciu zmenime pripocitanim). Kedze je koniec na pozicii -4, po pridani dielca smerom ku kladnym cislam dostavame koniec metra na poziciu -4 + 5 = 1. V tuto chvilu je najlavejsi bod metra -4, najpravejsi 15 a koniec metra je na pozicii 1. Asi okrem tychto 3 cisel je dolezite vediet aj aktualny smer (+1 pridavam dielce smerom k +nekonecnu, -1 pridavam dielce smerom k minus nekonecnu).

Co na to treba z hladiska programovania: minPoz, maxPoz, koniec, smer. Na zaciatku minPoz=0, maxPoz=0, koniec=0, smer=1. Ohyb znamena smer = smer*(-1). Pridanie dielca zmena: koniec = koniec + smer*dlzkaDielca; Popritom je minPoz najmensia hodnota, aka kedy bola v koniec a maxPoz najvacsia hodnota aka kedy bola v koniec. Dlzka metra je na konci po zlozeni: maxPoz-minPoz.

Aj ked sa to mozno zda ako tazky programatorsky problem, skor je to otazka zamysliet sa nad tym, ako tuto ulohu vyriesit v realnom svete (resp. co sa vlastne robi pri rieseni ulohy v realnom svete).