ALGORITMOS Y ESTRUCTURAS DE
DATOS
INTRODUCCIÓN GENERAL
Algoritmos y Estructuras de Datos son los pilares fundamentales de la ciencia de la computación y la
programación. Si bien la tecnología evoluciona rápidamente, estos conceptos permanecen
constantes, ya que definen cómo las computadoras procesan información, almacenan datos y
resuelven problemas de manera eficiente. Mientras que los algoritmos son los "procedimientos" o
"recetas" para resolver problemas, las estructuras de datos son las "contenedores" que organizan la
información para que los algoritmos puedan trabajar con ella de forma óptima.
ALGORITMOS
¿QUÉ ES UN ALGORITMO?
Un algoritmo es una secuencia finita, definida y ordenada de pasos precisos que permiten resolver
un problema específico o realizar una tarea determinada. Para que una secuencia de pasos sea
considerada un algoritmo, debe cumplir con características esenciales:
- Finitud: Debe terminar después de un número limitado de pasos.
- Definición: Cada paso debe estar claro y sin ambigüedades; no puede haber interpretaciones
múltiples.
- Entradas: Puede recibir cero o más datos como entrada.
- Salidas: Debe producir al menos una salida o resultado.
- Eficiencia: Aunque no es un requisito estricto para la definición, es un aspecto crucial en la práctica,
ya que determina si el algoritmo es útil en situaciones reales.
TIPOS DE ALGORITMOS
, Existen múltiples formas de clasificar los algoritmos según su propósito, enfoque o estructura:
Por enfoque de resolución:
- Algoritmos greedy (voraces): Toman la mejor decisión local en cada paso, esperando llegar a la
mejor solución global. Ejemplos incluyen el algoritmo para el problema del cambio de monedas (con
denominaciones estándar) y el algoritmo de Prim para árboles de expansión mínima.
- Algoritmos de divide y vencerás: Dividen el problema en subproblemas más pequeños y similares,
resuelven cada uno de forma independiente y luego combinan los resultados. Ejemplos clásicos son
el algoritmo de ordenamiento quicksort, mergesort y el algoritmo para multiplicación de matrices de
Strassen.
- Algoritmos de programación dinámica: Resuelven problemas complejos descomponiendo ellos en
subproblemas superpuestos y almacenando los resultados de estos subproblemas para evitar
cálculos repetitivos. Se usa en problemas como el cálculo de la secuencia de Fibonacci optimizada,
el problema de la mochila (knapsack) y el algoritmo de Floyd-Warshall para caminos más cortos en
grafos.
- Algoritmos de búsqueda exhaustiva (fuerza bruta): Prueban todas las posibles soluciones hasta
encontrar la correcta. Aunque simples de diseñar, suelen ser ineficientes para problemas grandes.
Ejemplos incluyen la búsqueda lineal y el algoritmo de fuerza bruta para el problema del viajante de
comercio.
- Algoritmos recursivos: Se definen a sí mismos llamándose a sí mismos con subproblemas más
pequeños. La recursión es una herramienta poderosa que simplifica la implementación de muchos
algoritmos, aunque puede llevar a problemas de eficiencia en memoria si no se maneja
adecuadamente.
Por tarea específica:
- Algoritmos de ordenamiento: Organizan datos en un orden predefinido (ascendente, descendente,
etc.). Además de quicksort y mergesort, destacan bubble sort, insertion sort, selection sort, heapsort
y radix sort.
- Algoritmos de búsqueda: Buscan la presencia o ubicación de un elemento específico en un
conjunto de datos. Incluyen búsqueda lineal, búsqueda binaria (para datos ordenados), búsqueda en
árboles y búsqueda en tablas hash.
- Algoritmos de grafos: Resuelven problemas relacionados con grafos (conjuntos de nodos
conectados por aristas). Ejemplos son el algoritmo de Dijkstra para caminos más cortos, el algoritmo
DATOS
INTRODUCCIÓN GENERAL
Algoritmos y Estructuras de Datos son los pilares fundamentales de la ciencia de la computación y la
programación. Si bien la tecnología evoluciona rápidamente, estos conceptos permanecen
constantes, ya que definen cómo las computadoras procesan información, almacenan datos y
resuelven problemas de manera eficiente. Mientras que los algoritmos son los "procedimientos" o
"recetas" para resolver problemas, las estructuras de datos son las "contenedores" que organizan la
información para que los algoritmos puedan trabajar con ella de forma óptima.
ALGORITMOS
¿QUÉ ES UN ALGORITMO?
Un algoritmo es una secuencia finita, definida y ordenada de pasos precisos que permiten resolver
un problema específico o realizar una tarea determinada. Para que una secuencia de pasos sea
considerada un algoritmo, debe cumplir con características esenciales:
- Finitud: Debe terminar después de un número limitado de pasos.
- Definición: Cada paso debe estar claro y sin ambigüedades; no puede haber interpretaciones
múltiples.
- Entradas: Puede recibir cero o más datos como entrada.
- Salidas: Debe producir al menos una salida o resultado.
- Eficiencia: Aunque no es un requisito estricto para la definición, es un aspecto crucial en la práctica,
ya que determina si el algoritmo es útil en situaciones reales.
TIPOS DE ALGORITMOS
, Existen múltiples formas de clasificar los algoritmos según su propósito, enfoque o estructura:
Por enfoque de resolución:
- Algoritmos greedy (voraces): Toman la mejor decisión local en cada paso, esperando llegar a la
mejor solución global. Ejemplos incluyen el algoritmo para el problema del cambio de monedas (con
denominaciones estándar) y el algoritmo de Prim para árboles de expansión mínima.
- Algoritmos de divide y vencerás: Dividen el problema en subproblemas más pequeños y similares,
resuelven cada uno de forma independiente y luego combinan los resultados. Ejemplos clásicos son
el algoritmo de ordenamiento quicksort, mergesort y el algoritmo para multiplicación de matrices de
Strassen.
- Algoritmos de programación dinámica: Resuelven problemas complejos descomponiendo ellos en
subproblemas superpuestos y almacenando los resultados de estos subproblemas para evitar
cálculos repetitivos. Se usa en problemas como el cálculo de la secuencia de Fibonacci optimizada,
el problema de la mochila (knapsack) y el algoritmo de Floyd-Warshall para caminos más cortos en
grafos.
- Algoritmos de búsqueda exhaustiva (fuerza bruta): Prueban todas las posibles soluciones hasta
encontrar la correcta. Aunque simples de diseñar, suelen ser ineficientes para problemas grandes.
Ejemplos incluyen la búsqueda lineal y el algoritmo de fuerza bruta para el problema del viajante de
comercio.
- Algoritmos recursivos: Se definen a sí mismos llamándose a sí mismos con subproblemas más
pequeños. La recursión es una herramienta poderosa que simplifica la implementación de muchos
algoritmos, aunque puede llevar a problemas de eficiencia en memoria si no se maneja
adecuadamente.
Por tarea específica:
- Algoritmos de ordenamiento: Organizan datos en un orden predefinido (ascendente, descendente,
etc.). Además de quicksort y mergesort, destacan bubble sort, insertion sort, selection sort, heapsort
y radix sort.
- Algoritmos de búsqueda: Buscan la presencia o ubicación de un elemento específico en un
conjunto de datos. Incluyen búsqueda lineal, búsqueda binaria (para datos ordenados), búsqueda en
árboles y búsqueda en tablas hash.
- Algoritmos de grafos: Resuelven problemas relacionados con grafos (conjuntos de nodos
conectados por aristas). Ejemplos son el algoritmo de Dijkstra para caminos más cortos, el algoritmo
