Ciencia computacional teórica

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Las ciencias de la computación teórica (TCS) es una división o un subconjunto de las ciencias de la computación y las matemáticas que se enfoca en aspectos más abstractos o matemáticos de la computación.

Estas divisiones y subconjuntos incluyen análisis de algoritmos y semántica formal de lenguajes de programación. Técnicamente, además de estos dos, hay cientos de divisiones y subconjuntos. Cada una de las múltiples partes tienen sus propios líderes personales individuales (de popularidad) y hay muchas asociaciones y grupos sociales profesionales y publicaciones de distinción.

Ámbito[editar]

No es fácil circunscribir las áreas de teoría precisamente el Special Interest Group on Algorithms and Computation Theory (SIGACT) de la ACM describe a su misión como la promoción de la ciencias de la computación teórica y nota:[1]

El campo de la ciencias de la computación teórica es interpretado ampliamente para incluir algoritmos, estructuras de datos, teoría de la complejidad computacional, computación distribuida, computación paralela, VLSI, aprendizaje de máquina, biología computacional, geometría computacional, teoría de la información, criptografía, computación cuántica, teoría computacional de números y álgebra, semántica de programa y verificación, teoría de autómatas y el estudio de la aleatoriedad. A menudo el trabajo en este campo es distinguido por su énfasis en la técnica y rigor matemáticos.

A esta lista, revista Transactions on Computation Theory de la ACM agrega teoría de la codificación, teoría del aprendizaje computacional y aspectos de ciencias de la computación teórica de áreas tales como bases de datos, recuperación de información, modelos económicos y redes.[2] A pesar de esta amplitud, la "gente de teoría" en ciencias de la computación se identifica a sí misma como diferente de la "gente de aplicaciones". Algunos se caracterizan como haciendo la "(más fundamental) 'ciencia' subyacente en el campo de la computación".[3] Otra "gente de teoría aplicada" sugiere que es imposible separar teoría y aplicación. Esto significa, que la llamada "gente de teoría" usa regularmente science experimental hecha en áreas menos teóricas como investigación de sistema de software. Esto también significa, que existe una cooperación más que una competencia mutuamente excluyente entre la teoría y aplicación.

 P \rightarrow Q \, DFAexample.svg Elliptic curve simple.png 6n-graf.svg
Lógica matemática Teoría de autómatas Teoría de números Teoría de grafos
\Gamma\vdash x : Int Commutative diagram for morphism.svg SimplexRangeSearching.png Blochsphere.svg
Teoría de tipos Teoría de categorías Geometría computacional Teoría de computación cuántica

Historia[editar]

Mientras que los algoritmos formales han existido durante milenios (en computación todavía se usa el algoritmo de Euclides para determinar el máximo común divisor de dos números), no fue sino hasta 1936 que Alan Turing, Alonzo Church y Stephen Kleene formalizaron la definición de un algoritmo en términos de computación. Mientras que los sistemas binario y lógico de las matemáticas habían existido antes de 1703, cuando Gottfried Leibniz formalizó la lógica con los valores binarios para verdadero y falso. Mientras que la inferencia lógica y prueba matemática habían existido en la antigüedad, en 1931 Kurt Gödel demostró con su teorema de incompletitud que hubieron limitaciones fundamentales sobre qué sentencias, incluso si verdaderas, podrían probarse.

Estos desarrollos han llevado a los estudios modernos de la lógica y computabilidad, y de hecho al campo de las ciencias de la computación teórica como un todo. La teoría de la información fue agregada al campo con una teoría matemática de 1948 sobre la comunicación por Claude Shannon. En la misma década, Donald Hebb introdujo un modelo matemático de aprendizaje en el cerebro. Con montaje de datos biológicos soportando esta hipótesis con algunas modificaciones, fueron establecidos los campos de [[red neuronal|redes neuronales] y procesamiento distribuido paralelo.

Con el desarrollo de la mecánica cuántica al principio del siglo XX llegó el concepto que operaciones matemáticas pudieran ser realizadas en una función de onda de una partícula. En otras palabras, se podrían calcular funciones en varios Estados simultáneamente. Esto llevó al concepto de un ordenador cuántico en la segunda mitad del siglo XX que despegó en la década de 1990 cuando Peter Shor demostró que tales métodos podrían utilizarse para factorizar números grandes en tiempo polinómico, lo que, si se aplican, haría más modernos sistemas de criptografía de clave pública inútilmente insegura.

Investigación de ciencias de la computación teórica moderna se basa en estos desarrollos básicos, pero incluye muchos otros problemas matemáticos e interdisciplinarios que han sido planteados.

Organizaciones[editar]

Revistas y boletines[editar]

Conferencias[editar]

Lectura adicional[editar]

Referencias[editar]

  1. «SIGACT». Consultado el 29-03-2009.
  2. «ToCT». Consultado el 09-06-2010.
  3. «Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing». Consultado el 29-03-2009.
  4. a b c d e The 2007 Australian Ranking of ICT Conferences: tier A+.
  5. a b c d e f g h i The 2007 Australian Ranking of ICT Conferences: tier A.

Véase también[editar]

Enlaces externos[editar]