Análisis y Diseño de Algoritmos

Análisis y Diseño de Algoritmos

• El contenido cubre el análisis y diseño de algoritmos.
• Se revisan algoritmos y métodos de ordenación.

Sílabo del Curso

• El nombre del curso es Análisis y Diseño de Algoritmos (100000S135).
• Esto corresponde al ciclo 1 de marzo de 2025.
• El curso forma parte de las carreras de Ingeniería de Sistemas e Informática e Ingeniería de Software.
• El curso otorga 3 créditos académicos.
• La enseñanza es presencial con 4 horas semanales.
• El curso proporciona las habilidades para desarrollar e implementar algoritmos complejos en programación orientada a objetos, para soluciones de software complejas.
• La sumilla indica que el curso es práctico y trata temas como ordenación, búsqueda, división, recursividad y grafos para plantear soluciones algorítmicas eficientes.
• Al finalizar, el alumno aplicará técnicas algorítmicas mediante el paradigma orientado a objetos.

Unidades y Logros Específicos de Aprendizaje

• La unidad 1 se centra en análisis de algoritmos y métodos de ordenación.
• Al finalizar la unidad, se espera que el estudiante aplique los fundamentos del análisis de algoritmos y métodos de ordenación para la resolución de problemas.
• La semana 1 a la 5 está dedicada a la Unidad de Aprendizaje 1.

Temario de la Unidad 1

• Complejidad algorítmica, eficiencia de un algoritmo, análisis de rendimiento, eficiencia y complejidad y notación Big O.
• Algoritmos de ordenación interna: intercambio, selección e inserción (codificación y complejidad).
• Algoritmos de ordenación externa y métodos de ordenación de archivos (mezcla directa, fusión natural, mezcla equilibrada múltiple, método polifásico).
• Resolución de problemas.

Unidad de Aprendizaje 2

• Se centra en métodos de búsqueda del curso.
• Al finalizar la unidad, se busca que el estudiante aplique los métodos algorítmicos para la resolución de problemas.
• Los temas cubiertos incluyen Algoritmos de Búsqueda Interna (TABLAS HASH: Tablas de Dispersión, Funciones de dispersión. Colisiones y resolución de colisiones. Exploración de direcciones).
• También, Algoritmos de Búsqueda Interna (TABLAS HASH: Realización de una tabla dispersa. Direccionamiento enlazado).
• Se ven Algoritmos de Búsqueda Externa (Algoritmos de Búsqueda en Archivos: Búsqueda secuencial mediante bloques. Búsqueda secuencial con índices. Búsqueda por transformación de claves. Listas Invertidas. Multilistas).
• Resolución de problemas asociados a estos temas.
• Las semanas 6 a la 10 están dedicadas a la Unidad de Aprendizaje 2.

Unidad de Aprendizaje 3

• Abarca la técnica de divide y vencerás.
• Al finalizar la unidad, se espera que el estudiante aplique métodos de "divide y vencerás" para ordenación y búsqueda.
• Se revisan temas como:
• Conceptos sobre la técnica divide y vencerás. Ordenación Shell y Rápida (Quick sort): Codificación y análisis del algoritmo.
• Búsqueda binaria (codificación y análisis), comparación con búsqueda lineal.
• Conceptos de recursividad, métodos recursivos, pila de llamadas, recursividad indirecta y comparación con iteración.
• Backtracking, algoritmos de vuelta atrás y selección óptima.
• Resolución de problemas.
• Las semanas 11 a la 15 están dedicadas a la Unidad de Aprendizaje 3.

Unidad de Aprendizaje 4

• Cubre la exploración de Grafos y Algoritmos Voraces.
• Al finalizar la unidad, el estudiante debe aplicar métodos de grafos dirigidos y no dirigidos para la solución de problemas.
• Se analizan grafos dirigidos, algoritmos fundamentales, representación de grafos, recorrido en anchura y profundidad.
• Se revisan la matriz de caminos, el algoritmo de Warshall y el algoritmo de Dijkstra para caminos más cortos con un solo origen.
• Para grafos no dirigidos, se ven algoritmos fundamentales y el árbol de expansión de corte mínimo (algoritmos de Prim y Kruskal).
• Las semanas 16 a la 18 están dedicadas a la Unidad de Aprendizaje 4.

Metodología de Enseñanza

• Se expone la construcción del conocimiento a través de ejemplos y casos prácticos.
• Se promueve la participación activa de los estudiantes mediante ejercicios, lecturas y preguntas.
• Se fomenta el aprendizaje individual y colaborativo para un trabajo metacognitivo.
• Se requiere la asistencia a clases tras leer los temas correspondientes a cada sesión.
• Se utilizan recursos como pizarra, multimedia, videos y comunicaciones electrónicas.

Sistema de Evaluación

• El cálculo del promedio final se basa en prácticas calificadas (PC), participación en clase (PA) y examen final (EXFN).
• La ponderación es: (20%)PC1 + (20%)PC2 + (20%)PC3 + (10%)PA + (30%)EXFN.
• La nota mínima aprobatoria final es 12.

Prácticas Calificadas

• La práctica calificada 1 (PC1) se realiza en la semana 5 y es individual.
• PC2 se realiza en la semana 10 (individual).
• PC3 se realiza en la semana 15 (individual).
• La participación en clase (PA) se evalúa en la semana 17, promediando las participaciones individuales.
• El examen final (EXFN) es individual y se realiza en la semana 18.

Indicaciones Adicionales sobre la Evaluación

• Si no se rinde el examen final, se puede rendir un examen de rezagado.
• La nota obtenida en el examen de rezagado reemplaza al examen final no rendido.
• Se debe rendir el examen de rezagado presentando una solicitud y pagando los derechos correspondientes según el tarifario de la Universidad.
• Los exámenes de rezagados se aplican al final del período lectivo y abarcan todos los temas vistos.
• Si no se rinde una práctica calificada (PC), se reemplaza por la nota del examen final.
• Si tampoco se rinde el examen final, se reemplaza por el examen rezagado automáticamente.
• Si hay más de una práctica calificada no rendida, solo se reemplaza la de mayor peso.

Preguntas de Prueba de Entrada

• ¿Cuál es la diferencia entre eficiencia y complejidad de un algoritmo, y por qué es importante la notación Big O?
• ¿Cómo funciona el algoritmo de ordenación por intercambio (Bubble Sort), y cuál es su complejidad?
• ¿Cómo funciona el algoritmo de mezcla directa en la ordenación externa, y en qué situaciones se utiliza?
• ¿Qué es el método polifásico de ordenación externa y en qué se diferencia de la mezcla equilibrada múltiple?
• Para una empresa de comercio electrónico, ¿qué algoritmo recomendarías para optimizar la búsqueda de productos, considerando que actualmente usan una búsqueda lineal lenta?
• ¿Qué algoritmo de ordenación recomendarías a una startup de análisis financiero que inicialmente implementó Bubble Sort, pero que no escala bien con grandes volúmenes de datos?
• ¿Cómo aplicarías el algoritmo de Dijkstra para implementar un sistema de navegación en tiempo real para el transporte público, considerando el tráfico en constante cambio?

Introducción a la Complejidad Algorítmica

• La eficiencia de los algoritmos es clave en el desarrollo de software debido al crecimiento exponencial de los datos.
• Las aplicaciones de inteligencia artificial y procesamiento de bases de datos dependen de algoritmos optimizados.
• La complejidad algorítmica permite analizar y comparar el rendimiento de diferentes soluciones.
• La notación Big O permite predecir el comportamiento de un algoritmo a medida que aumentan los datos.
• Se explorarán los conceptos de eficiencia algorítmica, cómo medir el rendimiento de los algoritmos y cómo elegir la mejor solución según la complejidad computacional.
• Al finalizar la sesión, se espera que el estudiante conozca la complejidad de los algoritmos, diferenciando su complejidad temporal y espacial aplicable en proyectos con Java.
• Es importante analizar la eficiencia de un algoritmo.

Algoritmos

• Un algoritmo es un conjunto finito de pasos definidos y organizados lógicamente para resolver un problema o tarea.
• Los algoritmos pueden expresarse en lenguaje natural, diagramas de flujo, pseudocódigo o lenguajes de programación.
• Un ejemplo de algoritmo es el proceso para preparar café, que incluye calentar agua, añadir café, revolver y servir.

Características de los Algoritmos

• Los algoritmos deben cumplir con las siguientes características:
• Definido: Cada paso debe estar claramente especificado, sin ambigüedades.
• Preciso: No debe haber confusión en la ejecución de los pasos.
• Finito: Debe terminar en algún momento; no puede ejecutarse indefinidamente.
• Ordenado: Las instrucciones deben seguir una secuencia lógica.
• Determinista: Para la misma entrada, siempre debe dar el mismo resultado.
• Eficiente: Debe usar la menor cantidad de recursos posible (tiempo y memoria).
• General: Puede aplicarse a distintos conjuntos de datos de entrada.

Complejidad Algorítmica

• La eficiencia de un algoritmo es clave en el desarrollo de software.
• La eficiencia determina qué tan rápido y qué tantos recursos consume una solución al procesar datos.
• El análisis del rendimiento permite seleccionar la mejor alternativa para resolver problemas computacionales.
• Un algoritmo eficiente 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 y uso de memoria.
• Ordenar una lista de 1,000,000 de números con un algoritmo lento como Burbuja (O(n²)) puede tardar minutos.
• Usar Quicksort (O(n log n)) lo hace en segundos.

Importancia del Análisis de Rendimiento

• El rendimiento de un algoritmo impacta la escalabilidad, la optimización de hardware y la experiencia del usuario.
• Un algoritmo ineficiente puede funcionar bien con pocos datos, pero volverse inusable con grandes volúmenes.
• Algoritmos eficientes requieren menos CPU y memoria.
• La velocidad de respuesta es crucial para la satisfacción del usuario.
• Un motor de búsqueda como Google no puede usar un algoritmo ineficiente para ordenar resultados porque millones de personas lo consultan simultáneamente.

Factores que Afectan la Eficiencia

• El tiempo de ejecución mide cuánto tarda un algoritmo en ejecutarse según la cantidad de datos de entrada (n).
• La notación Big-O (O) clasifica algoritmos según su crecimiento en función de n.
• Algunos ejemplos son: Acceder a un elemento en un array (constante), búsqueda binaria (logarítmico), recorrer un array (lineal), merge sort (cuasilineal), burbuja-selección (cuadrático), recursión sin optimizar (exponencial).
• Ejemplo: Buscar un número en una lista ordenada de 1 millón de elementos con búsqueda lineal recorre hasta 1 millón de pasos, mientras que la búsqueda binaria lo encuentra en aproximadamente 20 pasos.
• El uso de memoria mide cuánta memoria extra usa un algoritmo al ejecutarse.
• Depende de si el algoritmo modifica los datos originales, utiliza estructuras adicionales o usa recursión (que consume más memoria por el uso de la pila de llamadas).
• Quicksort es más eficiente en memoria que Merge Sort porque evita crear estructuras auxiliares.
• Fibonacci recursivo sin memorización usa mucha memoria por múltiples llamadas innecesarias.

Análisis de Rendimiento (Medición Empírica vs Teórica)

• 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:
  • Medición empírica: 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: El rendimiento real en una máquina específica.
  • Desventaja: no es generalizable, ya que depende del entorno de ejecución.
  • 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).
  • Esto no depende del hardware ni del lenguaje de programación.
  • Ventaja: Esto permite comparar algoritmos independientemente del entorno de ejecución.
  • Desventaja: No siempre refleja con precisión el tiempo de ejecución real.
• El tiempo de ejecución mide el tiempo real que tarda en ejecutarse un algoritmo.
• El conteo de operaciones calcula la cantidad de pasos o comparaciones realizadas sin ejecutarlo.
• Por ejemplo, una búsqueda lineal podría tardar 1 segundo en el peor caso, pero una búsqueda binaria haría la búsqueda en aproximadamente 20 pasos.

Eficiencia y Complejidad de Algoritmos

• Eficiencia Temporal: El 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: 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).

Notación 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.
• Ingora constantes y términos menores, centrándose solo en el comportamiento a gran escala.
• Ayuda a comparar algoritmos sin necesidad de ejecutarlos.
• Por 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 de Análisis de Complejidad

• Bucle Simple
  • Recorre n veces
  • Complejidad: O(n)(lineal).
• Bucle Anidado
  • Tiene dos bucles anidados
  • Cada uno recorriendo n veces.
  • Iteraciones totales: n * n = n².
  • Complejidad: O(n²)(cuadrática).

Actividad en Clase sobre Complejidad y Eficiencia

• Evaluar la comprensión de la notación Big O y la eficiencia de algoritmos mediante un análisis breve y práctico.
• Se presentan fragmentos de código en Java. Cada estudiante debe identificar su complejidad en notación Big O y justificar su respuesta.
• Comparación de Algoritmos:
  • Si se cuenta con dos algoritmos que difieren en complejidad. Uno es con O(n²) y otro con O(n log n). ¿Cuál elegirías para procesar una lista de 1,000,000 elementos?
• Desafío Final:
• ¿Por qué crees que en la vida real no siempre se usan los algoritmos más eficientes? Menciona un ejemplo donde la eficiencia no sea la única prioridad.

Práctica en Java: Análisis de Dígitos y Números Primos

• Desarrollar un programa en Java que cuente la cantidad de dígitos de un número entero positivo ingresado mediante dos métodos:
• 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.
• Mostrar el número de dígitos y el tiempo tomado por cada método.
• Desarrollar un programa que determine si un número es primo, implementando 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.
• Medir y comparar el tiempo de ejecución de ambos métodos.
• Actividad N° 01.

Actividad Adicional en Java: MCD y Recorrido de Matriz

• Se debe implementar 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, compararlos y explicar la complejidad en notación Big O.
• Se debe Escribir un programa que crea y llena una matriz de 1000x1000 con números aleatorios.
• Implementar dos métodos para recorrerla fila por fila y columna por columna.
• Comparar los tiempos de ejecución y analizar cuál es más eficiente.