A ciencia computacional teórica, en inglés: Theoretical computer science (TCS), é unha división das ciencias da computación e das matemáticas que se enfoca en aspectos máis abstractos ou matemáticos da computación.
Estas divisións e subconxuntos inclúen análises de algoritmos e semántica formal de linguaxes de programación. Tecnicamente, ademais destes dous, hai moitas outras divisións e subconxuntos. Cada unha das múltiples partes teñen os seus propios líderes persoais individuais (de popularidade) e hai moitas asociacións e grupos sociais profesionais e publicacións distinguidos.
Non é fácil circunscribir as áreas desta teoría; o Special Interest Group on Algorithms and Computation Theory (SIGACT) da ACM describe a súa misión como a promoción das ciencias da computación teórica e indica:[1]
- O campo das ciencias da computación teórica cobre unha ampla variedade de campos, incluíndo algoritmos, estruturas de datos, teoría da complexidade computacional, computación distribuída e paralela, VLSI, aprendizaxe de máquina, bioloxía computacional, xeometría computacional, teoría da información, criptografía, computación cuántica, teoría computacional de números e álxebra, semántica de programa e verificación, teoría de autómatas e o estudo da aleatoriedade. A miúdo o traballo neste campo distínguese pola súa énfase na técnica e o rigor matemáticos.
A esta listaxe, a revista Transactions on Computation Theory da ACM agrega a teoría da codificación, a teoría da aprendizaxe computacional e aspectos de áreas tales como bases de datos, recuperación de información, modelos económicos e redes.[2] A pesar desta amplitude, a "xente da teoría" en ciencias da computación identifícase a si mesma como diferente da "xente das aplicacións". Algúns caracterízanse como que fan a "ciencia subxacente máis fundamental no campo da computación".[3] Outra "xente da teoría aplicada" suxire que é imposible separar teoría e aplicación. Isto significa, que a chamada "xente da teoría" usa regularmente ciencia experimental feita en áreas menos teóricas como a investigación de sistemas de software. Isto tamén significa, que existe unha cooperación máis que unha competencia mutuamente excluínte entre a teoría e aplicación.
 |
 |
 |
P = NP ? | |
| Lóxica matemática | Teoría de autómatas | Teoría de números | Teoría de grafos | Teoría da complexidade computacional |
| GNITIRW-TERCES |  |
 |
 | |
| Criptografía | Teoría de tipos | Teoría de categorías | Xeometría computacional | Teoría de computación cuántica |
Mentres que os algoritmos formais existiron durante milenios (en computación aínda se emprega o algoritmo de Euclides para determinar o máximo común divisor de dous números), non foi até 1936 que Alan Turing, Alonzo Church e Stephen Kleene formalizaron a definición dun algoritmo en termos de computación. Os sistemas binario e lóxico das matemáticas existiran antes de 1703, cando Gottfried Leibniz formalizou a lóxica cos valores binarios para verdadeiro e falso. Mentres que a inferencia lóxica e as demostracións matemáticas existiran na antigüidade, en 1931 Kurt Gödel demostrou co seu teorema de incompletude que había limitacións fundamentais sobre que sentenzas, mesmo verdadeiras, poderían probarse.
Estes desenvolvementos levaron aos estudos modernos da lóxica e da computabilidade, e de feito ao campo das ciencias da computación teórica como un todo. A teoría da información foi incorporada ao campo cunha teoría matemática de 1948 sobre a comunicación por Claude Shannon. Na mesma década, Donald Hebb introduciu un modelo matemático de aprendizaxe no cerebro. Coa montaxe de datos biolóxicos soportando esta hipótese con algunhas modificacións, establecéronse os campos de redes neuronais e procesamento distribuído paralelo.
Co desenvolvemento da mecánica cuántica ao principio do século XX chegou o concepto de que as operacións matemáticas podían ser realizadas nunha función de onda dunha partícula. Noutras palabras, poderíanse calcular funcións en varios estados simultaneamente. Isto levou ao concepto dun computador cuántico na segunda metade do século XX que foi impulsado na década de 1990 cando Peter Shor demostrou que eses métodos poderían empregarse para factorizar números grandes en tempo polinómico, o que, se se aplican, farían máis modernos os sistemas de criptografía de clave pública.
A investigación nas ciencias da computación teórica moderna baséase nestes desenvolvementos básicos, pero inclúe moitos outros problemas matemáticos e interdisciplinarios que foron expostos.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
