5.26. CS212. Análisis y Diseño de Algoritmos (Obligatorio)

• Semestre: 5to Sem. Créditos: 4
• Horas del curso: Teoría: 2 horas; Práctica: 2 horas; Laboratorio: 2 horas;

• Prerrequisitos:

  • CS210. Algoritmos y Estructuras de Datos (4to Sem)
  • CS211. Teoría de la Computación (4to Sem)

5.26.1. Justificación

Los algoritmos son el corazón de la ciencia de la computación. Este curso proporciona las herramientas matemáticas y analíticas necesarias para evaluar la eficiencia de los algoritmos en términos de tiempo y espacio. Los estudiantes explorarán estructuras de datos fundamentales, análisis de complejidad y varios paradigmas de diseño, como fuerza bruta, algoritmos voraces y programación dinámica. Comprender estas técnicas es esencial para construir software que no solo sea funcional, sino también escalable y eficiente en el uso de recursos.

5.26.2. Objetivos Generales

1.

Dominar el uso de la notación asintótica para analizar el rendimiento de los algoritmos.

2.

Aplicar estructuras de datos fundamentales para resolver problemas computacionales.

3.

Usar estrategias algorítmicas como Voraz, Divide y Vencerás y Programación Dinámica.

4.

Analizar la complejidad de algoritmos en el mejor, promedio y peor de los casos.

5.

Desarrollar la capacidad de seleccionar el algoritmo más apropiado para un problema dado.

5.26.3. Contribución a los resultados (Outcomes)

AG-C08) Análisis de Problemas: Identifica, formula y analiza problemas complejos de computación. (Usage)

AG-C12) Aplica la teoría de la ciencia de la computación y los fundamentos de desarrollo de software para producir soluciones basadas en computadora. (Usage)

5.26.4. Contenido

5.26.4.1. Estructuras de Datos Fundamentales (6 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022, Kleinberg and Tardos, 2005]

Temas

1.

Tipo de Dato Abstracto (ADT) y operaciones sobre un ADT:

a)

Operaciones de diccionario (insertar, eliminar, encontrar)

2.

Arreglos:

a)

Numéricos vs no numéricos, cadenas de caracteres

b)

Unidimensionales (vector) vs multidimensionales (matriz)

3.

Registros/Estructuras/Tuplas y Objetos

4.

Listas enlazadas (por razones históricas):

a)

Simples vs Dobles y Lineales vs Circulares

5.

Pilas

6.

Colas y deques:

a)

Cola de prioridad basada en montículo

7.

Tablas/mapas hash:

a)

Resolución de colisiones y complejidad (por ejemplo, sondeo, encadenamiento, rehash)

8.

árboles:

a)

Binarios, n-arios y árboles de búsqueda

b)

Balanceados (por ejemplo, AVL, Rojo-Negro, Montículo)

9.

Conjuntos

Aprendizaje esperado (Learning Outcomes)

1.

Para cada ADT/Estructura de Datos en esta unidad:

a)

Explicar su definición, propiedades, representación(es) y operaciones de ADT asociadas.

b)

Explicar paso a paso cómo las operaciones de ADT asociadas con la estructura de datos la transforman.

[Explicar]

2.

Explicar cómo se maneja la evitación de colisiones y la resolución de colisiones en tablas hash [Explicar]

3.

Explicar la propiedad de montículo y el uso de montículos como una implementación de una cola de prioridad [Explicar]

5.26.4.2. Algoritmos Fundamentales (6 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022, Kleinberg and Tardos, 2005]

Temas

1.

Grafos (por ejemplo, [no]dirigidos, [a]cíclicos, [no]conexos y [no]ponderados):

a)

Representación de grafos: lista de adyacencia vs matriz

2.

Algoritmos de búsqueda:

a)

Complejidad O(n) (por ejemplo, búsqueda lineal/secuencial en arreglo/lista)

b)

Complejidad O(log ₂n) (por ejemplo, búsqueda binaria)

c)

Complejidad O(log _bn) (por ejemplo, búsqueda en árbol no informada en profundidad/amplitud)

3.

Algoritmos de ordenamiento (por ejemplo, estables, inestables):

a)

Complejidad O(n²) (por ejemplo, inserción, selección)

b)

Complejidad O(nlog n) (por ejemplo, quicksort, merge, timesort)

4.

Algoritmos de grafos:

a)

Camino más corto (por ejemplo, Dijkstra, Floyd)

b)

árbol de expansión mínima (por ejemplo, Prim, Kruskal)

5.

Algoritmos de ordenamiento:

a)

Complejidad O(nlog n) heapsort

b)

Pseudo O(n) complejidad (por ejemplo, bucket, counting, radix)

6.

Algoritmos de grafos:

a)

Clausura transitiva (por ejemplo, Warshall)

b)

Ordenamiento topológico

7.

Emparejamiento:

a)

Emparejamiento eficiente de cadenas (por ejemplo, Boyer-Moore, Knuth-Morris-Pratt)

b)

Emparejamiento de subsecuencia común más larga

c)

Emparejamiento de expresiones regulares

Aprendizaje esperado (Learning Outcomes)

1.

Para cada algoritmo en esta unidad explicar paso a paso cómo opera el algoritmo [Explicar]

2.

Para cada enfoque algorítmico (por ejemplo, ordenamiento) en esta unidad aplicar un ejemplo prototípico del enfoque (por ejemplo, ordenamiento por mezcla) [Aplicar]

3.

Dados los requisitos para un problema, desarrollar múltiples soluciones usando varias estructuras de datos y algoritmos. Posteriormente, evaluar la idoneidad, fortalezas y debilidades seleccionando un enfoque que satisfaga mejor los requisitos [Crear]

4.

Explicar factores más allá de la eficiencia computacional que influyen en la elección de algoritmos, como el tiempo de programación, la mantenibilidad y el uso de patrones específicos de la aplicación en los datos de entrada [Explicar]

5.

Para cada uno de los algoritmos y enfoques algorítmicos en los temas del Núcleo KA:

a)

Explicar un ejemplo prototípico del algoritmo, y

b)

Explicar paso a paso cómo opera el algoritmo.

[Explicar]

5.26.4.3. Algoritmos Avanzados (4 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022, Kleinberg and Tardos, 2005]

Temas

1.

Algoritmos de criptografía (por ejemplo, SHA-256)

2.

Algoritmos paralelos

3.

Algoritmos de consenso (por ejemplo, Blockchain):

a)

Prueba de trabajo vs prueba de participación

4.

Algoritmos de computación cuántica:

a)

Basados en oráculo (por ejemplo, Deutsch-Jozsa, Bernstein-Vazirani, Simon)

b)

Aceleración superpolinomial mediante QFT (por ejemplo, Shor)

c)

Aceleración polinomial mediante amplificación de amplitud (por ejemplo, Grover)

5.

Algoritmo de Transformada Rápida de Fourier (FFT)

6.

Algoritmo de evolución diferencial

Aprendizaje esperado (Learning Outcomes)

1.

Una apreciación de la computación cuántica y su aplicación a ciertos problemas [Explicar]

5.26.4.4. Estrategias Algorítmicas (24 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022, Dasgupta et al., 2006]

Temas

1.

Paradigmas:

a)

Fuerza Bruta (por ejemplo, búsqueda lineal, ordenamiento por selección, viajante de comercio, mochila)

b)

Disminuir y Vencer:

1)

Por una Constante (por ejemplo, ordenamiento por inserción, ordenamiento topológico)

2)

Por un Factor Constante (por ejemplo, búsqueda binaria)

3)

Por un Tamaño Variable (por ejemplo, Euclides)

c)

Dividir y Vencer (por ejemplo, búsqueda binaria, quicksort, mergesort, Strassen)

d)

Voraz (por ejemplo, Dijkstra, Kruskal, Mochila)

e)

Transformar y Vencer:

1)

Simplificación de instancia (por ejemplo, encontrar duplicados mediante preordenamiento de lista)

2)

Cambio de representación (por ejemplo, heapsort)

3)

Reducción de problema (por ejemplo, mínimo común múltiplo, programación lineal)

4)

Programación dinámica (por ejemplo, Floyd, Marshall, Bellman-Ford)

f )

Compromisos espacio vs tiempo (por ejemplo, hash)

2.

Manejo del crecimiento exponencial (por ejemplo, heurística A*, ramificación y poda, retroceso)

3.

Iteración vs recursión (por ejemplo, factorial, búsqueda en árbol)

4.

Paradigmas:

a)

Algoritmos de aproximación

b)

Mejora iterativa (por ejemplo, Ford-Fulkerson, simplex)

c)

Algoritmos aleatorizados/estocásticos (por ejemplo, corte máximo, bolas y cubos)

5.

Computación cuántica

Aprendizaje esperado (Learning Outcomes)

1.

Para cada uno de los paradigmas en esta unidad:

a)

Explicar sus características definitorias

b)

Explicar un ejemplo que demuestre el paradigma incluyendo cómo este ejemplo satisface las características del paradigma.

[Explicar]

2.

Para cada uno de los algoritmos en la unidad Fundamentos Algorítmicos (AL) -FoundationalDataStructuresAlgorithms, explicar el paradigma utilizado por el algoritmo y cómo ejemplifica este paradigma [Explicar]

3.

Dado un algoritmo, explicar el paradigma utilizado por el algoritmo y cómo ejemplifica este paradigma [Explicar]

4.

Dar un problema del mundo real, evaluar paradigmas algorítmicos apropiados y algoritmos de estos paradigmas que aborden el problema incluyendo evaluar los compromisos entre los paradigmas y algoritmos seleccionados [Evaluar]

5.

Dar ejemplos de algoritmos iterativos y recursivos que resuelvan el mismo problema, explicar los beneficios y desventajas de cada enfoque [Explicar]

6.

Evaluar si un enfoque voraz conduce a una solución óptima [Evaluar]

7.

Explicar varios enfoques para abordar problemas computacionales cuyas soluciones algorítmicas son exponenciales [Explicar]

5.26.4.5. Marco de Análisis de Complejidad (6 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022, Sipser, 2012]

Temas

1.

Marco de Análisis de Complejidad:

a)

Rendimiento de un algoritmo en el mejor caso, caso promedio y peor caso

b)

Mediciones empíricas y relativas (Orden de Crecimiento)

c)

Tamaño de entrada y operaciones primitivas

d)

Eficiencia de tiempo y espacio

2.

Mediciones empíricas de rendimiento

3.

Compromisos tiempo-espacio en algoritmos

Aprendizaje esperado (Learning Outcomes)

1.

Para cada algoritmo en la unidad Fundamentos Algorítmicos (AL) -FoundationalDataStructuresAlgorithms, explicar su clase de complejidad de tiempo de ejecución y por qué pertenece a esta clase [Explicar]

2.

Desarrollar estudios empíricos para determinar y validar hipótesis sobre la complejidad de tiempo de ejecución de varios algoritmos ejecutando algoritmos con entradas de varios tamaños y comparando el rendimiento real con el análisis teórico [Crear]

3.

Explicar ejemplos que ilustren los compromisos tiempo-espacio de algoritmos [Explicar]

4.

Explicar cómo el balance del árbol afecta la eficiencia de las operaciones de árbol de búsqueda binaria [Explicar]

5.26.4.6. Notación Asintótica y Clases de Complejidad (6 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022, Sipser, 2012]

Temas

1.

Análisis de complejidad asintótica (cotas promedio y peor caso):

a)

Notaciones formales Big-O, Big-Omega y Big-Theta

b)

Clases de Complejidad Fundamentales y Ejemplos/Problemas Representativos:

1)

O(1) Constante (por ejemplo, acceso a arreglo)

2)

O(log ₂n) Logarítmica (por ejemplo, búsqueda binaria)

3)

O(n) Lineal (por ejemplo, búsqueda lineal)

4)

O(nlog ₂n) Log Lineal (por ejemplo, mergesort)

5)

O(n²) Cuadrática (por ejemplo, ordenamiento por selección)

6)

O(n^c) Polinomial (por ejemplo, O(n³) eliminación gaussiana)

7)

O(2ⁿ) Exponencial (por ejemplo, Mochila, Satisfactibilidad (SAT), Viajante de Comercio (TSP), todos los subconjuntos)

8)

O(n!) Factorial (por ejemplo, circuito hamiltoniano, todas las permutaciones)

Aprendizaje esperado (Learning Outcomes)

1.

Para cada clase de complejidad fundamental en esta unidad, explicar un algoritmo que demuestre la complejidad de tiempo de ejecución asociada [Explicar]

2.

Aplicar la notación Big-O para dar cotas superiores en la complejidad tiempo/espacio de algoritmos [Aplicar]

5.26.4.7. Análisis de Complejidad II: Recursión, Amortización y Cotas Ajustadas (12 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022, Sipser, 2012]

Temas

1.

Notaciones Little-o, Little-Omega y Little Theta

2.

Análisis recursivo formal

3.

Análisis amortizado

Aprendizaje esperado (Learning Outcomes)

1.

Dado un problema para programar para el cual puede haber varios enfoques algorítmicos, evaluarlos y determinar cuáles son factibles, y seleccionar uno que sea óptimo en implementación y comportamiento de tiempo de ejecución [Evaluar]

2.

Usar relaciones de recurrencia para evaluar la complejidad de tiempo de algoritmos definidos recursivamente [Aplicar]

3.

Aplicar relaciones de recurrencia elementales usando una forma del Teorema Maestro [Aplicar]

5.26.4.8. Teoría de la Complejidad Computacional (6 horas) [Habilidades ]

Referencias Bibliográficas: [Sipser, 2012, Cormen et al., 2022]

Temas

1.

Tractabilidad e intractabilidad:

a)

Clases de Complejidad P, NP y NP-Completo

b)

Problemas NP-Completos (por ejemplo, SAT, Mochila, TSP)

c)

Reducciones

Aprendizaje esperado (Learning Outcomes)

1.

Explicar la importancia de la NP-Completitud [Explicar]

2.

Explicar ejemplos de problemas NP-completos [Explicar]

3.

Explicar las clases P y NP [Explicar]

5.26.5. Referencias Bibliográficas

[Cormen et al., 2022]

[Kleinberg and Tardos, 2005]

[Dasgupta et al., 2006]

[Sipser, 2012]