Ciencia computacional teórica

Las ciencias de la computación teórica o ciencias de la informática 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

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 las ciencias de la computación teórica y nota:^[1]​

El campo de las 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.

${\displaystyle P\rightarrow Q\,}$
Lógica matemática	Teoría de autómatas	Teoría de números	Teoría de grafos
${\displaystyle \Gamma \vdash x:Int}$
Teoría de tipos	Teoría de categorías	Geometría computacional	Teoría de computación cuántica

Historia

Artículo principal: Historia de las ciencias de la computación

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 hubo 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 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

• European Association for Theoretical Computer Science
• SIGACT

Revistas y boletines

• Information and Computation
• Theory of Computing (Revista open access)
• 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 (Revista open access)
• 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

Conferencias

• 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]​

Lectura adicional

• 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.

Referencias

1. «SIGACT». Consultado el 29 de marzo de 2009. 
2. . Archivado desde el original el 4 de noviembre de 2010. Consultado el 9 de junio de 2010. 
3. . Archivado desde el original el 22 de febrero de 2009. Consultado el 29 de marzo de 2009. 
4. The : tier A+.
5. The : tier A.

Véase también

• Ciencia formal
• Problemas no resueltos en ciencias de la computación

Enlaces externos

• Theoretical Computer Science (TCS) Advocacy Wiki
• Usenet comp.theory (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
• 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

•   Datos: Q2878974
•   Multimedia: Theoretical computer science