Model računanja

Izvor: Wikipedija
Skoči na: orijentacija, traži
Za drugo značenje, vidi računski model

Model računanja je termin iz teorije računanja: teorije izračunljivosti i računske teorije složenosti.

Model računanja je definicija skupa dopustivih operacija rabljenih u računanju i njihovih odgovarajućih troškova. Samo pretpostavljajući određen model računanja je moguće analizirati zahtijevane računske resurse, kao što su vrijeme izvršavanja i memorijski prostor, ili pak raspravljati o ograničenjima algoritama ili računala.

Prilikom raspravljanja o asimptotskim procjenama računske složenosti, uobičajeno je specificirati računski model u terminima primitivnih operacija koje imaju jedinični trošak, ili jednostavno operacija sa jediničnim troškom.

Postoje mnogi modeli računanja, koji se razlikuju u skupu dopustivih operacija i trošku njihovih računanja. Potpadaju u sljedeće široke kategorije: apstraktni stroj (apstraktno računalo), korišten u dokazima izračunljivosti i gornjih granica računske složenosti algoritama, te model decizijskog stabla, korišten u dokazima donjih granica računske složenosti algoritamskih problema.