COMPUTABILIDAD DE PROBLEMAS

Indice

1. Funcion Recursivas
1.1. Funciones Recursivas parciales
1.2. Funciones Recursivas Primitivas
2. Listas Simples
3.Listas de Listas
4. Arboles Binarios
5. Arboles Generales

1. Funcion Recursivas

Hasta ahora, nuestro estudio de los procesos computacionales y sus capacidades se ha basado en un enfoque operativo, no funcional. Nos hemos centrado en cómo se lleva a cabo un cálculo, no en lo que este cálculo logra. Sin embargo, nuestro objetivo es identificar las funciones que pueden calcularse con al menos un sistema computacional, así que debemos alejarnos de cualquier método específico para expresar o ejecutar los cálculos. En otras palabras, queremos utilizar el término computable para decir que una función puede calcularse mediante algún´ algoritmo, más que por un algoritmo que pueda implementarse en algún´ sistema especıfico.

1.1. Funciones Recursivas parciales

Para ampliar nuestro estudio de las funciones computables más allá de las funciones totales computables, aplicamos la técnica de construcción conocida como mineralización. Esta técnica nos permite construir una función 9 f : N n → N a partir de otra función g : N n+1 → N declarando a f(x¯) como la menor y en N tal que g(x¯, y) = 0 y g(x¯, z) está definida para todos los enteros no negativos z menores que yo . Esta construcción se representa con la notación: f(x¯) = µy[g(x¯, y) = 0] Como ejemplo, supongamos que g(x, y) se define de acuerdo con los valores que aparecen en la tabla 1, y que f(x) se define como µy[g(x, y) = 0]. Entonces, f(0) = 4, f(1) = 2, y f(2) no ésta definido ya que, aunque 4 es el menor valor de y para el cual g(2, y) = 0, g(2, z) no está definido para todos y cada uno de los valores de z menores que 4. En lo que se refiere al valor de f(3), la tabla no nos proporciona suficiente información para determinar si se encuentra definido o no.

 1.2. Funciones Recursivas Primitivas

Como hemos dicho, el primer objetivo de esta sección es ampliar el repertorio de las funciones que sabemos que son recursivas primitivas, proporcionando una serie de ejemplos útiles ´ que suelen aparecer en las aplicaciones de ordenador tradicionales. Posteriormente, el segundo objetivo ser ‘a el de esclarecer la diferencia entre la clase de las funciones recursivas primitivas y la clase de las funciones totales computables. Ejemplos de funciones recursivas primitivas. Comenzaremos nuestro estudio de las funciones recursivas primitivas considerando la colección de las funciones constantes, las cuales producen una salida fija predeterminada, sin importar cuál sea la entrada. Las funciones constantes cuyas salidas son tuplas de un solo elemento están representadas por K n m, donde n indica la dimensión del dominio y m es el valor de salida de la función. Así, K 2 3 establece la correspondencia entre cualquier tupla de dos elementos y el entero 3. Cualquier función constante de la forma Kn m es recursiva primitiva, ya que puede calcularse mediante la composición de las siguientes funciones iniciales: la proyección π n 0 , para la obtención de la tupla vacía a partir de cualquier n-tupla; la función ζ para la obtención de 0; y m aplicaciones de la función σ para la obtención del valor m. Por ejemplo: K2 3 (x1, x2) = σ ◦ σ ◦ σ ◦ ζ ◦ π 2 0 (x1, x2) = 3

  

2. Listas Simples

 3.Listas de Listas

 4. Arboles Binarios

En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, a cíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma solo existe un camino entre un par de nodos.

Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque'

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Existen tipos de árboles binarios que suelen usarse para fines específicos, como:

Árbol binario de búsqueda

Árbol de Fibonacci

Clasificación de Árboles Binarios

Existen cuatro tipos de árbol binario:.

• A. B. Distinto.
• A. B. Similares.
• A. B. Equivalentes.
• A. B. Completos.

A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

A. B. DISTINTO

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:

A. B. SIMILARES

Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Ejemplo:

A. B. EQUIVALENTES

Son aquellos árboles que son similares y que además los nodos contienen la misma información. Ejemplo:

A. B. COMPLETOS

Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.

5. Arboles Generales

Los arboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.

Los arboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas.

La definición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro  etc.. Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamados subárboles. Una forma particular de árbol puede ser la estructura vacía.

La figura siguiente representa a un árbol general.

Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos.

Los arboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro.