| e-gradiva | Sistemi | Motorola | Omrežja | ||||||
 |
|||||||||
| SERŠ Maribor | |||||||||
Izračunljiv problem je tisti, za katerega je moč najti algoritem, ki ga izračuna v končnem številu korakov. Vendar pa to ne pomeni, da lahko vsak končni algoritem tudi izračunamo. Vsak realni končni avtomat nima končno velikega pomnilnika in zaradi tega ni mogoče množiti dveh poljubno velikih števil, kar pa bi lahko storili na Turingovem stroju. Ne glede na to kako velik pomnilnik imamo, vedno bo obstajalo večje število, kot ga lahko v naš pomnilnik zapišemo, saj v resničnem svetu ni pomnilnika z neskončno kapaciteto.
Poleg končnega pomnilnika, se pri resničnem računanju pojavlja še ena omejitev. To je čas računanja. Vemo sicer, da je pri izračunljivih problemih število ukazov končno, vendar je to končno število lahko zelo veliko. Tipičen računalnik lahko dan danes opravi okrog 109 ukazov na sekundo. Če npr. potrebujemo za rešitev nekega problema 1019 ukazov, bo reševanje trajalo več kot 300 let. Za praktične namene je ta problem seveda nerešljiv.
V splošnem lahko rečemo, da obstajajo težki problemi, ki so sicer v principu rešljivi, vendar jih ne moremo rešiti zaradi omejenega pomnilnika in/ali omejenega časa. Take probleme imenujemo neobvladljivi problemi. Vzemimo, da želimo na računalniku rešiti neki problem. O njegovi težavnosti lahko zastavimo naslednji dve vprašanji:
Odgovora na ti dve vprašanji običajno označujemo kot prostorska in časovna kompleksnost problema. Prvo merimo s številom vhodnih spremenljivk in številom in velikostjo podatkovnih struktur, ki jih uporablja algoritem. Drugo merimo s številom korakov ali ukazov, lahko pa tudi elementarnih operacij, ki jih mora opraviti procesor med izvrševanjem algoritma. Ker za veliko problemov obstaja več algoritmov, je tu bolje govoriti o kompleksnosti algoritmov kot o kompleksnosti problema. Tako prostor kot čas, ki ju potrebuje nek algoritem, sta običajno odvisna od vhodnih podatkov. Če jih je več je praviloma potrebno več prostora in več časa. Praktične izkušnje tudi kažejo, da je časovna kompleksnost dosti bolj omejevalna kot prostorska. V nadaljevanju se bomo zato omejili samo na njo. Povejmo pa, da večina stvari, ki jih bomo povedali o časovni kompleksnosti, na skoraj enak način velja za prostorsko.
Za podajanje kompleksnosti algoritmov se običajno uporablja tako imenovana notacija veliki O, kjer črka O pomeni "order of" ali po naše "reda velikosti". Če rečemo, da ima nek algoritem časovno kompleksnost O(f (n)), to pomeni, da algoritem za rešitev problema velikosti n potrebuje k*f(n) elementarnih operacij, kjer je f(n) neka funkcija velikosti problema n, k pa je neka konstanta. Velikost problema n je običajno definiran kot število neodvisnih vhodnih spremenljivk . Kakšna je vrednost konstante k, nas ne zanima, važno je le, da se število operacij spreminja v skladu s funkcijo f(n) oziroma ima red velikosti f(n). Algoritem, ki zahteva 0,1* f(n) elementarnih operacij ima torej enako kompleksnost kot algoritem 10* f(n). Časovna zahtevnost je v resnici relativen pojem, ki ima smisel samo skupaj z dogovorjeno množico elementarnih operacij. Ker nam gre pri časovni zahtevnosti samo za približno oceno reda zahtevnosti, si lahko privoščimo precejšno ohlapnost.
Danes je splošno sprejeta ocena, da so rešljivi algoritmi s polinomsko funkcijo f(n). Najpogostejše polinomske funkcije za opis časovne zahtenosti so log2 n, n*log2 n, n2, n3. Medtem, ko so kn (k - konstanta), nn in n! nad-polinomske in jih tudi imenujemo eksponencialne. Eksponencialne funkcije že pri malih n postanejo ekstremno velike in algoritmi, pri katerih je časovna zahtevnost opisana z eksponencialno funkcijo realno-časovno nerešljivi.
Sedaj pa si poglejmo najbolj slaven problem, ki ima eksponencialno časovno zahtevnost.
Eden od najbolj znanih neobvladljivih problemov, ki nastopa tudi v vrsti drugačnih oblik, je problem trgovskega potnika. Imamo n mest, katerih medsebojno razdaljo podaja n x n matrika |dij|, kjer je dij pozitivno celo število. Trgovski potnik mora prepotovati vsa mesta tako, da obišče vsako mesto natanko enkrat. Problem je, kako najti pot z najmanjšo skupno dolžino.
Ta problem je očitno rešljiv, saj obstaja samo (n-1)!/2 različnih poti. Računalnik mora samo sešteti razdalje vsake poti in izbrati najkrajšo. Zelo hitro pa lahko ugotovimo, da bi že pri razmeroma majhnih vrednostih n celo najhitrejši računalnik potreboval milijarde let. Pri n.pr. n=51 (glavna mesta vseh držav ZDA) imamo 50!/2 različnih poti, kar predstavlja 65-mestno desetiško število.
Dejstvo, da je nek problem neobvladljiv, v splošnem pomeni, da ga je v nekem pametnem času mogoče rešiti samo, če je velikost problema n manjša od neke maksimalne vrednosti m. Vrednost m je odvisna od problema in seveda od hitrosti (število operacij na sekundo) računalnika ki ga uporabljamo za reševanje. Zdi se samoumevno, da lahko s povečevanjem hitrosti računalnika povečamo m na poljubno želeno vrednost. Žal pa temu ni tako.
Gor
Sistemi
Motorola 68XX
Neodločljivi problemi
Fizikalne omejitve 
SERŠ Maribor, Strokovna gimnazija, leto: 2003/04, avtor: Primož Brezovnik