ISC ED U4 EstructurasNoLineales Práctica4

IV
Estructuras no lineales
4 Práctica 04: Árboles y Grafos . . . . . . . . 33

4.1 Ejercicio 1 - Árboles: Obteniendo información de
los árboles
4.2 Ejercicio 2 - Grafos: Camino más corto
4.3 Ejercicio 3 - Puzzle-8: Uso de algoritmos de
búsqueda
4.4 Entregables (Evidencias)
4.5 Forma/Medio y fecha de entrega
4.6 Lista de cotejo para la evaluación de la práctica 4
Árboles
Grafos
4. Práctica 04: Árboles y Grafos
4.1 Ejercicio 1 - Árboles: Obteniendo información de los árboles

4.1.1 Descripción
Escriba un programa que lea un archivo de texto plano, este archivo de texto plano debe contener
información de un árbol binario (el árbol binario almacena números enteros). Una vez cargado y
generado el árbol binario, realizar lo siguiente:
1. Muestre el árbol binario cargado del archivo de texto plano. El formato o estructura para
visualizar el árbol cargado queda a su consideración.
2. Calcule e imprima cuántos nodos tiene el árbol binario
3. Encuentre e imprima el máximo valor guardado en el árbol y el promedio de los mismos.
4. Realice el recorrido preorden, inorden y postorden
5. Calcule el nivel del árbol
4.2 Ejercicio 2 - Grafos: Camino más corto

4.2.1 Descripción
Escriba un programa que lea un archivo de texto plano que contiene los vértices y aristas de un grafo
dirigido ponderado, a partir del contenido del archivo debe de generar el grafo dirigido ponderado
y realizar lo siguiente con un menú de opciones:
1. Mostrar la matriz de distancias o la lista de adyacencia del grafo.
2. Agregar vértice
3. Agregar arista
4. Eliminar vértice
5. Eliminar arista
6. Buscar el camino más corto a partir de un nodo (vértice) origen y un nodo (vértice) destino.
Use el algoritmo de Dijkstra para este punto.
ISC - M.C.C. Manuel Hernández Hernández Estructura de datos 33

34
4.3 Ejercicio 3 - Puzzle-8: Uso de algoritmos de búsqueda
4.3.1 Descripción
Los puzzles constituyen un excelente campo para aplicar y probar los métodos de búsqueda. El
puzzle más frecuentemente utilizado es el puzzle-8; es decir, aquel de dimensión 3x3, donde se
deben de acomodar los números del 1a 8. En la figura 4.1 se presenta un ejemplo de puzzle-8.
Figure 4.1: Ejemplo de puzzle-8
El problema queda definido en función de:

• Un estado inicial y un estado final (ver figura 4.1)
• Un conjunto de movimientos (u operadores) permitidos para cambiar de una configuración
a otra. Es decir, un operador está asociado al concepto de movimiento y es el que permite
transformar un estado a otro (ver figura 4.2).
Figure 4.2: Movimientos válidos
• Un conjunto de movimientos (u operadores) prohibidos (ver figura 4.3).
Figure 4.3: Movimientos prohibidos
Crear una aplicación que permita resolver el juego Puzzle-8 para lo cual debe usar los algoritmos
de búsqueda en anchura y búsqueda en profundidad.

1. Programas
Puede entregar de las siguientes formas los programas:
• Los archivos .java (Si utiliza el IDE Netbeans los archivos .java (código fuente) se encuentran en la carpeta src)
• Si el/los programa(s) utiliza(n) interfaz gráfica de usuario, entregar el proyecto creado con el IDE (sea de netbeans o
eclipse).
Al inicio de cada clase (archivo .java) debe agregar la siguiente información:
/**
* Nombre de la institución: ITSTA
* Carrera: Ingeniería en Sistemas Computacionales
* Asignatura: Estructura de datos
* Unidad No.: 4 - Estructuras no lineales (árboles y grafos)
* Práctica No.: 4
* No. de equipo:
* Nombres de los integrantes:
* Fecha de entrega:
* Objetivo / Descripción del problema:
*
*/
// A partir de aquí va todo el código del programa que resuelve

// el ejercicio de la práctica
2. Reporte - Entregar el reporte con las siguientes características:
Numenclatura para nombre del archivo

• Numenclatura:
ISC_ED_U4_Práctica4_EstructurasNoLineales_Reporte_EQN, donde N es el número
de equipo.
• Por ejemplo:
ISC_ED_U4_Práctica4_EstructurasNoLineales_Reporte_EQ2.pdf
Estructura del reporte
• Portada (Logo y Nombre de la institución, Logo y Nombre de la Carrera, Asignatura, Nombre del docente: M.C.C.
Manuel Hernández Hernández, Número y Nombre de la práctica: Práctica 4 - Aplicación de las estructuras de
datos no lineales (árboles y grafos), Número de equipo, Integrantes del equipo, Grupo y Fecha de entrega)
• Índice de contenido
• Índice de figuras
• Objetivo de la práctica
1. Ejercicio 1. Árboles: Obteniendo información de los árboles
1.1. Descripción del problema/ejercicio
1.2. Explicación del código relevante de solución
1.3. Resultados (Capturas de pantalla de la ejecución del programa. Explicar los resultados)
2. Ejercicio 2. Grafos: Camino más corto
3. Ejercicio 3. Puzzle-8: Uso de algoritmos de búsqueda
4. Conclusiones (De cada integrante del equipo)

36
3. Vídeo
Grabar un vídeo corto (de 10 minuntos máximo) con la ejecución y explicación del/los
programa(s) de la práctica. Recomendación: Agregar al principio del vídeo una portada con
sus datos.
Numenclatura para nombre del archivo de vídeo
• Numenclatura:
ISC_ED_U4_Práctica4_EstructurasNoLineales_Vídeo_EQN.mp4
• Por ejemplo:
ISC_ED_U4_Práctica4_EstructurasNoLineales_Vídeo_EQ2.mp4
4.5 Forma/Medio y fecha de entrega

Medio de entrega
Subir los entregables (evidencias) de la práctica 4 en la plataforma Google ClassRoom
Fecha límite de entrega
Lunes 23 de octubre de 2023 antes de las 11:59pm
4.6 Lista de cotejo para la evaluación de la práctica 4

1. (30%) Funcionamiento. Los programas funcionan de forma correcta generando los resultados esperados con base a lo que se
pide en cada ejercicio. Cada ejercicio está ponderado con el 10%, siendo la suma de los 3 ejercicios el 30%:
2. (10%) Dominio o nivel de conocimiento del programa. El alumno conoce la estructura y código fuente del programa;
además explica adecuadamente el funcionamiento del programa demostrando su conocimiento de cada uno de los programas.
3. (15%) Implementación de las estructuras no lineales. Implementan las estructuras de datos no lineales árboles y grafos de la
forma correcta (usando las buenas prácticas de programación). Además, hace uso de los algoritmos de búsqueda en anchura y
búsqueda en profundidad. Usan de forma adecuada la memoria, es decir, deciden de forma correcta de SI aplicar memoria
dinámica o estádica en la solución de los problemas o ejercicios.
4. (15%) Programas (Código fuente). Entrega el código fuente (archivo .java sin comprimir) de cada programa que resuelve
cada ejercicio (ejercicio 1, 2 y 3). Cada programa (ejercicio) está ponderado con el 5%, siendo la suma de los 3 programas
entregados el 15%.
5. (10%) Reporte de la práctica. Entrega reporte cumpliendo con la estructura establecida. Sin errores ortográficos ni de
acentuación. Entrega el archivo PDF sin comprimir.
6. (15%) Vídeo de la práctica. Entrega el vídeo con la explicación de la estrcutura y código fuente del programa, así mismo el
funcionamiento de cada uno los ejercicios de la práctica. Se encuentra en formato MP4 y con una duración no mayor a 10
minutos. Entrega el archivo de vídeo MP4 sin comprimir. Cada programa explicado en el vídeo está ponderado con el 5%, la
suma de los tres programas explicados dan el 15%.
7. (5%) Entrega de la evidencia (vídeo, reporte y los programas de la práctica) en tiempo y forma. Entrega el estudiante en
plataforma sin retraso.
NOTA: Si no se puede visualizar el archivo (programa .java, reporte de la práctica en PDF y el vídeo explicativo) de forma correcta,
tendrán cero en los criterios que aplique.

ISC ED U4 EstructurasNoLineales Práctica4

Cargado por

Copyright:

Formatos disponibles

ISC ED U4 EstructurasNoLineales Práctica4

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

ISC ED U4 EstructurasNoLineales Práctica4

Cargado por

Copyright:

Formatos disponibles

IV

4 Práctica 04: Árboles y Grafos . . . . . . . . 33

4. Práctica 04: Árboles y Grafos

4.1 Ejercicio 1 - Árboles: Obteniendo información de los árboles

4.2 Ejercicio 2 - Grafos: Camino más corto

ISC - M.C.C. Manuel Hernández Hernández Estructura de datos 33

4.3 Ejercicio 3 - Puzzle-8: Uso de algoritmos de búsqueda

Figure 4.1: Ejemplo de puzzle-8

El problema queda definido en función de:

Figure 4.2: Movimientos válidos

• Un conjunto de movimientos (u operadores) prohibidos (ver figura 4.3).

Figure 4.3: Movimientos prohibidos

ISC - M.C.C. Manuel Hernández Hernández Estructura de datos 34

4.4 Entregables (Evidencias)

Al inicio de cada clase (archivo .java) debe agregar la siguiente información:

// A partir de aquí va todo el código del programa que resuelve

2. Reporte - Entregar el reporte con las siguientes características:

Numenclatura para nombre del archivo

ISC - M.C.C. Manuel Hernández Hernández Estructura de datos 35

4.5 Forma/Medio y fecha de entrega

Subir los entregables (evidencias) de la práctica 4 en la plataforma Google ClassRoom

Fecha límite de entrega

Lunes 23 de octubre de 2023 antes de las 11:59pm

4.6 Lista de cotejo para la evaluación de la práctica 4

ISC - M.C.C. Manuel Hernández Hernández Estructura de datos 36

También podría gustarte