Introducción al Diseño de Algoritmos
Publicado el 1 de diciembre de 2025
Introducción al Diseño de Algoritmos
El diseño de algoritmos constituye la base de la ingeniería de software. Comprender sus fundamentos es esencial para desarrollar procedimientos informáticos robustos y fiables. Este capítulo sienta las bases para distinguir una solución correcta de una simplemente funcional.
1. Definición de Elementos Clave
¿Qué es un algoritmo?
Definición
Un algoritmo es un procedimiento formal diseñado para completar una tarea específica. En esencia, representa la idea central detrás de cualquier programa informático razonable. Para ser relevante, un algoritmo debe resolver un problema general y bien especificado.
Distinción entre Problema e Instancia
La distinción entre un problema y una instancia de un problema es fundamental:
- Problema Algorítmico: Se define describiendo el conjunto completo de instancias sobre las que debe operar y el formato de la salida deseada.
- Instancia: Es un caso particular de la entrada para ese problema.
Piénsalo así
Un problema es como una receta general de cocina, mientras que una instancia es cuando cocinas esa receta con ingredientes específicos en tu cocina.
El Problema de la Clasificación (Sorting)
Un ejemplo clásico es el problema de clasificación (sorting). Este requiere ordenar una secuencia de claves.
Problema: Clasificación (Sorting)
Entrada: Una secuencia de claves
Salida: La permutación (reordenamiento) de la secuencia de entrada tal que:
Ejemplos de instancias particulares:
# Instancia 1: Nombres
Entrada: {Mike, Bob, Sally, Jill, Jan}
Salida: {Bob, Jan, Jill, Mike, Sally}
# Instancia 2: Números
Entrada: {154, 245, 568, 324, 654, 324}
Salida: {154, 245, 324, 324, 568, 654}
¿Cuál de las siguientes opciones representa una INSTANCIA del problema de clasificación?
2. Fundamentos de la Calidad Algorítmica
Propiedades Deseables de un Algoritmo
Los Tres Pilares
De manera general, un buen algoritmo debe cumplir tres propiedades deseables:
- Correcto: Siempre debe producir un resultado preciso
- Eficiente: Debe ejecutarse rápidamente
- Fácil de implementar: Debe ser práctico en su desarrollo
En este contexto, la corrección algorítmica es prioritaria.
Garantizar la Corrección
Advertencia
Raramente resulta obvio si un algoritmo dado resuelve correctamente un problema. Los algoritmos correctos suelen estar acompañados de una prueba de corrección, la cual explica por qué se sabe que el algoritmo debe tomar cada instancia del problema y producir el resultado deseado.
Corrección vs. Heurística
Existe una diferencia fundamental entre algoritmos y heurísticas:
| Algoritmo | Heurística |
|---|---|
| Procedimiento que siempre genera un resultado correcto | Puede realizar un buen trabajo habitualmente |
| Garantía de corrección en todas las instancias | No ofrece garantía de corrección |
| Respaldado por pruebas matemáticas | Basado en intuición o experiencia |
Ejemplo: Insertion Sort como un Procedimiento Correcto
El método conocido como insertion sort es un procedimiento que resuelve el problema de clasificación:
Proceso del Insertion Sort:
- Comienza con un solo elemento (formando trivialmente una lista ordenada)
- Inserta incrementalmente los elementos restantes
- Mantiene la lista ordenada en cada paso
Visualización paso a paso:
Paso 0: [5] | 2, 8, 1, 9 → Ya está "ordenado" (1 elemento)
Paso 1: [2, 5] | 8, 1, 9 → Insertamos 2 en su posición
Paso 2: [2, 5, 8] | 1, 9 → Insertamos 8 al final
Paso 3: [1, 2, 5, 8] | 9 → Insertamos 1 al inicio
Paso 4: [1, 2, 5, 8, 9] → Insertamos 9 al final
Este algoritmo es general, ya que funciona igual de bien con nombres que con números, siempre que exista la operación de comparación adecuada.
¿Por qué se considera que Insertion Sort es un ALGORITMO y no una heurística?
3. Algoritmos, Heurísticas y Modelado de Problemas
El Proceso de Modelado
Definición: Modelado
El modelado se define como el arte de formular una aplicación o tarea en términos de problemas bien descritos y estructuras abstractas rigurosamente definidas, como permutaciones, grafos o conjuntos.
¿Por Qué Modelar?
Pro Tip
La mayoría de los algoritmos están diseñados para trabajar con estructuras abstractas. Para aplicar técnicas de diseño algorítmico a problemas del mundo real, es necesario describir el problema de forma abstracta.
Esto permite que el proceso se relacione con soluciones ya existentes, eliminando incluso la necesidad de diseñar o implementar nuevos algoritmos.
Estructuras Combinatorias Fundamentales
A continuación, se presenta una lista de estructuras abstractas comunes utilizadas en el proceso de modelado:
Permutaciones
- Representan disposiciones u ordenamientos de ítems
- Relevantes cuando el problema busca una “secuencia” o “tour”
- Ejemplo: Rutas de entrega, planificación de tareas
Subconjuntos
- Representan selecciones de un conjunto de ítems
- Relevantes cuando el problema busca una “selección” o “grupo”
- Ejemplo: Selección de proyectos, asignación de recursos
Grafos
- Modelan relaciones entre pares arbitrarios de objetos
- Relevantes para cualquier tipo de “red” o “circuito”
- Ejemplo: Redes sociales, mapas de carreteras
Strings
- Representan secuencias de caracteres
- Relevantes para “texto” o “patrones”
- Ejemplo: Búsqueda de texto, análisis de ADN
Ejemplo: Optimización de Recorrido de Robot (TSP)
Problema del Viajante (TSP)
El problema de optimización del recorrido de un robot requiere encontrar el ciclo más corto que visite un conjunto de puntos.
Modelado: Esto se modela como un problema que busca una permutación óptima de los puntos.
Heurística Incorrecta: Nearest-Neighbor
La heurística Nearest-Neighbor (Vecino más cercano):
- En cada paso, camina al vecino no visitado más cercano
- Parece lógico e intuitivo
- PERO ES INCORRECTA porque no garantiza encontrar el recorrido más corto
Contraejemplo visual:
Puntos: A, B, C, D dispuestos así:
A----1----B
| |
1 9
| |
C----1----D
Nearest-Neighbor desde A:
A → C (1) → D (1) → B (9)
Total = 11 + distancia B→A
Solución óptima:
A → B (1) → D (1) → C (1) → A (1)
Total = 4
¡La heurística NO encuentra el óptimo!
Lección: Producir una instancia donde un procedimiento falla se conoce como hallar un contraejemplo, lo cual es la mejor manera de demostrar que un algoritmo es incorrecto.
¿Qué significa encontrar un 'contraejemplo' en el contexto de algoritmos?
4. Casos de Estudio y Procedimientos
El Problema de Programación de Películas
Movie Scheduling Problem
Entrada: Un conjunto de intervalos de tiempo
Objetivo: Seleccionar el subconjunto más grande de intervalos que no se superpongan entre sí
Modelado: Este problema se modela en términos de subconjuntos.
Ejemplo Práctico
Películas disponibles (inicio → fin):
A: 09:00 → 11:00 (2 horas)
B: 10:00 → 11:30 (1.5 horas)
C: 11:00 → 13:00 (2 horas)
D: 11:30 → 13:30 (2 horas)
E: 13:00 → 14:00 (1 hora)
¿Cuál es la selección óptima?
Heurísticas Incorrectas
Cuidado con estas heurísticas
Aunque procedimientos basados en la intuición parecen eficientes, son incorrectos:
- Earliest Job First: Aceptar el trabajo con la fecha de inicio más temprana
- Shortest Job First: Aceptar el trabajo más corto
Problema: Aceptar el primer trabajo o el más corto puede bloquear la posibilidad de aceptar muchos otros trabajos, impidiendo el resultado óptimo.
Aplicando Earliest Job First:
1. Elegimos A (09:00 → 11:00) - el más temprano
2. B se superpone con A → descartamos
3. C se superpone con A → descartamos
4. D se superpone con A → descartamos
5. Elegimos E (13:00 → 14:00)
Resultado: {A, E} = 2 películas
Pero la solución óptima es:
{A, C, E} = 3 películas ¡o incluso {B, D, E}!
¡La heurística no encontró el óptimo!
Aplicando Shortest Job First:
1. Elegimos E (1 hora) - el más corto
2. Elegimos B (1.5 horas) - siguiente más corto
Pero B termina a las 11:30 y E empieza a las 13:00
→ ¡Son compatibles!
3. Ya no podemos añadir A, C ni D porque se superponen
Resultado: {B, E} = 2 películas
Solución óptima: {A, C, E} = 3 películas
¡La heurística priorizó la duración sobre la compatibilidad!
Búsqueda Exhaustiva: Correcta pero Ineficiente
Advertencia
Para garantizar la corrección, una opción es la búsqueda exhaustiva (ExhaustiveScheduling), donde se evalúan los subconjuntos de intervalos.
✅ Ventaja: Es correcto, ya que considera todas las posibilidades
❌ Desventaja: Es extremadamente lento para valores grandes de
Ejemplo: Para películas → combinaciones a evaluar
El Método de Programación Óptima
Algoritmo Correcto y Eficiente
Existe un método que resuelve el problema de programación de películas de manera correcta Y eficiente:
Procedimiento: OptimalScheduling(I)
- Mientras el conjunto no esté vacío:
- Acepte el trabajo de con la fecha de finalización más temprana
- Elimine y cualquier intervalo que lo intercepte de
Idea clave: Siempre se debe seleccionar el trabajo que termine primero, ya que esto maximiza las oportunidades para aceptar trabajos futuros.
Aplicando OptimalScheduling al ejemplo:
Estado inicial:
A: 09:00 → 11:00
B: 10:00 → 11:30
C: 11:00 → 13:00
D: 11:30 → 13:30
E: 13:00 → 14:00
Paso 1: Elegir el que termine más temprano
→ A termina a las 11:00 (el más temprano)
→ Aceptamos A
→ Eliminamos B (se superpone con A)
Películas restantes:
C: 11:00 → 13:00
D: 11:30 → 13:30
E: 13:00 → 14:00
Paso 2: Elegir el que termine más temprano
→ C termina a las 13:00 (el más temprano)
→ Aceptamos C
→ Eliminamos D (se superpone con C)
Películas restantes:
E: 13:00 → 14:00
Paso 3: Elegir el que termine más temprano
→ Solo queda E
→ Aceptamos E
Resultado final: {A, C, E} = 3 películas ✓
¡Solución óptima!
¿Por qué funciona?
- Al elegir siempre el que termina primero, dejamos más tiempo disponible
- Esto maximiza las oportunidades para películas futuras
- Es un algoritmo greedy (voraz) que resulta ser óptimo para este problema
En el algoritmo OptimalScheduling, ¿por qué elegir el trabajo que termina más temprano garantiza una solución óptima?
5. Cierre: Conclusiones Operacionales
Una vez que se ha diseñado un procedimiento, la verificación de su corrección es crucial. La herramienta principal para esta verificación es la prueba.
Lección Clave sobre Corrección
Lección Crítica
Los procedimientos que parecen razonables pueden ser fácilmente incorrectos.
La corrección de un algoritmo es una propiedad que debe demostrarse cuidadosamente.
La búsqueda de contraejemplos es el mejor método para refutar la corrección de una heurística. Un contraejemplo es una instancia que produce una salida incorrecta.
Lección Clave sobre Modelado
El Poder del Modelado
El modelado de la aplicación en términos de estructuras y algoritmos bien definidos es el paso más importante hacia una solución.
Esto implica la formulación del problema real —a menudo involucrando objetos del mundo real— en parámetros y estructuras abstractas como:
- Subconjuntos
- Grafos
- Permutaciones
- Strings
Analogía Final
Analogía: Navegación
Piense en el diseño de algoritmos como la planificación de una ruta de navegación:
- El problema: Llegar del punto A al punto B
- El algoritmo: El procedimiento que define los pasos
- Una heurística: “Siempre girar en la calle más ancha”
- Podría funcionar bien la mayor parte del tiempo
- Pero fallará estrepitosamente en una rotonda o calle sin salida
Solo un algoritmo correcto, apoyado por una prueba o modelo matemático, garantiza que la secuencia de pasos funcionará bajo cualquier configuración de entrada.
Resumen de Conceptos Clave
Conceptos Fundamentales
- Algoritmo: Procedimiento que SIEMPRE produce resultado correcto
- Heurística: Procedimiento que usualmente funciona, sin garantías
- Problema vs Instancia: General vs caso específico
- Modelado: Traducir problemas reales a estructuras abstractas
Propiedades de un Buen Algoritmo
- ✅ Correcto (prioritario)
- ⚡ Eficiente
- 🛠️ Fácil de implementar
Estructuras de Modelado
- Permutaciones: Secuencias, tours
- Subconjuntos: Selecciones, grupos
- Grafos: Redes, circuitos
- Strings: Texto, patrones
Técnicas de Verificación
- ✓ Pruebas de corrección
- ✗ Búsqueda de contraejemplos
- 🔍 Análisis exhaustivo (correcto pero lento)
¿Cuál es el orden de prioridad en las propiedades de un buen algoritmo?
¡Felicidades!
Has completado la introducción al diseño de algoritmos. Ahora comprendes la diferencia entre algoritmos y heurísticas, la importancia de la corrección, y cómo modelar problemas del mundo real usando estructuras abstractas.
Próximo paso: Aplicar estos conceptos en problemas más complejos y aprender técnicas de diseño algorítmico como divide y vencerás, programación dinámica, y algoritmos voraces.