Informàtica teòrica

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

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]

P → Q {\displaystyle P\rightarrow Q\,} Teoria d'autòmats Teoria de nombres Teoria de grafs
Lògica Matemàtica Teoria d'Autòmats Teoria de Nombres Teoria de Grafs
Γ ⊢ x : I n t {\displaystyle \Gamma \vdash x:Int} Teoria de Categories Geometria Computacional Computació Quàntica
Teoria de Tipus Teoria de Categories Geometria Computacional Computació Quàntica

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.


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

  • European Association for Theoretical Computer Science
  • SIGACT

Revistes

Plantilla:Unreferenced section

  • Information and Computation
  • Theory of Computing (open access journal)
  • Formal Aspects of Computing
  • Journal of the ACM
  • SIAM Journal on Computing (SICOMP)
  • SIGACT News
  • Theoretical Computer Science
  • Theory of Computings Systems
  • International Journal of Foundations of Computer Science
  • Chicago Journal of Theoretical Computer Science (open access journal)
  • Foundations and Trends in Theoretical Computer Science
  • Journal of Automata, Languages and Combinatorics
  • Acta Informatica
  • Fundamenta Informaticae
  • ACM Transactions on Computation Theory
  • ACM Transactions on Algorithms
  • Information Processing Letters

Conferències

  • Annual ACM Symposium on Theory of Computing (STOC)[4]
  • Annual IEEE Symposium on Foundations of Computer Science (FOCS)[4]
  • ACM–SIAM Symposium on Discrete Algorithms (SODA)[4]
  • Annual ACM Symposium on Computational Geometry (SoCG)[5]
  • International Colloquium on Automata, Languages and Programming (ICALP)[5]
  • Symposium on Theoretical Aspects of Computer Science (STACS)[5]
  • European Symposium on Algorithms (ESA)[5]
  • IEEE Symposium on Logic in Computer Science (LICS)[4]
  • International Symposium on Algorithms and Computation (ISAAC)[5]
  • Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)[5]
  • Workshop on Randomization and Computation (RANDOM)[5]
  • Computational Complexity Conference (CCC)[5]
  • ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)[5]
  • ACM Symposium on Principles of Distributed Computing (PODC)[4]

Vegeu també

Notes

  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

  • Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1. Covers theory of computation, but also program semantics and quantification theory. Aimed at graduate students.

Enllaços externs

  • Usenet comp.theory
  • List of academic conferences in the area of theoretical computer science at confsearch
  • Theoretical Computer Science - StackExchange, a Question and Answer site for researchers in theoretical computer science
  • Computer Science Animated
  • http://theory.csail.mit.edu/ @ Massachusetts Institute of Technology