Skip to the content ForoHackers
Log inJoin

Algoritmos: por dónde empezar

Algorithms
#3396 · · Quote · 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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply