Ciencia computacional teórica

Les ciencies de la computación teórica (TCS) ye una división o un subconxuntu de les ciencies de la computación y les matemátiques que s'enfoca n'aspeutos más astractos o matemáticos de la computación.

Estes divisiones y subconxuntos inclúin analises d'algoritmos y semántica formal de llinguaxes de programación. Téunicamente, amás d'estos dos, hai cientos de divisiones y subconxuntos. Caúna de les múltiples partes tienen los sos propios líderes personales individuales (de popularidá) y hai munches asociaciones y grupos sociales profesionales y publicaciones de distinción.

Ámbitu

Nun ye fácil circunscribir les árees de teoría precisamente'l Special Interest Group on Algorithms and Computation Theory (SIGACT) de l'ACM describe a la so misión como la promoción de les ciencies de la computación teórica y nota:^[1]

El campu de les ciencies de la computación teórica ye interpretáu llargamente pa incluyir algoritmos, estructures de datos, teoría de la complexidá computacional, computación distribuyida, computación paralela, VLSI, aprendizaxe de máquina, bioloxía computacional, xeometría computacional, teoría de la información, criptografía, computación cuántica, teoría computacional de númberos y álxebra, semántica de programa y verificación, teoría d'autómates y l'estudiu de l'aleatoriedad. De cutiu el trabayu nesti campu ye estremáu pola so énfasis na téunica y rigor matemáticos.

A esta llista, revista Transactions on Computation Theory de la ACM amiesta teoría de la codificación, teoría del aprendizaxe computacional y aspeutos de ciencies de la computación teórica d'árees tales como bases de datos, recuperación d'información, modelos económicos y redes.^[2] A pesar d'esta amplitú, la "xente de teoría" en ciencies de la computación identificar a sigo mesma como distinta de la "xente d'aplicaciones". Dalgunos caracterícense como faciendo la "(más fundamental) 'ciencia' subxacente nel campu de la computación".^[3] Otra "xente de teoría aplicada" suxer que ye imposible dixebrar teoría y aplicación. Esto significa, que la llamada "xente de teoría" usa regularmente science esperimental fecha n'árees menos teóriques como investigación de sistema de software. Esto tamién significa, qu'esiste una cooperación más qu'una competencia mutuamente escluyente ente la teoría y aplicación.

$P\rightarrow Q\,$
Lóxica matemática	Teoría d'autómates	Teoría de númberos	Teoría de grafos
$\Gamma \vdash x:Int$
Teoría de tipos	Teoría de categoríes	Xeometría computacional	Teoría de computación cuántica

Historia

Ente que los algoritmos formales esistieron mientres milenios (en computación inda s'usa l'algoritmu d'Euclides pa determinar el máximu común divisor de dos númberos), nun foi sinón hasta 1936 que Alan Turing, Alonzo Church y Stephen Kleene formalizaron la definición d'un algoritmu en términos de computación. Ente que los sistemes binariu y lóxicu de les matemátiques esistieren antes de 1703, cuando Gottfried Leibniz formalizó la lóxica colos valores binarios pa verdaderu y falsu. Ente que la inferencia lóxica y prueba matemática esistieren na antigüedá, en 1931 Kurt Gödel demostró cola so teorema de incompletitud qu'hubo llimitaciones fundamentales sobre qué sentencies, inclusive si verdaderes, podríen probase.

Estos desarrollos llevaron a los estudios modernos de la lóxica y computabilidad, y de fechu al campu de les ciencies de la computación teórica como un tou. La teoría de la información foi amestada al campu con una teoría matemática de 1948 sobre la comunicación por Claude Shannon. Na mesma década, Donald Hebb introdució un modelu matemáticu d'aprendizaxe nel celebru. Con montaxe de datos biolóxicos soportando esta hipótesis con dellos cambeos, fueron establecíos los campos de redes neuronales y procesamientu distribuyíu paralelu.

Col desenvolvimientu de la mecánica cuántica de primeres del sieglu XX llegó'l conceutu qu'operaciones matemátiques pudieren ser realizaes nuna función d'onda d'una partícula. N'otres pallabres, podríen calculase funciones en dellos Estaos simultáneamente. Esto llevó al conceutu d'un ordenador cuánticu na segunda metá del sieglu XX que desapegó na década de 1990 cuando Peter Shor demostró que tales métodos podríen utilizase pa factorizar númberos grandes en tiempu polinómico, lo que, si aplíquense, fadría más modernos sistemes de criptografía de clave pública en devanéu insegura.

Investigación de ciencies de la computación teórica moderna basar nestos desarrollos básicos, pero inclúi munchos otros problemes matemáticos ya interdisciplinarios que fueron plantegaos.

Organizaciones

Revistes y boletinos

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 Informática
Fundamenta Informaticae
ACM Transactions on Computation Theory
ACM Transactions on

Algorithms * Information Processing Letters

Conferencies

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]

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

Referencies

↑ «SIGACT». Consultáu'l 29 de marzu de 2009.
↑ «ToCT». Archiváu dende l'orixinal, el 4 de payares de 2010. Consultáu'l 9 de xunu de 2010.
↑ «Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing». Archiváu dende l'orixinal, el 22 de febreru de 2009. Consultáu'l 29 de marzu de 2009.
↑ ^4,0 ^4,1 ^4,2 ^4,3 ^4,4 The 2007 Australian Ranking of ICT Conferences: tier A+.
↑ ^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: tier A.

Ver tamién

Enllaces esternos

SIGACT directory of additional theory links Archiváu 2017-07-15 en Wayback Machine
Theory Matters Wiki Archiváu 2017-06-19 en Wayback Machine Theoretical Computer Science (TCS) Advocacy Wiki
Usenet comp.theory (enllaz rotu disponible n'Internet Archive; ver l'historial y la última versión).
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

[1] «SIGACT». Consultáu'l 29 de marzu de 2009.

[2] «ToCT». Archiváu dende l'orixinal, el 4 de payares de 2010. Consultáu'l 9 de xunu de 2010.

[3] «Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing». Archiváu dende l'orixinal, el 22 de febreru de 2009. Consultáu'l 29 de marzu de 2009.

[core-a-plus-4] 4,0 ^4,1 ^4,2 ^4,3 ^4,4 The 2007 Australian Ranking of ICT Conferences: tier A+.

[core-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: tier A.

[1]

[2]

[3]

[4]

[5]