Mes: febrero 2022

Tiempo de ejecución

Tiempo de ejecución

Se denomina tiempo de ejecución (runtime en inglés) al intervalo de tiempo en el que un programa de computadora se ejecuta en un sistema operativo. Este tiempo se inicia con la puesta en memoria principal del programa, por lo que el sistema operativo comienza a ejecutar sus instrucciones. El intervalo finaliza en el momento en que este envía al sistema operativo la señal de terminación, sea esta una terminación normal, en que el programa tuvo la posibilidad de concluir sus instrucciones satisfactoriamente, o una terminación anormal, en el que el programa produjo algún error y el sistema debió forzar su finalización.

Leer más

Teoría de autómatas

Teoría de autómatas

Esta teoría provee modelos matemáticos que formalizan el concepto de computadora o algoritmo de manera suficientemente simplificada y general para que se puedan analizar sus capacidades y limitaciones. Algunos de estos modelos juegan un papel central en varias aplicaciones de las ciencias de la computación, incluyendo procesamiento de texto, compiladores, diseño de hardware e inteligencia artificial.

Existen muchos otros tipos de autómatas como las máquinas de acceso aleatorio, autómatas celulares, máquinas ábaco y las máquinas de estado abstracto, sin embargo en todos los casos se ha mostrado que estos modelos no son más generales que la máquina de Turing, pues la máquina de Turing tiene la capacidad de simular cada uno de estos autómatas. Esto da lugar a que se piense en la máquina de Turing como el modelo universal de computadora.

Teoría de la complejidad computacional

Teoría de la complejidad computacional

Aun cuando un problema sea computable, puede que no sea posible resolverlo en la práctica si se requiere mucha memoria o tiempo de ejecución. La teoría de la complejidad computacional estudia las necesidades de memoria, tiempo y otros recursos computacionales para resolver problemas, de esta manera es posible explicar por qué unos problemas son más difíciles de resolver que otros. Uno de los mayores logros de esta rama es la clasificación de problemas, similar a la tabla periódica, de acuerdo a su dificultad. En esta clasificación los problemas se separan por clases de complejidad.

Esta teoría tiene aplicación en casi todas las áreas de conocimiento donde se desee resolver un problema computacionalmente, porque los investigadores no solo desean utilizar un método para resolver un problema, sino utilizar el más rápido. La teoría de la complejidad computacional también tiene aplicaciones en áreas como la criptografía, donde se espera que descifrar un código secreto sea un problema muy difícil a menos que se tenga la contraseña, en cuyo caso el problema se vuelve fácil.

Cálculo lambda

Cálculo lambda

En lógica matemática, el cálculo lambda es un sistema formal diseñado para investigar la definición de función, la noción de aplicación de funciones y la recursión. Fue introducido por Alonzo Church y Stephen Kleene en la década de 1930 como parte de sus investigaciones sobre los fundamentos de las matemáticas. Church usó el cálculo lambda en 1936 para resolver el Entscheidungsproblem. Puede ser usado para definir de manera limpia y precisa qué es una «función computable«.

El interrogante de si dos expresiones del cálculo lambda son equivalentes no puede ser resuelto por un algoritmo general. Esta fue la primera pregunta, incluso antes que el problema de la parada, cuya indecidibilidad fue probada. El cálculo lambda tiene una gran influencia sobre los lenguajes funcionales, como LispML Haskell.

Se puede considerar al cálculo lambda como uno de los lenguajes universales de programación más minimalistas. Consiste en una regla de transformación simple (sustitución de variables) y un esquema simple para definir funciones.

El cálculo lambda es universal porque cualquier función computable puede ser expresada y evaluada a través de él. Por lo tanto, es equivalente a las máquinas de Turing. Sin embargo, el cálculo lambda no hace énfasis en el uso de reglas de transformación y no considera las máquinas reales que pueden implementarlo. Se trata de una propuesta más cercana al software que al hardware.

Teoría de la computación

Teoría de la computación

La teoría de la computación o teoría de la informática es un conjunto de conocimientos racionales y sistematizados que se centran en el estudio de la abstracción de los procesos, con el fin de reproducirlos con ayuda de sistemas formales, es decir, a través de símbolos y reglas lógicas. La teoría de la computación permite modelar procesos dentro de las limitaciones de dispositivos que procesan información y que efectúan cálculos; como, por ejemplo, el ordenador. Para ello, se apoya en la teoría de autómatas, a fin de simular y estandarizar dichos procesos, así como para formalizar los problemas y darles solución.