La informática teórica ( TCS ) es un subconjunto de la informática y las matemáticas generalesque se centra en aspectos matemáticos de la informática como la teoría de la computación , la teoría del lenguaje formal , el cálculo lambda y la teoría de tipos .
Es difícil delimitar con precisión las áreas teóricas. El Grupo de Interés Especial en Algoritmos y Teoría de la Computación (SIGACT) de la ACM proporciona la siguiente descripción: [1]
TCS cubre una amplia variedad de temas que incluyen 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 y álgebra de números computacionales . El trabajo en este campo a menudo se distingue por su énfasis en la técnica y el rigor matemático .
Si bien la inferencia lógica y la prueba matemática habían existido anteriormente, en 1931 Kurt Gödel demostró con su teorema de incompletitud que existen limitaciones fundamentales sobre qué afirmaciones pueden probarse o refutarse.
La teoría de la información se añadió 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 creciente cantidad 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 [ cita requerida ] .
Con el desarrollo de la mecánica cuántica a principios del siglo XX surgió el concepto de que se podían realizar operaciones matemáticas en la función de onda de una partícula completa. En otras palabras, se podrían calcular funciones en múltiples estados simultáneamente. Esto llevó 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 podían usarse para factorizar grandes números en tiempo polinomial , lo que, si se implementara, daría algunos resultados modernos. Los algoritmos de criptografía de clave pública como RSA son inseguros. [ cita necesaria ]
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:
Un algoritmo es un procedimiento de cálculo paso a paso. 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 [2] de instrucciones bien definidas [3] para calcular una función . [4] A partir de un estado inicial y una entrada inicial (quizás vacía ), [5] las instrucciones describen un cálculo que, cuando se ejecuta , avanza a través de un número finito [6] de estados sucesivos bien definidos, y eventualmente produce una "salida" [ 7] 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. [8]
La teoría de los autómatas es el estudio de las máquinas abstractas y los autómatas , así como de los problemas computacionales que pueden resolverse utilizándolos. 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 ). Autómata proviene de la palabra griega αὐτόματα que significa "autoactuante".
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 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 confiables . Normalmente, esto implica la eliminación de redundancia y la corrección (o detección) de errores en los datos transmitidos.
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. [9] 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 . [10]
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 computadoras , pero es similar a la bioinformática , que es una ciencia interdisciplinaria que utiliza computadoras para almacenar y procesar datos biológicos.
La teoría de la complejidad computacional es una rama de la teoría de la computación que se enfoca en clasificar 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 una computadora, lo que equivale a afirmar que el problema puede resolverse mediante la aplicación mecánica de pasos matemáticos, como por ejemplo un algoritmo .
Un problema se considera intrínsecamente difícil si su solución requiere importantes recursos, cualquiera que sea el 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 (utilizados 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 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 del movimiento y problemas de visibilidad), sistemas de información geográfica (GIS) (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 por computadora (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, a un algoritmo se le dan muestras etiquetadas de alguna manera útil. Por ejemplo, las muestras podrían ser descripciones de hongos y las etiquetas podrían indicar si los hongos son comestibles o no. El algoritmo toma estas muestras previamente etiquetadas y 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 del rendimiento, como minimizar la cantidad de errores cometidos en nuevas muestras.
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 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 ). [11] De manera más general, se trata de construir y analizar protocolos que superen la influencia de los adversarios [12] y que estén relacionados con diversos 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 . [13] 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 de cajero automático , contraseñas de computadoras 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 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. Es teóricamente posible romper dicho sistema, 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 números 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 romper ni siquiera 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 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 . [14] [15]
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 utilizan índices de árbol B para pequeños porcentajes de recuperación de datos y los compiladores y 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 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 factor organizativo clave en el diseño de software. El almacenamiento y la recuperación se pueden realizar sobre datos almacenados tanto en la memoria principal como en la memoria secundaria .
La computación distribuida estudia 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 . [16] Los componentes interactúan entre sí para lograr un objetivo común. Tres características importantes de los sistemas distribuidos son: concurrencia de componentes, falta de un reloj global y falla independiente de los componentes. [16] Los ejemplos de sistemas distribuidos varían desde sistemas basados en SOA hasta juegos en línea multijugador masivo , aplicaciones peer-to-peer y redes blockchain como Bitcoin .
Un programa de computadora que se ejecuta en un sistema distribuido se llama programa distribuido y la programación distribuida es el proceso de escribir dichos programas. [17] Existen muchas alternativas para el mecanismo de paso de mensajes, incluidos conectores tipo RPC y colas de mensajes . Un objetivo y 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 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.
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 . [18] 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, la realización de un análisis matemático apropiado puede contribuir a la confiabilidad y robustez de un diseño. [19]
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 especificación y especificación de software y hardware. verificación. [20]
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 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 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 , [21] la evolución [22] y la función [23] de los códigos moleculares, la selección de modelos en estadística, [24 ] física térmica, [25] computación cuántica , lingüística , detección de plagio, [26] reconocimiento de patrones , detección de anomalías y otras formas de análisis de datos . [27]
Las aplicaciones de temas fundamentales de la teoría de la información incluyen la compresión de datos sin pérdidas (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 abonado 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 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. 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.
El aprendizaje automático es una disciplina científica que se ocupa de la construcción y estudio de algoritmos que pueden aprender de los datos. [28] Dichos algoritmos operan construyendo un modelo basado en entradas [29] : 2 y usándolo para hacer predicciones o decisiones, en lugar de seguir solo instrucciones explícitamente programadas.
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 es inviable diseñar y programar algoritmos explícitos basados en reglas . Las aplicaciones de ejemplo incluyen filtrado de spam , reconocimiento óptico de caracteres (OCR), [30] motores de búsqueda y visión por computadora . El aprendizaje automático a veces se combina con la minería de datos , [31] aunque se centra más en el análisis exploratorio de datos. [32] El aprendizaje automático y el reconocimiento de patrones "pueden verse como dos facetas del mismo campo". [29] : vii
La computación paralela es una forma de computación en la que muchos cálculos se llevan a cabo simultáneamente, [33] operando 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 bits , nivel de instrucción , datos y paralelismo de tareas . El paralelismo se ha empleado durante muchos años, principalmente en la informática de alto rendimiento , pero el interés en él ha aumentado últimamente debido a las limitaciones físicas que impiden el escalado de frecuencia . [34] 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, [35] la computación paralela se ha convertido en el paradigma dominante en la arquitectura de las computadoras , principalmente en forma de procesadores multinúcleo . [36]
Los programas informáticos paralelos son más difíciles de escribir que los secuenciales, [37] 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 lograr un buen rendimiento del programa paralelo.
La máxima aceleración posible de un único 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, implementación, análisis, caracterización y clasificación de los lenguajes de programación y sus características individuales . Se incluye dentro de la disciplina de la informática teórica, dependiendo y afectando 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 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 el caso de que la evaluación fuera de cadenas sintácticamente ilegales, el resultado no sería un cálculo. La semántica describe los procesos que sigue una computadora al ejecutar 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 cálculo .
Una computadora cuántica es un sistema de computación que hace uso directo de fenómenos mecánico-cuánticos , como la superposición y el entrelazamiento , para realizar operaciones con datos . [38] 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 siempre está 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 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 [39] y Richard Feynman en 1982. [40] [41] También se formuló una computadora cuántica con espines como bits cuánticos para su uso como espacio-tiempo cuántico en 1968. [42]
En 2014 [actualizar], la computación cuántica aún está en su infancia, pero se han llevado a cabo experimentos en los que se ejecutaron operaciones computacionales cuánticas en un número muy pequeño de qubits. [43] 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 en computación cuántica para desarrollar computadoras cuánticas con fines de seguridad tanto civiles como nacionales, como el criptoanálisis . [44]
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 informática debería ser un subcampo de la informática científica , generalmente se consideran campos distintos porque la informática científica suele basarse en cálculos numéricos con números aproximados de coma flotante , mientras que el cálculo simbólico enfatiza el cálculo exacto con expresiones que contienen variables que no tienen cualquier valor dado y, por lo tanto, se manipulan como símbolos (de ahí el nombre de cálculo simbólico ).
Las aplicaciones de software que realizan cálculos simbólicos se denominan sistemas de álgebra informática , 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 polinomial , integración indefinida , etc. .
La integración a muy gran escala ( VLSI ) es el proceso de creación de un circuito integrado (IC) combinando miles de transistores en un solo chip. VLSI comenzó en la década de 1970, cuando se estaban desarrollando complejas tecnologías de comunicaciones 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 constar de una CPU , una ROM , una RAM y otra lógica adhesiva . VLSI permite a los fabricantes de circuitos integrados agregar todos estos circuitos en un solo chip.