Skip to the content ForoHackers
Log inJoin

Algoritmos: por dónde empezar

Algorithms
#890 · Ophuscado · · Report

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

  1. Escribe desde cero la búsqueda binaria y la ordenación por inserción, y enuncia sus invariantes.
  2. Aprende la notación O grande y resuelve recurrencias sencillas, como la de la ordenación por mezcla.
  3. Implementa mergesort, quicksort y montículos; cuenta comparaciones con entradas aleatorias y adversas.
  4. Resuelve problemas clásicos con programación dinámica y con la estrategia voraz, y mira dónde falla esta última.
  5. 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

Log in or join to reply.