Informática teórica

La informática teórica es un subcampo de la informática y las matemáticas que se centra en los fundamentos abstractos y matemáticos de la computación .

Es difícil delimitar con precisión las áreas teóricas. El Grupo de Interés Especial sobre Algoritmos y Teoría de la Computación (SIGACT) de la ACM ofrece la siguiente descripción: ^[1]

TCS cubre una amplia variedad de temas, incluidos algoritmos , estructuras de datos , complejidad computacional , computación paralela y distribuida , computación probabilística , computación cuántica , teoría de autómatas , teoría de la información , criptografía , semántica y verificación de programas , teoría de juegos algorítmicos , aprendizaje automático , biología computacional , economía computacional , geometría computacional y teoría de números computacionales y álgebra . El trabajo en este campo a menudo se distingue por su énfasis en la técnica matemática y el rigor .

Si bien la inferencia lógica y la prueba matemática ya existían previamente, en 1931 Kurt Gödel demostró con su teorema de incompletitud que existen limitaciones fundamentales sobre qué afirmaciones pueden probarse o refutar.

La teoría de la información se incorporó a este campo con una teoría matemática de la comunicación de Claude Shannon en 1948. En la misma década, Donald Hebb introdujo un modelo matemático del aprendizaje en el cerebro. Con la acumulación de datos biológicos que respaldaban esta hipótesis con algunas modificaciones, se establecieron los campos de las redes neuronales y el procesamiento distribuido paralelo . En 1971, Stephen Cook y, trabajando de forma independiente , Leonid Levin , demostraron que existen problemas prácticamente relevantes que son NP-completos , un resultado histórico en la teoría de la complejidad computacional . ^[2]

La investigación teórica moderna en informática se basa en estos desarrollos básicos, pero incluye muchos otros problemas matemáticos e interdisciplinarios que se han planteado, como se muestra a continuación:

${\displaystyle P\rightarrow Q\,}$					¿P = NP  ?
Lógica matemática	Teoría de autómatas	Teoría de números	Teoría de grafos	Teoría de la computabilidad	Teoría de la complejidad computacional
GNITIRW-TERCES	${\displaystyle \Gamma \vdash x:{\text{Int}}}$
Criptografía	Teoría de tipos	Teoría de categorías	Geometría computacional	Optimización combinatoria	Teoría de la computación cuántica

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

Un algoritmo es un método eficaz expresado como una lista finita ^[3] de instrucciones bien definidas ^[4] para calcular una función . ^[5] A partir de un estado inicial y una entrada inicial (quizás vacía ), ^[6] las instrucciones describen un cálculo que, cuando se ejecuta , procede a través de un número finito ^[7] de estados sucesivos bien definidos, produciendo finalmente una "salida" ^[8] 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 una entrada aleatoria. ^[9]

La teoría de autómatas es el estudio de las máquinas abstractas y los autómatas , así como de los problemas computacionales que pueden resolverse mediante su uso. Es una teoría de la informática teórica, dentro del campo de las matemáticas discretas (una sección de las matemáticas y también de la informática ). Autómata proviene de la palabra griega αὐτόματα que significa "autoactuante".

La teoría de autómatas es el estudio de máquinas virtuales autónomas para ayudar en la comprensión lógica del proceso de entrada y salida, sin o con etapas intermedias de cálculo (o cualquier función /proceso).

La teoría de la codificación es el estudio de las propiedades de los códigos y su idoneidad para una aplicación específica. Los códigos se utilizan para la compresión de datos , la criptografía , la corrección de errores y, más recientemente, también para la codificación de redes . Los códigos son estudiados por 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 normalmente implica la eliminación de la redundancia y la corrección (o detección) de errores en los datos transmitidos.

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 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 .

Un problema se considera inherentemente 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 la complejidad de la comunicación ), el número de puertas en un circuito (utilizado en la complejidad del circuito ) y el número de procesadores (utilizado en la 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 las computadoras pueden y no pueden hacer.

La geometría computacional es una rama de la informática dedicada al estudio de algoritmos que pueden expresarse 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 los gráficos por computadora y el diseño y fabricación asistidos por computadora ( CAD / CAM ), pero muchos problemas en la 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 incluyen la robótica (planificación de movimiento y problemas de visibilidad), sistemas de información geográfica (SIG) (ubicación y búsqueda geométrica, planificación de rutas), diseño de circuitos integrados (diseño y verificación de geometría de CI), ingeniería asistida por computadora (generación de mallas) y visión artificial (reconstrucción 3D).

Los resultados teóricos del aprendizaje automático tratan principalmente de un tipo de aprendizaje inductivo llamado aprendizaje supervisado. En el aprendizaje supervisado, se dan muestras a un algoritmo que están etiquetadas de alguna manera útil. Por ejemplo, las muestras pueden ser descripciones de hongos y las etiquetas pueden indicar si los hongos son comestibles o no. El algoritmo toma estas muestras previamente etiquetadas y las usa 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 antes. El objetivo del algoritmo de aprendizaje supervisado es optimizar alguna medida de rendimiento, como minimizar la cantidad de errores cometidos en muestras nuevas.

La teoría de números computacionales , también conocida como teoría algorítmica de números , es el estudio de algoritmos para realizar cálculos numéricos teóricos . El problema más conocido en este campo es la factorización de números enteros .

La criptografía es la práctica y el estudio de técnicas para la comunicación segura en presencia de terceros (llamados adversarios ). ^[10] De manera más general, se trata de construir y analizar protocolos que superen la influencia de los adversarios ^[11] y que estén relacionados con varios aspectos de la seguridad de la información como la confidencialidad de los datos , la integridad de los datos , la autenticación y el no repudio . ^[12] La criptografía moderna cruza las disciplinas de las matemáticas , la informática y la ingeniería eléctrica . Las aplicaciones de la criptografía incluyen tarjetas ATM , contraseñas de computadora 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 ciencia informática; los algoritmos criptográficos están diseñados 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. Es teóricamente posible romper un sistema de este tipo, pero es inviable hacerlo por cualquier medio práctico conocido. Por lo tanto, estos esquemas se denominan computacionalmente seguros; los avances teóricos, por ejemplo, las mejoras en los algoritmos de factorización de números enteros y la tecnología informática más rápida requieren que estas soluciones se adapten continuamente. Existen esquemas teóricamente seguros de la información que se puede demostrar que no se pueden romper ni siquiera con un poder de cómputo ilimitado (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.

Una estructura de datos es una forma particular de organizar datos en una computadora para que puedan usarse de manera eficiente . ^{[13] [14]}

Existen distintos tipos de estructuras de datos que se adaptan a distintos tipos de aplicaciones y algunas están altamente especializadas para tareas específicas. Por ejemplo, las bases de datos utilizan índices de árbol B para pequeños porcentajes de recuperación de datos y los compiladores y las bases de datos utilizan tablas hash dinámicas como tablas de búsqueda.

Las estructuras de datos proporcionan un medio para gestionar grandes cantidades de datos de manera eficiente para usos tales como bases de datos de gran tamaño y servicios de indexación de Internet . Por lo general, las estructuras de datos eficientes son clave para diseñar algoritmos eficientes . Algunos métodos de diseño formal y lenguajes de programación enfatizan las estructuras de datos, en lugar de los algoritmos, como el factor organizador clave en el diseño de software. El almacenamiento y la recuperación se pueden realizar en datos almacenados tanto en la memoria principal como en la memoria secundaria .

La computación distribuida estudia los sistemas distribuidos. Un sistema distribuido es un sistema de software en el que los componentes ubicados en computadoras en red se comunican y coordinan sus acciones mediante el envío de mensajes . ^[15] Los componentes interactúan entre sí para lograr un objetivo común. Tres características significativas de los sistemas distribuidos son: concurrencia de componentes, falta de un reloj global y falla independiente de los componentes. ^[15] Los ejemplos de sistemas distribuidos varían desde sistemas basados ​​en SOA hasta juegos en línea multijugador masivos , aplicaciones peer to peer y redes blockchain como Bitcoin .

Un programa informático que se ejecuta en un sistema distribuido se denomina programa distribuido , y la programación distribuida es el proceso de escribir dichos programas. ^[16] Existen muchas alternativas para el mecanismo de paso de mensajes, incluidos conectores tipo RPC y colas de mensajes . Un objetivo y un desafío importante de los sistemas distribuidos es la transparencia de la ubicación .

La complejidad basada en información (IBC) estudia algoritmos óptimos y la complejidad computacional para problemas continuos. La IBC ha estudiado problemas continuos como la integración de trayectorias, ecuaciones diferenciales parciales, sistemas de ecuaciones diferenciales ordinarias, ecuaciones no lineales, ecuaciones integrales, puntos fijos e integración de muy alta dimensión.

Los métodos formales son un tipo particular de técnicas basadas en matemáticas para la especificación , desarrollo y verificación de sistemas de software y hardware . ^[17] El uso de métodos formales para el diseño de software y hardware está motivado por la expectativa de que, como en otras disciplinas de ingeniería, realizar un análisis matemático apropiado puede contribuir a la confiabilidad y robustez de un diseño. ^[18]

Los métodos formales se describen mejor como la aplicación de una variedad bastante amplia de fundamentos teóricos de la ciencia informática, en particular cálculos lógicos , lenguajes formales , teoría de autómatas y semántica de programas , pero también sistemas de tipos y tipos de datos algebraicos a problemas de especificación y verificación de software y hardware. ^[19]

La teoría de la información es una rama de las matemáticas aplicadas , la ingeniería eléctrica y la informática que implica la cuantificación de la información . La teoría de la información fue desarrollada por Claude E. Shannon para encontrar límites fundamentales en las operaciones de procesamiento de señales , como la compresión de datos y el almacenamiento y la comunicación confiable de datos. Desde su inicio, se ha ampliado para encontrar aplicaciones en muchas otras áreas, incluida la inferencia estadística , el procesamiento del lenguaje natural , la criptografía , la neurobiología ^[20], la evolución ^[21] y la función ^[22] de los códigos moleculares, la selección de modelos en estadística, ^[23] la física térmica, ^[24] la computación cuántica , la lingüística , la detección de plagio, ^[25] el reconocimiento de patrones , la detección de anomalías y otras formas de análisis de datos . ^[26]

Las aplicaciones de temas fundamentales de la teoría de la información incluyen la compresión de datos sin pérdida (por ejemplo, archivos ZIP ), la compresión de datos con pérdida (por ejemplo, MP3 y JPEG ) y la codificación de canales (por ejemplo, para la línea de abonado digital (DSL) ). El campo está en la intersección de las matemáticas , la estadística , la informática , la física , la neurobiología y la ingeniería eléctrica . Su impacto ha sido crucial para el éxito de las misiones Voyager al espacio profundo, la invención del disco compacto, la viabilidad de los teléfonos móviles, el desarrollo de Internet , el estudio de la lingüística y de la percepción humana, la comprensión de los agujeros negros y muchos otros campos. Los subcampos importantes de la teoría de la información son la codificación de fuentes , la codificación de canales , la teoría de la complejidad algorítmica , la teoría de la información algorítmica , la seguridad teórica de la información y las medidas de información.

El aprendizaje automático es una disciplina científica que se ocupa de la construcción y el estudio de algoritmos que pueden aprender de los datos. ^[27] Estos algoritmos funcionan construyendo un modelo basado en entradas ^{[28] : 2} y usándolo para hacer predicciones o tomar decisiones, en lugar de seguir solo instrucciones programadas explícitamente.

El aprendizaje automático puede considerarse un subcampo de la informática y la estadística . Tiene fuertes vínculos con la inteligencia artificial y la optimización , que aportan métodos, teorías y dominios de aplicación al campo. El aprendizaje automático se emplea en una variedad de tareas informáticas en las que el diseño y la programación de algoritmos explícitos basados ​​en reglas no es factible. Las aplicaciones de ejemplo incluyen el filtrado de spam , el reconocimiento óptico de caracteres (OCR), ^[29] los motores de búsqueda y la visión artificial . El aprendizaje automático a veces se confunde con la minería de datos , ^[30] aunque esta se centra más en el análisis exploratorio de datos. ^[31] El aprendizaje automático y el reconocimiento de patrones "pueden verse como dos facetas del mismo campo". ^{[28] : vii}

^[39]

La computación paralela es una forma de computación en la que se llevan a cabo muchos cálculos simultáneamente, ^[40] operando sobre el principio de que los grandes problemas a menudo se pueden dividir en otros más pequeños, que luego se resuelven "en paralelo" . Hay varias formas diferentes de computación paralela: a nivel de bits , a nivel de instrucciones , de datos y de tareas . El paralelismo se ha empleado durante muchos años, principalmente en la computación de alto rendimiento , pero el interés en él ha crecido últimamente debido a las restricciones físicas que impiden el escalado de frecuencia . ^[41] Como el consumo de energía (y en consecuencia la generación de calor) por parte de las computadoras se ha convertido en una preocupación en los últimos años, ^[42] la computación paralela se ha convertido en el paradigma dominante en la arquitectura informática , principalmente en forma de procesadores multinúcleo . ^[43]

Los programas de computación en paralelo son más difíciles de escribir que los secuenciales, ^[44] porque la concurrencia introduce varias clases nuevas de errores potenciales de software , de los cuales las condiciones de carrera son las más comunes. La comunicación y la sincronización entre las diferentes subtareas suelen ser algunos de los mayores obstáculos para obtener un buen rendimiento de los programas en paralelo.

La máxima aceleración posible de un solo programa como resultado de la paralelización se conoce como ley de Amdahl .

La teoría de los lenguajes de programación es una rama de la informática que se ocupa del diseño, la implementación, el análisis, la caracterización y la clasificación de los lenguajes de programación y sus características individuales . Se enmarca dentro de la disciplina de la informática teórica, tanto en función de las matemáticas , la ingeniería de software y la lingüística como en función de ellas. Es un área de investigación activa, con numerosas revistas académicas dedicadas a ello.

En la teoría de lenguajes de programación , la semántica es el campo que se ocupa del estudio matemático riguroso del significado de los lenguajes de programación . Lo hace evaluando el significado de cadenas sintácticamente legales definidas por un lenguaje de programación específico, mostrando el cálculo involucrado. En tal caso, si la evaluación fuera de cadenas sintácticamente ilegales, el resultado sería no computacional. La semántica describe los procesos que sigue una computadora cuando ejecuta un programa en ese lenguaje específico. Esto se puede mostrar describiendo la relación entre la entrada y la salida de un programa, o una explicación de cómo se ejecutará el programa en una determinada plataforma , creando así un modelo de computación .

Un ordenador cuántico es un sistema de cálculo que hace uso directo de fenómenos mecánico-cuánticos , como la superposición y el entrelazamiento , para realizar operaciones sobre datos . ^[45] Los ordenadores cuánticos son diferentes de los ordenadores digitales basados ​​en transistores . Mientras que los ordenadores digitales requieren que los datos se codifiquen en dígitos binarios ( bits ), cada uno de los cuales está siempre en uno de dos estados definidos (0 o 1), la computación cuántica utiliza qubits (bits cuánticos), que pueden estar en superposiciones de estados. Un modelo teórico es la máquina cuántica de Turing , también conocida como ordenador cuántico universal. Los ordenadores cuánticos comparten similitudes teóricas con los ordenadores no deterministas y probabilísticos ; un ejemplo es la capacidad de estar en más de un estado simultáneamente. El campo de la computación cuántica fue introducido por primera vez por Yuri Manin en 1980 ^[46] y Richard Feynman en 1982. ^{[47] [48]} Una computadora cuántica con espines como bits cuánticos también fue formulada para su uso como espacio-tiempo cuántico en 1968. ^[49]

Se han llevado a cabo experimentos en los que se ejecutaron operaciones computacionales cuánticas en un número muy pequeño de qubits. ^[50] La investigación práctica y teórica continúa, y muchos gobiernos nacionales y agencias de financiación militar apoyan la investigación de computación cuántica para desarrollar computadoras cuánticas para fines tanto civiles como de seguridad nacional, como el criptoanálisis . ^[51]

El álgebra computacional , también llamada computación simbólica o computación algebraica, es un área científica que se refiere al estudio y desarrollo de algoritmos y software para manipular expresiones matemáticas y otros objetos matemáticos . Aunque, propiamente hablando, el álgebra computacional debería ser un subcampo de la computación científica , generalmente se consideran campos distintos porque la computación científica suele basarse en el cálculo numérico con números aproximados de punto flotante , mientras que la computación simbólica enfatiza el cálculo exacto con expresiones que contienen variables que no tienen ningún valor dado y, por lo tanto, se manipulan como símbolos (de ahí el nombre de computación simbólica ).

Las aplicaciones de software que realizan cálculos simbólicos se denominan sistemas de álgebra computacional , haciendo alusión con el término sistema a la complejidad de las principales aplicaciones que incluyen, al menos, un método para representar datos matemáticos en una computadora, un lenguaje de programación de usuario (normalmente diferente del lenguaje utilizado para la implementación), un gestor de memoria dedicado, una interfaz de usuario para la entrada/salida de expresiones matemáticas, un gran conjunto de rutinas para realizar operaciones habituales, como simplificación de expresiones, diferenciación mediante la regla de la cadena , factorización de polinomios , integración indefinida , etc.

La integración a muy gran escala ( VLSI ) es el proceso de creación de un circuito integrado (CI) mediante la combinación de miles de transistores en un solo chip. La VLSI comenzó en la década de 1970, cuando se estaban desarrollando tecnologías complejas de semiconductores y comunicación . El microprocesador es un dispositivo VLSI. Antes de la introducción de la tecnología VLSI, la mayoría de los CI tenían un conjunto limitado de funciones que podían realizar. Un circuito electrónico puede constar de una CPU , ROM , RAM y otra lógica de unión . La VLSI permite a los fabricantes de CI agregar todos estos circuitos en un solo chip.

• Asociación Europea de Informática Teórica
• SIGNACT® es una empresa de consultoría de gestión de proyectos que se dedica a la investigación, desarrollo y desarrollo de productos de alta tecnología.
• Instituto Simons para la teoría de la computación

• Matemáticas discretas y ciencias de la computación teórica
• Información y computación
• Teoría de la computación ( revista de acceso abierto )
• Aspectos formales de la informática
• Revista de la ACM
• Revista SIAM sobre Computación (SICOMP)
• Noticias de SIGNACT
• Ciencias de la computación teórica
• Teoría de los sistemas informáticos
• TheoretiCS ( revista de acceso abierto )
• Revista internacional de fundamentos de la informática
• Revista de acceso abierto de Chicago Journal of Theoretical Computer Science
• Fundamentos y tendencias en informática teórica
• Revista de Autómatas, Lenguajes y Combinatoria
• Acta Informática
• Fundamentos de informática
• Transacciones ACM en la teoría de la computación
• Complejidad computacional
• Revista de complejidad
• Transacciones ACM sobre algoritmos
• Cartas de procesamiento de información
• Open Computer Science ( revista de acceso abierto )

• Simposio anual de la ACM sobre teoría de la computación (STOC) ^[52]
• Simposio anual del IEEE sobre fundamentos de la informática (FOCS) ^[52]
• Innovaciones en informática teórica (ITCS)
• Fundamentos matemáticos de la informática (MFCS) ^[53]
• Simposio Internacional de Ciencias de la Computación en Rusia (CSR) ^[54]
• Simposio ACM–SIAM sobre algoritmos discretos (SODA) ^[52]
• Simposio IEEE sobre lógica en informática (LICS) ^[52]
• Conferencia sobre complejidad computacional (CCC) ^[55]
• Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) ^[55]
• Simposio anual sobre geometría computacional (SoCG) ^[55]
• Simposio ACM sobre Principios de Computación Distribuida (PODC) ^[52]
• Simposio ACM sobre paralelismo en algoritmos y arquitecturas (SPAA) ^[55]
• Conferencia anual sobre teoría del aprendizaje (COLT) ^[55]
• Conferencia internacional sobre tendencias actuales en teoría y práctica de la informática (SOFSEM) ^[56]
• Simposio sobre Aspectos Teóricos de la Informática (STACS) ^[55]
• Simposio Europeo sobre Algoritmos (ESA) ^[55]
• Taller sobre algoritmos de aproximación para problemas de optimización combinatoria (APPROX) ^[55]
• Taller sobre aleatorización y computación (RANDOM) ^[55]
• Simposio Internacional sobre Algoritmos y Computación (ISAAC) ^[55]
• Simposio Internacional sobre Fundamentos de la Teoría de la Computación (FCT) ^[57]
• Taller internacional sobre conceptos de teoría de grafos en informática (GT)

• Ciencia formal
• Problemas sin resolver en informática
• Ley Sun-Ni

• Martin Davis , Ron Sigal, Elaine J. Weyuker , Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica , 2.ª ed., Academic Press, 1994, ISBN 0-12-206382-1 . Abarca la teoría de la computación , pero también la semántica de programas y la teoría de la cuantificación . Dirigido a estudiantes de posgrado. 

• Directorio SIGACT de enlaces teóricos adicionales (archivado el 15 de julio de 2017)
• Wiki de defensa de la teoría de la informática (TCS) Wiki de defensa de la teoría de la informática (TCS)
• Lista de congresos académicos en el área de informática teórica en confsearch
• Ciencias de la computación teóricas – StackExchange, un sitio de preguntas y respuestas para investigadores en ciencias de la computación teóricas
• Ciencia informática animada
• Teoría de la computación en el Instituto Tecnológico de Massachusetts