informática teórica

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

Un algoritmo es un método eficaz expresado como una lista finita ^{[ 3 ]} de instrucciones bien definidas ^{[ 4 ]} para calcular una función . ^{[ 5 ]} Partiendo de un estado inicial y una entrada inicial (quizás vacía ), ^{[ 6 ]} las instrucciones describen un cálculo que, al ejecutarse , 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 estudia las máquinas abstractas y los autómatas , así como los problemas computacionales que pueden resolverse mediante ellos. Es una teoría de la informática teórica, perteneciente a las matemáticas discretas (una rama de las matemáticas y también de la informática ). El término autómata proviene de la palabra griega αὐτόματα, que significa "autoaccionante".

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

La teoría de la codificación estudia 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 . Diversas disciplinas científicas, como la teoría de la información , la ingeniería eléctrica , las matemáticas y la informática , estudian los códigos 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.

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 dichas clases entre sí. Un problema computacional se entiende como una tarea que, en principio, puede 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 un algoritmo .

Un problema se considera intrínsecamente difícil si su solución requiere recursos significativos, independientemente del algoritmo utilizado. La teoría formaliza esta intuición mediante la introducción de 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 ), el número de compuertas 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 geométricos . 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 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), 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 los circuitos integrados), la ingeniería asistida por ordenador (CAE) (generación de mallas) y la visión por ordenador (reconstrucción 3D).

Los resultados teóricos en aprendizaje automático se centran principalmente en un tipo de aprendizaje inductivo llamado aprendizaje supervisado. En este tipo de aprendizaje, se le proporcionan a un algoritmo muestras etiquetadas de forma útil. Por ejemplo, las muestras podrían ser descripciones de setas, y las etiquetas podrían indicar si las setas son comestibles o no. El algoritmo toma estas muestras previamente etiquetadas y las utiliza para generar un clasificador. Este clasificador es una función que asigna etiquetas a las muestras, incluidas aquellas que el algoritmo nunca ha visto antes. El objetivo del algoritmo de aprendizaje supervisado es optimizar alguna medida de rendimiento, como minimizar el número de errores cometidos con muestras nuevas.

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 de teoría de números . El problema más conocido en este campo es la factorización de 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 ]} En términos más generales, se trata de construir y analizar protocolos que superen la influencia de los adversarios ^{[ 11 ]} 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 . ^{[ 12 ]} 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 de la informática; los algoritmos criptográficos se diseñan en torno a supuestos de dificultad computacional , lo que hace que sean difíciles de romper en la práctica por cualquier adversario. Si bien teóricamente es posible romper un sistema de este tipo, resulta inviable hacerlo por cualquier medio práctico conocido. Por lo tanto, estos esquemas se denominan computacionalmente seguros; los avances teóricos, como las mejoras en los algoritmos de factorización de enteros y la mayor velocidad de la tecnología informática, exigen que estas soluciones se adapten continuamente. Existen esquemas teóricamente seguros desde el punto de vista de la información que, demostrablemente, no pueden romperse ni siquiera con una capacidad de cómputo ilimitada —un ejemplo es el cifrado 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 los datos en una computadora para que puedan usarse de manera eficiente . ^{[ 13 ] [ 14 ]}

Los distintos 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 B-tree para recuperar pequeños porcentajes de datos, y los compiladores y las bases de datos utilizan tablas hash dinámicas como tablas de consulta.

Las estructuras de datos proporcionan un medio para gestionar grandes cantidades de datos de forma eficiente para usos como bases de datos de gran tamaño y servicios de indexación de internet . Generalmente, las estructuras de datos eficientes son clave para diseñar algoritmos eficientes . Algunos métodos de diseño formal y lenguajes de programación hacen hincapié en las estructuras de datos, en lugar de los algoritmos, como el factor organizativo clave en el diseño de software. El almacenamiento y la recuperación de datos pueden realizarse 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 intercambio de mensajes . ^{[ 15 ]} Los componentes interactúan entre sí para lograr un objetivo común. Tres características significativas de los sistemas distribuidos son: la concurrencia de los componentes, la ausencia de un reloj global y la posibilidad de fallos independientes de los componentes. ^{[ 15 ]} Ejemplos de sistemas distribuidos abarcan desde sistemas basados ​​en SOA hasta juegos multijugador masivos en línea, 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 los conectores tipo RPC y las colas de mensajes . Un objetivo y un desafío importante de los sistemas distribuidos es la transparencia de ubicación .

La complejidad basada en la información (IBC, por sus siglas en inglés) estudia los 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 las matemáticas para la especificación , el desarrollo y la 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 fiabilidad y robustez de un diseño. ^{[ 18 ]}

Los métodos formales se describen mejor como la aplicación de una amplia variedad 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 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 involucra la cuantificación 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, incluyendo 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) ). Este 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 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 basada en la teoría 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 ]} Dichos algoritmos operan 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ía y dominios de aplicación al campo. El aprendizaje automático se emplea en diversas tareas informáticas donde el diseño y la programación de algoritmos explícitos basados ​​en reglas resultan inviables. Algunos ejemplos de aplicaciones incluyen el filtrado de spam , el reconocimiento óptico de caracteres (OCR), ^{[ 29 ]} los motores de búsqueda y la visión artificial . A veces, el aprendizaje automático se confunde con la minería de datos , ^{[ 30 ]} aunque esta última se centra más en el análisis exploratorio de datos. ^{[ 31 ]} El aprendizaje automático y el reconocimiento de patrones "pueden considerarse dos facetas del mismo campo". ^{[ 28 ] : vii}

^{[ 39 ]}

La computación paralela es una forma de computación en la que se realizan muchos cálculos simultáneamente, ^{[ 40 ]} operando bajo 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: paralelismo a nivel de bits , a nivel de instrucciones , de datos y de tareas . El paralelismo se ha empleado durante muchos años, principalmente en computación de alto rendimiento , pero el interés en él ha crecido últimamente debido a las limitaciones físicas que impiden el escalado de frecuencia . ^{[ 41 ]} Como el consumo de energía (y, en consecuencia, la generación de calor) 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 de computadoras , principalmente en forma de procesadores multinúcleo . ^{[ 43 ]}

Los programas informáticos paralelos son más difíciles de escribir que los secuenciales, ^{[ 44 ]} 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 lograr un buen rendimiento de los programas paralelos.

La máxima aceleración posible de un solo programa como resultado de la paralelización se conoce como la 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 informática teórica, y depende de las matemáticas , la ingeniería de software y la lingüística , a la vez que las influye . Es un área de investigación activa, con numerosas revistas académicas especializadas.

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 . Para ello, evalúa el significado de cadenas sintácticamente válidas definidas por un lenguaje de programación específico, mostrando la computación involucrada. Si la evaluación se realizara sobre cadenas sintácticamente inválidas, el resultado sería la ausencia de computación. La semántica describe los procesos que sigue un ordenador al ejecutar un programa en ese lenguaje específico. Esto se puede demostrar describiendo la relación entre la entrada y la salida de un programa, o explicando cómo se ejecutará el programa en una plataforma determinada , creando así un modelo de computación .

Una computadora cuántica es un sistema de computación que utiliza directamente fenómenos de la mecánica cuántica , como la superposición y el entrelazamiento , para realizar operaciones con datos . ^{[ 45 ]} 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 cúbits (bits cuánticos), que pueden estar en superposiciones de estados. Un modelo teórico es la máquina de Turing cuántica , también conocida como la 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 ^{[ 46 ]} y Richard Feynman en 1982. ^{[ 47 ] [ 48 ]} También se formuló una computadora cuántica con espines como bits cuánticos para su uso como espacio-tiempo cuántico en 1968. ^{[ 49 ]}

Se han realizado experimentos en los que se ejecutaron operaciones de computación cuántica en un número muy pequeño de cúbits. ^{[ 50 ]} La investigación, tanto práctica como teórica, continúa, 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 civiles y 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 . Si bien, en rigor, 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 se basa habitualmente en cálculos numéricos con números de coma flotante aproximados , mientras que la computación simbólica enfatiza los cálculos exactos 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 , y el término sistema alude a la complejidad de las aplicaciones principales que incluyen, como mínimo, un método para representar datos matemáticos en un ordenador, 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 amplio conjunto de rutinas para realizar operaciones habituales, como la simplificación de expresiones, la diferenciación mediante la regla de la cadena , la factorización de polinomios , la integración indefinida , etc.

La integración a muy gran escala ( VLSI ) es el proceso de crear un circuito integrado (CI) combinando miles de transistores en un solo chip. La VLSI surgió en la década de 1970, cuando se desarrollaban tecnologías complejas de semiconductores y comunicaciones . 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. Un circuito electrónico podía constar de una CPU , ROM , RAM y otros componentes lógicos . La VLSI permite a los fabricantes de CI integrar todos estos circuitos en un solo chip.