Inform\'atica. Segundo Trabajo (11-5-1998). POLINOMIOS EN DOS VARIABLES Estos ejercicios pueden resolverse individualmente o en un grupo de no m\'as de 3 alumnos. Aquellos trabajos entre los que se detecte copia ser\'an penalizados. Cada grupo debe enviar por correo electr\'onico dos mensajes: (-) Uno en el que S\'OLO se debe incluir el fichero con el programa que se pide, con ``Subject'' trabajo2.scm y enviado s\'olo por uno de los componentes del grupo. Para la correcci\'on, se considerar\'a que el programa enviado es todo el mensaje, por lo que cualquier texto que no forme parte del programa deber\'a ser comentado (con puntos y comas). Antes de incluir el fichero en el mensaje comprueba que el fichero carga perfectamente en el Scheme de Merlin evaluando (load "NOMBRE-DE-FICHERO") donde NOMBRE-DE-FICHERO es el nombre del fichero en el que has escrito el trabajo y que vas a enviar por correo. Cualquier trabajo enviado que no cargue no se corregir\'a. (-) Otro mensaje, enviado por el MISMO componente del grupo que envi\'o el anterior, con ``Subject'' Grupo trabajo 2, en el que se especifican claramente los componentes del grupo, así como cualquier otra observaci\'on que se quiera incluir. NOTA IMPORTANTE: Los mensajes deben tener el ``Subject'' indicado EXACTAMENTE. Las direcciones de correo son: Si tu profesor es F\'elix Lara: felix@merlin.fie.us.es Si tu profesor es Álvaro Romero: aroji@merlin.fie.us.es Si tu profesor es Miguel Ángel Guti\'errez: naranjo@merlin.fie.us.es El trabajo ser\'a corregido usando Scheme en Merlín, pero por supuesto puedes realizar el trabajo en casa. Se valorar\'an no s\'olo la correcci\'on de los programas sino tambi\'en la claridad en la presentaci\'on, por lo que cada programa deber\'a estar adecuadamente comentado adem\'as de llevar a cabo, de manera correcta y eficiente, la tarea que se le pide. Los programas deber\'an ser enviados no m\'as tarde del 12 DE JUNIO DE 1998. NOTA: NO INCLUIR el texto de la pr\'actica en el fichero en el que se haga el trabajo. INTRODUCCI\'ON El objetivo de este trabajo es el desarrollo de un peque\~no conjunto de procedimientos orientados a la manipulaci\'on simb\'olica de polinomios en dos variables. Se tratar\'a de implementar algunas operaciones algebraicas b\'asicas entre ellos, como la suma, el producto. Para ello, deberemos elegir alguna forma de representar los polinomios que nos permita operar con ellos con cierta naturalidad. En consecuencia, definiremos un tipo abstracto de dato cuyos constructores y selectores reflejen los valores b\'asicos que determinan un polinomio (los coeficientes de sus t\'erminos, el grado, etc.) y que intervienen de manera esencial en las operaciones en consideraci\'on. LA REPRESENTACI\'ON Un polinomio en 2 variables (X e Y), est\'a determinado por una sucesi\'on de monomios. Por ejemplo, el polinomio P(X,Y)=3X^2Y-7XY+5X^4-3Y+2X^5Y^2-19 est\'a determinado por los monomios: 3X^2Y, -7XY, 5X^4, -3Y, 2X^5Y^2, -19 Por tanto, para representar al polinomio p(x,y) nos bastar\'a representar de alg\'un modo, cada uno de los monomios que lo constituyen. Esto \'ultimo puede conseguirse identificando cada uno de estos monomios con una lista de tres elementos: el coeficiente, el exponente de la x y el exponente de la y (en ese orden). Por ejemplo, el monomio -7XY se representa por la lista (-7 1 1), y el monomio -19 por la lista (-19 0 0). En consecuencia, para representar un polinomio p(X,Y), podemos usar la lista de los monomios que lo constituyen, representados cada uno de ellos por una lista de tres elementos, seg\'un acabamos de comentar. Teniendo en cuenta esto, un polinomio se representar\'a entonces por una lista de listas de 3 elementos. Cada una de esas listas de tres elementos, contiene tres n\'umeros que corresponden (en ese orden) al coeficiente, el exponente de la X y el exponente de la Y, de cada uno de los monomios del polinomio p(X,Y). Por ejemplo, el polinomio p(X,Y) escrito anteriormente, estaría representado por la lista: ((3 2 1) (-7 1 1) (5 4 0) (-3 0 1) (2 5 2) (-19 0 0)) Debemos, sin embargo, imponer algunas restricciones m\'as a nuestra representaci\'on. Una lista formada por listas de 3 n\'umeros representar\'a un polinomio s\'olo cuando: (-) El 0 nunca sea el primer elemento de una de las listas (es decir, si el coeficiente de un monomio es 0, el monomio no aparece en la representaci\'on). En consecuencia, el polinomio nulo estar\'a representado por la lista vacía. (-) No contenga dos listas correspondientes a monomios con los mismos exponentes para la X y la Y. Por ejemplo, la lista ((3 1 2) (-4 2 1) (0 2 3) (12 0 1) (45 1 2)) \noindent no representa al polinomio $Q(X,Y)=3XY^2-4X^2Y+0X^2Y^3+12Y+45XY^2$ ya que las listas (0 2 3) y (45 1 2) incumplen las restricciones impuestas. Para representar adecuadamente el polinomio $q(X,Y)$ debemos SIMPLIFICARLO primero. Para ello basta observar que, en realidad, $Q(X,Y)=48XY^2+4X^2Y+12Y$ y así, la lista ((48 1 2) (-4 2 1) (12 0 1)) nos da una representaci\'on correcta del polinomio. El orden en que aparecen las listas en la representaci\'on del polinomio NO es importante y, en consecuencia, otra representaci\'on igualmente correcta sería, por ejemplo, ((12 0 1) (-4 2 1) (48 1 2)) EJERCICIO 1.- Definir un procedimiento es-polinomio?, de un argumento, que devuelva como valor #t si ha recibido como entrada un polinomio y #f en otro caso. Por ejemplo, (es-polinomio? ()) ==> #t (es-polinomio? '((1 3 5))) ==> #t (es-polinomio? '(2 3 4)) ==> #f (es-polinomio? '((12 0 1) (-4 2 0) (48 1 2))) ==> #t (es-polinomio? '((12 0 1) (-4 2 0) (0 1 2))) ==> #f (es-polinomio? '((12 0 1) (-4 2 0) (23.5 0 1) (9 1 2))) ==> #f (es-polinomio? 'xy) ==> #f EL TIPO ABSTRACTO DE DATO Para manejar de manera c\'omoda y flexible la representaci\'on introducida en el apartado anterior, describimos a continuaci\'on 4 procedimientos b\'asicos, que se utilizar\'an como los selectores y constructores de un tipo abstracto de dato, a la hora de definir el resto de los procedimientos pedidos. Dado un polinomio p(X,Y) necesitamos procedimientos que nos den los siguientes valores asociados a p(X,Y): (-) El grado del polinomio, esto es, el par (n,m) definido por las siguientes condiciones: (-) En p(X,Y) existe un monomio con n como exponente de la X y m como exponente de la Y (y naturalmente con coeficiente distinto de 0). (-) n+m es el m\'aximo de las sumas de los exponentes de los monomios que forman el polinomio p(X,Y). (-) De entre todos los pares (j,k) de exponentes de monomios de p(X,Y), cuya suma j+k es la mayor posible, (n,m) es el que tiene su primera componente mayor. Por ejemplo, el grado del polinomio P(X,Y)=3X^2Y-7XY+5X^4-3Y+2X^5Y^2-19 es (5,2) ya que para cualquier otro monomio de p(X,Y) la suma de los exponentes de X e Y es menor que 7. Para el polinomio Q(X,Y)=48XY^2+4X^2Y+12Y el grado ser\'a (2,1) ya que aunque la suma de los exponentes es 3 para el monomio 48XY^2 y para el monomio 4X^2Y, en este \'ultimo caso el exponente de la X es mayor. (-) El coeficiente asociado a cada uno de los monomios del polinomio. (-) El resto del polinomio, es decir, el polinomio resultante al eliminar del polinomio p(X,Y), el monomio cuyo grado coincide con el grado de p(X,Y). Como complemento a estos valores resulta importante tener un polinomio b\'asico a partir del cual poder construir otros. Elegiremos como polinomio b\'asico el polinomio nulo que, como sabemos est\'a representado por la lista vacía, (). Para ello definiremos globalmente la variable el-polinomio-nulo: (define el-polinomio-nulo '()) Deben definirse 3 selectores, tal y como se pide a continuaci\'on: EJERCICIO 2.- Definir un procedimiento grado de un argumento que, al recibir como entrada un polinomio (representado como hemos descrito) nos devuelva el grado del polinomio (en forma de par punteado). Por ejemplo: (grado el-polinomio-nulo) ==> (0 . 0) (grado '((12 3 5) (1 0 2) (1 0 9) (34 1 1))) ==> (0 . 9) (grado '((234 1 5) (7 2 0) (12 0 6) (34 1 1) (33 0 0))) ==> (1 . 5) EJERCICIO 3.- Definir un procedimiento coeficiente, de tres argumentos que, al recibir como entrada dos n\'umeros enteros no negativos, i y j, y un polinomio p (siempre en la representaci\'on descrita) devuelva el coeficiente con que aparece el t\'ermino X^iY^j en el polinomio p. Por ejemplo: (coeficiente 1 2 el-polinomio-nulo) ==> 0 (coeficiente 0 0 el-polinomio-nulo) ==> 0 (coeficiente 0 2 '((12 3 5) (1 0 2) (1 0 9) (34 1 1))) ==> 1 (coeficiente 0 0 '((234 1 5) (7 2 0) (12 0 6) (34 1 1) (33 0 0))) ==> 33 (coeficiente 3 6 '((234 1 5) (7 2 0) (12 0 6) (34 1 1) (33 0 0))) ==> 0 EJERCICIO 4.- Definir un procedimiento resto con un argumento, que al recibir como entrada un polinomio p, devuelva como valor el polinomio obtenido al eliminar de p su t\'ermino lider, es decir, el monomio de p cuyo grado coincide con el grado de p. Por ejemplo: (resto el-polinomio-nulo) ==> () (resto '((12 3 5) (1 0 2) (1 0 9) (34 1 1))) ==> ((12 3 5) (1 0 2) (34 1 1)) (resto '((234 1 5) (7 2 0) (12 0 6) (34 1 1) (33 0 0))) ==> ((7 2 0) (12 0 6) (34 1 1) (33 0 0)) Por \'ultimo, necesitamos un constructor b\'asico por medio del cual construir nuevos polinomio en la representaci\'on escogida, a partir de otros ya dados. EJERCICIO 5.- Definir un procedimiento haz-polinomio que reciba como entrada, un n\'umero c, un par punteado (formado por dos n\'umeros enteros no negativos, i y j) y un polinomio, p y devuelva como valor el polinomio obtenido al a\~nadir a p el monomio cX^iY^j. Por ejemplo: (haz-polinomio 7 '(3 . 1) el-polinomio-nulo) ==> ((7 3 1)) (haz-polinomio 35 '(0 . 0) el-polinomio-nulo) ==> ((35 0 0)) (haz-polinomio 6 '(1 . 1) '((12 3 5) (1 0 2) (1 0 9) (34 1 1))) ==> ((12 3 5) (1 0 2) (1 0 9) (40 1 1)) (haz-polinomio 56 '(3 . 2) '((234 1 5) (7 2 0) (12 0 6) (34 1 1) (33 0 0)) ) ==> ((234 1 5) (7 2 0) (12 0 6) (34 1 1) (33 0 0) (56 3 2)) LAS OPERACIONES Usando los selectores y el constructor definidos (junto con la constante el-polinomio-nulo), deben definirse los siguientes procedimientos : EJERCICIO 6.- Un predicado es-cero? que devuelve como valor #t al recibir como entrada el polinomio nulo y devuelve #f en caso contrario. Por ejemplo: (es-cero? el-polinomio-cero) ==> #t (es-cero? '((2 3 4))) ==> #f (es-cero? '((12 3 5) (1 0 2) (1 0 9) (34 1 1))) ==> #f EJERCICIO 7.- Un procedimiento termino-lider de un argumento que, al recibir como entrada un polinomio p, devuelva como valor el monomio de p que tiene el mismo grado que p. Por ejemplo: (termino-lider el-polinomio-nulo) ==> () (termino-lider '((35 0 0))) ==> ((35 0 0)) (termino-lider '((12 3 5) (1 0 2) (1 0 9) (34 1 1))) ==> ((1 0 9)) (termino-lider '((234 1 5) (7 2 0) (12 0 6) (34 1 1) (33 0 0))) ==> ((234 1 5)) EJERCICIO 8.- Un procedimiento constante, de un argumento que, al recibir como entrada un n\'umero k nos devuelva el polinomio de grado (0,0), con coeficiente k (es decir, el polinomio constante igual a k). Por ejemplo, (constante 6) ==> ((6 0 0)) (constante -7.3) ==> ((-7.3 0 0)) (constante 0) ==> () EJERCICIO 9.- Un procedimiento suma, de dos argumentos, que reciba como entrada dos polinomios y nos devuelva el polinomio obtenido al sumarlos. Por ejemplo: (suma '((2 3 4) (2.3 1 2) (-12 0 2)) '((6 2 2) (7.1 3 4) (-56 1 0))) ==> ((-12 0 2) (-56 1 0) (2.3 1 2) (6 2 2) (9.1 3 4)) (suma '((1 2 0)) '((12 3 5) (1 0 2) (1 0 9) (34 1 1))) ==> ==> ((1 0 2) (1 0 9) (34 1 1) (1 2 0) (12 3 5)) (suma '((2 3 4) (2.3 1 2) (-12 0 2)) el-polinomio-nulo) ==> ==> ((2 3 4) (2.3 1 2) (-12 0 2)) (suma '((45 6 7)) '((-45 6 7))) ==> () EJERCICIO 10.- Un procedimiento multiplica-por-monomio de dos argumentos, que reciba como entrada un monomio, por ejemplo ((c i j)), y un polinomio, p(X,Y), y nos devuelve el polinomio obtenido al multiplicar el monomio cX^iY^j por p(X,Y). Por ejemplo: (multiplica-por-monomio '((2 1 3)) el-polinomio-nulo) ==> () (multiplica-por-monomio '((2 1 3)) '((2 3 4) (2.3 1 2) (-12 0 2))) ==> ==> ((-24 1 5) (4.6 2 5) (4 4 7)) EJERCICIO 11.- Un procedimiento producto, de dos argumentos, que reciba como entrada dos polinomios y nos devuelva el polinomio obtenido al multiplicarlos. Por ejemplo: (producto '((2 1 3)) '((2 3 4) (2.3 1 2) (-12 0 2))) ==> ==> ((-24 1 5) (4.6 2 5) (4 4 7)) (producto '((2 3 4) (2.3 1 2) (-12 0 2)) '((6 2 2) (7.1 3 4))) ==> ==> ((-72 2 4) (13.8 3 4) (-85.2 3 6) (16.33 4 6) (12 5 6) (14.2 6 8)) (producto '((2 3 4) (2.3 1 2) (-12 0 2)) '((6 2 2) (7.1 0 0))) ==> ==> ((-85.2 0 2) (16.33 1 2) (-72 2 4) (28.0 3 4) (12 5 6)) (producto el-polinomio-cero '((2 3 4) (2.3 1 2) (-12 0 2))) ==> () EJERCICIO 12.- Un procedimiento ITERATIVO, potencia, de dos argumentos, que reciba como entrada un polinomio p y un n\'umero entero n <= 0 y devuelva el polinomio obtenido multiplicando p por si mismo n veces. Si n=0 devolver\'a el polinomio constante 1. (potencia '((2 1 3)) 0) ==> ((1 0 0)) (potencia '((2 1 3)) 1) ==> ((2 1 3)) (potencia '((2 1 3)) 3) ==> ((8 3 9)) (potencia '((2 3 4) (2.3 1 2) (-12 0 2)) 2) ==> ==> ((144 0 4) (-55.2 1 4) (5.29 2 4) (-48 3 6) (9.2 4 6) (4 6 8)) EJERCICIO 13.- Un procedimiento parametrizado, evalua, con un argumento, que, al recibir como entrada un polinomio p(X,Y) d\'e como valor un procedimiento ITERATIVO de dos argumentos, que al recibir como entrada dos n\'umeros a y b devuelva como valor el n\'umero p(a,b). ((evalua '((2 3 4) (2.3 1 2) (-12 0 2))) 1 0) ==> 0.0 ((evalua '((2 3 4) (2.3 1 2) (-12 0 2))) 0 1) ==> -12.0 ((evalua '((2 3 4) (2.3 1 2) (-12 0 2))) 1 1) ==> -7.7 ((evalua el-polinomio-nulo) 2 3) ==> 0 EJERCICIO 14.- Un procedimiento generador, de dos argumentos, que reciba como entrada un procedimiento, f, tambi\'en de dos argumentos, y un par punteado (formado por dos n\'umeros enteros no negativos n y m) y devuelva el polinomio, p(X,Y) cuyo grado es (n,m) y para cada i y j el correspondiente monomio de p(X,Y), tiene como coeficiente el n\'umero f(i,j) (es decir, el valor de (f i j)). (generador (lambda (i j) 0) '(2 . 4)) ==> () (generador (lambda (i j) 2) '(1 . 1)) ==> ==> ((2 0 0) (2 0 1) (2 0 2) (2 1 0) (2 1 1)) (generador + '(2 . 1)) ==> ==> ((1 0 1) (2 0 2) (3 0 3) (1 1 0) (2 1 1) (3 1 2) (2 2 0) (3 2 1)) NOTA: Este \'ultimo procedimiento puede utilizarse para definir la operaciones anteriores (siempre y cuando \'el haya sido definido a partir del constructor y los selectores elegidos).