Semana3

Getting Started: Subtema 2.3 - Designing Algorithms

Basado en: Cormen et al., 2022

---

🔎 Introducción

Este subtema presenta principios y estrategias clave para diseñar algoritmos, proporcionando un marco sólido para resolver problemas computacionales de forma eficaz y eficiente.

---

🧩 Estrategias de Diseño de Algoritmos

Se destacan tres estrategias fundamentales:

1. División y Conquista

• Descripción: Se divide un problema grande en subproblemas más pequeños y manejables.
• Proceso: Resolver recursivamente cada subproblema y combinar sus soluciones para obtener la respuesta final.
• Ejemplo clásico: Ordenamiento por mergesort, búsqueda binaria.

---

2. Programación Dinámica

• Descripción: Técnica para problemas donde se almacenan soluciones intermedias para evitar cálculos redundantes.
• Utilidad: Problemas de optimización, como la secuencia más larga común o el problema de la mochila.
• Principio clave: Superposición de subproblemas y subestructura óptima.

---

3. Algoritmos Codiciosos (Greedy)

• Descripción: Construye soluciones paso a paso seleccionando la opción que parece mejor localmente en cada paso.
• Aplicaciones comunes: Cambio de moneda, tareas de intervalo (scheduling).
• Nota: No siempre garantiza la solución óptima global, pero es eficiente y sencillo.

---

📊 Importancia del Análisis

Evaluar la eficiencia de un algoritmo es fundamental:

• Tiempo: ¿Cuánto tarda el algoritmo?
• Espacio: ¿Cuánta memoria utiliza?

Se utilizan notaciones asintóticas como Big O para:

• Clasificar algoritmos.
• Predecir rendimiento en función del tamaño de entrada.
• Tomar decisiones informadas en diseño y optimización.

---

🧪 Ejemplos Básicos de Diseño

Ejemplo Java: División y Conquista (Búsqueda Binaria)

public class BusquedaBinaria {
    public static int buscar(int[] arr, int clave) {
        int inicio = 0, fin = arr.length - 1;
        while (inicio <= fin) {
            int medio = (inicio + fin) / 2;
            if (arr[medio] == clave) return medio;
            if (arr[medio] < clave) inicio = medio + 1;
            else fin = medio - 1;
        }
        return -1; // No encontrado
    }

    public static void main(String[] args) {
        int[] datos = {1, 3, 5, 7, 9};
        int resultado = buscar(datos, 7);
        System.out.println("Índice encontrado: " + resultado);
    }
}

• Complejidad: O(log n)

---

Ejemplo Java: Programación Dinámica (Fibonacci con memoización)

import java.util.HashMap;

public class Fibonacci {
    private static HashMap<Integer, Long> memo = new HashMap<>();

    public static long fib(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);

        long resultado = fib(n - 1) + fib(n - 2);
        memo.put(n, resultado);
        return resultado;
    }

    public static void main(String[] args) {
        int n = 40;
        System.out.println("Fibonacci de " + n + " es: " + fib(n));
    }
}

---

Ejemplo Java: Algoritmo Codicioso (Cambio de Moneda)

public class CambioMoneda {
    public static int cambiar(int[] monedas, int monto) {
        int totalMonedas = 0;
        for (int i = monedas.length - 1; i >= 0; i--) {
            while (monto >= monedas[i]) {
                monto -= monedas[i];
                totalMonedas++;
            }
        }
        return totalMonedas;
    }

    public static void main(String[] args) {
        int[] monedas = {1, 5, 10, 25}; // centavos
        int monto = 63;
        System.out.println("Número mínimo de monedas: " + cambiar(monedas, monto));
    }
}

---

📌 Conclusión

El diseño de algoritmos es una habilidad clave que permite a los programadores resolver problemas de manera efectiva y eficiente.
Comprender y aplicar estrategias como división y conquista, programación dinámica y algoritmos codiciosos es esencial para:

• Mejorar la calidad del software.
• Optimizar recursos computacionales.
• Afrontar problemas complejos con soluciones inteligentes.

---