From Wikipedia, the free encyclopedia
Konputazioaren teoria edo teoria informatikoa prozesuen abstrakzioaren azterketan zentratzen den ezagutza arrazional eta sistematizatuaren multzoa da, sistema formalen laguntzaz erreproduzitzeko, hau da, sinboloen eta arau logikoen bidez. Konputazioaren teoriak prozesuak modelatzeko aukera ematen du informazioa prozesatzen eta kalkuluak egiten dituzten gailuen mugen barruan; adibidez, ordenagailua. Horretarako, automaten teorian oinarritzen da prozesu horiek simulatu eta estandarizatzeko, bai eta arazoak formalizatu eta irtenbideak emateko ere[1].
Teoria horrek ordenagailu edo algoritmo baten kontzeptua nahikoa sinplifikatu eta orokorrean formalizatzen duten eredu matematikoak eskaintzen ditu bere gaitasunak eta mugak aztertu ahal izateko. Eredu horietako batzuek funtsezko zeregina dute informatikaren hainbat aplikaziotan, besteak beste, testuen prozesamenduan, konpilagailuetan, hardwarearen diseinuan eta adimen artifizialetan.
Automata mota asko daude, hala nola ausazko sarbideko makinak, automata zelularrak, abako makinak eta egoera abstraktuko makinak; hala ere, kasu guztietan frogatu da eredu horiek ez direla Turing makina baino orokorragoak, Turing makinak automata horietako bakoitza simulatzeko gaitasuna baitu. Horrek Turing makina ordenagailuaren eredu unibertsala dela pentsatzea dakar.
Teoria horrek, algoritmoak erabiliz, problemak ebazteko aukeraren mugak aztertzen ditu. Informatikaren zati handi bat arazoak, algoritmikoki, konpontzera bideratzen da; beraz, ezinezko problemak aurkitzea sorpresa handia da. Konputagarritasunaren teoria baliagarria da problema horiek, algoritmikoki, konpontzen ez saiatzeko, eta horrela denbora eta esfortzua aurrezteko.
Teoria horretan problemak ezintasun-mailaren arabera sailkatzen dira:
Bada sailkapen horren bertsio orokorrago bat, non konputaezinak diren arazoak beste batzuk baino arazo zailagoetan banatzen diren. Sailkapen horiek lortzeko, tresna nagusia erreduzigarritasunaren kontzeptua da. arazo bat arazora makurtzen da baldin eta arazoa konpontzen dakizula suposatuz gero arazoa konpontzea posible dela; hori bitartez ikusten da, eta informalki esan nahi du arazoa ez dela arazoa baino zailagoa konpontzeko. Esaterako, pertsona batek gehikuntzak egiten badakiela kontuan hartuz, oso erraza da batuketa errepikatuz biderkatzen irakastea; beraz, biderkatzea batuketak egitera murrizten da.
Arazo bat konputagarria bada ere, agian, ezinezkoa izango da praktikan konpontzea memoria edo exekuzio denbora asko behar bada. Konplexutasun konputazionalaren teoriak memoriaren, denboraren eta beste baliabide konputazional batzuen beharrak aztertzen ditu problemak ebazteko; horrela, arazo batzuk konpontzen beste batzuk baino zailagoak zergatik diren azal daiteke. Adar horren lorpen handienetako bat arazoen sailkapena da, taula periodikoaren antzekoa, zailtasunaren araberakoa. Sailkapen horretan, problemak konplexutasun klaseen bidez bereizten dira.
Teoria horrek arazo bat konputazionalki ebatzi nahi den ia ezagutza-eremu guztietan du aplikazioa, zeren, ikertzaileek problema bat ebazteko metodoa erabiltzeaz gain, azkarrena erabili nahi baitute. Konplexutasun konputazionalaren teoriak baditu aplikazioak ere kriptografia bezalako alorretan, non kode sekretu bat argitzea arazo oso zaila izango dela espero den pasahitza izan ezean, eta, kasu horretan, arazoa erraza bihurtzen da.
Konputazioaren teoria propioa XX. mendearen hasieran hasten da, ordenagailu elektronikoak asmatu baino pixka bat lehenago. Garai horretan, hainbat matematikarik galdetzen zuten ea ba ote zegoen metodo unibertsalik problema matematiko guztiak ebazteko. Horretarako, problemak ebazteko metodoaren nozio zehatza garatu behar izan zuten, hau da, algoritmoaren definizio formala.
Eredu formal horietako batzuk Alonzo Church (Lambda kalkulua), Kurt Gödel (funtzio errekurtsiboak) eta Alan Turing (Turingen makina) aitzindariek proposatu zituzten. Eredu horiek baliokideak direla frogatu da, algoritmo berdinak simula ditzaketen zentzuan, nahiz eta modu ezberdinetan egin. Konputazio-eredu berrienen artean, programazio-lengoaiak daude, aurreko ereduen parekoak ere frogatu direnak; Hori Church-Turing-en aierurako froga sendoa da, dauden eta egon daitezkeen algoritmo guztiak Turing-en makina batean, edo baliokidean, simula daitekeela funtzio errekurtsiboak erabiliz. 2007an, Nachum Dershowitz eta Yuri Gurevichek algoritmoen axiomatizazio batzuetan oinarritutako aieru horren froga bat argitaratu zuten[2].
Teoria horren lehen emaitzetako bat algoritmikoki ebazteko ezinezko problemak egotea izan zen, geldiketa-arazoa izanik horietako ospetsuena. Arazo horietarako ez dago eta ez da egongo haiek konpondu ditzakeen algoritmorik, ordenagailuan zenbat denbora edo memoria dagoen axolarik izan gabe. Gainera, konputagailu modernoen agerpenarekin, teorian konpon daitezkeen arazo batzuk praktikan ezinezkoak zirela ikusi zen, irtenbide horiek denbora edo memoria ez-errealistak behar baitzituzten aurkitzeko.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.