Este proyecto trata sobre problemas de teoría de grafos y camino problema. Consulte el curso para encontrar el modelo correcto.
15 horas (durante 5 clases) 2 alumnos por equipo Tómese su tiempo tanto en la calidad como en el contenido. El profesor asociado y los profesores asistentes no responderán preguntas sobre el proyecto. |
Escala: 50 puntos
- 10 puntos
- 10 puntos
- 15 puntos
- 15 puntos
“Solo sígueme y corre como si tu vida dependiera de ello. Porque lo hace ".
Tarea 1: Formar los equipos
El número de Gladers crece día a día. Se desafía su papel de liderazgo y se cuestiona su autoridad. Además, todavía estás encerrado en el Claro.
La única forma de encontrar una salida es liderar sin piedad a los Habitantes. Para ello, debes demostrar que tienes la cualidad de un gran líder. Las glándulas se aterrorizan ante la idea de atravesar el laberinto y esto genera tensión. Se acerca la revuelta.
Debe crear un clima de confianza y seguridad. Tienes que encontrar la manera de formar algunos grupos de compañeros según sus preferencias. Pero no quieres dividir a los Gladers, así que usa una cantidad mínima de grupo.
Demuestra que puedes formar un buen equipo con esta primera muestra de 10 Gladers:
Glader | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
No puedo estar con | 2,5,6 | 1,3,7 | 2,4,8 | 3,5,9 | 1,4,10 | 1,8,9 | 2,9,10 | 3,6,10 | 4,6,7 | 5,7,8 |
- Dibuja el gráfico correspondiente (1 punto)
- Discute sobre el valor de tu método de resolución (1 punto)
- Encuentra una solución (2 puntos)
- Escriba el algoritmo y el diagrama de flujo de un algoritmo codicioso correspondiente a su método (3 puntos)
- Implemente el algoritmo codicioso y muestre la solución para el siguiente gráfico (3 puntos).
Tarea 2: todo se mantiene bien
Ahora que sus equipos están formados, necesita aumentar el sentido de unidad dentro de cada grupo. La unión es fuerza, y como decían los vikingos: de una buena comida surge una amistad milenaria.
Para aumentar la confianza entre cada miembro de un equipo, organiza la comida de la siguiente manera:
- Cada equipo tiene su propia mesa redonda
- No se puede tener el mismo vecino de una comida a otra
Los equipos funcionarán bien una vez que cada miembro se encuentre con los demás.
- Dibuje el gráfico correspondiente, por ejemplo, con un equipo de nueve miembros (1 punto)
- ¿Cuántas comidas puedes hacer con un equipo de nueve miembros?
- Muestra el problema (1 punto)
- Mostrar método (2 puntos)
- Resolver el problema (1 punto)
- Encuentre un algoritmo de búsqueda de fuerza bruta para encontrar la organización de una mesa para las comidas
- Mostrar diagrama de flujo (3 puntos)
- Mostrar complejidad (2 puntos)
Tarea 3: ¿Cómo escapar al laberinto?
Tus grupos se han vuelto más fuertes que nunca. Pero el miedo al laberinto y sus peligros todavía paraliza a los Habitantes del Claro. Sólo la lógica fría y rígida de las matemáticas puede disipar esta niebla.
Sin embargo, no puedes perder tiempo en el laberinto porque abre poco tiempo todos los días. Debes cuidar de tus compañeros y diseñar un método para trazar el mapa del laberinto sin perderte. Una vez que el mapa esté listo, debe encontrar el camino correcto para ir a la salida.
- Utilice un algoritmo codicioso y su diagrama de flujo para encontrar la salida en un laberinto. Adáptelo para mapear un laberinto desconocido / aleatorio (2 puntos)
- Construya una gráfica basada en el siguiente laberinto que muestre las intersecciones como vértices (3 puntos)
- Descubra cómo llegar a la salida perdiendo la menor cantidad de tiempo (3 puntos)
No tienes mucho tiempo para llegar a la salida. Después de invertir las paredes, encuentras algún atajo gracias a la hiedra que crece durante años. Esos atajos (en rojo) tardan tanto en viajar como desde la puerta hasta el primer turno (tres unidades).
- Construya un gráfico basado en el siguiente laberinto (4 puntos)
- Descubra cómo llegar a la salida perdiendo la menor cantidad de tiempo (3 puntos)
Tarea 4: eres MALVADO
Estás sobre el laberinto. Recuerdas todo sobre tu pasado y decides tomar el control del laberinto. Tomas contacto discretamente con WICKED. Una hora más tarde, mientras tus compañeros siguen demoliendo las salas de vigilancia, un humo espeso invade las habitaciones y te hace dormir.
Te despiertas solo. Frente a usted hay una docena de paneles de control. Entiende que las fuerzas armadas de WICKED vinieron y reconstruyeron el puesto de control. Un teclado frente a ti con signos extraños, los botones comienzan a parpadear mientras el laberinto se transforma. Una palabra queda a su derecha: "Sólo los mejores tienen derecho a vivir, hacer su trabajo".
Decides hacerlo laberinto más dinámico y autónomo en el camino del cambio. Para ello es necesario crear programas que se encarguen de renovar el trabajo hora tras hora. MALVADO es BUENO.
- Hacer el algoritmo prim aleatorio
- Mostrar diagrama de flujo (3 puntos)
- Muestra tu programa y comenta cada función (3 puntos)
- Mostrar un resultado y comentarlo (1 puntos)
- Hacer el algoritmo de autómata celular
- Mostrar diagrama de flujo (3 puntos)
- Muestra tu programa y comenta cada función (4 puntos)
- Mostrar un resultado y comentarlo (1 puntos)
Echar un vistazo: https://en.wikipedia.org/wiki/Maze_generation_algorithm
ES 
FR 
EN