Loading AI tools
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.
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
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.
Algoritmos
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
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
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
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
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
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
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
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
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.
- Information and Computation
- Theory of Computing (Revista open access)
- Formal Aspects of Computing
- Journal of the ACM
- SIAM Journal on Computing (SICOMP)
- SIGACT News
- Theoretical Computer Science
- Theory of Computings Systems
- International Journal of Foundations of Computer Science
- Chicago Journal of Theoretical Computer Science (Revista open access)
- Foundations and Trends in Theoretical Computer Science
- Journal of Automata, Languages and Combinatorics
- Acta Informatica
- Fundamenta Informaticae
- ACM Transactions on Computation Theory
- ACM Transactions on Algorithms
- Information Processing Letters
- Annual ACM Symposium on Theory of Computing (STOC)[16]
- Annual IEEE Symposium on Foundations of Computer Science (FOCS)[16]
- ACM–SIAM Symposium on Discrete Algorithms (SODA)[16]
- Annual ACM Symposium on Computational Geometry (SoCG)[17]
- International Colloquium on Automata, Languages and Programming (ICALP)[17]
- Symposium on Theoretical Aspects of Computer Science (STACS)[17]
- European Symposium on Algorithms (ESA)[17]
- IEEE Symposium on Logic in Computer Science (LICS)[16]
- International Symposium on Algorithms and Computation (ISAAC)[17]
- Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)[17]
- Workshop on Randomization and Computation (RANDOM)[17]
- Computational Complexity Conference (CCC)[17]
- ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)[17]
- ACM Symposium on Principles of Distributed Computing (PODC)[16]
- 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.
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.
