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

  1. 10 puntos
  2. 10 puntos
  3. 15 puntos
  4. 15 puntos
Teoría de grafos del proyecto: la teoría de grafos del proyecto de Mazerunner

“Solo sígueme y corre como si tu vida dependiera de ello. Porque lo hace ".

Tarea 1: Formar los equipos

Teoría de grafos del proyecto: la teoría de grafos del proyecto de Mazerunner

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

 

  1. Dibuja el gráfico correspondiente (1 punto)
  2. Discute sobre el valor de tu método de resolución (1 punto)
  3. Encuentra una solución (2 puntos)
  4. Escriba el algoritmo y el diagrama de flujo de un algoritmo codicioso correspondiente a su método (3 puntos)
  5. Implemente el algoritmo codicioso y muestre la solución para el siguiente gráfico (3 puntos).

búsqueda de caminos de la teoría de grafos del proyecto

Tarea 2: todo se mantiene bien

Teoría de grafos del proyecto: la teoría de grafos del proyecto de Mazerunner

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.

  1. Dibuje el gráfico correspondiente, por ejemplo, con un equipo de nueve miembros (1 punto)
  2. ¿Cuántas comidas puedes hacer con un equipo de nueve miembros?
    1. Muestra el problema (1 punto)
    2. Mostrar método (2 puntos)
    3. Resolver el problema (1 punto)
  3. Encuentre un algoritmo de búsqueda de fuerza bruta para encontrar la organización de una mesa para las comidas
    1. Mostrar diagrama de flujo (3 puntos)
    2. Mostrar complejidad (2 puntos)

Tarea 3: ¿Cómo escapar al laberinto?

Teoría de grafos del proyecto: la teoría de grafos del proyecto de Mazerunner

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.

  1. 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)
  2. Construya una gráfica basada en el siguiente laberinto que muestre las intersecciones como vértices (3 puntos)
  3. Descubra cómo llegar a la salida perdiendo la menor cantidad de tiempo (3 puntos)

búsqueda de caminos de la teoría de grafos del proyecto

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).

  1. Construya un gráfico basado en el siguiente laberinto (4 puntos)
  2. Descubra cómo llegar a la salida perdiendo la menor cantidad de tiempo (3 puntos)

búsqueda de caminos de la teoría de grafos del proyecto

Tarea 4: eres MALVADO

Teoría de grafos del proyecto: la teoría de grafos del proyecto de Mazerunner

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.

  1. Hacer el algoritmo prim aleatorio
    1. Mostrar diagrama de flujo (3 puntos)
    2. Muestra tu programa y comenta cada función (3 puntos)
    3. Mostrar un resultado y comentarlo (1 puntos)
  2. Hacer el algoritmo de autómata celular
    1. Mostrar diagrama de flujo (3 puntos)
    2. Muestra tu programa y comenta cada función (4 puntos)
    3. Mostrar un resultado y comentarlo (1 puntos)

Echar un vistazo: https://en.wikipedia.org/wiki/Maze_generation_algorithm

Compartir, repartir
es_ESES