Informàtica teòrica

De la Viquipèdia, l'enciclopèdia lliure

La Informàtica teòrica és una divisió o subconjunt de la Informàtica i les Matemàtiques que se centra en els aspectes més abstractes o formals de la informàtica.

Aquesta divisió inclou l'Anàlisi d'algorismes i la Semàntica Formal dels llenguatges de programació. Hi ha més conjunts d'estudi a part d'aquests dos, els quals tenen diferents grups professionals i associacions d'estudi i revistes i congressos diferents.

Abast[modifica]

No és senzill circumscriure amb precisió les àrees d'aquesta teoria i el grup de treball Special Interest Group on Algorithms and Computation Theory (SIGACT) de l'ACM descriu la seva missió com la de promoure la informàtica teorica i notes.[1]

El camp de la informàtica teòrica s'interpreta àmpliament de manera que inclou algoritme, estructures de dades, Complexitat computacional, computació distribuïda, computació paral·lela, circuit integrat a molt gran escala, aprenentatge automàtic, Biologia computacional, Geometria computacional, Teoria de la informació, Criptografia, Computació quàntica, Teoria de nombres, Àlgebra computacional, Semàntica formal, Mètodes Formals, Teoria de la computabilitat i l'estudi de l'Atzar. Aquestes tasques es distingeixen pel seu èmfasi en tècniques matemàtiques i el rigor matemàtic.

A aquesta llista, la revista “Transactions on Computation Theory” de l'ACM hi afegeix la Teoria de codis, Aprenentatge de computadors i aspectes teòrics de parts de la informàtica tals com bases de dades, Recuperació d'Informació, models econòmics i de xarxes.[2] Tot i l'ampli ventall que abasta aquesta disciplina, els especialistes en aquest camp es diferencien ells mateixos dels especialistes més aplicats. Ells mateixos sovint es defineixen com que fan la ciència més fonamental que hi ha sota la Informàtica.[3]

Teoria d'autòmats Teoria de nombres Teoria de grafs
Lògica Matemàtica Teoria d'Autòmats Teoria de Nombres Teoria de Grafs
Teoria de Categories Geometria Computacional Computació Quàntica
Teoria de Tipus Teoria de Categories Geometria Computacional Computació Quàntica

Història[modifica]

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.


Aquests esdeveniments han portat a l'estudi modern de la lògica i la computabilitat, i de fet el camp de les ciències de la computació teòrica en conjunt. La Teoria de la informació va ser introduït en el camp el 1948 amb una teoria matemàtica de la computació feta per Claude Shannon. A la mateixa dècada, Donald Hebb va introduir el concepte matemàtic d'aprenentatge del cervell. Amb les dades biològiques que sustenten aquesta hipòtesi i algunes modificacions es van establir els camps de la xarxa neuronal i processament paral·lel distribuït.

Amb el desenvolupament de la Mecànica quàntica a inicis del segle xx va introduir el concepte 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 d'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 a 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[modifica]

Revistes[modifica]

Plantilla:Unreferenced section

Conferències[modifica]

Vegeu també[modifica]

Notes[modifica]

  1. ↑ «SIGACT». [Consulta: 29 març 2009].
  2. ↑ «ToCT». [Consulta: 9 juny 2010].
  3. ↑ «Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing». [Consulta: 29 març 2009].
  4. ↑ 4,0 4,1 4,2 4,3 4,4 The 2007 Australian Ranking of ICT Conferences Arxivat 2009-10-02 a Wayback Machine.: tier A+.
  5. ↑ 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8 The 2007 Australian Ranking of ICT Conferences Arxivat 2009-10-02 a Wayback Machine.: tier A.

Bibliografia[modifica]

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Informàtica teòrica
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Informàtica_teòrica&oldid=33379715»