Ciencia computacional teórica

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.

Ámbito

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:

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. 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". 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\rightarrow Q\,$				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	$\Gamma \vdash x:{\text{Int}}$
Criptografía	Teoría de tipos	Teoría de categorías	Xeometría computacional	Teoría de computación cuántica

Historia

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.

Véxase tamén

Bibliografía

• Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, complexity, and languages: fundamentals of theoretical computer science (en inglés) (2.ª ed.). Academic Press. ISBN 0-12-206382-1.  Cobre a teoría da computación, mais tamén semática de programa e teoría da cuantificación.

Outros artigos

• Ciencias formais

Ligazóns externas

• SIGACT directory of additional theory links
• Theory Matters Wiki Theoretical Computer Science (TCS) Advocacy Wiki
• Usenet comp.theory^{[Ligazón morta permanente]}
• List of academic conferences in the area of theoretical computer science en confsearch
• Theoretical Computer Science - StackExchange, a Question and Answer site for researchers in theoretical computer science
• Computer Science Animated
• Teoría da computación no Instituto de Tecnoloxía de Massachusetts (en inglés)