Algoritmos de Ordenación
Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar información de una manera especial basándonos en un criterio de ordenamiento.
Ordenación por burbuja (Bubble Sort)
El ordenamiento de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado.
Ordenación por inserción (Insertion Sort)
Insertion Sort (o "Ordenamiento por Inserción") es una técnica de ordenación que construirá la secuencia ordenada de elementos uno a la vez, comparando siempre cada elemento con los elementos ya ordenados a la izquierda e insertándolo en la posición correcta.
Ordenación por selección (Selection Sort)
Selection Sort o Ordenamiento por Selección, busca el elemento más pequeño en el conjunto de elementos y lo coloca en la posición correcta. Luego, busca el siguiente elemento más pequeño y lo coloca en la siguiente posición correcta. Repite este proceso hasta que todos los elementos estén ordenados.
Ordenación rápida (Quick Sort)
QuickSort es un algoritmo basado en el principio “divide y vencerás”. Es una de los algoritmos más rápidos conocidos para ordenar. Este método es recursivo, aunque existen versiones con formas iterativas que lo hacen aún más rápido.
Ordenación por fusión (Merge Sort)
El algoritmo de ordenación Merge Sort es un método eficiente, general y comparativo para ordenar listas o arrays. Es un ejemplo clásico de un algoritmo "divide y vencerás". Merge Sort divide el conjunto de datos en mitades más pequeñas, las ordena y luego las fusiona de nuevo en una sola lista ordenada.
Ordenación por montículo (Heap Sort)
La ordenación por montículos utiliza la propiedad de la raíz para ordenar el arreglo. Una vez que el arreglo cumpla las propiedades del montículo, quitamos la raíz y la colocamos al final del arreglo.
Un algoritmo de búsqueda es un conjunto de instrucciones que están diseñadas para localizar un elemento con ciertas propiedades dentro de una estructura de datos
Búsqueda lineal (Linear Search)
La búsqueda lineal recorre todos los elementos de una colección uno por uno hasta encontrar el elemento objetivo o llegar al final de la colección. Es el método más simple de búsqueda
Búsqueda binaria (Binary Search)
La búsqueda binaria se aplica en una colección ordenada. Divide la colección a la mitad repetidamente para encontrar el elemento objetivo. Si el elemento en el medio es el objetivo, se retorna el índice. Si el objetivo es menor o mayor, la búsqueda continua en la mitad correspondiente
Búsqueda en profundidad (DFS) en grafos
DFS explora un grafo o un árbol comenzando desde un nodo raíz y avanzando hacia los nodos más profundos posibles antes de retroceder. Se utiliza una estructura de pila (puede ser implícita en la recursión) para realizar la búsqueda.
Búsqueda en amplitud (BFS) en grafos
BFS explora un grafo o un árbol nivel por nivel, comenzando desde un nodo raíz y avanzando hacia los nodos vecinos antes de pasar a los siguientes niveles. Utiliza una estructura de cola para llevar a cabo la búsqueda.
son fundamentales en la informática y se utilizan para resolver problemas relacionados con redes, caminos, conexiones y estructuras de datos en forma de grafos.
Algoritmo de Dijkstra (camino más corto en grafos ponderados)
Encuentra el camino más corto desde un nodo fuente a todos los otros nodos en un grafo ponderado con pesos no negativos.
Algoritmo de Bellman-Ford (camino más corto en grafos con pesos negativos)
Encuentra el camino más corto desde un nodo fuente a todos los otros nodos en un grafo ponderado, incluso con pesos negativos. Puede detectar ciclos negativos
Algoritmo de Floyd-Warshall (camino más corto entre todos los pares)
es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución.
Algoritmo de Kruskal (árbol de expansión mínima)
Encuentra el árbol de expansión mínima (MST) en un grafo ponderado utilizando un enfoque basado en conjuntos disjuntos. Es útil para encontrar el conjunto de aristas que conecta todos los nodos con el menor peso total.
Algoritmo de Prim (árbol de expansión mínima)
El algoritmo de Prim permite encontrar un árbol recubridor mínimo de un grafo. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible.
Concepto de programación dinámica
La programación dinámica es una técnica de diseño de algoritmos utilizada para resolver problemas complejos que pueden ser descompuestos en subproblemas más simples. La esencia de la programación dinámica radica en almacenar las soluciones de estos subproblemas para evitar la recomputación y, así, optimizar el tiempo de ejecución.
Problemas clásicos: mochila, secuencia de Fibonacci, cadena de matrices
Problema de la Mochila (Knapsack Problem) Dado un conjunto de objetos, cada uno con un valor y un peso, y una mochila con una capacidad máxima, el objetivo es maximizar el valor total de los objetos que se pueden colocar en la mochila sin exceder la capacidad.
La secuencia de Fibonacci es una serie de números en la que cada número es la suma de los dos números anteriores. El objetivo es encontrar el n-ésimo número de la secuencia.
Problema de la Cadena de Matrices (Matrix Chain Multiplication)
consiste en dada una sucesión de matrices encontrar la manera de multiplicarlas usando el menor número de productos de elementos
Técnica de memorización y tabulación
Técnica de Memorización (Top-Down) es un enfoque top-down que resuelve el problema de manera recursiva, almacenando los resultados de los subproblemas a medida que se resuelven. Esto evita la necesidad de recalcular soluciones para subproblemas que ya han sido resueltos.
Técnica de Tabulación (Bottom-Up) es un enfoque bottom-up que resuelve el problema iterativamente, construyendo una tabla (o matriz) que contiene soluciones a todos los subproblemas. El algoritmo comienza resolviendo los subproblemas más pequeños y usa estas soluciones para construir la solución del problema principal.
Concepto de divide y vencerás
La técnica de Divide y Vencerás es un enfoque fundamental en el diseño de algoritmos. Esta técnica divide un problema en subproblemas más pequeños, resuelve los subproblemas de forma recursiva y luego combina las soluciones de los subproblemas para obtener la solución del problema original.
Ejemplos: Merge Sort, Quick Sort, búsqueda binaria
Es un algoritmo de ordenación que utiliza el enfoque de Divide y Vencerás para ordenar un arreglo dividiéndolo en mitades, ordenando las mitades de forma recursiva y luego combinando las mitades ordenadas
Es otro algoritmo de ordenación que divide un arreglo en dos subarreglos basados en un pivote, ordena los subarreglos de forma recursiva y combina los resultados para obtener el arreglo ordenado.
Es un algoritmo para encontrar un elemento en un arreglo ordenado. Divide el arreglo en mitades y determina en cuál mitad se encuentra el elemento buscado, repitiendo el proceso hasta encontrar el elemento o determinar que no está presente.
La complejidad computacional se refiere a la cantidad de recursos (como tiempo y memoria) que un algoritmo necesita para ejecutarse a medida que el tamaño de la entrada aumenta. Se suele medir en términos de tiempo (cuánto tarda) y espacio (cuánta memoria usa).
Notación Big O
La notación Big O es una forma de describir el comportamiento asintótico de un algoritmo, es decir, cómo cambia el tiempo de ejecución o el uso de memoria en función del tamaño de la entrada cuando este tamaño se vuelve muy grande. La notación Big O se centra en el comportamiento dominante y desprecia los factores constantes y los términos menos significativos.
Análisis de tiempo y espacio
Análisis de Tiempo:
Análisis de Espacio:
Casos promedio, mejor y peor caso
Las técnicas de optimización en computación se centran en mejorar la eficiencia de algoritmos y programas, tanto en términos de tiempo como de espacio.
Estrategias para mejorar la eficiencia
Análisis y Profiling
Perfilado (Profiling): Usar herramientas de perfilado para identificar cuellos de botella en el rendimiento. Esto te permite centrarte en las partes del código que consumen más tiempo o memoria.
Optimización Basada en Datos: Basar las optimizaciones en datos empíricos.
Optimización de Algoritmos
Elegir el Algoritmo Adecuado: Seleccionar algoritmos con mejor complejidad computacional para el problema en cuestión. Por ejemplo, usar Quick Sort en lugar de Bubble Sort para ordenación de grandes conjuntos de datos.
Algoritmos Aproximados: En algunos casos, un algoritmo exacto puede ser demasiado costoso. Los algoritmos aproximados ofrecen soluciones cercanas a la óptima con menor costo computacional.
Optimización de Estructuras de Datos
Elegir Estructuras de Datos Adecuadas: Utilizar estructuras de datos que proporcionen las operaciones necesarias de manera eficiente. Por ejemplo, usar tablas hash para búsquedas rápidas o árboles balanceados para operaciones de búsqueda y actualización eficientes.
Optimización Espacial: Reducir el uso de memoria mediante técnicas como la compresión de datos o el uso de estructuras de datos compactas.
Optimización de Código
Técnicas de poda (como poda alfa-beta en juegos)
La poda alfa-beta es una técnica de optimización aplicada en algoritmos de búsqueda de juegos, como el algoritmo Minimax, para reducir el número de nodos evaluados en el árbol de búsqueda.
Se utiliza en juegos de dos jugadores, como el ajedrez o el tres en raya, donde un jugador intenta maximizar su puntuación (Max) y el otro jugador intenta minimizarla (Min).
Cómo Funciona: