Ciencia computacional teórica

De Wikipedia, la enciclopedia libre

Las ciencias de la computación teórica o ciencias de la informática teórica (TCS) es una división o un subconjunto de las ciencias de la computación y las matemáticas que se enfoca en aspectos más abstractos o matemáticos de la computación.

Estas divisiones y subconjuntos incluyen análisis de algoritmos y semántica formal de lenguajes de programación. Técnicamente, además de estos dos, hay cientos de divisiones y subconjuntos. Cada una de las múltiples partes tienen sus propios líderes personales individuales (de popularidad) y hay muchas asociaciones y grupos sociales profesionales y publicaciones de distinción.

Ámbito[editar]

No es fácil circunscribir las áreas de teoría precisamente el Special Interest Group on Algorithms and Computation Theory (SIGACT) de la ACM describe a su misión como la promoción de las ciencias de la computación teórica y nota:[1]​

El campo de las ciencias de la computación teórica es interpretado ampliamente para incluir algoritmos, estructuras de datos, teoría de la complejidad computacional, computación distribuida, computación paralela, VLSI, aprendizaje de máquina, biología computacional, geometría computacional, teoría de la información, criptografía, computación cuántica, teoría computacional de números y álgebra, semántica de programa y verificación, teoría de autómatas y el estudio de la aleatoriedad. A menudo el trabajo en este campo es distinguido por su énfasis en la técnica y rigor matemáticos.

A esta lista, revista Transactions on Computation Theory de la ACM agrega teoría de la codificación, teoría del aprendizaje computacional y aspectos de ciencias de la computación teórica de áreas tales como bases de datos, recuperación de información, modelos económicos y redes.[2]​ A pesar de esta amplitud, la "gente de teoría" en ciencias de la computación se identifica a sí misma como diferente de la "gente de aplicaciones". Algunos se caracterizan como haciendo la "(más fundamental) 'ciencia' subyacente en el campo de la computación".[3]​ Otra "gente de teoría aplicada" sugiere que es imposible separar teoría y aplicación. Esto significa, que la llamada "gente de teoría" usa regularmente science experimental hecha en áreas menos teóricas como investigación de sistema de software. Esto también significa, que existe una cooperación más que una competencia mutuamente excluyente entre la teoría y aplicación.

Lógica matemática Teoría de autómatas Teoría de números Teoría de grafos
Teoría de tipos Teoría de categorías Geometría computacional Teoría de computación cuántica

Historia[editar]

Artículo principal: Historia de las ciencias de la computación

Mientras que los algoritmos formales han existido durante milenios (en computación todavía se usa el algoritmo de Euclides para determinar el máximo común divisor de dos números), no fue sino hasta 1936 que Alan Turing, Alonzo Church y Stephen Kleene formalizaron la definición de un algoritmo en términos de computación. Mientras que los sistemas binario y lógico de las matemáticas habían existido antes de 1703, cuando Gottfried Leibniz formalizó la lógica con los valores binarios para verdadero y falso. Mientras que la inferencia lógica y prueba matemática habían existido en la antigüedad, en 1931 Kurt Gödel demostró con su teorema de incompletitud que hubo limitaciones fundamentales sobre qué sentencias, incluso si verdaderas, podrían probarse.

Estos desarrollos han llevado a los estudios modernos de la lógica y computabilidad, y de hecho al campo de las ciencias de la computación teórica como un todo. La teoría de la información fue agregada al campo con una teoría matemática de 1948 sobre la comunicación por Claude Shannon. En la misma década, Donald Hebb introdujo un modelo matemático de aprendizaje en el cerebro. Con montaje de datos biológicos soportando esta hipótesis con algunas modificaciones, fueron establecidos los campos de redes neuronales y procesamiento distribuido paralelo.

Con el desarrollo de la mecánica cuántica al principio del siglo XX llegó el concepto que operaciones matemáticas pudieran ser realizadas en una función de onda de una partícula. En otras palabras, se podrían calcular funciones en varios Estados simultáneamente. Esto llevó al concepto de un ordenador cuántico en la segunda mitad del siglo XX que despegó en la década de 1990 cuando Peter Shor demostró que tales métodos podrían utilizarse para factorizar números grandes en tiempo polinómico, lo que, si se aplican, haría más modernos sistemas de criptografía de clave pública inútilmente insegura.

Investigación de ciencias de la computación teórica moderna se basa en estos desarrollos básicos, pero incluye muchos otros problemas matemáticos e interdisciplinarios que han sido planteados.

Temas[editar]

Algoritmos[editar]

Artículo principal: Algoritmo

Un algoritmo es un procedimiento paso a paso para realizar cálculos. Los algoritmos se utilizan para cálculo, procesamiento de datos y razonamiento automatizado.

Un algoritmo es un método eficaz expresado como una lista finita[4]​ de instrucciones bien definidas[5]​ para calcular una función.[6]​ Partiendo de un estado inicial y una entrada inicial (quizás vacía),[7]​ las instrucciones describen un cálculo que, cuando se ejecuta, procede a través de un finito[8]​ número de estados sucesivos bien definidos, produciendo eventualmente una "salida"[9]​ y terminando en un estado final. La transición de un estado al siguiente no es necesariamente determinista; algunos algoritmos, conocidos como algoritmos aleatorios, incorporan entradas aleatorias.[10]​

Teoría autómata[editar]

Artículo principal: Teoría de autómatas

Teoría de autómatas es el estudio de máquina abstracta y autómata, así como de los problemas computacionales que pueden resolverse usándolos. Es una teoría de la informática teórica, dentro de la matemática discreta (una sección de las matemáticas y también de la informática). Autómata viene de la palabra griega αὐτόματα que significa "que actúa por sí mismo".

La Teoría de Autómatas es el estudio de máquinas virtuales autooperativas para ayudar en la comprensión lógica del proceso de entrada y salida, sin o con etapa(s) intermedia(s) de computación (o cualquier función/proceso).

Teoría de la codificación[editar]

Artículo principal: Teoría de la codificación

Teoría de la codificación es el estudio de las propiedades de los códigos y su adecuación a una aplicación específica. Los códigos se utilizan para compresión de datos, criptografía, corrección de errores y, más recientemente, también para codificación de redes. Los códigos se estudian en diversas disciplinas científicas, como la teoría de la información, la ingeniería eléctrica, las matemáticas y la informática, con el fin de diseñar métodos de transmisión de datos eficientes y fiables. Esto suele implicar la eliminación de redundancias y la corrección (o detección) de errores en los datos transmitidos.

Biología computacional[editar]

Artículo principal: Biología computacional

Biología computacional implica el desarrollo y la aplicación de métodos teóricos y de análisis de datos, modelado matemático y técnicas de simulación computacional al estudio de sistemas biológicos, conductuales y sociales.[11]​ El campo está ampliamente definido e incluye fundamentos de informática, matemáticas aplicadas, animación, estadística, bioquímica, química, biofísica, biología molecular, genética, genómica, ecología, evolución, anatomía, neurociencia y visualización.[12]​

La biología computacional es diferente de la computación biológica, que es un subcampo de la informática y la ingeniería informática que utiliza la bioingeniería y la biología para construir ordenadores, pero es similar a la bioinformática, que es una ciencia interdisciplinar que utiliza ordenadores para almacenar y procesar datos biológicos.

Teoría de la complejidad computacional[editar]

Artículo principal: Teoría de la complejidad computacional

La Teoría de la complejidad computacional es una rama de la Teoría de la computación que se centra en clasificar los problemas computacionales según su dificultad inherente, y en relacionar esas clases entre sí. Se entiende por problema computacional una tarea que en principio es susceptible de ser resuelta por un ordenador, lo que equivale a afirmar que el problema puede resolverse mediante la aplicación mecánica de pasos matemáticos, como un algoritmo.

Se considera que un problema es intrínsecamente difícil si su solución requiere recursos significativos, sea cual sea el algoritmo utilizado. La teoría formaliza esta intuición, introduciendo modelos matemáticos de computación para estudiar estos problemas y cuantificando la cantidad de recursos necesarios para resolverlos, como el tiempo y el almacenamiento. También se utilizan otras medidas de complejidad, como la cantidad de comunicación (utilizada en complejidad de la comunicación), el número de compuertas en un circuito (utilizado en complejidad de los circuitos) y el número de procesadores (utilizado en computación paralela). Una de las funciones de la teoría de la complejidad computacional es determinar los límites prácticos de lo que los ordenadores pueden y no pueden hacer.

Geometría computacional[editar]

Artículo principal: Geometría computacional

Geometría computacional es una rama de la informática dedicada al estudio de algoritmos que pueden enunciarse en términos de geometría. Algunos problemas puramente geométricos surgen del estudio de algoritmos geométricos computacionales, y dichos problemas también se consideran parte de la geometría computacional.

El principal impulso para el desarrollo de la geometría computacional como disciplina fue el progreso en gráficos por ordenador y diseño y fabricación asistidos por ordenador (CAD/CAM), pero muchos problemas de geometría computacional son de naturaleza clásica, y pueden provenir de la visualización matemática.

Otras aplicaciones importantes de la geometría computacional son la robótica (planificación del movimiento y problemas de visibilidad), los sistemas de información geográfica (SIG) (localización y búsqueda geométrica, planificación de rutas), el diseño de circuitos integrados (diseño y verificación de la geometría de CI), la ingeniería asistida por ordenador (CAE) (generación de mallas), la visión por ordenador (reconstrucción 3D).

Teoría del aprendizaje computacional[editar]

Los resultados teóricos en el aprendizaje automático se refieren principalmente a un tipo de aprendizaje inductivo llamado aprendizaje supervisado. En el aprendizaje supervisado, un algoritmo recibe muestras etiquetadas de alguna manera útil. manera útil. Por ejemplo, las muestras pueden ser descripciones de setas, y las etiquetas pueden ser si las setas son comestibles o no. El algoritmo toma estas muestras previamente etiquetadas y las utiliza para inducir un clasificador. las utiliza para inducir un clasificador. Este clasificador es una función que asigna etiquetas a las muestras, incluidas las muestras que el algoritmo nunca ha visto previamente. El objetivo del algoritmo de aprendizaje supervisado es optimizar alguna medida de rendimiento, como minimizar el número de errores cometidos en muestras nuevas.

Teoría computacional de números[editar]

Artículo principal: Teoría de números computacional

Teoría de números computacional, también conocida como teoría algorítmica de números, es el estudio de algoritmos para realizar teoría de números cálculo. El problema más conocido en este campo es la factorización de enteros.

Criptografía[editar]

Artículo principal: Criptografía

Criptografía es la práctica y el estudio de técnicas para comunicación segura en presencia de terceros (llamados adversarios).[13]​ En términos más generales, se trata de construir y analizar protocolos que superen la influencia de los adversarios[14]​ y que están relacionados con diversos aspectos en seguridad de la información como la confidencialidad de los datos integridad de datos, autenticación y no repudio.[15]​ La criptografía moderna abarca las disciplinas de matemáticas, informática e ingeniería eléctrica. Las aplicaciones de la criptografía incluyen tarjetas ATM, contraseñas informáticas y comercio electrónico.

La criptografía moderna se basa en gran medida en la teoría matemática y la práctica de la informática; los algoritmos criptográficos se diseñan en torno a supuestos de dureza computacional, lo que hace que dichos algoritmos sean difíciles de romper en la práctica por cualquier adversario. En teoría, es posible romper un sistema de este tipo, pero es inviable hacerlo por cualquier medio práctico conocido. Los avances teóricos, como las mejoras en los algoritmos de factorización de enteros, y la aceleración de la tecnología informática obligan a adaptar continuamente estas soluciones. Existen esquemas de información teóricamente segura que no pueden romperse incluso con una potencia de cálculo ilimitada -un ejemplo es la libreta de un solo uso- pero estos esquemas son más difíciles de implementar que los mejores mecanismos teóricamente rompibles pero computacionalmente seguros.

Organizaciones[editar]

Revistas y boletines[editar]

Conferencias[editar]

Lectura adicional[editar]

Referencias[editar]

  1. ↑ «SIGACT». Consultado el 29 de marzo de 2009. 
  2. ↑ «ToCT». Archivado desde el original el 4 de noviembre de 2010. Consultado el 9 de junio de 2010. 
  3. ↑ «Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing». Archivado desde el original el 22 de febrero de 2009. Consultado el 29 de marzo de 2009. 
  4. ↑ "Cualquier algoritmo matemático clásico, por ejemplo, puede describirse en un número finito de palabras en inglés". Rogers, Hartley Jr. (1967). Teoría de las funciones recursivas y computabilidad efectiva. McGraw-Hill.  Página 2.
  5. ↑ Bien definidas con respecto al agente que ejecuta el algoritmo: "Hay un agente informático, normalmente humano, que puede reaccionar a las instrucciones y llevar a cabo los cálculos" (Rogers, 1967, p. 2).
  6. ↑ "un algoritmo es un procedimiento para calcular una función (con respecto a alguna notación elegida para números enteros) . .. esta limitación (a funciones numéricas) resulta en ninguna pérdida de generalidad",(Rogers, 1967, p. 1).
  7. ↑ "Un algoritmo tiene cero o más entradas, es decir, cantidades que se le dan inicialmente antes de que comience el algoritmo" (Knuth 1973:5).
  8. ↑ "Un procedimiento que tiene todas las características de un algoritmo excepto que posiblemente carece de finitud puede llamarse un 'método computacional'" (Knuth 1973:5).
  9. ↑ "Un algoritmo tiene una o más salidas, es decir, cantidades que tienen una relación especificada con las entradas" (Knuth 1973:5).
  10. ↑ Si un proceso con procesos interiores aleatorios (sin incluir la entrada) es o no un algoritmo es discutible. Rogers opina que: "un cómputo se lleva a cabo de una manera discreta paso a paso, sin el uso de métodos continuos o dispositivos analógicos . . se lleva a cabo de manera determinista, sin recurrir a métodos o dispositivos aleatorios, por ejemplo, dados" (Rogers, 1967, p. 2).
  11. ↑ Iniciativa de Ciencia y Tecnología de la Información Biomédica, ed. (17 de julio de 2000). «Definición de trabajo de los NIH sobre bioinformática y biología computacional». Archivado desde el original el 5 de septiembre de 2012. Consultado el 18 de agosto de 2012. 
  12. ↑ Centro de Biología Molecular Computacional. (ed.). «Acerca del CCMB». Consultado el 18 de agosto de 2012. 
  13. ↑ Rivest, Ronald L. (1990). «Criptología». En J. Van Leeuwen, ed. Handbook of Theoretical Computer Science 1. Elsevier. 
  14. ↑ Bellare, Mihir; Rogaway, Phillip (21 de septiembre de 2005). «Introducción». Introducción a la Criptografía Moderna. p. 10. 
  15. ↑ Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. (1997). Handbook of Applied Cryptography. ISBN 978-0-8493-8523-0. 
  16. ↑ a b c d e The 2007 Australian Ranking of ICT Conferences: tier A+.
  17. ↑ a b c d e f g h i The 2007 Australian Ranking of ICT Conferences: tier A.

Véase también[editar]

Enlaces externos[editar]

Obtenido de «https://es.wikipedia.org/w/index.php?title=Ciencia_computacional_teórica&oldid=157963800»