Terminología

RECURSIVIDAD

La recursividad (recursión) es aquella propiedad que posee un método por la cual puede llamarse a sí mismo. Aunque se puede utilizar la recursividad como una alternativa a la iteración, una solución recursiva es, normalmente, menos eficiente en términos de tiempo de computadora que una solución iterativa, debido a las operaciones auxiliares que llevan consigo las invocaciones suplementarias a los métodos; sin embargo, en muchas circunstancias, el uso de la recursión permite a los programadores especificar soluciones naturales, sencillas, que serían, en caso contrario, difíciles de resolver. Por esta causa, la recursión es una herramienta poderosa e importante en la resolución de problemas y en la programación. Diversas técnicas algorítmicas utilizan la recursión, como los algoritmos divide y vence y los algoritmos de vuelta atrás.

ÁRBOLES

Intuitivamente, el concepto de árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre sí a través de ramas. El árbol genealógico es el ejemplo típico más representativo del concepto de árbol general.

Un árbol consta de un conjunto finito de elementos, denominados nodos y de un conjunto finito de líneas dirigidas, denominadas ramas, que conectan los nodos. El número de ramas asociado con un nodo es el grado del nodo.

Un árbol es un conjunto de uno o más nodos tales que:

1. Hay un nodo diseñado especialmente llamado raíz.

2. Los nodos restantes se dividen en n ≥ 0 conjuntos disjuntos, T1 ... Tn, tal que cada uno de estos conjuntos es un árbol. A T1 ... Tn se les denomina subárboles del raíz.

Si un árbol no está vacío, entonces el primer nodo se llama raíz.

Además del nodo raíz, existen muchos términos utilizados en la descripción de los atributos de un árbol. En la Figura 13.3, el nodo A es el raíz. Utilizando el concepto de árboles genealógicos, un nodo puede ser considerado como padre si tiene nodos sucesores.

Estos nodos sucesores se llaman hijos. Por ejemplo, el nodo B es el padre de los hijos E y F. El padre de H es el nodo D. Un árbol puede representar diversas generaciones en la familia. Los hijos de un nodo y los hijos de estos hijos se llaman descendientes, y el padre y los abuelos de un nodo son sus ascendientes. Por ejemplo, los nodos E, F, I y J son descendientes de B. Cada nodo no raíz tiene un único padre y cada padre tiene cero o más nodos hijos. Dos o más nodos con el mismo padre se llaman hermanos. Un nodo sin hijos, tal como E, I, J, G y H se llama nodo hoja.

El nivel de un nodo es su distancia al nodo raíz. La raíz tiene una distancia cero de sí misma, por ello se dice que está en el nivel 0. Los hijos del nodo raíz están en el nivel 1, sus hijos están en el nivel 2, y así sucesivamente. Una cosa importante que se aprecia entre los niveles de nodos es la relación entre niveles y hermanos. Los hermanos están siempre al mismo nivel, pero no todos los nodos de un mismo nivel son necesariamente hermanos.

Los árboles se utilizan para representar fórmulas algebraicas, para organizar objetos en orden de tal forma que las búsquedas sean muy eficientes y en aplicaciones diversas tales como inteligencia artificial o algoritmos de cifrado. Casi todos los sistemas operativos almacenan sus archivos en árboles o estructuras similares a árboles. Además de las aplicaciones citadas, los árboles se utilizan en diseño de compiladores, procesado de texto y algoritmos de búsqueda.

GRAFOS

Un grafo es un conjunto de puntos (una estructura de datos) y un conjunto de líneas, cada una de las cuales une un punto a otro. Los puntos se llaman nodos o vértices y las líneas se llaman aristas o arcos.  Se representa con el par G = (V, A).

Un arco o arista representa una relación entre dos nodos, se representa por (u, v) siendo u, v el par de nodos.

§  Lazo: arista que une a un nodo(vértice) consigo mismo.

§  camino: secuencia de uno o mas aristas que conectan dos nodos.

§  La longitud de un camino es el número de aristas que comprende.

§  Se dice que dos vértices son adyacentes si hay una arista que los une.

Un grafo permite modelar relaciones arbitrarias entre objetos. Un grafo G = (V,A) es un par formado por un conjunto de vértices o nodos, V, y un conjunto de arcos o aristas, A.

Cada arco es el par (u,w), siendo u, w dos vértices relacionados.