Informàtica teòrica: diferència entre les revisions

 

== Història ==

Tot i que algorismes han existit des de fa segles (l'[[Algorisme d'Euclides]] per determinar el [[Màxim comú divisor]] de dos nombres encara s'usa en informàtica), no va ser fins al 1936 que [[Alan Turing]], [[Alonzo Church]] i [[Stephen Kleene]] van formalitzar la definició d'algorisme en termes de computabilitat. Mentre que el sistema binari de numeració i els [[Sistemes Formals]] han existit abans de 1703, és llavors quan [[Gottfried Leibniz]] va formalitzar la lògica amb valors binaris de “cert” o “fals”. Tot i que la inferència lògica i les demostracions matemàtiques han existit des de temps antics, fins al 1931 [[Kurt Gödel]] no va provar amb el seu [[Teorema d'incompletesa de Gödel]] que hi havia limitacions fonamentals en afirmacions que, inclús sent veritat, poden o no ser provades.

 

 

Amb el desenvolupament de la [[Mecànica quàntica]] a inicis del segle XX va introduir el concepte de que múltiples operacions matemàtiques es poden fer en una funció d'ona d'una partícula. En altres paraules, es poden calcular funcions en diferents estats simultàniament. Això porta cap al concepte de [[Ordinador quàntic]] a les darreries del segle XX, quan [[Peter Shor]] a la dècada del 1990 va demostrar que aquests mètodes es podrien usar per la factorització de grans nombres en [[temps polinòmic]], la qual cosa, si s'implementés, ocasionara que la majoria de la [[criptografia de clau pública]] fos insegura.

 

== Organitzacions ==