Ver la fonte de 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'[[Association for Computing Machinery|ACM]] describe a la so misión como la promoción de les ciencies de la computación teórica y nota:<ref>{{cita web | títulu = SIGACT | url = http://sigact.acm.org | fechaaccesu = 29 de marzu de 2009}}</ref>

: El campu de les ciencies de la computación teórica ye interpretáu llargamente pa incluyir [[algoritmu|algoritmos]], [[estructura de dato|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 [[computación simbólica|álxebra]], [[semántica de programa]] y [[métodos formales|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ático|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 [[base de datos|bases de datos]], [[recuperación d'información]], modelos económicos y [[rede de computadores|redes]].<ref>{{cita web| títulu = ToCT| url = http://toct.acm.org/journal.html| fechaaccesu = 9 de xunu de 2010| urlarchivu = https://web.archive.org/web/20101104004846/http://toct.acm.org/journal.html| fechaarchivu = 4 de payares de 2010}}</ref> 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".<ref>{{cita web | títulu = Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing | url = http://www.research.att.com/%7Edsj/nsflist.html#Intro | fechaaccesu = 29 de marzu de 2009 | urlarchivu = https://web.archive.org/web/20090222050646/http://www.research.att.com/~dsj/nsflist.html#Intro | fechaarchivu = 22 de febreru de 2009 }}</ref> 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.

{| style="border:1px solid #ddd; text-align:center; margin: 0 auto;" cellspacing="15"
| <math> P \rightarrow Q \,</math>
| [[Ficheru:DFAexample.svg|96px]]
| [[Ficheru:Elliptic curve simple.png|96px]]
| [[Ficheru:6n-graf.svg|96px]]
|-
| [[Lóxica matemática]]
| [[Teoría d'autómates]]
| [[Teoría de númberos]]
| [[Teoría de grafos]]
|-
| <math>\Gamma\vdash x : Int</math>
| [[Ficheru:Commutative diagram for morphism.svg|96px]]
| [[Ficheru:SimplexRangeSearching.png|96px]]
| [[Ficheru:Blochsphere.svg|96px]]
|-
| [[Teoría de tipos]]
| [[Teoría de categoríes]]
| [[Xeometría computacional]]
| [[Computación cuántica|Teoría de computación cuántica]]
|}

=== Historia ===

{{AP|Historia de les ciencies de la computación}}

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 [[sistema binariu|binariu]] y [[sistema lóxicu|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'[[Teoría hebbiana|aprendizaxe]] nel celebru. Con montaxe de datos biolóxicos soportando esta hipótesis con dellos cambeos, fueron establecíos los campos de [[rede neuronal|redes neuronales]] y [[Computación distribuyida|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 ==

* [[European Association for Theoretical Computer Science]]
* [[SIGACT]]

== Revistes y boletinos ==

* ''[[Information and Computation]]''
* ''[[Theory of Computing (revista)|Theory of Computing]]'' (Revista [[Open access (publicación)|open access]])
* ''[[Formal Aspects of Computing]]''
* ''[[Journal of the ACM]]''
* ''[[SIAM Journal on Computing]]'' (SICOMP)
* ''[[SIGACT News]]''
* ''[[Theoretical Computer Science (revista)|Theoretical Computer Science]]''
* ''[[Theory of Computings Systems]]''
* ''[[International Journal of Foundations of Computer Science]]''
* ''[[Chicago Journal of Theoretical Computer Science]]'' (Revista [[Open access (publicación)|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)<ref name="core-a-plus">The [https://web.archive.org/web/20091002002344/http://www.core.edu.au/rankings/Conference%20Ranking%20Main.html 2007 Australian Ranking of ICT Conferences]: tier A+.</ref>
* Annual IEEE [[Symposium on Foundations of Computer Science]] (FOCS)<ref name="core-a-plus"/>
* ACM–SIAM [[Symposium on Discrete Algorithms]] (SODA)<ref name="core-a-plus"/>
* Annual ACM [[Symposium on Computational Geometry]] (SoCG)<ref name="core-a">The [https://web.archive.org/web/20091002002344/http://www.core.edu.au/rankings/Conference%20Ranking%20Main.html 2007 Australian Ranking of ICT Conferences]: tier A.</ref>
* [[International Colloquium on Automata, Languages and Programming]] (ICALP)<ref name="core-a"/>
* [[Symposium on Theoretical Aspects of Computer Science]] (STACS)<ref name="core-a"/>
* [[European Symposium on Algorithms]] (ESA)<ref name="core-a"/>
* IEEE [[Symposium on Logic in Computer Science]] (LICS)<ref name="core-a-plus"/>
* [[International Symposium on Algorithms and Computation]] (ISAAC)<ref name="core-a"/>
* [[Workshop on Approximation Algorithms for Combinatorial Optimization Problems]] (APPROX)<ref name="core-a"/>
* [[Workshop on Randomization and Computation]] (RANDOM)<ref name="core-a"/>
* [[Computational Complexity Conference]] (CCC)<ref name="core-a"/>
* ACM [[Symposium on Parallelism in Algorithms and Architectures]] (SPAA)<ref name="core-a"/>
* ACM [[Symposium on Principles of Distributed Computing]] (PODC)<ref name="core-a-plus"/>

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

{{llistaref}}

== Ver tamién ==

* [[Ciencia formal]]
* [[Problemes ensin resolver en ciencies de la computación]]

== Enllaces esternos ==

* [http://www.sigact.org/webpages.php SIGACT directory of additional theory links] {{Webarchive|url=https://web.archive.org/web/20170715101741/http://www.sigact.org/webpages.php |date=2017-07-15 }}
* [http://theorymatters.org/ Theory Matters Wiki] {{Webarchive|url=https://web.archive.org/web/20170619133754/http://theorymatters.org/ |date=2017-06-19 }} Theoretical Computer Science (TCS) Advocacy Wiki 
* {{enllace rotu|1=[news://comp.theory Usenet comp.theory] |2=news://comp.theory/ |bot=InternetArchiveBot }}
* [http://www.confsearch.org/confsearch/cares/pages/topic.jsp?topic=Theory&sortMode=1&graphicView=1 List of academic conferences in the area of theoretical computer science] at [http://www.confsearch.org confsearch]
* [http://cstheory.stackexchange.com/ Theoretical Computer Science - StackExchange], a Question and Answer site for researchers in theoretical computer science
* [http://www.csanimated.com/browse.php Computer Science Animated]
* http://theory.csail.mit.edu/ @ [[Massachusetts Institute of Technology]]


{{Tradubot|Ciencia computacional teórica}}

{{control d'autoridaes}}
[[Categoría:Informática teórica]]