Análisis y Diseño de Algoritmos - Syllabus PDF

ANALISIS Y DISEÑO DE ALGORITMOS I UNIDAD ANÁLISIS DE ALGORITMOS Y MÉTODOS DE ORDENACIÓN Mg. Ing. Luis A. Loo Parián [email protected] PRUEBA DE ENTRADA  PREGUNTAS PRUEBA DE ENTRADA 1. Explica la diferencia entre eficiencia y complejidad...

ANALISIS Y DISEÑO DE ALGORITMOS I UNIDAD ANÁLISIS DE ALGORITMOS Y MÉTODOS DE ORDENACIÓN Mg. Ing. Luis A. Loo Parián [email protected] PRUEBA DE ENTRADA  PREGUNTAS PRUEBA DE ENTRADA 1. Explica la diferencia entre eficiencia y complejidad de un algoritmo. ¿Por qué la notación Big O es importante en el análisis de rendimiento? 2. Explica el funcionamiento del algoritmo de ordenación por intercambio (Bubble Sort). ¿Cuál es su complejidad en el mejor, peor y caso promedio? 3. ¿Cómo funciona el algoritmo de mezcla directa en la ordenación externa? Explica en qué situaciones se utiliza. 4. Explica el método polifásico de ordenación externa y en qué se diferencia de la mezcla equilibrada múltiple. 5. Una empresa de comercio electrónico necesita optimizar la búsqueda de productos en su plataforma. Actualmente, utilizan un algoritmo de búsqueda lineal sobre una lista desordenada de productos, pero el tiempo de respuesta es demasiado lento. ¿Qué algoritmo recomendarías para mejorar la eficiencia de la búsqueda? Justifica tu respuesta considerando la complejidad temporal y espacial. 6. Una startup de análisis financiero procesa grandes volúmenes de datos en tiempo real. Inicialmente, implementaron Bubble Sort, pero notaron que no escala bien cuando los datos aumentan. ¿Qué algoritmo de ordenación recomendarías en su lugar? Explica cómo funcionaría en términos de eficiencia y casos de uso. 7. Una ciudad quiere implementar un sistema de navegación en tiempo real para el transporte público, donde los buses eligen automáticamente la ruta más corta considerando el tráfico en cada momento. ¿Cómo se podría aplicar el algoritmo de Dijkstra en este sistema?. ¿Cuáles serían las limitaciones o desafíos al aplicarlo en una red vial en constante cambio? ANALISIS Y DISEÑO DE ALGORITMOS Complejidad Algorítmica: Eficiencia de un Algoritmo. Análisis de Rendimiento. Eficiencia y Complejidad. Notación Big O.  UTILIDAD Explica qué significa que un algoritmo sea eficiente. ¿Por qué es importante analizar la eficiencia de un algoritmo? ¿Cuál es la diferencia entre medir la eficiencia de un algoritmo de forma empírica y de forma teórica? ¿Qué es la notación Big O y para qué se utiliza en el análisis de algoritmos? Datos/Observaciones LOGRO DE LA SESIÓN Al finalizar la sesión, el estudiante conoce la complejidad de los algoritmos diferenciando su complejidad temporal y espacial , para ser aplicados en proyectos con java. INTRODUCCIÓN En un mundo donde la tecnología avanza constantemente y los volúmenes de datos crecen de manera exponencial, la eficiencia de los algoritmos se ha convertido en un factor clave en el desarrollo de software. Aplicaciones de inteligencia artificial, procesamiento de grandes bases de datos y sistemas en tiempo real dependen de algoritmos optimizados para ofrecer respuestas rápidas y consumir menos recursos. La complejidad algorítmica nos permite analizar y comparar el rendimiento de diferentes soluciones, identificando cuál es la más adecuada según el contexto. A través de la notación Big O, los desarrolladores pueden predecir cómo se comportará un algoritmo a medida que los datos aumenten, asegurando así su escalabilidad y eficiencia. En esta sesión, exploraremos los conceptos fundamentales de la eficiencia algorítmica, aprenderemos a medir el rendimiento de los algoritmos y analizaremos cómo elegir la mejor solución en función de su complejidad computacional. ALGORITMOS Un algoritmo es un conjunto finito de pasos bien definidos y organizados de manera lógica, que se utilizan para resolver un problema o realizar una tarea. Puede ser expresado en lenguaje natural, diagramas de flujo, pseudocódigo o lenguajes de programación. Ejemplo: Un algoritmo para preparar café podría incluir pasos como calentar agua, añadir café, revolver y servir.  CARACTERISTICAS Para que un conjunto de instrucciones sea considerado un algoritmo, debe cumplir con estas características: 1. Definido → Cada paso debe estar claramente especificado, sin ambigüedades. 2. Preciso → No debe haber confusión en la ejecución de los pasos. 3. Finito → Debe terminar en algún momento; no puede ejecutarse indefinidamente. 4. Ordenado → Las instrucciones deben seguir una secuencia lógica. 5. Determinista → Para la misma entrada, siempre debe dar el mismo resultado. 6. Eficiente → Debe usar la menor cantidad de recursos posible (tiempo y memoria). 7. General → Puede aplicarse a distintos conjuntos de datos de entrada. Ejemplo: Un algoritmo que suma dos números siempre debe proporcionar el mismo resultado si los números de entrada son los mismos.  COMPLEJIDAD ALGORITMICA La eficiencia de un algoritmo es clave en el desarrollo de software, ya que determina qué tan rápido y qué tantos recursos consume una solución al procesar datos. Analizar su rendimiento nos permite seleccionar la mejor alternativa para resolver problemas computacionales. Eficiencia de un Algoritmo: Un algoritmo eficiente es aquel que resuelve un problema en el menor tiempo posible y con el menor uso de recursos computacionales. La eficiencia se mide en términos de: Tiempo de ejecución: ¿Cuánto tarda el algoritmo en ejecutarse? Uso de memoria: ¿Cuántos recursos de almacenamiento necesita? Ejemplo: Ordenar una lista de 1,000,000 de números con un algoritmo lento como Burbuja (O(n²)) puede tardar minutos, mientras que Quicksort (O(n log n)) lo hace en segundos.  IMPORTANCIA DEL ANALISIS DE RENDIMIENTO El rendimiento de un algoritmo impacta en diversas áreas: Escalabilidad: Un algoritmo ineficiente puede funcionar bien con pocos datos, pero volverse inusable con grandes volúmenes. Optimización de hardware: Algoritmos eficientes requieren menos CPU y memoria, reduciendo costos y consumo energético. Experiencia del usuario: En aplicaciones web y móviles, la velocidad de respuesta es crucial para la satisfacción del usuario. Ejemplo: Un motor de búsqueda como Google no puede usar un algoritmo ineficiente para ordenar resultados, ya que millones de personas lo consultan simultáneamente.  FACTORES QUE AFECTAN LA EFICIENCIA Los principales factores que determinan la eficiencia de un algoritmo son: 1. Tiempo de Ejecución: Mide cuánto tarda en ejecutarse un algoritmo según la cantidad de datos de entrada (n). Se representa con la Notación Big-O (O), que clasifica algoritmos según su crecimiento en función de n: Ejemplo: Si queremos buscar un número en una lista ordenada de 1 millón de elementos: Búsqueda lineal (O(n)) → Recorre hasta 1 millón de pasos en el peor caso. Búsqueda binaria (O(log n)) → Lo encuentra en ≈20 pasos.  FACTORES QUE AFECTAN LA EFICIENCIA 2. Uso de Memoria: Mide cuánta memoria extra usa un algoritmo al ejecutarse. Depende de si el algoritmo: Modifica los datos originales o usa estructuras adicionales. Utiliza recursión (consume más memoria por el uso de la pila de llamadas). Ejemplo: Quicksort (O(n log n)) es más eficiente en memoria que Merge Sort (O(n)) porque evita crear estructuras auxiliares. Fibonacci recursivo sin memorización (O(2ⁿ)) usa mucha memoria por múltiples llamadas innecesarias.  ANALISIS DE RENDIMIENTO El rendimiento de un algoritmo determina qué tan eficiente es en términos de tiempo de ejecución y uso de recursos. Existen dos enfoques principales para analizarlo: 1. Medición Empírica: Consiste en ejecutar el algoritmo en una computadora y medir su tiempo de ejecución. Se ve afectado por factores externos como el hardware y la optimización del compilador. Se realiza mediante pruebas experimentales con diferentes volúmenes de datos. Ventaja: Refleja el rendimiento real en una máquina específica. Desventaja: No es generalizable, ya que depende del entorno de ejecución. 2. Análisis Teórico: Evalúa la eficiencia del algoritmo considerando el conteo de operaciones y su complejidad asintótica. Se representa con la notación Big O (O), que indica el crecimiento del tiempo de ejecución en función del tamaño de entrada (n). No depende del hardware ni del lenguaje de programación. Ventaja: Permite comparar algoritmos independientemente del entorno de ejecución. Desventaja: No siempre refleja con precisión el tiempo de ejecución real.  TIEMPO DE EJECUCIÓN Y CONTEO DE OPERACIONES Tiempo de ejecución: Mide el tiempo real que tarda en ejecutarse un algoritmo. Conteo de operaciones: Calcula la cantidad de pasos o comparaciones realizadas sin ejecutarlo. Ejemplo de comparación: Si queremos buscar un número en un arreglo de 1 millón de elementos: Búsqueda lineal (O(n)) podría tardar 1 segundo en el peor caso. Búsqueda binaria (O(log n)) haría la búsqueda en aproximadamente 20 pasos, reduciendo el tiempo significativamente.  EFICIENCIA Y COMPLEJIDAD DE ALGORITMOS Eficiencia Temporal: Se refiere al tiempo de ejecución del algoritmo. Se mide en función del número de operaciones realizadas. Se representa con la notación Big O (ej. O(n), O(n²), O(log n)). Un algoritmo más rápido suele ser preferible, pero depende del contexto de uso. Eficiencia Espacial: Se refiere a la cantidad de memoria que usa el algoritmo. Considera el uso de variables, estructuras de datos y recursividad. También se expresa en Big O (ej. O(1) → usa memoria constante, O(n) → usa memoria proporcional al tamaño de entrada). A veces se sacrifica espacio por velocidad (ej. programación dinámica). EFICIENCIA Y COMPLEJIDAD DE ALGORITMOS EFICIENCIA Y COMPLEJIDAD DE ALGORITMOS CLASIFICACIÓN DE ALGORITMOS SEGÚN SU COMPLEJIDAD La complejidad de un algoritmo describe cómo crece su tiempo de ejecución a medida que el tamaño de entrada (n) aumenta. Principales órdenes de complejidad en Big O:  NOTACION BIG O La Notación Big O describe cómo crece el tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de la entrada (n). Mide el peor caso de un algoritmo, es decir, el tiempo máximo que podría tomar en ejecutarse. Ignora constantes y términos menores, enfocándose solo en el comportamiento a gran escala. Ayuda a comparar algoritmos sin necesidad de ejecutarlos. Ejemplo: Si un algoritmo tiene O(n²), significa que su tiempo de ejecución crece cuadráticamente con respecto al tamaño de la entrada (n). Si otro tiene O(log n), crecerá mucho más lentamente a medida que n aumente.  EJEMPLOS 1. Dado un número n, imprimir todos los números del 1 al n y luego imprimir todas las combinaciones de pares (i, j) dentro de ese rango. Primer bucle: Se ejecuta n veces. Complejidad: O(n) (lineal). Segundo bucle: Tiene dos bucles anidados, cada uno recorriendo n veces. Iteraciones totales: n * n = n². Complejidad: O(n²) (cuadrática).  ACTIVIDAD EN CLASE Objetivo: Evaluar la comprensión de la notación Big O y la eficiencia de algoritmos mediante un análisis breve y práctico. 1. Se presentan los siguientes fragmentos de código en Java. Cada estudiante debe identificar su complejidad en notación Big O y justificar su respuesta.  ACTIVIDAD EN CLASE 2. Comparación de Algoritmos: Si tienes dos algoritmos: uno con O(n²) y otro con O(n log n), ¿cuál elegirías para procesar una lista de 1,000,000 elementos? Explica tu elección en una o dos frases. 3. Desafío Final: ¿Por qué crees que en la vida real no siempre se usan los algoritmos más eficientes? Comparte un ejemplo donde la eficiencia no sea la única prioridad.  PRÁCTICA 1. Se requiere desarrollar un programa en Java que permita contar la cantidad de dígitos de un número entero positivo ingresado por el usuario. Para ello, debe implementar dos métodos diferentes: Un método iterativo que divida el número entre 10 sucesivamente hasta que se reduzca a 0. Un método basado en logaritmos que determine la cantidad de dígitos usando Math.log10(). El programa debe medir el tiempo de ejecución de cada método utilizando System.nanoTime() y comparar los resultados. Finalmente, el programa debe mostrar el número de dígitos y el tiempo tomado por cada método. 2. Desarrolle un programa en Java que permita determinar si un número entero positivo ingresado por el usuario es primo. Para ello, debe implementar dos versiones del algoritmo: Comprueba la divisibilidad del número desde 2 hasta N-1. Comprueba la divisibilidad solo hasta la raíz cuadrada del número, descartando múltiplos innecesarios. El programa debe medir el tiempo de ejecución de ambos métodos utilizando System.nanoTime(), mostrar los resultados y compararlos.  ACTIVIDAD N° 01 1. Implemente un programa en Java que calcule el Máximo Común Divisor (MCD) de dos números ingresados por el usuario utilizando dos enfoques distintos: Método de restas sucesivas (algoritmo de Euclides básico). Método de divisiones sucesivas (algoritmo de Euclides optimizado). El programa debe medir el tiempo de ejecución de cada método y compararlos. Explique en los comentarios del código la complejidad de cada enfoque en notación Big O. 2. Escriba un programa que cree y llene una matriz de 1000x1000 con números aleatorios. Luego, implemente dos métodos para recorrerla fila por fila y columna por columna. Compare los tiempos de ejecución y analice cuál es más eficiente. PREGUNTAS  ¿QUÉ HEMOS APRENDIDO? ¿Qué aprendiste en la sesión de hoy? ¿Para qué crees que te sirve lo aprendido? CONCLUSIONES