0760-DA. Dato, abstracto Tipo de datos que se define, exclusivamente, en los términos de las operaciones que se aplican a objetos de dicho tipo, sin considerar la manera de representar su valor. Un tipo de datos abstracto es un (D,F,A) triple que consta de un conjunto de dominios D, un conjunto de funciones F, cada una de ellas con rango de dominio en D, y un conjunto de axiomas A que especifican las propiedades de las funciones en F.

0783-SA. Semántica de axiomas

Tratamiento semántico de los lenguajes de programación en el que el significado de un lenguaje está dado mediante la descripción de las sentencias ( o instrucciones) verdaderas que pueden hacerse sobre programas en ese lenguaje. Normalmente estas instrucciones se escriben en una notación formal adecuada tal como el cálculo de predicados o la lógica modal y atañen a los estados de ejecución antes y después de la ejecución del programa. Aunque al principio se enfocaba como una notación para pruebas de corrección de programas se observó que la lógica podía considerarse también como una semántica axiomática para un lenguaje de programación muy sencillo. Este enfoque se extendió, consecuentemente, a la descripción de lenguajes prácticamente útiles.

0792-AC. Algoritmos computables

Clases de complejidad. Forma de agrupar algoritmos o funciones computables según su complejidad. Las funciones computables que tienen la misma medida de complejidad están situadas en la misma clase de complejidad; las funciones de la misma clase son igualmente difíciles de computar (con respecto a la medida).La clasificación se hace, característicamente, para los lenguajes formales que pueden ser reconocidos por los programas de las máquinas (de T). Si L es un lenguaje formal reconocible por un programa de máquina (de T) determinista M, y la complejidad de tiempo para M es:

T_M(n)

Entonces L está clasificada según la naturaleza de:

T_M(n)

Luego si:

T_M(n)

está limitada (de forma polinómica o exponencial), entonces existe una función de límite:

S(n)

de tal modo que:

T_M(n) <= S(n)

0823-MC. Medida de complejidad

Medio de medir los recursos utilizados durante una computación. En la computación de una máquina (de T) se emplearán varios recursos, por ejemplo, espacio y tiempo. Estos pueden definirse como sigue.Dados un programa de máquina (de T) M y una cadena de entrada x, entonces TIEMPO (M,x) se define como el número de pasos en la computación de m en x antes de que M se detenga. El tiempo es indefinido (es decir: igual a infinito), si M no se detiene en x. La complejidad de tiempo de M se dice que es la función entera de:

T_M

donde

T_M (n) = max [Tiempo (M,x):½x½=n]

para el entero no negativo n.

El espacio (M,x) se define, de forma similar, como el número de cuadrados de cinta utilizados por M en x, y la complejidad de espacio se define por:

S_M(n) = max [Espacio (M,x):½x½=n]

Sin embargo, para distinguir el espacio que se necesita para operar como opuesto al de la cadena de entrada x, a veces se considera que la máquina tiene una cinta de entrada sólo de lectura y el Espacio (M,x) se define como el número de cuadrados con posibilidad de escritura utilizados por M en x.

También es posible la definición de medidas de complejidad más generales que comparten muchas de las propiedades comunes de tiempo y espacio. Se dice que un algoritmo está limitado de forma polinómica cuando la medida de complejidad:

T_M (n)

ó

S_M (n)

no aumenta con n más rápidamente que un polinomio en n; se dice que está limitado de forma exponencial aquel en el que la medida crece exponencialmente. Hay que observar que ambos casos implican la terminación del algoritmo.

Puerta de decisión. Puerta lógica electrónica cuya salida indica si una relación lógica es verdadera o falsa. Pueden considerarse los siguientes ejemplos: un comparador de igualdad, que indica cuando son iguales dos números binarios; un controlador de paridad impar que indica cuándo una entrada binaria tiene un número impar de unos; un elemento de mayoría, que indica cuándo las entradas binarias tienen más entradas 1 que 0.

0843-LR. Lógica, razonamiento

Representación del conocimiento y estudio del razonamiento desarrollado originalmente para formalizar el razonamiento matemático. En la lógica matemática, la investigación comprende métodos matemáticos tomados del álgebra o de la teoría de los algoritmos. Los dos sistemas más comunes son el cálculo proposicional y el de predicados.

La lógica ha sido adoptada de forma generalizada en el Sistema ISTP de Inteligencia artificial, como alternativa de las reglas de producción en los sistemas expertos y para representar el significado de manifestaciones en lenguaje natural. Se han desarrollado muchas lógicas alternativas en inteligencia artificial para representar la vaguedad o la incertidumbre del sentido común (en oposición al conocimiento matemático) y para representar la naturaleza provisional experimental del razonamiento del sentido común; entre ellas se pueden citar el razonamiento no monótono y el incierto.

0862-LNB. Lógica no binaria

Lógica digital para su utilización en los circuitos lógicos que se diseñan para manejar más de dos niveles (voltajes, etc.). En la lógica q valorada hay q niveles y cada elemento de la memoria (circuitos basculantes, etc.) puede existir en q estados diferentes. La clasificación de los circuitos lógicos en combinatorios y secuenciales se aplica a la lógica de valores múltiples exactamente como a la lógica binaria. Normalmente hay gran interés en la lógica ternaria (q = 3) y algo menos en la cuaternaria (q = 4). Estas lógicas prometen números reducidos de puertas lógicas, elementos de la memoria y, quizá más significativamente, de interconexiones. La lógica ternaria es sencilla de poner en aplicación en la tecnología CMOS y hay posibilidad de que llegue a ser importante en el diseño de los circuitos de VLSI. Su riqueza lógica incrementada se demuestra en el hecho de que existen 16 puertas binarias posibles de dos entradas, pero 19.683 puertas ternarias (haciendo caso omiso de las degradaciones en ambos casos).

0864-ME. Matriz estocástica

Matriz aleatoria; matriz probabilista. Matriz muy utilizada, por ejemplo, en la teoría de la comunicación, modelación y simulación, en la que cada fila es una distribución de probabilidad, es decir, cada elemento se encuentra entre 0 y 1, y la suma de los elementos de cada fila es la unidad. Una matriz doblemente estocástica es una matriz estocástica cuya transposición es una matriz estocástica.

0879-PE. Proceso estocástico (conjetura)

Proceso aleatorio. Conjunto de variables aleatorias cuyos valores cambian con el tiempo (o, a veces, en el espacio). Ejemplos de esto son las poblaciones afectadas por nacimientos y muertes, la longitud de una cola o la cantidad de agua en un embalse. Los modelos estocásticos son aquellos en los que la variación aleatoria es de mucha importancia, en contraposición con los modelos deterministas. Los procesos estocásticos dan explicaciones teóricas de muchas distribuciones de probabilidad, y son la base del análisis de datos en serie cronológica.

0923-RR. Redes recurrentes

La Red recurrente se puede entrenar mediante algoritmo de propagación hacia atrás. En cada paso se comparan las activaciones de las unidades de salida con las activaciones deseadas y se propagan los errores hacia atrás por la red. Cuando se completa el entrenamiento, la red podrá llevar a cabo una secuencia de acciones. Ciertas características de la propagación hacia atrás, como la generalización automática, también se cumplen en las redes recurrentes.

0682-CR. Seguridad

El sistema de seguridad desarrollado por SCiNet, además de incluir los protocolos convencionales (SET, SSL, OTP, PGP, VeriSign, ThaWte, CertPlus, etc.) integra el Cripto-sistema de seguridad FP2®, compuesto por algoritmos fractales-perceptuales basados en sistemas dinámicos no lineales (algoritmos de generación infinita comprimidos en espacios finitos). Esto último, dicho en forma comprensible, quiere decir: la imposibilidad de descifrado.