Curso-Taller PC

Dirigido a

Este curso-taller está dirigido a todos los estudiantes de educación superior interesados en participar en los concursos de programación ICPC.

Objetivo

Obtener un panorama general de la programación competitiva por medio del estudio y la práctica de los conocimientos y técnicas fundamentales más recurrentes en los concursos de programación ICPC.

Fechas

Inicia el 10 de febrero de 2021 y termina el 9 de junio de 2021

Horario

Miércoles 13:00-15:00 hrs (UTC-5)

Duración

32 horas (16 sesiones de 2 horas cada una)

Modalidad

En línea a través de Microsoft Teams

Acreditación

Se otorgará constancia de acreditación a todos los participantes que cumplan con los requisitos de asistencia y evaluación.

Instructor

Victor Yoguel Salazar Alanis
Medallista de Oro en la Olimpiada Mexicana de Informática 2016
Finalista Regional ICPC México 2018, 2019 y 2020

Contenido

Sesiones	Videos	Problemas	Diapositivas
1. Introducción a la programación competitiva y C++/STL Presentación del curso, panorama general y oportunidades en programación competitiva, fundamentos de C++, biblioteca estándar STL, problemas en programación competitiva.
2. Técnicas básicas de conteo Regla de la suma, regla del producto, permutaciones, combinaciones, separadores y problemas de ejemplo.
3. Análisis de complejidad Análisis asintótico, Big O, constantes en la complejidad, producto de complejidades, suma de complejidades, complejidad de memoria, análisis por amortización, límites de tiempo.
4. Problemas de optimización Técnica de optimización BUD para eliminar cuellos de botella, trabajo innecesario y trabajo duplicado en la solución de un problema.
5. Greedy Introducción a la técnica Greedy y resolución de problemas por medio de la misma.
6. Pilas y colas Resolución de problemas utilizando estructuras de datos fundamentales de pilas y colas.
7. Recursión Resolución de problemas utilizando recursión en problemas clásicos: sucesión de Fibonacci, generación de subconjuntos, generación de permutaciones y problema diversos.
8. Upsolving Resolución de problemas asignados en tareas anteriores: rangos, salsa la pikina, permutaciones de caracteres y tercias.
9. Complejidad logarítmica Logaritmos, búsqueda binaria, métodos de ordenamiento bubble sort, insertion sort, quick sort, merge sort, counting/bucket sort.
10. Búsqueda binaria Diseño, implementación iterativa y recursiva, errores comunes, funciones STL binary_search, lower_bound, upper_bound.
11. Estructuras de datos Estructuras de datos y algoritmos del STL de C++ map/unordered_map, set/unordered_set, multiset/unordered_multiset, find, priority_queue, min priority_queue, policy-based data structures.
12. Problemas de búsqueda y ordenamiento Resolución de problemas clásicos de búsqueda y ordenamiento utilizando estructuras de datos y algoritmos del STL de C++: unordered_map, multiset, lower_bound, upper_bound.
13. Programación dinámica Introducción a programación dinámica por medio de problemas clásicos: Fibonacci, dice combinations, book shop (knapsack), minimizing coins.
14. Teoría de números Aritmética modular, pequeño teorema de Fermat, exponenciación binaria modular (implementación iterativa y recursiva), teorema fundamental de la aritmética, criba de Eratóstenes, GCD y LCM.
15. Grafos Terminología, representación (matriz de adyacencia y lista de adyacencia), recorridos DFS y BFS, caminos más cortos (Dijkstra), unión-buscar.
16. Evaluación y cierre del curso Evaluación del curso y recomendaciones de sitios y libros para continuar aprendiendo y preparándose.

Contacto

Para mayor información comunícate por correo con M.C. Froylán Eloy Hernández Castro (fhernand@uaslp.mx)