Algoritmo

Este artículo es una explicación de concepto sobre el tema Algoritmo — incluyendo preguntas de examen, puntos clave y etiquetas.

En resumen

Un algoritmo es una secuencia finita y claramente definida de pasos para resolver un problema. Se evalúa según criterios como corrección, tiempo de ejecución, consumo de memoria, estabilidad y robustez.

Descripción técnica compacta

Un algoritmo procesa entradas bien definidas y produce salidas determinísticas o probabilísticas. Típicamente se describe en pseudocódigo con precondiciones y postcondiciones.

Para el análisis se utilizan notaciones asintóticas:

• O (cota superior)
• Ω (cota inferior)
• Θ (cota ajustada)

Frecuentemente separadas por casos mejor/promedio/peor y complementadas con análisis amortizado.

Paradigmas de diseño típicos:

• Divide y Conquista
• Greedy
• Programación Dinámica
• Backtracking
• Aleatorización

Las estructuras de datos (Array, Lista, Heap, Tabla Hash, Árbol, Grafo) determinan significativamente los costos reales.

Aspecto de seguridad: Las entradas de peor caso pueden desencadenar Algoritmic Complexity Attacks, por lo que la validación de entrada y los límites de recursos son relevantes.

Puntos clave para examen

• Exacto vs heurístico/aproximado; determinístico vs aleatorizado
• O/Ω/Θ; Mejor/Promedio/Peor; amortizado
• Paradigmas: D&C, Greedy, DP, Backtracking
• IHK: Precondiciones/postcondiciones, terminación, invariantes de bucle
• Práctica: Elegir la estructura de datos adecuada, medir primero y luego optimizar
• Seguridad: Endurecimiento contra peor caso, límites
• Documentación: Definición del problema, pseudocódigo, complejidad, protocolos de prueba

Componentes centrales

1. Especificación (entrada/salida/condiciones límite)
2. Modelo de costos (tiempo/memoria/I/O)
3. Pseudocódigo (secuencia, selección, bucle)
4. Elección de estructura de datos
5. Corrección (invariantes/inducción/terminación)
6. Análisis de complejidad
7. Enfoque de diseño
8. Detalles de implementación (recursión/iteración)
9. Robustez/seguridad
10. Pruebas (casos límite, fuzzing, regresión)

Ejemplo práctico: Insertion Sort (Pseudocódigo)

funcion insertionSort(a)
  para i de 1 a longitud(a)-1
    key <- a[i]
    j <- i-1
    mientras j >= 0 y a[j] > key
      a[j+1] <- a[j]
      j <- j-1
    fin
    a[j+1] <- key
  fin
  devuelve a

Explicación: Estable, in-place, peor caso O(n^2), mejor caso O(n) con datos casi ordenados.

Preguntas típicas de examen (con respuesta breve)

1. ¿O vs Ω vs Θ? O cota superior, Ω cota inferior, Θ cota ajustada.
2. ¿Cuándo es correcto Greedy? Cuando se cumplen subestructura óptima y propiedad de elección greedy.
3. ¿Cómo se reconoce Programación Dinámica? Subproblemas superpuestos + subestructura óptima.
4. ¿Cómo se demuestra terminación? Función de variación que decrece estrictamente y está acotada inferiormente.

Respuesta libre

Para tareas de IHK lo que cuenta es: definir el problema claramente, escribir pseudocódigo limpio, justificar la complejidad y probar casos límite. En sistemas reales, los efectos de cache/I/O y la robustez contra entradas de peor caso son decisivos.

Estrategia de aprendizaje

1. Escribir pseudocódigo + invariante para preguntas anteriores.
2. Medir tiempos de ejecución (búsqueda lineal vs binaria, diferentes ordenamientos).
3. Modelar un ejemplo de DP (mochila) como tabla.
4. Probar siempre casos límite y condiciones de salida.

Fuentes más importantes

1. https://de.wikipedia.org/wiki/Algorithmus
2. https://cp-algorithms.com/