324 – T. P.

Lapso 2010/1

1/7

UNIVERSIDAD NACIONAL ABIERTA VICERRECTORADO ACADÉMICO ÁREA INGENIERÍA

TRABAJO PRÁCTICO: ASIGNATURA: COMPUTACIÓN II CÓDIGO: 324 FECHA DE ENTREGA DE LAS ESPECIFICACIONES AL ESTUDIANTE: A partir de la primera semana de aplicación de pruebas, a través del asesor de la asignatura en su centro local FECHA DE DEVOLUCIÓN DEL INFORME POR EL ESTUDIANTE: Adjunto a la Segunda Prueba Integral NOMBRE DEL ESTUDIANTE: CÉDULA DE IDENTIDAD: CORREO ELECTRÓNICO: CENTRO LOCAL: CARRERA: 236 NÚMERO DE ORIGINALES: FIRMA DEL ESTUDIANTE: LAPSO: 2010/1 UTILICE ESTA MISMA PÁGINA COMO CARÁTULA DE SU TAREA O TRABAJO RESULTADOS DE CORRECCIÓN: OBJ N°

1

2

3

4

5

6

7

8

0:N 1:L L

Ingeniería de Sistemas

9

10

11

12

13

324 – T. P.

Lapso 2010/1

2/7

ESPECIFICACIONES DEL TRABAJO PRÁCTICO A continuación se describen las especificaciones del Trabajo Práctico que usted deberá desarrollar para lograr los objetivos 4, 5 y 6, del lapso actual. 1- OBJETIVO 4 En un laboratorio se tienen 40 sustancias que se deberán almacenar en cierto número de anaqueles. Algunas sustancias no se pueden colocar en el mismo anaquel en donde otras sustancias específicas estén, ya que podrían reaccionar y de esta manera ocasionar daños. El problema consiste en determinar el número mínimo de anaqueles a adquirir ( no se tomará en cuenta la capacidad), respetando las condiciones existentes entre las 40 sustancias.

Por ejemplo: en un conjunto de 25 sustancias se sabe que s1 no es compatible con s5 ni con s25, s4 no es compatible con s5 ni con s16, s2 no es compatible con s10 ni con s16 y s10 no es compatible con s2 ni con s22 Una manera de representar esta situación es a través de un grafo, cuyos nodos o vértices representan las sustancias y los arcos la relación de incompatibilidad entre pares de sustancias. Para el ejemplo dado, el grafo es el siguiente:

1

4

10

2

5

16

25

Figura 1

Ingeniería de Sistemas

22

324 – T. P.

Lapso 2010/1

3/7

Para resolver el problema se sugiere el empleo de un método de coloración de grafos, el cual consiste en la asignación de un color a cada vértice de tal manera que no halla dos vértices adyacentes(unidos por un arco) que tengan el mismo color. Por lo tanto el problema se traduce en hallar una coloración del grafo de sustancias no compatibles que utilice el menor número de colores. Un algoritmo frecuentemente usado para resolver este problema, es intentar colorear con un primer color el mayor número de vértices, como sea posible, luego emplear un segundo color igualmente en los restantes, como sea posible y así sucesivamente hasta cubrir todos los vértices. Sobre la base de esta situación, elabore un programa en PASCAL, que permita resolver lo siguiente: ¾ Dado un conjunto de 40 sustancias, realizar lo siguiente: • Construir el grafo que represente la situación: La matriz de Adyacencia debe crearse automáticamente, por ejemplo utilizando un proceso de generación de números aleatorios(NA) para representar las relaciones entre sus elementos. Para ello puede emplear la función Random, la cual permite generar números aleatorios entre 0 y 1. Se sugiere utilizar esta función e implementarla como se describe a continuación: ⎧0 si 0 ≤ NA ≤ 0,5 f ( NA) = ⎨ ⎩1 si 0,5 < NA ≤ 1

La matriz generada debe ser simétrica, por lo tanto el procedimiento usado para crearla, generará el triángulo superior de dicha matriz, empleando los números aleatorios y la función f(x) y luego igualará los elementos ( aij ) del triángulo inferior de la matriza fin de respetar las relaciones de simetría( aij = aji). No se generarán los elementos de la diagonal, ya que la relación no es reflexiva ( ver la Figura 2) Triángulo Superior Triángulo Inferior

Ingeniería de Sistemas

Figura 2

324 – T. P.

Lapso 2010/1

4/7

• Determinar el número de anaqueles y cuáles sustancias podrán colocarse en cada uno de ellos. Ayuda: Un algoritmo útil para colorear un grafo es el siguiente: Algoritmo Greedy Para Coloración de Grafos: Comienzo Color_nuevo := φ Para cada vértice s no coloreado de G hacer Si (s es no adyacente a ningún vértice de Color_Nuevo ) entonces Comienzo Marcar s como coloreado Agregar s a Color_Nuevo Fin {Si} Fin

G : conjunto de vértices Color_nuevo es un conjunto de vértices de G, a los que se les asignará el mismo color.

2- OBJETIVO 5 Elabore un programa en PASCAL que realice lo siguiente: ¾ Crear un archivo con los siguientes datos: • Código identificador de la sustancia (numérico) • Descripción (alfabético, 30 caracteres) • Anaquel donde se almacena (numérico). Puede haber varias sustancias en un mismo anaquel. • Cantidad en gramos(numérico) ¾

Estructura 1. Ordenar el archivo creado, de acuerdo al código del anaquel en donde se almacena, en orden ascendente. Permitir desplegar por Ingeniería de Sistemas

324 – T. P.

Lapso 2010/1

5/7

pantalla e imprimir el archivo antes y después del ordenamiento. Emplee el método Quicksort.

3- OBJETIVO 6

Elabore un programa en PASCAL para implementar la búsqueda de una sustancia por su código, en un archivo ordenado, con la configuración dada en la Estructura 1. El programa permitirá la introducción de datos, continuamente por teclado. Describa el método utilizado y sus ventajas computacionales. Instrucciones generales sobre el Trabajo Práctico Para considerar el logro de cada uno de los objetivos, el estudiante debe entregar lo siguiente: • Listado documentado del programa. En el encabezado de cada procedimiento, función o sección de programa que lo requiera, debe incluir un breve comentario del proceso que se realiza o del método que aplica. Igualmente es conveniente hacerlo en la definición de las estructuras de datos y variables utilizadas. • Listado de los resultados. • Respuestas a los solicitado en la sección 1 • Disquete o CD que contenga el programa fuente (.PAS) y el programa ejecutable (.EXE), debidamente identificado con el nombre del estudiante. Si utiliza unidades modulares (units) en PASCAL, debe incluirlas. Recomendaciones • Emplee nombres de variables, constantes, procedimientos alusivos a lo que representan.

funciones

y

• Utilice un diseño modular para la resolución del problema. Esta estructura aportará legibilidad y facilidad de comprensión,

Ingeniería de Sistemas

324 – T. P.

Lapso 2010/1

6/7

además evitará redundancias en los procesos. Evite variables globales en las funciones y procedimientos. Emplee parámetros en los mismos, determine cuáles son parámetros valor y cuáles parámetros variables. • Desarrolle algoritmos eficientes. • Elabore procedimientos de validación de la data y de detección de errores para evitar interrupciones inesperadas en la ejecución del trabajo. • El disquete/CD debe estar libre de virus y debe entregarse en un sobre conjuntamente con el listado de programa y resultados. No use cinta engomada para adherir el disquete, ya que podría dañar la lámina protectora del mismo. • El trabajo se entregará completo, adjunto a la segunda prueba integral, con una portada similar a la presentada en las especificaciones de este trabajo. • Recuerde que los trabajos prácticos son estrictamente individuales. No se aceptarán códigos o parte de ellos iguales. El profesor podrá realizar una verificación oral y/o escrita, sobre el trabajo en cuestión si lo creyera conveniente.

Criterio de corrección Se considera logrado el objetivo si al menos se cumple con lo siguiente: 9 Entrega del listado documentado del programa, codificado en PASCAL, en forma modular y estructurada. En el encabezado de cada procedimiento, función o sección de programa que lo requiera y en la declaración de las estructuras de datos se incluye un breve comentario acerca del proceso, método o definición de estructura, según sea el caso. Se elabora un programa para resolver el problema planteado en la parte 1. Las partes 2 y 3 se llevan a cabo en un sólo programa o en programas separados.

Ingeniería de Sistemas

324 – T. P.

Lapso 2010/1

7/7

9 El programa corre sin restricciones. En general cada programa incluye módulos que realizan o contribuyen a alcanzar lo solicitado en las especificaciones. 9 Incluye las respuestas en las secciones solicitadas. 9 Entrega el listado de los resultados. 9 Entrega un disquete o CD que contenga el programa fuente (.PAS) y el programa ejecutable (.EXE), de acuerdo a lo especificado.

FIN DE LAS ESPECIFICACIONES DEL TP

Ingeniería de Sistemas