Laskettavuus

Wikipedia
Loikkaa: valikkoon, hakuun

Laskettavuus tai laskettavuusteoria on teoreettisen tietojenkäsittelytieteen haara, joka tutkii ongelmien ratkeavuutta ja ratkaisemisen tehokkuutta algoritmisesti. Käytännössä laskettavuusteoriassa pyritään selvittämään, voidaanko jokin ongelma ratkaista tietokoneiden avulla vai ei, ja jos voidaan, kuinka tehokkaasti. Tehokkuus voi tarkoittaa joko laskennan vaatimaa aikaa tai muistikapasiteettia.

Ongelmanasettelu on ensin muotoiltava täsmällisesti erilaisten laskennan mallien avulla, joiden voidaan ajatella olevan tietokoneiden matemaattisia malleja. Esimerkki tällaisesta mallista on Turingin kone. Vasta tämän jälkeen voidaan analysoida, kuinka paljon laskentaresursseja tehtävä vaatii tai onko se ylipäänsä ratkaistavissa.

Katso myös[muokkaa | muokkaa wikitekstiä]

Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.