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