Algoritmos y Estructura de Datos

1. Semana 01 — Serie de Padovan

La serie de Padovan es una sucesión de números naturales definida por los valores iniciales P(0)=P(1)=P(2)=1, y la relación de recurrencia para n ≥ 3: P(n) = P(n−2) + P(n−3).

Pseudocódigo:

Inicializar P(0) = 1
Inicializar P(1) = 1
Inicializar P(2) = 1
Para n desde 3 hasta N hacer:
    P(n) = P(n-2) + P(n-3)
Imprimir los valores P(0) a P(N)

2. Entrega 03 — Lista enlazada y Fibonacci recursivo

Ejercicio: Lista enlazada — borrar nodo en posición específica

Función deleteNode(position) sobre la clase LinkedList:

• Operación: Borra un nodo en la posición que se pasa por parámetro.
• Coste temporal: O(N) donde N es el número de nodos a recorrer.

Código:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def deleteNode(self, position):
        if self.head is None:
            return
        if position == 0:
            self.head = self.head.next
            return self.head
        index = 0
        current = self.head
        prev = self.head
        temp = self.head
        while current is not None:
            if index == position:
                temp = current.next
                break
            prev = current
            current = current.next
            index += 1
        prev.next = temp
        return prev

Ejercicio: Fibonacci recursivo optimizado

Algoritmo recursivo con coste O(N) (más eficiente que el recursivo básico, menos que el de matrices O(log n)).

def fibonacci(n, second_last, last):
    if n - 1 == 0:
        return second_last
    else:
        new_last = second_last + last
        second_last = last
        return fibonacci(n - 1, second_last, new_last)

print(fibonacci(21, 0, 1))  # 6765

3. Entrega 04 — Búsqueda binaria iterativa

Implementación del algoritmo de búsqueda binaria mediante un proceso iterativo.

La función busca un elemento en una lista ordenada dividiéndola repetidamente en mitades. Comienza calculando el punto medio y comparando su valor con el elemento buscado. Si coincide, devuelve su índice; si es menor, ignora la mitad izquierda; si es mayor, ignora la derecha. Se repite hasta encontrar el elemento o hasta que no queden elementos.

def binarySearch(arr, l, r, x):
    while l <= r:
        mid = l + (r - l) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            l = mid + 1
        else:
            r = mid - 1
    return -1

arr = [2, 3, 4, 10, 40]
x = 10
result = binarySearch(arr, 0, len(arr)-1, x)

Resultado: Elemento encontrado en la posición 3.

4. Entrega 06 — Árboles binarios, AVL y heap

Algoritmo iterativo para recorrer un árbol (inorden)

1. Creamos una pila vacía S.
2. Añadimos (push) el nodo actual a la pila. Nos movemos al extremo izquierdo hasta llegar a extremo vacío.
3. Si hemos llegado al extremo (y la pila no está vacía), mostramos el elemento superior de la pila. Nos movemos a la derecha.
4. Volvemos al paso 2.
5. Finalizamos cuando el nodo está vacío y la pila está también vacía.

Ejemplo en inorden: 4 2 5 1 3.

Árbol AVL

Árbol binario de búsqueda siempre balanceado. Factor de equilibrio = Altura(subárbol derecho) − Altura(subárbol izquierdo). Debe ser -1, 0 o 1.

Rotaciones: simple derecha, simple izquierda, doble derecha, doble izquierda.

Árbol Heap

Max-Heap: cada nodo tiene valor mayor o igual que sus hijos (raíz es el máximo).

Min-Heap: cada nodo tiene valor menor o igual que sus hijos (raíz es el mínimo).

Es un árbol binario completo: todos los niveles están llenos excepto el último, que se llena de izquierda a derecha.

5. Entrega 07/08 — Blockchain, hash tables y P vs NP

Estructura de datos en la Blockchain de Bitcoin

• Bloques: contienen lista de transacciones, puntero hash al bloque anterior, timestamp y nonce. Crean una cadena inmutable.
• Árbol de Merkle: organiza las transacciones para verificar eficientemente la existencia de una transacción sin revisar toda la cadena.
• Tabla Hash: almacena direcciones y claves para búsqueda rápida de saldos y transacciones.

Algoritmos clave

• SHA-256: genera hashes únicos para bloques y transacciones.
• Prueba de Trabajo (PoW): resuelve un problema criptográfico para añadir bloques.
• Distribución P2P: cada nodo mantiene una copia de la blockchain; consenso via PoW.

Implicaciones de P vs NP

La seguridad de la blockchain se basa en que resolver problemas criptográficos es mucho más difícil que verificar su solución. Si P = NP, esta seguridad podría verse comprometida.

Proyecto: Votaciones descentralizadas

Blockchain aplicado a votaciones: los votos se registran como transacciones en bloques (inmutabilidad), un árbol de Merkle verifica validez, y la cadena pública permite auditoría en tiempo real.

6. Evaluación Tema 05 — P vs NP

¿En qué consiste P = NP?

P: problemas que se pueden resolver eficientemente (tiempo polinómico).

NP: problemas cuyos resultados pueden verificarse eficientemente, aunque no necesariamente resolverse rápidamente.

La incógnita: ¿Todo problema verificable eficientemente (NP) también puede resolverse eficientemente (P)?

• Ejemplo P: suma de números grandes.
• Ejemplo NP: problema del viajante de comercio (verificar es fácil, resolver requiere probar todas las combinaciones).

Aplicaciones prácticas

• Criptografía: seguridad de contraseñas y cifrado (bancos, comunicaciones) basada en problemas NP.
• Logística: optimización de rutas de reparto (viajante de comercio).
• Medicina: plegamiento de proteínas para diseño de medicamentos.

Problema: suma de subconjunto

Conjunto {-2, -3, 8, 15, -10}. ¿Existe un subconjunto que sume 0? Sí: {-2, -3, -10, 15}.

Para n grande, este problema es NP: requiere probar todas las combinaciones posibles (complejidad exponencial).