Saltar al contenido ForoHackers

Algoritmos: por dónde empezar

Algoritmos
#3396 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder