COMPUTABILIDAD DE PROBLEMAS

COMPUTABILIDAD DE PROBLEMAS

La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con la llamada máquina de Turing. La teoría de la computabilidad se interesa por cuatro preguntas:

• ¿Qué problemas puede resolver una máquina de Turing?
• ¿Qué otros formalismos equivalen a las máquinas de Turing?
• ¿Qué problemas requieren máquinas más poderosas?
• ¿Qué problemas requieren máquinas menos poderosas?

La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.

FUNCIONES RE CURSIVAS

 Se dice que una función es recursiva cuando el cuerpo de la función utiliza a la propia función. Dentro de una función recursiva suelen distinguirse dos partes: 
 -   Los casos base: Son aquellos que para su solución no requieren utilizar la función que se está definiendo. 
 -   Los casos recursivos: Son aquellos que sí que requieren utilizar la función que se está definiendo. 
Las definiciones recursivas funcionan siempre y cuando las llamadas recursivas se realicen de forma que en algún momento se lleguen a los casos base.

Una función es recursiva final cuando tras la llamada recursiva no hay que realizar ningún cómputo adicional. Es decir, el valor devuelto en la llamada recursiva es igual al valor que debe devolver la función.

Ejemplos

    Para calcular el factorial de un número se distinguen dos casos: si el número es cero o si es mayor. El primer caso es un caso base, pues sabemos que la solución es 1, mientras que para el resto de los casos utilizaremos una llamada recursiva. La distinción de casos puede realizarse por cualquiera de los 4 métodos que conocemos. Veámoslo por ejemplo con el uso de patrones:

    fact 0 = 1
    fact n = n * fact (n-1)
Nótese que la recursión terminará para cualquier valor de entrada positivo, pues en cada llamada recursiva el parámetro se va decrementando, hasta que en algún momento llegue a valer 0. Nótese también que la recursión no es final, pues tras la llamada recursiva es necesario multiplicar el valor obtenido por el parámetro de entrada.
La función anterior puede convertirse en final si se añade un parámetro acumulador:
    fact n = fact' n 1
    fact' 0 acum = acum
    fact' n acum = fact' (n-1) (n*acum)
La recursión es una estrategia muy potente cuando se utilizan listas. Veamos por ejemplo cómo calcular la longitud de una lista:
    long [] = 0
    long (x:xs) = 1 + long xs
Nótese que la distinción de casos se hace en base a si la lista es vacía o no. Sabemos que la definición termina porque en cada llamada recursiva se reduce en una unidad la longitud de la lista, por lo que en algún momento llegará a estar vacía.

Errores típicos:

• El orden de las alternativas es muy importante en presencia de funciones recursivas, pues un orden erróneo puede provocar que la recursión no termine nunca.
• Al definir una función por patrones, es posible equivocarse al escribir el nombre de la función en alguna de las definiciones. En dicho caso, la función fallará, y si ha afectado a los casos base, posiblemente no terminará.

          Funciones re cursivas Parciales

Decimos que la función parcial: Ψ se define por minimización sobre la función parcial φ si: ψ(x)={min{z|φ((x,z))=1∧∀ω<z(φ((x,ω))↓)} si este conjunto es no vacío; ↑ en otro caso.

Definimos las funciones recursivas parciales como aquellas que se pueden obtener a partir de las funciones básicas, combinándolas mediante composición, formación de pares y minimización.

La definición de minimización puede extenderse al caso en que partimos de una función parcial. A veces, denotaremos la función resultante también como ψ=μφ, pero evitaremos la notación ψ(x)=μz[φ(x,z)=1], que sugiere menos condiciones de las precisadas en la definición. Si imaginamos que intentamos calcular su valor por una búsqueda lineal, podemos intuir que no conseguiremos respuesta en dos ocasiones: cuando el objeto buscado no existe, o cuando uno inferior al provoca una búsqueda indefinida que no para, y así nos hace dudar de cual es realmente él mínimo. De nuevo, una familia F es cerrada por minimización sí, para cualquier función φ∈F, la función ψ=μφ que se define por minimización sobre φ pertenece a F.

Definición: Sea F adecuada. La familia de las funciones "recursivas parciales en F" es la menor familia de funciones parciales que contiene a F y es cerrada por composición, por minimización y por formación de pares.

Las siguientes funciones siempre son recursivas parciales en F, cuando F es adecuada: las funciones básicas, las constantes, las proyecciones, la función signo, las de comparación según el orden y de igualdad, la conjunción, la disyunción y la negación entre predicados, el cociente y el resto de la división entera por defecto. Cuando las funciones de F sean únicamente las básicas, omitiremos la expresión "en F", y diremos únicamente "funciones recursivas parciales". Será equivalente, entonces, decir "funciones calculables parciales" o "simplemente funciones calculables". La subclase de las funciones "recursivas totales" en F esta formada por aquellas que resulten ser funciones totales de entre las funciones recursivas parciales en F. Del mismo modo, son predicados recursivos aquellos que corresponden a funciones características que sean recursivas parciales (obviamente totales).

          Funciones re cursivas Primitiva

La variable o argumento de una función recursiva primitiva es un número natural o una n-tupla de números naturales (i₁, i₂,..., i_n), mientras que el resultado o valor de la función es un número natural. Una función recursiva primitiva es n-aria si toma como argumento o variable n-uplas de números naturales. El conjunto de las funciones primitivas recursivas se define según las siguientes reglas:

1. Para todo k >= 0, la función cero k-aria definida como zero_k(n₁, n₂, ..., n_k) = 0, para todo número natural n₁, n₂, ..., n_k, es primitiva recursiva.
2. La función sucesor S, de aridad 1, que produce el siguiente entero según los axiomas de Peano, es primitiva recursiva.
3. Las funciones de proyección P_iⁿ, de aridad n que producen como resultado su argumento de la posición i son primitivas recursivas.
4. Composición: Dadas f, una función primitiva recursiva de aridad k, y g₁,...,g_k, funciones primitivas recursivas de aridad n, la composición de f con g₁,...,g_k, es decir, la función h(x₁,...,x_n) = f(g₁(x₁,...,x_n),...,g_k(x₁,...,x_n)), es primitiva recursiva.
5. Recursión primitiva: Dadas f, una función primitiva recursiva de aridad k, y g, una función primitiva recursiva de aridad k+2, la función h de aridad k+1 definida como h(0,x₁,...,x_k) = f(x₁,...,x_k) y h(S(n), x₁,...,x_k) = g(h(n, x₁,...,x_k), n, x₁,...,x_k), es primitiva recursiva.

Se puede notar que las funciones de proyección permiten contrarrestar la rigidez impuesta por la paridad de las funciones en la definición anterior, dado que en la composición se puede pasar cualquier subconjunto de los argumentos.

Una función es primitiva recursiva si es la función constante cero, la función sucesor, una proyección o si se define a partir de funciones primitivas recursivas utilizando únicamente composición y recursión primitiva.

LISTAS SIMPLES

Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un indice sino mediante un puntero. 
La asignación de memoria es hecha durante la ejecución. 

En una lista los elementos son contiguos en lo que concierne al enlazado.

En cambio, mientras que en un array los elementos están contiguos en la memoria, en una lista los elementos están dispersos. El enlace entre los elementos se hace mediante un puntero. En realidad, en la memoria la representación es aleatoria en función del espacio asignado. 

El puntero siguiente del último elemento tiene que apuntar hacia NULL (el fin de la lista). 

Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el puntero Siguientepermite el cambio hacia el próximo elemento. 
El desplazamiento se hace en una sola dirección, del primer al último elemento. 
Si deseas desplazarte en las dos direcciones (hacia delante y hacia atrás) deberás utilizar las listas doblemente enlazadas. 

LISTA DE LISTAS

En ciencias de la computación, una lista de listaa es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales ?¿!"?¿67qAHDF al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

Una lista enlazada es un tipo de dato autorreferenciado porque contienen un puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: listas enlazadas simples, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares.

Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp, Scheme y Haskell tienen estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.

ARBOLES BINARIOS

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, ací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

ARBOLES GENERALES

Los arboles representan las estructuras no lineales y dinámicas de datos más importantes encomputación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de unprograma. 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 sonarreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas.Ladefinición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colecciónde elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea unarelación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor,sucesor, ancestro, etc.. 

Un vídeo pequeño que explica un poco sobre el tema gggg..................