Refuerzo PUJ: algoritmia y lógica¶
Dieciséis horas de refuerzo para los estudiantes de Árboles y Grafos de la Pontificia Universidad Javeriana Cali, repartidas en cuatro sábados de cuatro horas: 17 y 24 de octubre, 7 y 14 de noviembre. Lo que se repasa es la base que Árboles y Grafos y Estructuras de Datos dan por vista, así que el material sirve a los dos cursos.
Desde el segundo, cada sábado tiene tres horas de programación y una de lógica. Una hora de programación gira alrededor de un problema de juez en línea del nivel de las tareas de Estructuras de Datos: diez minutos para leer el enunciado y buscar sus trampas, unos cuarenta para resolverlo en el computador y diez para su costo: de qué depende el tamaño de la entrada, cuántas veces corre cada ciclo y el total en \(O\). La idea o la estructura que hace falta se recuerda cuando el problema la pide. La hora de lógica se trabaja en papel: predicados y cuantificadores, la definición de \(O\) grande y el invariante de ciclo, planteado sobre los ciclos de los problemas de clase. Las sesiones del 24 de octubre y del 7 de noviembre dejan tres problemas de tarea cada una.
Las soluciones vienen en Python y en C++. Quien llega de Estructuras de Datos puede trabajar el mismo ejercicio en C.
Programa¶
Sesiones¶
- 17 de octubre. Estructuras y un recorrido: las estructuras con lo que cuesta cada operación, la memoria y la pila de llamadas, y un recorrido contra dos con UVa 11078.
- 24 de octubre. Tramos, matrices y lógica: los acumulados y el mejor tramo de un arreglo con UVa 507, en dos horas, los acumulados en dos dimensiones con UVa 108, y en lógica proposiciones, cuantificadores y la definición de \(O\).
- 7 de noviembre. Bisección y recorridos en grafos: encontrar la función de decisión con UVa 11516 y UVa 12032, el recorrido en amplitud con tope de pasos con UVa 336, y el recorrido en profundidad y los ciclos en un grafo dirigido, con UVa 11686 para resolver en casa.
- 14 de noviembre. Planteamiento e invariantes de ciclo: cómo se plantea la solución de tres problemas, la bisección sobre la respuesta para transcribir textos, el recorrido en amplitud sobre una rejilla con zonas prohibidas y el recorrido en profundidad para pintar con dos colores, y en lógica los invariantes de ciclo de UVa 11078 y UVa 507.
Clases en video¶
Las grabaciones de cada sesión están en la lista de reproducción del refuerzo, en orden: la sesión más reciente queda al final. Cada sesión se parte en videos cortos, para volver a un tema puntual sin recorrer la sesión entera. El reproductor de abajo va sobre la lista completa; la barra que lo encabeza la abre en YouTube, en una pestaña nueva.