Pogovor:Računski model

Iz MaFiRaWiki

Kaj je algoritem?

Ali res želimo trditi, da se mora algoritem končati na poljubnih podatkih? Po moje se mora končati na poljubnih smiselnih podatkih. Na primer: algoritem, ki poišče najkrajšo pot v grafu sprejme za vhodni podatek seznam vozlišč, seznam povezav ter začetno in končno vozlišče. Če bi res veljalo, da se mora algoritem obvezno ustaviti, bi moral najprej preveriti, ali je res dobil smiselne podatke (lahko bi se zgodilo, da se kaka povezava sklicuje na vozlišče, ki ni našteto v seznamu vozlišč). In če podatki niso smiselni, kako naj algoritem odgovori? AndrejBauer 21:26, 29 oktober 2006 (CET)

Če želimo imeti vse poštimano moramo vztrajati pri definiciji, da se algoritem ustavi pri poljubnih podatkih. Težava ni v tem, da moramo vedno za reševanje problema P v praksi napisati pravi algoritem. Pogosto zadošča, da napišemo progam A, ki se ustavi le pri smiselnih podatkih. Ključno pa je vprašanje, ali sploh obstaja za problem P algoritem B, ki se zna odločiti, ali so podatki smiselni (in se ustavi, če niso), oz. požene A, če so. Kombinacija B in A zagotavlja, da za naš problem P obstaja algoritem, ki ga rešuje in se ustavi pri vsakem vhodu (vsaki nalogi problema P). Drugače povedano, vedeti moramo, ali je množica smiselnih nalog problema totalno rekurzivna.TomazPisanski 21:58, 29 oktober 2006 (CET)

Še tole, čar celotne zgodbe je, da je definicija algoritma (v smislu, ki ga zagovarjam), neodvisna od izbire (standarndega univerzalenga) modela računanja.TomazPisanski 22:02, 29 oktober 2006 (CET)

Kaj so smiselni podatki?

Pri opisu računskega modela je zaenkrat spuščen še en pomemben del, ki govori o kodiranju vhodnih podatkov. Če ne privzamemo standardnega kodiranja v nek jezik, bi lahko z goljufanjem rešili tudi nerešlive probleme. Npr. če bi želel napisati program H v Javi ki rešuje problem zaustavitve in dobi na vhodu zakodiran program A v Javi in podakte P, ki naj bi jih A izvajal, pa bi takoj na zacetku zapisal 1, če se program A ustavi pri podatkih P in 0, če se A ne ustavi pri podatkih P, bi program H lahko samo pogledal prvi znak in se pravilno odločil.Torej moramo paziti, da so vsa standardna kodiranja nalog med seboj ekvivalentna (celo polinomsko prevedljiva). Če bi denimo kodiral naravna števila v eniškem sistemu, bi bil problem odločitve, ali je število n praštevilo rešljiv v linearnem času kar z Eratostenovim rešetom (spet goljufanje). Zato moramo biti toliko bolj pazljivi, ko govorimo o smiselnih podatkih. Če se tega ne da opredeliti na preprostem sintaktičnem nivoju regularnih jezikov, je to bolj čudna reč, v katero raje ne bi drezal.TomazPisanski 22:17, 29 oktober 2006 (CET)

Osebna orodja