Sry, napísal som už príspevok ale omylom som to zavrel, tak v krátkosti.
Zz: ano, už to s prevodom čísel k ničomu nevedie; ja som to písal len ako ukážku M. Prýmkovi, že existuje viac firiem, ktoré sa aspoň pri nábore chcú niečo teoretickejšie (aj keď je pravda, že prakticky - naprogramovať).
Teda já o tomhle nic nevím, ale mám takové podezření, že jakmile začneme brát v úvahu cache, diskové operace, přerušení apod., tak to už jsme u úplně jiného typu výpočtu než co se řeší v teoretické složitosti jako O(xy)... Mýlím se?
Skôr sa mýliš, aj keď možno nie tak úplne. V cache oblivious modeli ide o počet cache missov na rozdiel od počtu krokov, v čom máš pravdu. Ale O(...) tam sú.
Teda keď cache oblivious algoritmus beží v O(f(n)), tak bude mať O(f(n)/c) cache missov pre veľkosť cache c. To platí pre ľubovolné c, takže sa dá povedať, že sa program chová ku cache-i optimálne.
A zaujímavé je, že aj keď sú to "len výpočty" s istými predpokladmi, tak to na dnešnom "domrvenom HW" funguje pomerne presne.
Hraje to nějakou roli u té dříve zmiňované nemožnosti (obecně) zjistit, zda dva programy dělají totéž?
Za predpokladu konečnej abecedy (čo je v PC zrejmé) si myslím, že ano - konečná páska => konečný počet stavov počítača => stačí zistiť ekvivalenciu konečných automatov a to vieme => vieme zistiť, či 2 programy robia to isté.
Mám tam niekde chybu?
1675 Odpovědí
288766 Zhlédnutí