Introducción, búsquedas y programación dinḿica

Anxo López Rodríguez

Introducción, búsquedas y programación dinḿica

Algoritmos | 2ºGRIA

Un algoritmo es un conjunto finito y ordenado de pasos o instrucciones precisas que permiten resolver un problema o realizar una tarea, es decir, llegar a su resultado o solución. Los algoritmos son las bases de los programas, ya que no dejan de ser un algoritmo en leguaje máquina. No obstante, los algoritmos existieron ya desde antes de la informática. Por ejemplo:

Con respecto a las computadoras, los algoritmos son secuencias formalizadas y precisas que una computadora puede entender y ejecutar. Todos los programas estan construidos sobre ellos y se traducen en lenguajes de programación para su ejecucion. Se caracterizan por ser claros, eficientes (Resolución en tiempo razonable y pocos recursos) y ser generales (Vale para una familia de problemas). Hay varios tipos de algoritmos:

En este caso nos vamos a centrar en los de búsqueda.

La búsqueda es un proceso de encontrar un elemento ovjetivo dentro de un grupo de elementos o determinar su inexistencia. El objetivo para su optimización es minimizar el numero de comparaciones lo máximo posíble. Las busquedas pueden ser internas (Memoria principal) y Externa (Memoria secundaria). Hay varios tipos de búsqueda:

Búsqueda lineal

El tipo mas sencillo, compara uno a uno los elementos hasta encontrar el necesario o revisar sin éxito. Complejidad O(n). Ejemplo: Busco 5 en [1, 4, 5, 6, 7, 9]

public static int bus_lineal(int[] valores, int buscar) {
    for (int i = 0; i < valores.length; i++) {
        if (valores[i] == buscar) {
            return i; // ¡Encontrado!
        }
    }
    return -1; // No encontrado
}

// Exemplo de uso:

int[] datos = {5, 12, 7, 9, 3};
int posicion = bus_lineal(datos, 9);
System.out.println("Resultado de la búsqueda: " + posicion);

Búsqueda binaria

Deben de estar ordenados los elementos. Disminuye progresivamente el nº de elementos sobre el que se realiza la busqueda a la mitad. TRas log2n divisiones se locaiza el elemento o se sabe que no está. Complejidad O(log n). Ejemplo: Busco 1 en [1, 4, 5, 7, 9]


public static int bus_binaria(int[] valores, int buscar) {
    int izq = 0, dcha = valores.length - 1;
    while (izq <= dcha) {
        int med = (izq + dcha) / 2;
        if (valores[med] == buscar) return med;
        if (valores[med] < buscar) izq = med + 1;
        else dcha = med - 1;
    }
    return -1; // No encontrado
}

//Se atopa o valor, imprime a posición:
System.out.println(bus_binaria(new int[]{1, 3, 5, 7, 9, 11}, 7));

Búsqueda mediante hashing

Es un tipo de búsqueda que emplea funciones hash, tranforma un elemento en una dirección o índice situado dentro del array.

Una función hash es una regla matemática que transforma una entrada en un valor, que suelen ser números enteros. Esta entrada puede ser un texto, otro número…

Una clave es el objeto que empleas para acceder a un valor. Por ejemplo en ‘map.put(“58966854I”, “Anxo”)’ la clave sería 58966854I.

El valor obtenido al transformar la clave se denomina HashCode, se calcula usando el método ‘hashCode ()’ y reflejará la posicion del elemento dentro de una tabla hash (La estructura donde se almacenan estos elementos). Si dos elementos tienen el mismo HashCode se produce una colisión.

La posición de la tabla hash donde se guarda el par clave-valor se llama bucket. Para ver en que bucket cae una clave, el HashCode se transforma en un índice y se sigue esta formula: ‘int bucketIndex = hash & (capacity - 1)’. El razonamiento que emplea la formula es el siguiente:

Las ventajas de este sistema es que los elementos no tienen por que estar ordenados y que es independiente al número de elementos. En la mayor parte de los casos se emplea la clave como el índice de cada registro. La eficiencia del método depende de como de uniforme distrubuye nuestra función hash los elementos.

Ejemplo:

import java.util.HashMap;

public class HashSearchExample2 {
    public static void main(String[] args) {
        HashMap<Integer, String> estudiantes = new HashMap<>();
        estudiantes.put(101, "Ana");
        estudiantes.put(202, "Luis");
        estudiantes.put(303, "María");

        // Buscar
        int id = 202;
        if (estudiantes.containsKey(id)) {
            System.out.println("Alumno encontrado: " + estudiantes.get(id));
        } else {
            System.out.println("Alumno no registrado");
        }
    }
}

Para evitar colisiones, se emplean técnicas como truncamiento (Uso los X últimos dígitos de la clave como índice), División (Siendo m el tamaño de la tabla y k la clave, calculo $ℎ(𝑘) = 𝑘 mod 𝑚 $. Por ejemplo: Clave 21 tamaño 10 sería 1) o mediante potencias (Se eleva la clave a un número y se utilizan números del medio. Por ejemplo $589² = 346921 \Longrightarrow 469 $ si cogemos los 3 números del medio).

Programación Dinámica

Técnica de diseño de algoritmos utilizada para resolver problemas que pueden dividirse en subproblemas más pequeños que se repiten. Tiene como objetivo reducir el tiempo de ejecución evitando recalcular soluciones previas. La programación dinámica almacena los resultados mediante un proceso denominado “memorización” o “almacenamiento en tabla”, a diferencia de los algoritmos recursivos clásicos. Este proceso es útil pero se debe equilibrar la optimización de tiempo y espacio según las necesidades del problema, ya que en el caso contrario se puede demasiado almacenamiento. La PD solo funciona cuando el problema completo puede construirse a partir de las soluciones óptimas de sus subproblemas, lo que se denomina subestructura óptima. Hay varios tipos de diseño:

Recursividad

Un método recursivo es aquel que se resuelve llamándose a sí mismo con una versión más simple del problema. Para que funcione:

Ejemplo:

public static int factorial(int n) {
    if (n == 1) {
        return 1; 
    }
    return n * factorial(n - 1);
}