# Introducción \[...] # 1.1 ¿Qué es? \[...] # 2.1 ¿Qué es? \[...] # 2.2 Hashing La técnica Hashing consiste en un sistema de almacenamiento y búsqueda de elementos a través de una estructura de posiciones direccionables dado un campo clave del elemento llamado campo de dispersión ### 2.2.1 ¿Qué es Hashing? > In computing, a **Hash table (or Hashing)** is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A **Hash table** uses a **Hash function** to compute an **index**, also called a **Hash code**, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored. Tras leer la definición de WikiPedia, podríamos definir que en informática, una **tabla Hash** (o **Hashing**) es una estructura de datos que asocia a través de una **función Hash (H)** un **campo clave (campo de dispersión)** con un **elemento (K)** y es almacenado en una **dirección de memoria (A)**, como por ejemplo un **Array**. {% hint style="info" %} El termino **Hashing** también puede ser llamado: **Tabla hash, mapa hash, matriz asociativa, tabla de dispersión o tabla fragmentada**. {% endhint %} ### 2.2.2 Entendiendo la técnica Hashing La técnica **Hashing** consiste en un **sistema de almacenamiento y búsqueda de elementos** a través de una **estructura de posiciones direccionables** dado un **campo clave** del elemento conocido como **campo de dispersión**. El **campo de dispersión** se utiliza cómo **índice** para almacenar y recuperar el elemento completo. La **función Hash (H)** se aplica al **campo de dispersión de un elemento (K)** para obtener la **dirección de almacenamiento (A)**. * La función toma como entrada el valor del campo de dispersión del elemento. * La función devuelve cómo salida el espacio de almacenamiento asignado. **Fórmula matemática:** $$ H: K → A $$ Los problemas asociados a la técnica Hashing son: * Disponer de un número elevado de **elementos (K)** y un conjunto pequeño de **direcciones de almacenamiento (A)**. * Necesidad de una **función Hash (H)** que las relacione. ![](/files/-MC3RkFGLieABsBDom65) En la imagen, podemos ver que a un número "n" de **elementos (K)** se le aplica una **función Hash** a partir del **campo de dispersión (NIF)** y de esta forma obtener la **dirección de almacenamiento** en los **espacios de almacenamiento (A)**. Las funciones Hash tienen varias aplicaciones: * **Seguridad:** Se utiliza en criptografía, por ejemplo para la codificación de contraseñas, donde una contraseña **nunca** se debe guardar en **texto plano**. Normalmente a este tipo de encriptación se les denomina **Hashing Algorithm One Way**, es decir, solo tienen una dirección a partir de un texto inicial. * **Transporte de información.** * **Estructura de datos.** * **Correctores ortográficos.** * **Tablas de compiladores (basados en léxicos).** * **Diccionario de datos.** {% hint style="info" %} **Determinística**: significa que dada una misma entrada, siempre va a generar el mismo valor como salida. Es decir, que no depende de una variable externa (**transparencia referencial**). {% endhint %} Existen diferentes estrategias para la definición de funciones Hash: * Truncamiento. * Doblamiento. * Aritmética modular. * Otras funciones: * Funciones criptográficas: [MD5](https://en.wikipedia.org/wiki/MD5), [SHA-1, SHA-256](https://en.wikipedia.org/wiki/Secure_Hash_Algorithms), etc. * [Jenkins Hash Function](https://en.wikipedia.org/wiki/Jenkins_hash_function). * [Cuckoo Hash Function](https://en.wikipedia.org/wiki/Cuckoo_hashing). * [Robin Hood Hash](https://en.wikipedia.org/wiki/Hash_table#Robin_Hood_hashing). * [Rayuela (Hopscoth Hashing)](https://en.wikipedia.org/wiki/Hopscotch_hashing) #### 2.2.2.1 Truncamiento Ignorar una parte de la clave y considerar únicamente el resto. > H(2**3**945**6**6**7**) = 367 #### 2.2.2.2 Doblamiento Dividir directamente la clave en varias partes y combinar estas (sumas, restas, etc). Si el resultado es mayor al número de posiciones, se trunca. > H(**23***94***56***67*) = 23 + 94 + 56 + 67 = 240 #### 2.2.2.3 Aritmética modular Convertir la clave en un valor numérico entero (si no lo es) y calcular el resto (módulo). > H(23945667) = 23945667 mod 1000 = 667 #### **2.2.2.4 Caso práctico** 1\. Disponemos del siguiente registro: ``` class Client { int id; string name; string nif; } ``` 2\. El atributo **NIF** es elegido cómo **campo de dispersión**. 3\. La capacidad de almacenamiento es **A = \[0...99]**. Total 100 espacios de almacenamiento. 4\. Se decide elegir una **estrategia de Truncamiento** para la función Hash. 5\. La representación de la función Hash sería: **H(NIF) → \[0...99]** Por ejemplo, al realizar la función Hash obtenemos los dos últimos números del NIF y se utilizan cómo indice para su almacenamiento. * 0 → H(17951753) = 53 * 1 → H(18654123) = 23 * 2 → H(17621853) = 53 {% hint style="danger" %} Cómo podemos ver en el ejemplo, la técnica Hashing utilizada nos generaría un problema de colisión con los elementos (NIFs): 0 y 2. {% endhint %} ### 2.2.3 Problemas de colisión Si dos campos de dispersión de dos elementos diferentes generan un Hash que como resultado es el mismo indice, se dice que existe una **colisión**. Los registros no podrán ser almacenados en la misma posición. En estos casos, cuando una casilla está ocupada, la función Hash debe buscar otra ubicación a almacenar y hacerlo de tal forma que podamos buscarlo cuando se requiera. * Una función de cálculo H provoca colisión entre dos claves K1 y K2 si se cumple que **H(K1) = H(K2)**. * Una tabla Hash tiene que tener un tamaño suficientemente grande para reducir el número de colisiones. * Las colisiones suponen una penalización en la función Hash, porque se debe calcular en tiempo de ejecución y controlar las direcciones de almacenamiento libres implican mayor coste. * Cuando una función Hash no genera ninguna colisión, se dice que es perfecta. {% hint style="danger" %} Un problema bastante común que ocurre con las funciones Hash es el **aglomeramiento**. El aglomeramiento ocurre cuando la estructura de la función Hash provoca que claves usadas comúnmente tiendan a caer muy cerca unas de otras o incluso consecutivamente en la tabla Hash. Esto puede degradar el rendimiento de manera significativa, cuando la tabla se llena usando ciertas estrategias de resolución de colisiones, como la exploración lineal. {% endhint %} #### 2.2.3.1 Soluciones al problema de colisión Si la posición de un elemento ya esta ocupada, entonces hay que insertarlo en otra nueva mediante un proceso de **solución de colisiones**. {% hint style="warning" %} Es muy importante tener en cuenta donde ha sido almacenado el elemento con colisión para los procesos de búsqueda. {% endhint %} Existen varias técnicas de resolución de colisiones, pero las más populares son: * Técnica Hashing Cerrado: * Exploración lineal * Exploración cuadrática * Pruebas dependientes de clave. * Técnica Hashing Abierta: * Encadenamiento. Todas las alternativas a una colisión se pueden expresar mediante una función. Ejemplo: * En primer lugar, tenemos **H\[0] = H(K)**, dirección candidata para la **clave K**. * Si existe colisión, **se realiza un bucle en busca de una posición libre en la tabla Hash**, utilizando una **variable "i"** que se **inicia a 0** para iterar. Y se ejecuta la siguiente iteración, siendo **G(x, y)** una función de calculo de incremento: * **i = i + 1** * **H = G(K, i)** * La función **G(x, y)** dependerá del tipo de técnica de resolución de colisiones escogida. #### 2.2.3.1.1 Exploración lineal (Técnica Hashing Cerrado) Se trata la tabla Hash como una **estructura circular**, el siguiente elemento después del último es el primero. En el proceso de **inserción**, cuando ocurre una colisión se debe **recorrer la tabla Hash de forma secuencial y de forma circular a partir del punto de colisión, buscando el siguiente hueco libre**. En el proceso de búsqueda, si se produce colisión se **recorre la tabla Hash secuencialmente y de forma circular. El proceso concluye cuando el elemento es hallado, o bien se encuentra una posición vacía**. **Función G(K, i)** | Sin colisión | Colisión | | ---------------------------------- | ------------------------------------------ | | **H\[0] = H(K) = K mod nElements** | **H = G(K, i) = (H(K) + i) mod nElements** | **Ventajas** * Se exploran todas las direcciones. * Solo se produce un error si se ocupan todas las posiciones. **Desventajas** * Se producen agrupamientos alrededor de ciertas claves, mientras que otras zonas de almacenamiento permanecerían vacías. * Si las concentraciones de claves son muy frecuentes, la función Hash se verá muy penalizada y la búsqueda será principalmente secuencial perdiendo así las ventajas de la técnica Hash **(agrupamiento primario)**. {% hint style="info" %} El caso ideal es disponer de una tabla Hash cuyo tamaño sea el doble del número de elementos a insertar. El principal problema es que desperdicia mucha memoria. {% endhint %} #### 2.2.3.1.2 Exploración cuadrática (Técnica Hashing Cerrado) Similar a la exploración lineal, dispone de una **estructura circular** con un **desplazamiento de posición (inserción y búsqueda) del cuadrado del valor de la iteración actual**. **Función G(K, i)** | Sin colisión | Colisión | | ---------------------------------- | -------------------------------------------- | | **H\[0] = H(K) = K mod nElements** | **H = G(K, i) = (H(K) + i^2) mod nElements** | **Ventajas** * Evita el agrupamiento primario de la exploración lineal. **Desventajas** * No se evalúan todas las direcciones potencialmente libres. * Puede generar falsos negativos, disponer de posiciones libres e indicar que no las hay. * Mayor complejidad en la función Hash para calcular cuando a terminado el ciclo y conocer que se ha recorrido circularmente la tabla. * Aparece el **agrupamiento secundario**, las claves que colisionen en la misma posición seguirán el mismo camino de saltos, haciendo cada vez mayor su dirección de almacenamiento. #### 2.2.3.1.3 Dependiente de la clave (Técnica Hashing Cerrado) La estructura es conjunto ordenado de **asociaciones** entre una **clave "i"** y un **valor de datos**. $$ G(K,i) = G(i) $$ El caso perfecto consiste en que las claves sean únicas para que exista una relación uno a uno y evitar las colisiones. La solución reside en hacer que la exploración tras la colisión no dependa tan sólo de la posición inicial, sino también del propio valor de la clave. * De esta forma, claves distintas que han sido enviadas a la misma posición inicial seguirán rutas distintas tras la colisión. * Se consigue un mejor aprovechamiento de las posiciones vacías que existan en la tabla. Para obtener otro parámetro dependiente de la clave se necesita definir una **segunda función de dispersión**. Lo habitual es que la segunda función defina el salto en la exploración. **Función G(K, i)** | Sin colisión | Colisión | | ---------------------------------- | ---------------------------------------------- | | **H\[0] = H(K) = K mod nElements** | **H = G(K, i) = (H(K) + d · i) mod nElements** | Cada nuevo intento explora el hueco situado a una distancia **d** a la derecha. Si **d = 1** tendríamos una exploración lineal. El valor del salto **"d"** depende del valor de la clave. * Un método habitual de definirlo, si se utiliza como función de dispersión secundaria el método de división: **d = max(1, K div nElements)** Una exploración a base de saltos de **"d"** celdas no siempre recorrerá todas las celdas. Por ejemplo, si la tabla tiene tamaño 12 y el salto es 4, sólo vamos a recorrer las 3 celdas distintas antes de entrar en un ciclo. {% hint style="info" %} **Teorema:** Si **nElements** y **d** son primos entre sí se garantiza un recorrido completo. **Propuesta 1:** Imponer que nElements sea un número primo y d no sea múltiplo de nElements. Si hay que reestructurar la tabla para hacerla más grande, escoger el siguiente primo mayor que 2 x nElements. **Propuesta 2:** Imponer que nElements sea una potencia de dos, y que "d" sea un número impar (si es par, se le suma 1). {% endhint %} **Ventajas** * Velocidad y sencillez. **Desventajas** * Si **H(K1) = H(K2) = H\[0]**, siempre se producirá colisión para esas dos claves. #### **2.2.3.1.4 Encadenamiento** (Técnica Hashing Abierta) Los elementos que colisionan se van añadiendo a una lista asociada a la posición que colisiona. No se añaden registros, sino listas. Cada posición de la tabla se mantiene con una lista enlazada en la que se van insertando elementos cuyo valor Hash les asigna la misma posición. ![](/files/-MCXXSN0SCSTpMz5TKfD) #### **2.2.3.1.4.1 Caso práctico** Dada la siguiente secuencia de inserciones {17, 9, 13, 21, 23, 46, 6, 41}, calcula el factor de carga y representa la siguiente tabla Hash con n = 10 y H(K, 10) = K mod 10. **Solución:** ![](/files/-MCxG6Nr10KgFxH_Seye) ### 2.2.4 Eliminación Una posición vacía indica el final de una ruta de exploración. Si al borrar un elemento marcamos la casilla como vacía, entonces se rompen las rutas en las que éste elemento es un punto intermedio. Si la exploración no se detiene en las casillas vacías, las búsquedas fallidas recorrerían toda la tabla. El recolocar los elementos de las rutas rotas causaría nuevas recolocaciones en cascada de los elementos existentes. La solución para estos casos es **no eliminar el elemento, pero marcar la casilla como borrada** para que en la búsqueda no se encuentre. **2.2.4.1 Caso práctico** Hemos aprendido que una posición vacía indica el final de una ruta de exploración. Imaginemos que se quiere eliminar el valor 13 de la siguiente tabla: ![](/files/-MCXYmp2INe0HXEVElwF) Si al borrar el elemento, se marca la casilla como vacía, entonces se rompen las rutas en las que este elemento es un punto intermedio. Dejaría de ser accesible los elementos 22 y 23. Cómo solución, no eliminamos el elemento sino que marcamos la casilla cómo borrada para que la siguiente búsqueda no la encuentre. ![](/files/-MCXZNzOOF5A4wgJA3wo) ### 2.2.5 Eficiencia El **factor de carga** de una tabla Hash se calcula como: $$ α = N/M $$ Donde **N** es el **número de celdas ocupada** y **M** es el **tamaño de la tabla Hash**. **La probabilidad de que un nuevo registro colisione en el primer intento es igual al factor de carga** (suponiendo que todos los espacios de almacenamiento tienen la misma probabilidad de ser accedidos). **Contra mayor sea el factor de carga mas colisiones habrá**. El factor de carga comprende de 0 a 1. La probabilidad de colisión en el segundo intento es: $$ N(N-1) - (M(M-1)) $$ La probabilidad de colisión en el intento "i" es: $$ N(N-i ... N-(i+1)) - (M(M-i ... M(M-(i+1))) $$ Para números N y M grandes, la probabilidad de colisión en el intento "i" se toma aproximadamente cómo: $$ (N/M)^i $$ El **número de intentos antes de insertar** un registro se calcula: $$ 1 / (1 - α) $$ El **número de intentos antes de encontrar un registro** se calcula: $$ numAttempts = (1 / α) \* ln(1 / 1 - α) $$ ### 2.2.5 Rehashing (Redispersión) Cuando la tabla Hash se llena (o supera el umbral de inserción eficiente en las pruebas lineales, cuadraticas, etc) se degrada el rendimiento y es necesario una **redispersión**. La **redispersión** consiste en obtener una nueva tabla Hash con mayor capacidad de almacenamiento cuyo tamaño depende de la alternativa de colisión elegida. Ejemplo: Siguiente número primo, siguiente potencia de dos, etc. Es decir, aumentar el tamaño de la tabla para reducir el factor de carga. {% hint style="danger" %} Se deben pasar los valores de la antigua tabla Hash a la nueva. Por cada elemento en la vieja tabla, se calcula su nueva posición en la nueva y se inserta en ella. Si no se recolocan los valores ya insertados, se producirán errores a la hora de la búsqueda. {% endhint %} Normalmente, la redispersión se aplica cuando: * La ocupación de la tabla es superior al 50%. * Cuando se supera cierto número de colisiones. * Cada vez que hay una colisión. La redispersión, aunque necesaria, supone un alto coste: * Mayor uso de memoria dinámica. * Coste en tiempo de ejecución, debido a la recolocación de los elementos y del calculo del siguiente tamaño. {% hint style="info" %} También se puede realizar **redispersión inversa**. Acortar o reducir el tamaño de la tabla Hash cuando su ocupación es < 30 %. {% endhint %} ### 2.2.6 Conclusiones ¿Qué tipo de técnica Hashing es mejor? ¿Hashing cerrado (lineal, cuadrática, etc) o Hashing abierto (lista enlazada)? * Ambas tienen un tiempo de inserción y búsqueda O(n) para el peor caso. * Ambas tienen un tiempo de inserción y búsqueda O(α) para el caso medio, cuando (α < 1) * La técnica de Hashing cerrado usa menos espacio, pero necesita redispersión. Esta recomendado para datos almacenados en disco. * La técnica de Hashing abierta usa más espacio, pero no necesita de redispersión (utiliza memoria dinámica). Esta recomendado para datos almacenados en memoria. ### 2.2.7 Ejercicio final A partir de un nombre y apellido, por cada letra, conseguir el número binario y éste, pasarlo a decimal y realizar el módulo de 26. Insertarlo en una tabla Hash de 20 posiciones a través de la estrategia de truncamiento, obteniendo el último dígito. Si existe colisión, resolverlo mediante exploración cuadrática. * Calcula el factor de carga. * Probabilidad de colisión en el octavo intento. * Número de intentos antes de hacer una inserción. * Número de intentos para poder encontrar un dato. **Solución:** Nombre y apellido: **JOSÉ PELEATO** = K = 11 | Acción | Operación | | ----------------------------------------------- | ----------------------------------------------- | | Factor de carga | 11/20 = 0,55 = 55 % | | Probabilidad de colisión en el octavo intento | (11 - 7) / (20 - 7) = 4 / 13 = 0,3076 = 30,76 % | | Número de intentos antes de hacer una inserción | 1 / (1 - 0,55) = 2,222222222 = 2 | | Número de intentos para encontrar un dato | (1 / 0,55) \* ln(1 / (1 - 0,55)) = 1,4518 = 1 | | Letra | Binario | Decimal | Módulo 26 | Inserción | Operación | | ----- | -------- | ------- | --------- | ------------- | ------------------------------------- | | J | 01001010 | 74 | 2**2** | H(J) = 2 | - | | O | 01001111 | 79 | **1** | H(O) = 1 | - | | S | 01010011 | 83 | **5** | H(S) = 5 | - | | É | 11001001 | 201 | 1**9** | H(É) = 9 | - | | P | 01010000 | 80 | **2** | ~~H(P) = 2~~ | H(P) = 2 | | | | | | H(P) = 3 | H(P) = G(2, 1) = (2+1^2) mod 11 = 3 | | E | 01000101 | 69 | 1**7** | H(E) = 7 | | | L | 01001100 | 76 | 2**4** | H(L) = 4 | | | E | 01000101 | 69 | 1**7** | ~~H(E) = 7~~ | H(E) = 7 | | | | | | H(E) = 8 | H(E) = G(7, 1) = (7+1^2) mod 11 = 8 | | A | 01000001 | 65 | 1**3** | ~~H(A) = 3~~ | H(A) = 3 | | | | | | ~~H(A) = 4~~ | H(A) = G(3, 1) = (3+1^2) mod 11 = 4 | | | | | | ~~H(A) = 7~~ | H(A) = G(3, 2) = (3+2^2) mod 11 = 7 | | | | | | ~~H(A) = 1~~ | H(A) = G(3, 3) = (3+3^2) mod 11 = 1 | | | | | | ~~H(A) = 8~~ | H(A) = G(3, 4) = (3+4^2) mod 11 = 8 | | | | | | H(A) = 6 | H(A) = G(3, 5) = (3+5^2) mod 11 = 6 | | T | 01010100 | 84 | **6** | ~~H(T) = 6~~ | H(T) = 6 | | | | | | ~~H(T) = 7~~ | H(T) = G(6, 1) = (6+1^2) mod 11 = 7 | | | | | | H(T) = 10 | H(T) = G(6, 2) = (6+2^2) mod 11 = 10 | | O | 01001111 | 79 | **1** | ~~H(O) = 1~~ | H(O) = 1 | | | | | | ~~H(O) = 2~~ | H(O) = G(1, 1) = (1+1^2) mod 11 = 2 | | | | | | ~~H(O) = 5~~ | H(O) = G(1, 2) = (1+2^2) mod 11 = 5 | | | | | | ~~H(O) = 10~~ | H(O) = G(1, 3) = (1+3^2) mod 11 = 10 | | | | | | ~~H(O) = 6~~ | H(O) = G(1, 4) = (1+4^2) mod 11 = 6 | | | | | | ~~H(O) = 4~~ | H(O) = G(1, 5) = (1+5^2) mod 11 = 4 | | | | | | ~~H(O) = 4~~ | H(O) = G(1, 6) = (1+6^2) mod 11 = 4 | | | | | | ~~H(O) = 6~~ | H(O) = G(1, 7) = (1+7^2) mod 11 = 6 | | | | | | ~~H(O) = 10~~ | H(O) = G(1, 8) = (1+8^2) mod 11 = 10 | | | | | | ~~H(O) = 5~~ | H(O) = G(1, 9) = (1+9^2) mod 11 = 5 | | | | | | ~~H(O) = 2~~ | H(O) = G(1, 10) = (1+10^2) mod 11 = 2 | | | | | | ~~H(O) = 1~~ | H(O) = G(1, 11) = (1+11^2) mod 11 = 1 | **Representación:** ![](/files/-MD4Hquh-sOpvICDleMJ) {% hint style="danger" %} Cómo podemos ver, para el segundo caso de H(O), dado que hemos elegido la exploración cuadrática, no se podría realizar la inserción. Aun quedándose 9 espacios libres. {% endhint %} ### 2.2.8 Extra {% embed url="" %} {% embed url="" %} {% embed url="" %} ### 2.2.9 Bibliografía Referencias en español: 1. Curso Técnico Superior Universitario: Programación avanzada. [Ilerna Online](https://www.ilerna.es/es/fp-universidad/programacion-avanzada-tecnico-superior-universitario-484). 2. Grado en Ingeniería Informática. Temario: Backtraking y Hashing. [UCAM Murcia](https://online.ucam.edu/estudios/grados/informatica-a-distancia). 3. 4. Referencias en inglés: 1. 2. # 2.3 Recursividad Se llama recursividad (o recursión) a un proceso mediante el que una función se llama a sí misma de forma repetida, hasta que se satisface alguna determinada condición ### 2.3.1 ¿Qué es la Recursividad? > In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. En informática, podemos entender la **recursividad** cómo un método para resolver un problema donde la solución depende de soluciones a instancias más pequeñas del mismo problema. Tales problemas se pueden resolver por el uso de funciones que se llaman a sí mismas, además, se necesita identificar el caso final, la condición para finalizar el proceso, llamado **caso base**. Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea total. Las claves para construir un proceso de recursividad son: * Cada llamada recurrente se debería definir sobre un **problema de menor complejidad** (algo más fácil de resolver). * **Ha de existir al menos un caso base** para evitar que la recurrencia sea infinita. ### 2.3.2 Entendiendo la Recursividad Se llama **recursividad** (o **recursión**) a un proceso mediante el que una función se llama a sí misma de forma repetida, hasta que se satisface alguna determinada condición. La mayoría de los lenguajes de programación dan soporte a la **recursividad** permitiendo a una función llamarse a sí misma, de tal forma podríamos construir alternativas en los lenguajes imperativos a estructuras de bucles (loops) como while y for que son usadas para realizar tareas repetitivas. {% hint style="info" %} Podemos transformar en muchos casos los algoritmos recursivos en iterativos con más o menos dificultad y viceversa. {% endhint %} **Tipos de algoritmos recursivos:** * **Lineales**: Cada invocación genera una nueva invocación y sólo una, excepto la última. Ejemplo: Calcular el [factorial de un número](/algoritmia/recursividad#2-3-4-caso-practico-2-factorial-de-n). * **Múltiples**: Una misma invocación puede generar más de una invocación. Ejemplo: [Fibonacci](/algoritmia/recursividad#2-3-6-caso-practico-4-fibonacci). En general las soluciones recursivas son: * Menos eficientes que las iterativas. * Más claras y sencillas que las iterativas. > Lo correcto es; pensar en recursivo, implementar en iterativo. {% hint style="warning" %} A continuación se plantean una serie de casos prácticos para comprender la técnica de recursividad. Ejemplos basados en JavaScript. {% endhint %} ### 2.3.3 Caso práctico 1: Suma infinita desde N ```javascript sum = (num) => { console.log(num); sum(num + 1); } sum(10); ``` {% hint style="danger" %} Cómo se puede ver en este ejemplo, el algoritmo se ejecuta de forma infinita ya que no dispone de ninguna condición (caso base) para salir del proceso. Aquí podemos ver una implementación no acabada o mal planteada de la Recursividad. {% endhint %} ### 2.3.4 Caso práctico 2: Factorial de N ```javascript factorial = (num) => { return num === 0 ? 1 : num * factorial(num - 1); } const n = 10; const result = factorial(n); console.log(result); ``` ### 2.3.5 Caso práctico 3: Potencia de un número elevado a N ```javascript exponentiation = (base, exponent) => { return (exponent === 1) ? base : base * exponentiation(base, exponent - 1); } const base = 2; const exponent = 6; const result = exponentiation(base, exponent); console.log(result); ``` ### 2.3.6 Caso práctico 4: Fibonacci Programa recursivo que calcula la función de Fibonacci de un número N. El valor de la función de Fibonacci se obtiene de la siguiente manera: * Fibonacci(0) = 1 * Fibonacci(1) = 1 * Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) ```javascript fibonacci = (num) => { if (num === 0) return 1; if (num === 1) return 1; return fibonacci(num-1) + fibonacci(num-2); } const n = 10; for (let i = 0; i <= n; i++) { const result = fibonacci(i); console.log(`i: ${i} fibonacci: ${result}`); } ``` ### 2.3.7 Caso práctico 5: Torres de Hanoi \[...] ### 2.3.8 Bibliografía Referencias en español: 1. 2. 3. 4. 5. Referencias en inglés: 1. 2. # 2.4 Backtracking Backtracking es una estrategia algorítmica que busca todas las posibles soluciones dado un conjunto de variables inicial para encontrar el resultado definido por el problema ### 2.4.1 ¿Qué es Backtracking? > Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. **Backtracking** (o **vuelta atrás**) es una **técnica algorítmica para encontrar soluciones a problemas que tienen una solución completa**, en los que el orden de los elementos no importa, y en los que existen una serie de variables, a cada una de las cuales, debemos asignarle un valor teniendo en cuenta unas restricciones dadas. O lo que es lo mismo, es una **estrategia algorítmica que busca todas las posibles soluciones dado un conjunto de variables inicial** para encontrar el resultado definido por el problema. La técnica de **Backtracking** se apoya en el uso de la [recursividad](/algoritmia/recursividad) para la búsqueda exhaustiva de todas las combinaciones posibles. El termino fue utilizado por primera vez por el matemático [D.H. Lehmer](https://es.wikipedia.org/wiki/Derrick_Henry_Lehmer) en la década de 1950. ### 2.4.2 Explicando la técnica Backtracking con un caso práctico Dado un conjunto de números enteros {14, 10, 6} encontrar si existe algún subconjunto cuya suma sea igual a 20. ![](/files/-MDAy7s1NvWuXRljVc7M) ### 2.4.3 Entendiendo la técnica Backtracking **Backtracking** es una técnica algorítmica para hacer una búsqueda exhaustiva y sistemática por todas las configuraciones posibles del espacio de búsqueda del problema. Se suele aplicar en la resolución de un gran número de problemas, muy especialmente en los de **decisión** y **optimización**. * **Problemas de decisión**: Búsqueda de las soluciones que satisfacen ciertas restricciones. * Ejemplo: [Problema de las N-Reinas](/algoritmia/backtracking#2-4-5-caso-practico-el-problema-de-las-8-reinas). * **Problemas de optimización**: Búsqueda de la mejor solución en base a una función objetivo. * Ejemplo: [Problema de la mochila](/algoritmia/backtracking#2-4-7-extra). {% hint style="danger" %} **Los algoritmos de tipo Backtracking suelen ser muy ineficientes**. Aunque se utilizan para resolver problemas para los que no existe un algoritmo eficiente. Para mejorar la técnica de Backtracking se recomienda el uso de la programación paralela. {% endhint %} De forma general, el método del Backtracking, concebido como tal, genera todas las secuencias de forma sistemática y organizada, de manera que prueba todas las posibles combinaciones de un problema hasta que encuentra la correcta. En general, la forma de actuar consiste en elegir una alternativa del conjunto de opciones en cada etapa del proceso de resolución, y si esta elección no funciona (no nos lleva a ninguna solución), la búsqueda vuelve al punto donde se realizó esa elección, e intenta con otro valor. Cuando se han agotado todos los posibles valores en ese punto, la búsqueda vuelve a la anterior fase en la que se hizo otra elección entre valores. Si no hay más puntos de elección, la búsqueda finaliza. La técnica de Backtracking es usada en muchos ámbitos de la programación, por ejemplo, para el cálculo de expresiones regulares o para tareas de reconocimiento de texto y de sintaxis de lenguajes regulares. También es usado incluso en la implementación de algunos lenguajes de programación y da soporte a muchos algoritmos en inteligencia artificial. De forma matemática: * El conjunto de soluciones se expresa en tuplas, donde cada una es el valor de la solución. $$ s = (v\_1, v\_2, ... v\_n) $$ * El conjunto parcial de soluciones será aquel en que se encuentre en cierto nivel K: $$ s\_p = (v\_1, v\_2, ... v\_k) → K <= n $$ * Si se puede añadir un elemento más, la solución avanza a otro nivel (K+1). * Si no existe ningún valor, se retrocede al valor (K-1). * Se continua hasta que una solución parcial sea una solución al problema o hasta que no queden mas posibilidades a probar. El resultado es equivalente a hacer **una búsqueda en profundidad** en el árbol de soluciones. Sin embargo, este árbol es implícito, no se almacena en ningún lugar. Los hijos de un nodo del nivel K son las prolongaciones posibles al añadir una nueva etapa. Para examinar el conjunto de posibles soluciones es suficiente con recorrer el árbol construyendo soluciones parciales a medida que se avanza en el recorrido. **Los números de cada nodo marcan el recorrido del árbol.** Los **nodos hoja** representan que puede no haber una solución por ese camino y hay que volver atrás, o bien que es una solución. ### 2.4.4 Eficiencia La **eficiencia** consiste en la medida del coste en el uso de recursos que necesita el algoritmo para llevar a cabo su tarea. Los recursos más importantes son: * Tiempo de ejecución * Espacio de almacenamiento En conclusión, podemos decir que debido al coste creado en tiempo y memoria (por la pila recursiva) los algoritmos de vuelta atrás no son todo lo eficientes que deberían, y debemos dejarlos para resolver parte de otros problemas o problemas reducidos. Aún así, la gran ventaja que tienen es que si hay solución la encontrarán. **Ventajas:** * Si existe una solución, la calcula. * Es un esquema sencillo de implementar. * Adaptable a las características especificas de cada problema. **Desventajas:** * Coste exponencial en la mayoría de los casos. * Si el espacio de búsqueda es infinito, la solución, aunque exista, no se encontrará nunca. * Por termino medio consume mucha memoria al tener que almacenar las llamadas recursivas. **La aplicación del Backtracking antes de programar consiste en:** * Qué tipo de árbol es adecuado para el problema * ¿Cómo es la representación de la solución (tupla)? * Cómo generar un recorrido según el árbol * Generar un nuevo nivel. * Generar los niveles hermanos. * Retroceder en el árbol. * Determinar cómo es la forma del árbol de Backtracking, o lo que es lo mismo, cómo es la representación de la solución. * Elegir el esquema de algoritmo adecuado, adaptándolo en caso necesario. * Implementar las funciones genéricas para la aplicación concreta: según la forma del árbol y las características del problema. * Posibles mejoras usando variables locales con valores acumulados, realizar podas del árbol, etc. La medida se denomina **complejidad** del algoritmo y pueden ser agrupadas por soluciones: * **Dependencia del procesador:** Aunque fijemos el tamaño y los valores concretos del vector y el valor buscado, el algoritmo tardará tiempos distintos en ordenadores diferentes. * **Dependencia con el tamaño de la entrada:** No se tarda igual buscar en un vector de 10 elementos, que buscar en uno de 1.000.000. * **Dependencia de valores de la entrada:** Aunque fijemos el tamaño del vector, no se tarda lo mismo en buscar un valor que está en la primera posición que otro que no esté en el vector. #### 2.4.4.1 Dependencia del procesador * No medir tiempo en segundos, sino en número de operaciones elementales ejecutadas. **Operación elemental:** Toda operación que tarda un tiempo constante en cualquier procesador razonable. Tipicamente se consideran elementales las asignaciones, operaciones aritméticas y relacionales con tipos de datos de tamaño fijo, acceso a arrays. En general se cuenta solo con un tipo de operación concreta, la más relevante para la eficiencia del algoritmo. Es una medida independiente del procesador. #### 2.4.4.2 Dependencia con el tamaño de la entrada * Uno o más valores relacionados con los datos de entrada que sirven de parámetros para expresar las funciones que miden el uso de recursos del algoritmo. * En el caso de algoritmos que trabajan sobre colecciones de datos, suele ser el número de datos que contienen. * Para algoritmos de cálculo con enteros de tamaño arbitrario, se suele usar el número de bits de esos enteros. Se tratan cómo un array de bits. * Expresar la complejidad no mediante un valor sino por una función cuyo parámetro(s) es el tamaño de la entrada. * El tamaño de la entrada, si es un único valor, se suele denominar n. * La complejidad temporal se denominará mediante la función T(n). * La complejidad espacial se denominará mediante la función E(n). * De esa función nos interesa, más que su forma concreta, su ritmo de crecimiento. #### 2.4.4.3 Dependencia de valores de la entrada. * Dividir el análisis en casos. * Analizar subconjuntos de las entradas cuya complejidad es la misma para todas las entradas de ese subconjunto (análisis de peor y mejor caso). * Calcular un promedio, dado una distribución estadística de las entradas. Tipicamente se supone que todas las posibles entradas son equiparables (Análisis de caso promedio y tiempo amortizado). **Cota superior (Análisis del peor caso)** * Calcula la complejidad del algoritmo para las entradas (del mismo tamaño) que maximizan la complejidad. $$ Tworst (n) = max\[T(n, input)] $$ **Cota inferior (Análisis en el mejor caso)** * Calcula la complejidad del algoritmo para las entradas (del mismo tamaño) que minimizan la complejidad. $$ Tbest (n) = min\[T(n, input)] $$ ### 2.4.5 Búsqueda secuencial * **Operación elemental:** Elegimos contar comparaciones en las que intervenga un elemento del vector. * **Tamaño de la entrada:** Elegimos tomar como tamaño de entrada el número de elementos del vector. * **Cota superior (Análisis del peor caso):** Para vectores de tamaño n, las entradas que hacen que el algoritmo trabaje más son aquellas en que el valor buscado no se encuentra en el vector. $$ T\_w = n $$ * **Cota inferior (Análisis del mejor caso):** Las entradas que hacen que el algoritmo trabaje menos son aquellas en que el valor buscado está en la primera posición del vector. $$ T\_b = 1 $$ ### 2.4.6 Árboles de búsqueda Cómo ya hemos comentado anteriormente el algoritmo de vuelta atrás proporciona una manera sistemática de generar todas las posibles soluciones siempre que se puedan resolver por etapas, lo que se asemeja mucho a una búsqueda combinatoria (probar todas la posibles combinaciones). Para conseguir este estudio tan exhaustivo del problema, se considera que se trabaja con un árbol (figura 1) que cuya existencia es sólo implícita, para nosotros cada nodo del nivel k representa una parte de la solución y nuestro árbol estará formado por las K etapas que se considerarán ya realizadas. ![Figura 1: Árbol de búsqueda](/files/-MDefSKHLeJCWmWrWD6z) La búsqueda realizada sobre el árbol es una búsqueda en profundidad. En el transcurso de la búsqueda si se encuentra un estado incorrecto, se ha de retroceder hasta la decisión anterior y si existe uno o más caminos aún no explorados que puedan conducir a la solución, el recorrido del árbol continúa por uno de ellos (hijos si nos referimos a un árbol). Si no quedasen más alternativas la búsqueda fallaría y el problema no tendría solución. En este caso en el que consideramos el problema en forma de árbol, la solución sería un camino que llevara desde el nodo raíz hasta uno nodo hoja, y las soluciones parciales llevarían desde el nodo raíz a los nodos interiores del árbol. ### 2.4.7 Notación asintótica * Dada una función **f(n)** la notación **O(f(n))** representa al conjunto de funciones con la siguiente propiedad: ![](/files/-MDLQcQmdjvvlvd6lE8O) *Cuando **g(n)** pertenece a las cotas superiores de **f(n)**, si y solo si, existe un **n(sub-cero)** que pertenece al conjunto de número naturales positivos y existe un **c** que pertenece al conjunto de reales positivos, tal que, para todo **n**, ese **n** tiene que ser mayor a ese **n(sub-cero)**, que cumpla que **g(n)** sea menor o igual que **c** por **f(n)**.* * El conjunto **O(f(n))** se denomina conjunto de cotas superiores generado por **f(n)**. * Toda función que pertenece a **O(f(n))** se dice que está acotada superiormente por **f(n)**. * El conjunto **O(f(n))** representa a las funciones que: * Tienen un ritmo de crecimiento igual o menor que **f(n)**. * No importa las constantes de proporcionalidad (positivas) por las que esté multiplicaba la función (podemos ajustar el valor de **c** en la definición). * Solo importa el comportamiento para valores de **n** grandes, con tendencia a infinito. ![](/files/-MDLQlpS_Ujl3BDQPmAv) ### 2.4.8 Branch & Bound **Branch & Bound (Ramificación y poda)** consiste en una variante del esquema de Backtracking. Se define como un método capaz de **buscar más rápido** las **soluciones de un problema**, aplicando **estrategias de exclusión (poda)** en los nodos que no conducen a una solución optima, **en base a un coste asociado al nodo**. Basado en un recorrido del **árbol de expansión (en profundidad)**, se aplica sobre todo a problemas de optimización. Las estrategias para encontrar la soluciones más optimas se denomina **poda (pruning)**. Una poda consta de cotas que permiten excluir de la búsqueda ramas que no conducen a una solución (se evita ramificar nodos). Para determinar que nodo va a ser ramificado, dependiendo de la estrategia, necesitamos una estructura capaz de almacenar aquellos nodos pendientes de ser analizados **(Lista de Nodos Vivos, LNV)**. Un nodo vivo en el árbol es el que tiene posibilidades de ser ramificado, es decir, el que ha sido creado y no ha sido explorado, ni podado todavía. La LNV contiene nodos pendientes de tratar por el algoritmo. #### 2.4.8.1 Estrategias de ramificación En un algoritmo de ramificación y poda se realizan tres etapas: 1. **Etapa de selección:** Se encarga de extraer un nodo de la LNV. La forma de escogerlo depende de la estrategia de ramificación. 2. **Etapa de ramificación:** Se generan los posibles hijos del nodo seleccionado en la etapa anterior. 3. **Etapa de poda:** Se estudian los nodos generados en la etapa de ramificación. Solo aquellos que pasan cierto filtro se introducen en la LNV. El resto de nodos son podados. El recorrido del árbol depende de cómo se gestiona la LNV. Existen tres tipos: * **Recorrido en profundidad - LIFO (Last in, first out):** La lista se trata como una pila. ![](/files/-MDdXt-vTA6NcwfbEmch) * **Recorrido en anchura - FIFO (First in, first out):** La lista se trata como una cola. ![](/files/-MDVrl6BKgfPHjY60AOm) * **Estrategia de mínimo coste (nodo más prometedor):** Se utiliza una cola con prioridades para almacenar nodos ordenados por su coste. Entre todos los nodos de la lista de nodos vivos, elegir el que tenga mayor beneficio (o menor coste) para explorar a continuación. En caso de empate (de beneficio o coste estimado) deshacerlo usando un criterio FIFO o LIFO. * **Estrategia coste FIFO:** Seleccionar de la LNV el que tenga mayor beneficio y en caso de empate escoger el primero que se introdujo. * **Estrategia coste LIFO:** Seleccionar de la LNV el que tenga mayor beneficio y en caso de empate escoger el último que se introdujo. {% hint style="info" %} El objetivo es utilizar la estrategia que permita encontrar la solución más rápido. {% endhint %} #### 2.4.8.2 Estrategias de poda Para cada nodo establecemos una estimación de la mejor solución posible a partir de él (cota). Las cotas determinan cuando se puede realizar una poda del árbol, si el valor de la cota es peor que la mejor solución obtenida hasta ese momento, no se exploran sus hijos. Para cada nodo "i" podemos tener: * Cota inferior(i) de la mejor solución alcanzable a partir del nodo "i". * Cota superior(i) de la mejor solución alcanzable a partir del nodo "i". * Estimación del beneficio (o coste) que se puede encontrar a partir de ese nodo. Se puede obtener a partir de las cotas, usar la media o una de ellas. Si M(i) es la mejor solución alcanzable a partir del nodo "i", se debe verificar lo siguiente: $$ CotaInferior(i) <= M(i) <= CotaSuperior(i) $$ #### 2.4.8.3 Tiempo de ejecución El tiempo de ejecución de un algoritmo de B\&B depende de: * **El número de nodos recorridos**, dependencia de la efectividad de la poda. * **El tiempo empleado en cada nodo**, tiempo necesario para hacer las estimaciones e coste y gestionar la lista de nodos vivos en función de la estrategia de ramificación. En el **peor caso**, el tiempo de un algoritmo B\&B será igual al de un algoritmo de Backtracking (o peor incluso, si tenemos en cuenta el tiempo que requiere la LNV). En el **caso promedio**, se suelen obtener mejoras con respecto a Backtracking. La "clave" consiste en buscar un equilibrio en la precisión con respecto a Backtracking. * **Muy precisas:** Mayor poda, se recorren menos nodos, pero aumenta el tiempo en realizar estimaciones. * **Poco precisas:** Menor poda, se recorren más nodos, pero disminuye el tiempo de las estimaciones. ### 2.4.9 Backtracking vs. Branch & Bound En **Backtracking**, tan pronto como se genera un nuevo hijo del nodo en curso, dicho hijo pasa a ser el nodo en curso. En **B\&B**, se generan todos los hijos del nodo en curso antes de que cualquier otro nodo vivo pase a ser el nuevo nodo en curso (no se realiza un recorrido en profundidad por defecto). En consecuencia: * En Backtracking, los únicos nodos vivos son los que está en el camino de la raíz al nodo en curso. * En B\&B puede haber más nodos vivos que en Backtracking, que se almacenan en una lista de nodos vivos. En Backtracking, el test de comprobación realizado por la funciones de evaluación nos indica únicamente si un nodo concreto nos puede llevar a una solución o no. En B\&B, sin embargo, se acota el valor de la solución a la que nos puede conducir un nodo concreto, de forma que esta acotación nos permite: * Podar el árbol (si sabemos que no nos va a llevar a una solución mejor de la que ya tenemos). * Establecer el orden de ramificación (de modo que comenzaremos explorando las ramas mas prometedores del árbol). ### 2.4.10 Caso práctico Backtracking: El problema de las 8-Reinas El problema de las **n-Reinas (N-Queens)** es un juego cuyo objetivo consiste en colocar **n-reinas en una tablero de ajedrez (n\*n) sin que se amenacen entre ellas según las normas del ajedrez** (que no estén en la misma fila, columna o diagonal). **Restricciones explicitas:** $$ s\_i = \[1, 2, 3, 4, 5, 6, 7, 8] → 1 <= i <= 8 $$ $$ |s\_i|^8 = 8^8 = 16.777.216 $$ **Restricciones implícitas:** Podemos deducir que cada reina se ha de colocar en una columna, partiendo del caso inicial que la reina "i" se colocara en la fila "i". * Las restricciones para este problema consiste en que dos reinas no pueden colocarse en la misma fila. $$ (y\_i, y\_j) → y\_i <> y\_j $$ * Todas las reinas deben estar en columnas diferentes: $$ (x\_i, x\_j) → x\_i <> x\_j $$ * Todas las reinas deben estar en diagonales diferentes: $$ (x\_i, x\_j) → |j-i| <> |x\_j-x\_i| $$ Gracias a la primera restricción implícita podemos decir que todas las soluciones son permutaciones de {1, 2, 3, 4, 5, 6, 7, 8}, lo que reduce el espacio de soluciones a 8! = 40320. **1º Paso: Representación de la solución** Utilizaremos un vector de n elementos, donde el valor del indice sera la columna y el valor la posición de la fila. El valor -1 significará celda no ocupada. ![](/files/-MDAuLvPWDRsC1RX57Sx) **2º Paso: Representación del árbol** ![](/files/-MDB0nhMvCoAUPTn0Ja8) **3º Paso: Codificación** Ejemplo en pseudocódigo: ```c const n = 8; function validation(solution=array[n] of int, k: int): boolean { for i=0 to k-1 DO // absoluteValue = |x-y| if (solution[i] === solution[k] or absoluteValue(solution[i], solution[k]) === absoluteValue(i, k)) then return false; end end return true; } function nQueens(solution=array[n] of int, stage: int): boolean { if stage > n then return false; success = false; solution[stage] = 0; repeat solution[stage] = solution[stage] + 1; if validation(solution, stage) then if stage <> n THEN success = queens(solution, stage + 1); else success = true; end end until (solution[stage] === n) OR success === true; return success; } ``` Ejemplo en JavaScript: ### 2.4.11 Caso práctico B\&B {% file src="/files/-MFX0m3g8MtYZcqJ\_ygJ" %} backtracking\_branch\_bound {% endfile %} ### 2.4.12 Otros casos prácticos Otros problemas que se pueden resolver con Backtracking: 1. [Problema de la mochila](https://es.wikipedia.org/wiki/Problema_de_la_mochila). 2. Problema del laberinto. 3. [Problema del salto de caballo](https://es.wikipedia.org/wiki/Problema_del_caballo). 4. [Problema de los cuadrados mágicos](https://es.wikipedia.org/wiki/Cuadrado_m%C3%A1gico). 5. Sudoku ### 2.4.13 Extra {% embed url="" %} {% embed url="" %} {% embed url="" %} ### 2.4.14 Bibliografía Referencias en español: 1. Curso Técnico Superior Universitario: Programación avanzada. [Ilerna Online](https://www.ilerna.es/es/fp-universidad/programacion-avanzada-tecnico-superior-universitario-484). 2. Grado en Ingeniería Informática. Temario: Backtraking y Hashing. [UCAM Murcia](https://online.ucam.edu/estudios/grados/informatica-a-distancia). 3. 4. [El esquema algorítmico del Backtracking](https://openlibra.com/es/book/el-esquema-algoritmico-del-backtraking) Referencias en inglés: 1. # 2.5 Algoritmos de búsqueda ### 2.5.1 ¿Qué es un algoritmo de búsqueda? \[...] ### 2.5.2 Búsqueda lineal \[...] ### 2.5.3 Búsqueda binaria \[...] ### 2.5.4 Árboles de búsqueda binarios (ABB) \[...] ### 2.5.5 Árboles de búsqueda binarios balanceados (AVL) \[...] ### 2.5.6 Patrones de búsqueda \[...] ### 2.5.X Extra {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} {% embed url="" %} ### 2.5.Y Bibliografía Referencias en español: 1. Curso Técnico Superior Universitario: Programación avanzada. [Ilerna Online](https://www.ilerna.es/es/fp-universidad/programacion-avanzada-tecnico-superior-universitario-484). 2. Grado en Ingeniería Informática. Temario: Backtraking y Hashing. [UCAM Murcia](https://online.ucam.edu/estudios/grados/informatica-a-distancia). 3. Referencias en inglés: 1. # 2.6 Algoritmos de clasificación \[...] ### 2.6.X Extra {% embed url="" %} {% embed url="" %} ### 2.5.Y Bibliografía Referencias en español: 1. Curso Técnico Superior Universitario: Programación avanzada. [Ilerna Online](https://www.ilerna.es/es/fp-universidad/programacion-avanzada-tecnico-superior-universitario-484). 2. Grado en Ingeniería Informática. Temario: Backtraking y Hashing. [UCAM Murcia](https://online.ucam.edu/estudios/grados/informatica-a-distancia). 3. Referencias en inglés: 1. # Diccionario \[...]