• ES Español
• EN English

5.33. Algoritmos para Problemas Complejos (Obligatorio)

5.33.1. Justificación ↑ Volver arriba

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 ↑ Volver arriba

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) ↑ Volver arriba

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 ↑ Volver arriba

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

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] ↑ Volver arriba

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] ↑ Volver arriba

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:
6. Explicar un ejemplo prototípico del algoritmo, y
7. Explicar paso a paso cómo opera el algoritmo. enumerate [Explicar]

5.33.4.4. Algoritmos Fundamentales (12 horas) [Habilidades AG-C08,AG-C12] ↑ Volver arriba

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 ↑ Volver arriba

Halim, S. and Halim, F. (2020). Competitive Programming 4: The Lower Bound of Programming Contests. Lulu.

Laaksonen, A. (2020). Competitive Programmer's Handbook. Draft.

Skiena, S. S. (2020). The Algorithm Design Manual. Springer, 3rd edition.