0068-RH. Red Heurística Emplea un planeamiento de autoestudio para llegar a la solución de un problema. La construcción de un sistema que no sea heurístico refleja directamente el conocimiento existente de un algoritmo que pueda dar la solución a un problema. En contraposición, un sistema heurístico tiene que constituirse de tal manera que pueda adquirir el conocimiento necesario para la obtención de la solución requerida.

0086-PD. Procedimiento de Decisión

Problema de decisión. Tarea que para cada entrada posible requiere una salida <<verdadero>> o <<falso>>, según la entrada posea, o no, una cierta propiedad. El algoritmo que produzca la decisión adecuada a cada caso recibe la denominación de procedimiento de decisión para ese problema. Entonces, se dice que este problema es soluble, en tanto que un problema insoluble es aquel para el cual no existe ningún procedimiento de decisión. Como ejemplo se puede citar la validez lógica, en que las entradas son expresiones lógicas, con la salida <<verdadero>> para las expresiones válidas y <<falso>> para las otras. Este problema es soluble para la lógica proposicional (siendo la construcción de tablas de verdad un problema de decisión), pero no lo es para la lógica de predicados. Los problemas solubles pueden clasificarse posteriormente según la eficacia de los procedimientos de decisión existentes para ellos .

Algunos problemas insolubles poseen un procedimiento de semidecisión, es decir, un algoritmo que da correctamente las salidas de <<verdadero>> pero falla al terminar en los casos en que la salida debe ser <<falso>>. Esto es lo mismo que decir que las entradas que requieren la salida <<verdadero>> forman un grupo que es recursivamente enumerable, pero no recursivo. De forma alternativa, se puede decir que el problema corresponde a un predicado que es semidecidible, pero no decidible. Sin embargo, existe otra formulación según la cual, mientras la correcta correspondencia desde las entradas a un <<verdadero>> y <<falso>> no es una función computable, su restricción a las entradas de <<verdadero>> da una función parcial computable.

000106-AL. Algoritmos

Conjunto prescrito de reglas o instrucciones bien definidas para la resolución de un problema, por ejemplo, la realización de un cálculo, en un número finito de pasos. Una de las funciones principales de un programa consiste en expresar un algoritmo en una notación formal; gran parte de lo que se dice sobre los programas se aplica a los algoritmos, y viceversa. Un algoritmo efectivo es aquel que es computable de forma efectiva. El estudio de la existencia de algoritmos efectivos para computar cantidades particulares constituye la base de la teoría de los algoritmos. Excepto para el más sencillo de los algoritmos, resulta difícil probar que un algoritmo es correcto o, incluso, especificar el efecto que se desea conseguir. Por regla general, en la práctica es necesario contentarse con la validación del algoritmo. Este proceso certifica, o verifica, que un algoritmo realizará el cálculo que se le pide. Esto implica la comprobación de la rutina en una variedad de elementos del problema y asegurándose de que se comporta satisfactoriamente en estas pruebas. Si el conjunto de pruebas se ha elegido lo suficientemente bien, puede confiarse en el algoritmo.

El análisis de algoritmos es el estudio de las características del comportamiento de un algoritmo dado. Una rama de este estudio, el análisis de los casos medios, examina el comportamiento medio de un algoritmo. El análisis de casos peores estudia la conducta cuando las circunstancias son las más desfavorables posibles. Pueden analizarse los algoritmos en función de su complejidad y eficacia. La eficacia de un algoritmo se caracteriza por su orden. Si dos algoritmos del mismo problema son de igual orden, pueden considerarse ambos aproximadamente eficaces en lo que se refiere al cálculo. La eficacia algorítmica es útil para cuantificar las dificultades de implementación de ciertos problemas.

Eficacia algorítmica; rendimiento algorítmico. Medida del tiempo medio de ejecución empleado por un algoritmo para completar su operación con un conjunto de datos. Un algoritmo de clasificación por el método de burbujas será eficaz al clasificar N elementos en proporción con, y del orden de, Nˆ2, generalmente formulado: O(Nˆ2). Esto es así porque una media de N/2 veces comparaciones es necesaria N/2 veces, dando Nˆ2/4 comparaciones totales, de aquí que sea del orden de Nˆ2. En contraposición, la clasificación rápida posee una eficacia O(Nlog2N).

0128-AD. Arboles de Derivación

Gramática ambigua. Gramática independiente del contexto que deriva una misma palabra de árboles diferentes de derivación, o, de forma equivalente, de secuencias distintas de derivación del extremo derecho o del izquierdo.

0186-AD. Datos, abstracción

Datos, información. Información que se ha preparado, frecuentemente, en un formato particular, para una finalidad específica. El término posee tres connotaciones especiales.

En primer lugar, el concepto de dato como algo distinto del de instrucción de programa. Por ejemplo, en el código fuente las declaraciones de datos son diferentes de las instrucciones ejecutables; en el momento de la ejecución, el espacio de memoria es repartido entre los datos (constantes y variables) y las instrucciones; además los ficheros de datos son distintos de los ficheros de programas. (Sin embargo, estas distinciones dependen del contexto puesto que los ficheros de programas y las instrucciones de código objeto y fuente sirven como datos a programas tales como los compiladores y los cargadores-editores de montaje.)

En segundo lugar, en el contexto de un programa individual o de una serie de programas, el término datos puede utilizarse en un sentido más restringido significando la entrada en oposición a los resultados (salida), como, por ejemplo, en la preparación de los datos o su validación. (Sin embargo, los resultados de un proceso son, casi de forma invariable, datos de uno subsiguiente.)

En tercer lugar, y más generalmente, se habla, con frecuencia, de los datos como de un concepto distinto de los de texto, voz e imagen y, también, de proceso de datos en oposición a tratamiento de textos, de voz y de imagen. Esta aplicación del término se basa en la naturaleza muy estructurada de los datos en las aplicaciones tradicionales de proceso de datos, en oposición a la estructura, mucho más libre, de los textos en el lenguaje natural, comunicación vocal e imágenes visuales.

Abstracción de datos. El principio de definir un tipo de datos en razón de las operaciones aplicables a los objetos de dicho tipo, con la limitación de que los valores de tales objetos pueden modificarse y observarse sólo mediante la utilización de estas operaciones. La aplicación del principio general de abstracción conduce al de contener conocimiento acerca del dominio del programa (por ejemplo, matemáticas o modelador por elementos finitos) y también conocimiento experto sobre la manera mejor de utilizar el software para resolver problemas en ese dominio. Se incluyen sistemas frontales inteligentes para una amplia gama de programas (por ejemplo, estadísticos, de modelador por elementos finitos) y son potencialmente importantes al ampliar la disponibilidad del software existente.