Saltar a contenido

Ejercicios · Refuerzo PUJ 7 de noviembre

Actividades para trabajar en el navegador los temas de la sesión del 7 de noviembre. Las actividades de tope, palitos y la escalera corren el código de los tres problemas que se resuelven en clase.

Cómo se plantea la solución

repartir textos entre empleados

Bisección sobre la respuesta: preguntas de planteamiento, y después se mueven lo y hi sobre la fila de textos hasta 1700.

una rejilla con zonas prohibidas

Se marcan las zonas con la distancia euclidiana y se avanza el frente de la cola sobre el tablero, decidiendo qué vecinas entran.

dos colores

Se escoge el color de cada nodo con la pila de llamadas a la vista, hasta ver el choque en el triángulo y el pedazo que queda sin mirar.

Recorrido en amplitud con tope de pasos

el recorrido con tope de pasos

UVa 336, el problema de la hora 2, sobre las dos redes de la muestra. Se predice cuántos nodos quedan por fuera y después corre el código de la sesión, con la cola y las distancias a la vista. Una tarjeta aplica a la misma consulta tres errores: expandir un nodo a distancia TTL, marcar al sacar de la cola y consultar un nodo ausente.

amplitud

El vértice más lejano del arranque, con un color por capa: por qué la primera vez que la búsqueda toca a alguien es siempre por el camino más corto.

Recorrido en profundidad y ciclos

los tres estados y los ciclos

UVa 11686, el problema de la hora 3. En cada arista se decide si cierra un ciclo, con el diamante y con un grafo que tiene uno, y una respuesta equivocada explica qué mirar. Después corre la función dfs de la sesión, y una tabla muestra en qué grafos responde mal quien lleva solo dos estados.

topodfs

El orden topológico con la profundidad, en sus formas recursiva y con pila explícita, sobre otros cuatro grafos.

Bisección: encontrar la función

la escalera y el factor de fuerza

UVa 12032, el problema de la hora 1. Se predice la fuerza mínima mirando la escalera y después corre el código de la sesión, las dos funciones: la que simula la subida, que es la función de decisión, y la que la bisecta. Cuatro escaleras, entre ellas una donde la respuesta no es el salto más grande.

buscar

La búsqueda binaria sobre un arreglo ordenado, división por división, con las posiciones descartadas tachándose. Es la mecánica que después se aplica sobre una función de decisión en vez de sobre un arreglo.

Costo

tamano

Ocho soluciones de juez, entre ellas la de UVa 839: decir de qué variable depende el tamaño, cuántas veces corre cada ciclo o llamada, el total en \(O\) y si alcanza contra los límites del enunciado.

Invariantes de ciclo

sumar

La suma de un arreglo: predecir qué devuelve, mirar la traza de estados y encontrar los invariantes \(I_0\) e \(I_1\), que se demuestran con inicialización, estabilidad y terminación.

credito

UVa 11078: los invariantes del mayor y de mejor, con el mayor llamado maximo. Al elegir un candidato errado, la traza marca en rojo el chequeo donde falla.

mayores

El mayor y el segundo mayor en un recorrido: ninguno de los dos invariantes se demuestra por separado, y un arreglo con todos los valores iguales decide cómo escribir el del segundo.

tramo

UVa 507 sin el desempate: los invariantes de suma y de mejor. Trae la respuesta del ejercicio en papel, así que va después de intentarlo.