Informatika teoriko

Informatika teorikoa edo Konputazio teorikoa konputazioaren zientzien eta matematikaren atal edo azpimultzo bat da, konputazioaren alderdi abstraktuagoetan edo matematikoagoetan fokatzen dena.

Esparrua 
Ez da erraza informatika teorikoaren arloak mugatzea. ACMren Special Interest Group on Algorithms and Computation Theory (SIGACT) delakoak horrela azaltzen ditu:

 Informatika teorikoaren eremuak interpretazio zabala eskatzen du, honako atalak barneratuz: algoritmoak, datu-egiturak, konplexutasun konputazionalaren teoria, konputazio banatua, konputazio paraleloa, VLSI, ikasketa automatikoa, biologia konputazionala, geometria konputazionala, informazioaren teoria, kriptografia, konputazio kuantikoa, zenbakien eta aljebraren teoria konputazionala, programen semantika eta egiaztapena, automaten teoria eta zorizkotasunaren azterketa. 

ACMren Transactions on Computation Theory aldizkariak gehikuntzak egiten dizkio aurreko zerrendari, kodetze-teoria, ikasketa konputazionalaren teoria gehituz, baita informatikaren arlo ohikoago batzuk ere, hala nola datu-baseak, informazioa berreskuratzea eta sareak.

Historia 
Algoritmo formalak milurtekotan ezagunak izan diren arren (konputazioan Euclides-en algoritmoa erabiltzen da oraindik bi zenbakiren zatitzaile komun handiena zehazteko), 1936ra arte ez zen algoritmo baten definizioa formalizatu konputazioari begira;  Alan Turing-ek, Alonzo Church-ek eta Stephen Kleen-ek egindako ekarpenaren eskutik. Matematiketan sistema bitar eta formalak agertzen ziren 1703 baino lehen, baina urte hartan Gottfried Leibnizek egiazko eta faltsu balio bitarren logika formalizatu zuen. Inferentzia logiko eta matematika-froga aspaldikoak ziren arren, 1931n Kurt Gödel-ek ez-osotasunaren teoremarekin frogatu zuen funtsezko mugak zeudela sententziak frogatu ahal izateko, egiazkoak izan arren

Horrela iritsi da logikaren eta konputagarritasunaren azterketa modernora eta informatika teorikora. Informazioaren teoria gehitu zenClaude Shannonek komunikazioari buruz 1948an proposatutako teoria matematikoaren harira. Hamarkada berean garun barruko ikasketaren eredu matematikoa aurkeztu zuen  Donald Hebbek. Biologian nolabait oinarrituta bi eremu berri ezarri ziren: neurona-sareak eta konputazio banatu paraleloa.

XX. mendearen hasieran mekanika kuantikoaren garapenarekin iritsi zen partikula baten uhin-funtzio batean egin zitezkeen eragiketa matematikoen kontzeptua. Horren ondorioz, XX. mendearen bigarren erdian, konputagailu kuantikoaren kontzeptua sortu zen, 1990eko hamarkadan bultzada handia izango zuena Peter Shor-ek frogatu zuenean metodo horiek  erabil zitezkeela zenbaki handiak denbora polinomikoan faktorizatzeko, kriptografia iraultzeko aukera emanez.

Erreferentziak

Kanpo estekak 

 ALAN TURING 100 URTE: Informatikak zor diona/

Informatika teorikoa