Lankide:Joxan Garaialde/Sistema ez lineal

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.

Azpiadar nagusiak

Automaten teoria

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.

Konputagarritasunaren teoria

Artikulu nagusia: «Konputagarritasunaren teoria»

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:

• Konputagarriak dira konponbidea dagoenean beti ebazten dituen algoritmo bat dutenentzat eta ez duten kasuak bereizteko gai dena. Erabakigarriak, konpongarriak edo errekurtsibo gisa ere ezagutzen dira .
• Erdikonputagarriak dira soluzio bat aurkitzeko, baldin badago, gai den algoritmo bat dutenentzat, baina hori zehazten duen algoritmorik ez dago soluziorik existitzen ez denean (kasu horretan, irtenbidea aurkitzeko, algoritmoa begizta infinitu batean sartuko litzateke). Adibide klasiko nagusia geldiketaren arazoa da. Arazo horiek zerrendagarri, errekurtsiboki zenbakarri edo ezagutagarri gisa ere ezagutzen dira, izan ere, arazoaren kasu posible guztiak zerrendatzen badira konponbidea duten horiek antzeman daitezkeelako.
• Konputaezinak dira ebatzi ditzakeen algoritmorik ez dutenak, konponbiderik duten ala ez kontuan hartu gabe. Adibide klasikoa inplikazio logikoaren arazoa da, eta proposizio logiko bat teorema noiz den zehaztean datza; problema horretarako, proposizio bat edo bere ezeztapena teorema den bereizten duen algoritmorik ez dago kasu guztietarako.

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. $A$arazo bat $B$ arazora makurtzen da baldin eta $B$ arazoa konpontzen dakizula suposatuz gero $A$ arazoa konpontzea posible dela; hori $A\leq _{t}B$ bitartez ikusten da, eta informalki esan nahi du $A$ arazoa ez dela $B$ 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.

Konplexutasun konputazionalaren teoria

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.

Beste azpiadarrak

• Eredu konputazionalak. Konputazio bat egitearen abstrakzioak aztertzen ditu. Horren barruan sartzen dira automaten teoriaren eredu klasikoak eta beste eredu batzuk, hala nola funtzio errekurtsiboak, lambda kalkulua eta baita programazio lengoaiak ere.
• Informazio algoritmikoaren teoria. Konplexutasunean oinarritzen da datu-segida bat ( katea) algoritmikoki deskribatzeko; hemen, konplexutasuna bere deskribapen txikienaren luzeraren arabera neurtzen da.
• Zehaztapen eta egiaztapen formala. Problema bat behar bezala modelatzen dela ziurtatzeko metodologiak eta soluzio algoritmikoaren zuzentasuna baliozkotzeko sistema formalak bilatzen ditu.
• Ikaskuntza Konputazionalaren teoriak ordenagailuek beren jokabideak modu autonomoan aldarazi ditzaketen algoritmoak bilatzen ditu, datu enpirikoetan oinarrituta eta, zehazki, adibide eta kontraadibideetan oinarrituta. Ikaskuntza mota horri <b id="mwWQ">ikaskuntza gainbegiratua</b> deitzen zaio. Konplexutasun konputazionalaren teoriaren antzera, teoria horretan, funtzioak ikasi beharreko zailtasun-mailaren arabera sailkatzen dira.
• Moten teoria. Enuntziatuen sailkapena bilatzen du hizkuntzaren teoria formalaren tresnak erabiliz kalkulatzen dituzten balio moten arabera.

Historia

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.

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.

Bibliografia

• American Mathematical Society. 2010 Mathematics Subject Classification. .
• Boolos, George; Burgess, John; & Jefrey, Richard (2007). Computability and Logic. Cambridge. ISBN 978-0-521-70146-4. 
• Cooper, S. Barry (2004). Computability Theory. Chapman & Hall/CRC. ISBN 1-58488-237-9. 
• Kelley, Dean (1995). Teoría de autómatas y lenguajes formales. Prentice Hall. ISBN 978-0-691-13382-9. 
• Sipser, Michael (2005). Introduction to the Theory of Computation (2 edición). Course Technology. ISBN 978-0534950972.