Ciencia computacional teórica

A ciencia computacional teórica, en , é 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.
96x96px 117x117px 96x96px 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-TERCES96x96px 103x103px 96x96px  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.

 Notas 

 Véxase tamén 
 Bibliografía 
  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
 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 

Categoría:Matemáticas
Categoría:Informática