Fundamentos de Algoritmia: Estructuras, Tipos y Aplicaciones en Computación

Definición de Algoritmo

Un algoritmo es un conjunto de instrucciones definidas, ordenadas y acotadas. Su propósito fundamental es:

• Resolver problemas.
• Realizar cálculos.
• Desarrollar tareas específicas.

Componentes del Algoritmo

• Input (entrada): Información inicial con la que trabaja el sistema.
• Proceso: Conjunto de pasos lógicos para llegar a la solución.
• Output (salida): Resultados finales obtenidos tras la ejecución.

Características de los Algoritmos

Para que un algoritmo sea eficiente y funcional, debe cumplir con las siguientes propiedades:

• Preciso: Debe estar libre de ambigüedades.
• Ordenado: Debe seguir una secuencia lógica y clara.
• Finito: Debe contar con un número determinado de pasos y terminar en algún momento.
• Concreto: Debe ofrecer una solución definida al problema planteado.
• Definido: Debe producir el mismo resultado siempre que se parta de la misma entrada.

Clasificación Básica

Los algoritmos pueden categorizarse bajo distintos criterios:

• Por sistema de signos: Cuantitativos y cualitativos.
• Por uso de ordenador: Computacionales y no computacionales.
• Por función: Existen 5 tipos principales (búsqueda, ordenamiento, dinámica, voraces y probabilísticos).

Algoritmos de Búsqueda

Estos algoritmos se encargan de localizar elementos específicos dentro de estructuras de datos:

• Secuencial: Compara los elementos uno a uno hasta encontrar el objetivo.
• Binaria: Se aplica exclusivamente en conjuntos ordenados; utiliza la estrategia de divide y vencerás.

Algoritmos de Ordenamiento

Reorganizan los elementos siguiendo un criterio específico (numérico o lexicográfico):

• Burbuja: Intercambia elementos vecinos si están en el orden incorrecto.
• Selección: Busca el menor elemento y lo coloca en la posición correspondiente de forma sucesiva.
• Rápido (QuickSort): Utiliza un elemento pivote para dividir el conjunto y ordenar de forma recursiva.

Algoritmos Voraces (Greedy)

Siguen una estrategia de elegir la mejor opción local en cada paso con la esperanza de llegar a una solución óptima:

• Dijkstra: Utilizado para encontrar el camino más corto en grafos.
• Huffman: Empleado en la compresión de datos.
• Advertencia: No siempre garantizan la solución global óptima.

Programación Dinámica

Este enfoque divide el problema en subproblemas más pequeños y almacena sus soluciones para evitar cálculos redundantes. Es ideal para optimizar la recursión al dividir el conjunto de datos.

• Ejemplos de uso: Serie de Fibonacci y el problema de la mochila.
• Ventaja: Reduce significativamente el tiempo de ejecución.

Algoritmos Probabilísticos

Utilizan la aleatoriedad en su lógica para encontrar una solución "buena", aunque no siempre sea la óptima absoluta. Se emplean cuando existen limitaciones críticas de tiempo o memoria.

• Montecarlo: Presenta una pequeña probabilidad de error, la cual es reducible si se invierte más tiempo de ejecución.
• Las Vegas: La ejecución se realiza en un tiempo fijo; si encuentra una solución, esta es garantizadamente correcta.
• Optimización: Se pueden mejorar repitiendo el proceso con submuestras diferentes.

Estructuras de Control

Las estructuras de control son fundamentales para modificar el flujo de ejecución de los algoritmos:

• Secuenciales: Los pasos se ejecutan uno tras otro de forma lineal.
• Condicionales: Permiten tomar decisiones basadas en criterios lógicos.

Subtipos y Control Iterativo

• Condicionales: Pueden ser simples (SI), dobles, múltiples o anidadas.
• Iterativas (bucles):
  • Fijo: Se repite un número determinado de veces mediante un contador (variable de índice).
  • Indeterminado: Basado en condiciones, como Mientras que (mientras la condición sea verdadera) o Hasta que (hasta que la condición sea falsa).