5.33. CS311. Algoritmos para Problemas Complejos (Obligatorio)

• Semestre: 6to Sem. Créditos: 3
• Horas del curso: Teoría: 2 horas; Laboratorio: 2 horas;

• Prerrequisitos:

  • CS212. Análisis y Diseño de Algoritmos (5to Sem)

5.33.1. Justificación

La Programación Competitiva entrena a los estudiantes para resolver problemas algorítmicos complejos bajo restricciones de tiempo y recursos. Este curso cierra la brecha entre el diseño algorítmico teórico y la implementación de alto rendimiento. Cubre técnicas avanzadas en programación dinámica, teoría de grafos y matemáticas, fomentando el pensamiento analítico requerido para entrevistas de ingeniería de software de primer nivel y concursos de programación internacionales como el ICPC.

5.33.2. Objetivos Generales

1.

Dominar técnicas y paradigmas avanzados de programación competitiva.

2.

Desarrollar la capacidad de analizar rápidamente la complejidad de soluciones potenciales.

3.

Implementar estructuras de datos eficientes para consultas de rango y actualizaciones dinámicas.

4.

Aplicar algoritmos matemáticos y geométricos especializados para resolver problemas de concursos.

5.

Optimizar código para velocidad de ejecución y uso de memoria en un entorno competitivo.

5.33.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.33.4. Contenido

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

Referencias Bibliográficas: [Halim and Halim, 2020, Laaksonen, 2020]

Temas

1.

Búsqueda Completa: Retroceso Recursivo y Máscaras de bits.

2.

Estrategias Voraces: Propiedad de elección y subestructura óptima.

3.

Divide y Vencerás: Búsqueda Binaria sobre la respuesta y Búsqueda Ternaria.

4.

Programación Dinámica: Reducción de estado, DP de dígitos y DP en árboles.

Aprendizaje esperado (Learning Outcomes)

1.

Aplicar técnicas de poda de búsqueda para resolver problemas NP-difíciles con restricciones pequeñas [Usar]

2.

Identificar el paradigma más eficiente para un enunciado de problema dado [Evaluar]

5.33.4.2. Algoritmos Fundamentales (12 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Halim and Halim, 2020, Skiena, 2020]

Temas

1.

Árboles de Fenwick (Árboles Binarios Indexados).

2.

Árboles de Segmentos: Propagación Diferida y Árboles de Segmentos Persistentes.

3.

Descomposición de Raíz Cuadrada y Algoritmo de Mo.

4.

Tablas Dispersas para RMQ.

Aprendizaje esperado (Learning Outcomes)

1.

Implementar estructuras de consulta de rango para actualizaciones de datos en tiempo real [Evaluar]

2.

Analizar las compensaciones entre diferentes estructuras de datos de consulta de rango [Usar]

5.33.4.3. Algoritmos Fundamentales (12 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Laaksonen, 2020, Halim and Halim, 2020]

Temas

1.

Flujo en Redes: Flujo Máximo Corte Mínimo (Dinic y Edmonds-Karp).

2.

Componentes Fuertemente Conexas (Tarjan y Kosaraju).

3.

Emparejamiento Bipartito y Descomposición Pesado-Ligero.

4.

Descomposición por Centroide en árboles.

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.33.4.4. Algoritmos Fundamentales (12 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Skiena, 2020, Laaksonen, 2020]

Temas

1.

Teoría de Números: Criba de Eratóstenes, Euclides Extendido e Inverso Modular.

2.

Combinatoria: Inclusión-Exclusión y Lema de Burnside.

3.

Geometría Computacional: Producto Cruz, Envolvente Convexa (Cadena Monótona) e Intersección de líneas.

4.

Transformada Rápida de Fourier (FFT) para multiplicación de polinomios.

Aprendizaje esperado (Learning Outcomes)

1.

Resolver problemas combinatorios usando aritmética modular [Usar]

2.

Implementar primitivas geométricas para análisis de relaciones espaciales [Evaluar]

5.33.5. Referencias Bibliográficas

[Halim and Halim, 2020]

[Laaksonen, 2020]

[Skiena, 2020]