Algoritmos e Estruturas de Dados

• Un algoritmo consiste en un conjunto finito de pasos diseñados para resolver un problema específico.
• Las estructuras de datos son métodos especializados para organizar información en una computadora, facilitando su uso eficiente.

Características de un Algoritmo

• Finito: Debe constar de un número limitado de pasos.
• Definido: Cada paso debe ser preciso y carecer de ambigüedad.
• Entrada: Puede aceptar cero o más entradas para su procesamiento.
• Salida: Debe producir uno o más resultados como consecuencia de su ejecución.
• Efectividad: Los pasos deben ser básicos y factibles de realizar.

Tipos de Algoritmos

• Algoritmos cualitativos: Los pasos se describen narrativamente, sin cálculos numéricos.
• Algoritmos cuantitativos: Los pasos involucran cálculos numéricos y operaciones matemáticas.
• Algoritmos computacionales: Diseñados específicamente para ser ejecutados en una computadora.
• Algoritmos no computacionales: No requieren el uso de una computadora para su ejecución.

Representación de Algoritmos

• Diagramas de flujo: Utilizan símbolos estandarizados para representar gráficamente la secuencia de pasos en un algoritmo.
• Pseudocódigo: Descripción informal de un algoritmo, utilizando un lenguaje similar a la programación, pero más comprensible.
• Lenguajes de programación: Implementación formal de un algoritmo en un lenguaje que puede ser ejecutado por una computadora.

Estructuras de Datos

• Una estructura de datos es un método para organizar datos en una computadora, facilitando su uso y manipulación eficiente.
• Permiten el almacenamiento y acceso organizado a los datos.

Tipos de Estructuras de Datos

• Estructuras de datos lineales: Los elementos se organizan de forma secuencial, uno tras otro.
• Estructuras de datos no lineales: Los elementos no se organizan de forma secuencial.

Estructuras de Datos Lineales

• Arreglos (Arrays): Colección de elementos del mismo tipo, almacenados en posiciones de memoria contiguas.
  • Permiten acceso rápido a elementos mediante su índice.
  • Tienen un tamaño fijo una vez que se definen.
• Listas enlazadas (Linked Lists): Colección de elementos (nodos), donde cada elemento contiene un puntero al siguiente.
  • Permiten un tamaño dinámico que puede cambiar durante la ejecución.
  • Facilitan la inserción y eliminación eficiente de elementos.
  • Requieren acceso secuencial para recorrer los elementos.
• Pilas (Stacks): Estructura LIFO (Last In, First Out), donde el último elemento añadido es el primero en ser removido.
  • Las operaciones principales son push (añadir) y pop (eliminar).
• Colas (Queues): Estructura FIFO (First In, First Out), donde el primer elemento añadido es el primero en ser removido.
  • Las operaciones principales son enqueue (añadir) y dequeue (eliminar).

Estructuras de Datos No Lineales

• Árboles (Trees): Estructura jerárquica compuesta por nodos conectados por aristas.
  • Árbol binario: Cada nodo tiene como máximo dos hijos.
  • Árbol de búsqueda binaria: Los nodos están ordenados para facilitar la búsqueda eficiente.
• Grafos (Graphs): Conjunto de nodos (vértices) conectados por aristas.
  • Pueden ser dirigidos o no dirigidos.
  • Útiles para representar relaciones complejas entre datos.
• Tablas Hash (Hash Tables): Estructura que permite almacenar y recuperar datos rápidamente mediante una función hash.
  • La función hash convierte la clave del dato en un índice para su almacenamiento.
  • El manejo de colisiones es crucial para mantener la eficiencia.

Operaciones Básicas en Estructuras de Datos

• Inserción: Agregar un nuevo elemento a la estructura.
• Eliminación: Remover un elemento existente de la estructura.
• Búsqueda: Encontrar un elemento específico dentro de la estructura.
• Ordenamiento: Organizar los elementos en un orden particular (ascendente, descendente, etc.).
• Actualización: Modificar un elemento existente en la estructura.

Algoritmos de Búsqueda

• Búsqueda lineal: Revisar cada elemento secuencialmente hasta encontrar el buscado.
• Búsqueda binaria: Dividir repetidamente la estructura a la mitad para encontrar el elemento buscado (requiere que la estructura esté ordenada).
• Búsqueda por hash: Utilizar una función hash para encontrar la ubicación del elemento directamente.

Algoritmos de Ordenamiento

• Ordenamiento por burbuja (Bubble Sort): Comparar pares de elementos adyacentes e intercambiarlos si están en el orden incorrecto, repitiendo hasta que la lista esté ordenada.
• Ordenamiento por selección (Selection Sort): Encontrar repetidamente el elemento mínimo y colocarlo al principio de la lista.
• Ordenamiento por inserción (Insertion Sort): Construir una lista ordenada insertando elementos uno a la vez en la posición correcta.
• Ordenamiento por mezcla (Merge Sort): Dividir la lista en sublistas, ordenarlas individualmente y luego fusionarlas en una lista ordenada.
• Ordenamiento rápido (Quick Sort): Seleccionar un elemento pivote y particionar la lista en dos sublistas basadas en el pivote, ordenando recursivamente.

Complejidad de Algoritmos

• La complejidad mide la cantidad de recursos (tiempo y espacio) necesarios para ejecutar un algoritmo.
• Notación Big O: Se utiliza para describir el comportamiento asintótico de un algoritmo.
• Complejidad temporal: Mide el tiempo de ejecución en función del tamaño de la entrada.
• Complejidad espacial: Mide la cantidad de memoria utilizada en función del tamaño de la entrada.

Ejemplos de Complejidades Comunes

• O(1): Complejidad constante, el tiempo de ejecución no depende del tamaño de la entrada.
• O(log n): Complejidad logarítmica, el tiempo de ejecución aumenta logarítmicamente con el tamaño de la entrada.
• O(n): Complejidad lineal, el tiempo de ejecución aumenta linealmente con el tamaño de la entrada.
• O(n log n): Complejidad lineal logarítmica, común en algoritmos de ordenamiento eficientes.
• O(n^2): Complejidad cuadrática, el tiempo de ejecución aumenta cuadráticamente con el tamaño de la entrada.
• O(2^n): Complejidad exponencial, el tiempo de ejecución aumenta exponencialmente con el tamaño de la entrada.

Importancia de la Selección de Algoritmos y Estructuras de Datos

• La elección correcta puede mejorar significativamente la eficiencia de un programa en términos de tiempo y uso de recursos.
• Un algoritmo ineficiente puede consumir muchos recursos y tardar mucho tiempo en ejecutarse, afectando el rendimiento.
• Una estructura de datos mal elegida puede dificultar el almacenamiento y acceso a los datos, complicando las operaciones.

Aplicaciones

• Los algoritmos y estructuras de datos son fundamentales en el desarrollo de software en diversas áreas.
• Se utilizan en sistemas operativos, bases de datos, compiladores, gráficos por computadora e inteligencia artificial.
• La comprensión de estos conceptos es crucial para diseñar soluciones eficientes y escalables en cualquier dominio de la informática.