Un algoritmo es un procedimiento finito y preciso que convierte una entrada en una salida. El campo pregunta qué procedimientos son correctos, cuántos pasos y cuánta memoria necesitan al crecer la entrada, y si existe uno mejor. Es la diferencia entre un programa que responde en un segundo y otro que nunca termina.
Conceptos clave
- Corrección: un invariante de bucle o un argumento por inducción demuestra que el procedimiento hace lo que dice, con cualquier entrada.
- Coste asintótico: la notación O grande describe cómo crecen el tiempo y el espacio con el tamaño de la entrada, sin contar constantes.
- Paradigmas de diseño: divide y vencerás, voraz, programación dinámica, vuelta atrás, aleatorización.
- Ordenación y búsqueda: los problemas estándar con los que se aprende cada técnica por primera vez.
- Peor caso, caso medio y coste amortizado: el mismo algoritmo se puede juzgar por su peor entrada, una típica o una larga secuencia de operaciones.
Vocabulario
- Recurrencia: una ecuación que define el coste de un problema mediante el coste de otros más pequeños.
- Subestructura óptima: una respuesta óptima se construye con respuestas óptimas de los subproblemas.
- Heurística: un método sin prueba de dar la mejor respuesta, que se usa porque es rápido y suele ser bueno.
- Razón de aproximación: cuánto puede alejarse del óptimo una respuesta, garantizado en el peor caso.
Qué estudiar, en orden
- Escribe desde cero la búsqueda binaria y la ordenación por inserción, y enuncia sus invariantes.
- Aprende la notación O grande y resuelve recurrencias sencillas, como la de la ordenación por mezcla.
- Implementa mergesort, quicksort y montículos; cuenta comparaciones con entradas aleatorias y adversas.
- Resuelve problemas clásicos con programación dinámica y con la estrategia voraz, y mira dónde falla esta última.
- Estudia los recorridos de grafos y los caminos mínimos, y compara tu código con el crecimiento previsto.
Etiquetas relacionadas
#data-structures #complexity #graph-theory #competitive-programming