Informática teórica

La informática teórica (TCS) es un subconjunto de la informática general y las matemáticas que se centra en los aspectos matemáticos de la informática, como la teoría de la computación, el cálculo lambda y la teoría de tipos.

Es difícil circunscribir las áreas teóricas con precisión. El Grupo de Interés Especial en Algoritmos y Teoría de la Computación (SIGACT) de la ACM proporciona la siguiente descripción:

TCS cubre una amplia variedad de temas incluyendo algoritmos, estructuras de datos, complejidad computacional, computación paralela y distribuida, computación probabilística, computación cuántica, teoría de automata, teoría de la información, criptografía, semántica del programa y verificación, teoría del juego algorítmico, 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 se distingue a menudo por su énfasis en la técnica matemática y el rigor.

Historia

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

La teoría de la información se agregó al campo con una teoría matemática de la comunicación de 1948 de Claude Shannon. En la misma década, Donald Hebb introdujo un modelo matemático de aprendizaje en el cerebro. Con la acumulación de datos biológicos que respaldan esta hipótesis con algunas modificaciones, se establecieron los campos de las redes neuronales y el procesamiento distribuido en 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.

Con el desarrollo de la mecánica cuántica a principios del siglo XX surgió el concepto de que las operaciones matemáticas se podían realizar en una función de onda de una partícula completa. En otras palabras, uno podría calcular funciones en múltiples estados simultáneamente. Esto condujo al concepto de una computadora cuántica 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 usarse para factorizar grandes números en tiempo polinomial, lo que, si se implementa, haría que algunos modernos algoritmos de criptografía de clave pública como RSA inseguros.

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:

P→ → Q{displaystyle Prightarrow Q,}					P = NP?
Lógica matemática	Teoría de Automata	Teoría del número	Teoría del Gráfico	Teoría de computación	Teoría de complejidad computacional
GNITIRW-TERCES	.. ⊢ ⊢ x:Int{displaystyle "Gamma"
Cryptography	Tipo teoría	Teoría de la categoría	Geometría computacional	Optimización combinada	Teoría de cálculo cuántica

Temas

Algoritmos

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

Un algoritmo es un método efectivo expresado como una lista finita de instrucciones bien definidas para calcular una función. Comenzando desde un estado inicial y una entrada inicial (quizás vacía), las instrucciones describen un cálculo que, cuando se ejecuta, avanza a través de un número finito de estados sucesivos bien definidos, y eventualmente produce "salida" y terminando en un estado final final. La transición de un estado al siguiente no es necesariamente determinista; algunos algoritmos, conocidos como algoritmos aleatorios, incorporan entradas aleatorias.

Teoría de autómatas

La teoría de los autómatas es el estudio de las máquinas abstractas y los autómatas, así como los problemas computacionales que se pueden resolver con ellos. Es una teoría en informática teórica, bajo matemáticas discretas (una sección de matemáticas y también de informática). Automata proviene de la palabra griega αὐτόματα que significa "autoactuación".

La teoría de los 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 etapa(s) intermedia(s) de computación (o cualquier función/proceso).

Teoría de la codificación

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 confiables. Esto normalmente implica la eliminación de la redundancia y la corrección (o detección) de errores en los datos transmitidos.

Biología computacional

La biología computacional implica el desarrollo y la aplicación de métodos teóricos y analíticos de datos, modelos matemáticos y técnicas de simulación computacional para el estudio de sistemas biológicos, conductuales y sociales. El campo está ampliamente definido e incluye fundamentos en 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.

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 usa la bioingeniería y la biología para construir computadoras, pero es similar a la bioinformática, que es una ciencia interdisciplinaria que usa computadoras 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 una computadora, lo que equivale a afirmar que el problema puede ser resuelto 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, independientemente del algoritmo utilizado. La teoría formaliza esta intuición al introducir modelos matemáticos de computación para estudiar estos problemas y cuantificar 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), la cantidad de puertas en un circuito (utilizada en la complejidad del circuito) y la cantidad de procesadores (utilizada en la computación paralela). Uno de los roles 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.

Geometría computacional

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 los algoritmos geométricos computacionales y tales 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 la 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 IC), ingeniería asistida por computadora (CAE) (generación de malla), visión artificial (reconstrucción 3D).

Teoría del aprendizaje computacional

Los resultados teóricos en el aprendizaje automático se relacionan principalmente con un tipo de aprendizaje inductivo llamado aprendizaje supervisado. En el aprendizaje supervisado, un algoritmo recibe muestras que están etiquetadas en algunos forma ú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 los utiliza para inducir un clasificador. Este clasificador es una función que asigna etiquetas a las muestras, incluidas las muestras que el algoritmo nunca antes había visto. El objetivo del algoritmo de aprendizaje supervisado es optimizar alguna medida de rendimiento, como minimizar la cantidad de errores cometidos en nuevas muestras.

Teoría computacional de números

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

Criptografía

La criptografía es la práctica y el estudio de técnicas de comunicación segura en presencia de terceros (llamados adversarios). De manera más general, se trata de construir y analizar protocolos que superen la influencia de los adversarios 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. La criptografía moderna se cruza con las disciplinas de las matemáticas, la informática y la ingeniería eléctrica. Las aplicaciones de la criptografía incluyen tarjetas de cajero automático, 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 informática; Los algoritmos criptográficos están diseñados en torno a suposiciones de dureza computacional, lo que hace que dichos algoritmos sean difíciles de romper en la práctica por parte de cualquier adversario. En teoría, es posible romper un sistema de este tipo, pero no es factible hacerlo por ningún 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 enteros y la tecnología informática más rápida requieren que estas soluciones se adapten continuamente. Existen esquemas de información teóricamente seguros que probablemente no se pueden descifrar incluso con una potencia informática ilimitada (un ejemplo es el bloc de notas de un solo uso), pero estos esquemas son más difíciles de implementar que los mejores mecanismos teóricamente descifrables pero computacionalmente seguros.

Estructuras de datos

Una estructura de datos es una forma particular de organizar los datos en una computadora para que se puedan usar de manera eficiente.

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

Las estructuras de datos brindan un medio para administrar grandes cantidades de datos de manera eficiente para usos tales como grandes bases de datos 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 los datos almacenados tanto en la memoria principal como en la memoria secundaria.

Cómputo distribuido

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 pasando mensajes. Los componentes interactúan entre sí para lograr un objetivo común. Tres características significativas de los sistemas distribuidos son: la concurrencia de componentes, la falta de un reloj global y la falla independiente de los componentes. 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 de computadora que se ejecuta en un sistema distribuido se denomina programa distribuido, y la programación distribuida es el proceso de escribir dichos programas. Hay muchas alternativas para el mecanismo de paso de mensajes, incluidos conectores tipo RPC y colas de mensajes. Un objetivo importante y un desafío de los sistemas distribuidos es la transparencia de la ubicación.

Complejidad basada en la información

La complejidad basada en la información (IBC) estudia los algoritmos óptimos y la complejidad computacional para problemas continuos. IBC ha estudiado problemas continuos como 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.

Métodos formales

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. 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 la ingeniería, realizar un análisis matemático adecuado puede contribuir a la confiabilidad y solidez de un diseño.

Los métodos formales se describen mejor como la aplicación de una variedad bastante amplia de fundamentos teóricos de la 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 software y Especificación y verificación de hardware.

Teoría de la información

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 confiables de datos. Desde sus inicios, 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, la evolución y función de los códigos moleculares, la selección de modelos en estadística, la física térmica, la computación cuántica, la lingüística, la detección de plagio, reconocimiento de patrones, detección de anomalías y otras formas de análisis de datos.

Las aplicaciones de los 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 línea de suscriptor digital (DSL)). El campo se encuentra 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 exterior, 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 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 de la teoría de la información y las medidas de la información.

Aprendizaje automático

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. Dichos algoritmos operan construyendo un modelo basado en entradas y usándolo para hacer predicciones o 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 brindan métodos, teoría 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), los motores de búsqueda y la visión artificial. El aprendizaje automático a veces se combina con la minería de datos, aunque se centra más en el análisis exploratorio de datos. El aprendizaje automático y el reconocimiento de patrones "pueden verse como dos facetas de el mismo campo."

Cálculo paralelo

La computación en paralelo es una forma de computación en la que se realizan muchos cálculos simultáneamente, según el principio de que los problemas grandes 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: nivel de bit, nivel de instrucción, datos y paralelismo de tareas. El paralelismo se ha empleado durante muchos años, principalmente en computación de alto rendimiento, pero últimamente ha crecido el interés debido a las limitaciones físicas que impiden el escalado de frecuencia. Dado que 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, la computación paralela se ha convertido en el paradigma dominante en la arquitectura de computadoras, principalmente en forma de procesadores multinúcleo.

Los programas informáticos paralelos son más difíciles de escribir que los secuenciales, porque la concurrencia introduce varias clases nuevas de posibles errores 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 del programa paralelo.

The maximum possible speed-up of a single program as a result of parallelization is known as Amdahl 's law.

Teoría del lenguaje de programación y semántica del programa

La teoría del lenguaje 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 encuadra dentro de la disciplina de la informática teórica, que depende y afecta a las matemáticas, la ingeniería de software y la lingüística. Es un área de investigación activa, con numerosas revistas académicas dedicadas.

En la teoría de los lenguajes de programación, la semántica es el campo relacionado con el 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 la no computación. 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.

Cálculo cuántico

Una computadora cuántica es un sistema de computación que hace uso directo de los fenómenos de la mecánica cuántica, como la superposición y el entrelazamiento, para realizar operaciones en los datos. Las computadoras cuánticas son diferentes de las computadoras digitales basadas en transistores. Mientras que las computadoras 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 usa 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 computadora cuántica universal. Las computadoras cuánticas comparten similitudes teóricas con las computadoras no deterministas y probabilísticas; 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 y Richard Feynman en 1982. También se formuló una computadora cuántica con espines como bits cuánticos para su uso como espacio-tiempo cuántico en 1968.

A partir de 2014, la computación cuántica aún está en pañales, pero se han llevado a cabo experimentos en los que las operaciones computacionales cuánticas se ejecutaron en una cantidad muy pequeña de qubits. Tanto la investigación práctica como la teórica continúan, y muchos gobiernos nacionales y agencias de financiación militar apoyan la investigación de la computación cuántica para desarrollar computadoras cuánticas con fines civiles y de seguridad nacional, como el criptoanálisis.

Cálculo simbólico

El álgebra informática, 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 generalmente se basa en el cálculo numérico con números de punto flotante aproximados, mientras que el cálculo simbólico 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 cómputo simbólico).

Las aplicaciones de software que realizan cálculos simbólicos se denominan sistemas de álgebra computacional, aludiendo 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 (generalmente diferente del lenguaje utilizado para la implementación), un administrador 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 usando la regla de la cadena, factorización de polinomios, integración indefinida, etc.

Integración a muy gran escala

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

Organizaciones

• European Association for Theoretical Computer Science
• SIGACT
• Simons Institute for the Theory of Computing

Revistas y boletines

• Discreta Matemáticas y Ciencias Teóricas de la Computación
• Información y comunicación
• Teoría de Computación (periódico de acceso abierto)
• Aspectos formales de la computación
• Journal of the ACM
• SIAM Journal on Computing (SICOMP)
• SIGACT Noticias
• Theoretical Computer Science
• Theory of Computing Systems
• TheoretiCS (periódico de acceso abierto)
• International Journal of Foundations of Computer Science
• Chicago Journal of Theoretical Computer Science (periódico de acceso abierto)
• Fundaciones y Tendencias en Ciencias Teóricas de la Computación
• Journal of Automata, Languages and Combinatorics
• Acta Informatica
• Fundamenta Informaticae
• ACM Transactions on Computation Teoría
• Complejidad computacional
• Journal of Complexity
• Transacciones ACM sobre algoritmos
• Cartas de procesamiento de información
• Open Computer Science (periódico de acceso abierto)

Conferencias

• Simposio anual ACM sobre Teoría de la Computación (STOC)
• Simposio anual de IEEE sobre Fundaciones de Ciencias de la Computación (FOCS)
• Innovaciones en Ciencias Teóricas de la Computación (ITCS)
• Mathematical Foundations of Computer Science (MFCS)
• Simposio Internacional de Ciencias de la Computación en Rusia (CSR)
• Simposio ACM-SIAM sobre algoritmos discretos (SODA)
• Simposio de IEEE sobre Lógica en Ciencias de la Computación (LICS)
• Conferencia de Complejidad Computacional (CCC)
• Coloquio Internacional sobre Automata, Idiomas y Programación (ICALP)
• Simposio Anual sobre Geometría Computacional (SoCG)
• Simposio ACM sobre Principios de Computación Distribuida (PODC)
• Simposio ACM sobre Paralelismo en Algoritmos y Arquitecturas (SPAA)
• Conferencia Anual sobre Teoría del Aprendizaje (COLT)
• Simposio sobre aspectos teóricos de la ciencia informática (STACS)
• Simposio Europeo sobre Algoritmos (ESA)
• Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
• Workshop on Randomization and Computation (RANDOM)
• Simposio Internacional sobre Algoritmos y Computación (ISAAC)
• Simposio Internacional sobre Fundamentos de la Teoría de la Computación
• International Workshop on Graph-Theoretic Concepts in Computer Science (WG)