Polinomios¶

Objetivo del módulo¶

Conocer el TAD polinomio y entender las implicaciones de las decisiones para su implementación.

Preguntas básicas¶

¿Cómo se define un TAD polinomio?
¿Qué decisiones hay que tomar para su implementación?
¿Cómo se combinan polinomios (sumas, multiplicaciones) según la representación escogida?
¿Qué compromisos de uso de memoria y rendimiento de CPU se adquieren?

Introducción¶

Un polinomio viene definido por una sumatoria de términos y exponentes de la siguiente manera:

\[P = \sum_{i=0}^{n-1} c_i x^{e_i}\]

Y el grado del mismo es el mayor $e_i$ tal que $c_i\ne 0$

Por ejemplo, el polinomio:

\[4x^3 + 2x^5 + x^2\]

tiene grado 5 y tiene coeficientes y exponentes:

$C=[4,2,1]$
$E=[3,5,2]$

observa que, a priori, no hacemos ninguna suposición sobre si los exponentes han de estar ordenados o han de ser únicos (sin repetidos).

TAD $Polynom$

$\forall P,Q,R \in Polynom;\;\; c,d \in \mathbb{R};\;\; e,f\in\mathbb{N}$

signatures: $$

(6)¶\[\begin{align} new() &\rightarrow Polynom\\ P.add\_term(c,e) &\rightarrow Polynom\\ P.is\_empty() &\rightarrow Bool\\ P.is\_zero() &\rightarrow Bool\\ P.sum(Q) &\rightarrow Polynom\;\;\text{suma dos polinomios}\\ P.smult(c,e) &\rightarrow Polynom \;\;\text{multiplica un polinomio por un término}\\ P.mult(Q) &\rightarrow Polynom\;\;\text{multiplica dos polinomios}\\ P.coef(f) &\rightarrow \mathbb{R}\;\; \text{suma de coeficientes de términos con exponente }f\\ P.grade() &\rightarrow \mathbb{N}\;\; \text{exponente más alto} \end{align}\]

\[ \begin{align}\begin{aligned} **axioms**:\\- **axiom 1**: $new().is\_empty() ::= True $ - **axiom 2**: $P.is\_empty() ::= |C|=|E|=0$ - **axiom 3**: $P.is\_zero() ::= \forall i | \sum_{j|e_i=e_j} c_j=0$\\ - **axiom 4**: $new().sum(Q) ::= Q$ - **axiom 5**: $P.add\_term(c,e).sum(Q) ::= P.sum(Q).add\_term(c,e)$\\**práctica**:\\usa los axiomas anteriores para sumar los siguientes dos polinomios:\\$$P=3x^5 + 4x^2 \;\;\;\;\;\; Q=2x + 7x^2\end{aligned}\end{align} \]

$3x^5 + 4x^2$ ::= $new().add\_term(4,2).add\_term(3,5)$
usando el axioma de suma varias veces:
- $P.sum(Q) ::=new().add\_term(4,2).add\_term(3,5).sum(Q)$
- $::= new().add\_term(4,2).sum(Q).add\_term(3,5)$
- $::= new().sum(Q).add\_term(4,2).add\_term(3,5)$
- $::= new().add\_term(4,2).sum(Q).add\_term(3,5)$
- $::= sum(Q).add\_term(4,2).add\_term(3,5)$

observación:

Fïjate que el axioma de suma lo podríamos haber definido también de la siguiente forma:

axiom 6: $P.sum(Q) ::= R | C_R = C_P + C_Q;\;E_R = E_P + E_Q\;\;\;$ siendo $+$ la operación de concatenación de listas

esta última definición es más operativa ya que implica dos estructuras de almacenamiento $C$ y $E$ para cada polinomio, y sugiere una implementación concreta. En cambio la definición anterior, en los axiomas 4 y 5, es más abstracta e independiente de implementación.

implementación:

La siguiente clase implementa estas definiciones. Observa el constructor, usamos list para copiar la lista pasada como argumento (si no, sería una referencia y se modificaría el original cuando hagamos operaciones).

from IPython.display import Math
import numpy as np
import numbers

class Pol:
    
    def __init__(self, elements=[]):
        self.elements = list(elements)
        
    def isEmpty(self):
        return len(self.elements==0)
        
    def add_term(self, coef, exp):
        assert (isinstance(coef, numbers.Real) or isinstance(coef,numbers.Integral)) and isinstance(exp, numbers.Integral), \
                "coef/exp must be float/int"
        self.elements.append((coef,exp))
        return self
        
    def sum(self, q):
        r = self.__class__()
        for c,e in self.elements+q.elements:
            r.add_term(c,e)
        return r
    
    def show(self):
        s = "+".join(["%s^{%s}"%(str(c) if e==0 else str(c)+"x" if c!=1 else "x", str(e) if e not in [0,1] else "") for c,e in self.elements if c!=0])
        s = s.replace("+-", "-")
        return Math(s)

p = Pol().add_term(3,5).add_term(4,2).add_term(3,0).add_term(5,10)
print(p.elements)
p.show()

[(3, 5), (4, 2), (3, 0), (5, 10)]

\[\displaystyle 3x^{5}+4x^{2}+3^{}+5x^{10}\]

q = Pol().add_term(2,1).add_term(7,2)
print(q.elements)
q.show()

[(2, 1), (7, 2)]

\[\displaystyle 2x^{}+7x^{2}\]

p.sum(q).show()

\[\displaystyle 3x^{5}+4x^{2}+3^{}+5x^{10}+2x^{}+7x^{2}\]

seguimos definiendo axiomas

axiom 7: $new().smult(d, f) ::= new()$
axiom 8: $P.add\_term(c,e).smult(d,f) ::= P.smult(d,f).add\_term(c*d, e+f)$

práctica:

usa los axiomas anteriores para multiplicar

\[P=3x^5 + 4x^2 \;\;\;\;\;\text{con el término}\;\;9x^3\]

$P.smult(9,3) ::=new().add\_term(4,2).add\_term(3,5).smult(9,3)$
$::=new().add\_term(4,2).smult(9,3).add\_term(27,8)$
$::=new().smult(9,3).add\_term(36,5).add\_term(27,8)$
$::=new().add\_term(36,5).add\_term(27,8)$

o sea $27x^8 + 36x^5$

y pensamos una definición más operativa

axiom 9: $P.smult(d,f)::=R|C_R = [c*d, \;\;\forall c\in C_P], E_R = [e+f, \;\;\forall e\in E_P]$

y ampliamos nuestra definición de polinomio (observa que usamos herencia de clases). Fíjate que la sintaxis de Python está diseñada para que se parezca lo más posible a la notación matemática anterior. Observa el uso de clone para evitar modificar el propio objeto.

import numbers
class Pol2(Pol):
    
    def clone(self):
        return Pol2(list(self.elements))
    
    def smult(self, d,f):
        assert (isinstance(d, numbers.Real) or isinstance(d,numbers.Integral)) and isinstance(f, numbers.Integral), "coef/exp must be float/int"
        r = self.__class__()
        r.elements = [(c*d, e+f) for c,e in self.elements]
        return r

p = Pol2().add_term(3,5).add_term(4,2)
p.clone().show()

\[\displaystyle 3x^{5}+4x^{2}\]

p.smult(9,3).show()

\[\displaystyle 27x^{8}+36x^{5}\]

más axiomas

axiom 10: $new().mult(Q) ::= new()$
axiom 11: $P.add\_term(c,e).mult(Q) ::= P.mult(Q).sum(Q.smult(c,e))$

práctica:

multipliquemos:

\[P=3x^5 + 4x^2 \;\;\;\;\;\; Q=2x + 7x^2\]

$P.mult(Q) ::=new().add\_term(4,2).add\_term(3,5).mult(Q)$
$::=new().add\_term(4,2).mult(Q).sum(Q.smult(3,5))$
$::=new().mult(Q).sum(Q.smult(4,2)).sum(Q.smult(3,5))$
$::=new().sum(Q.smult(4,2)).sum(Q.smult(3,5))$

implementemos:

class Pol3(Pol2):
    
    def mult(self, q):
        terms = [q.smult(c,e) for c,e in self.elements]
        r = terms[0]
        for t in terms[1:]:
            r = r.sum(t)
        
        return r

p = Pol3().add_term(3,5).add_term(4,2)
q = Pol3().add_term(2,1).add_term(7,2)

p.show()

\[\displaystyle 3x^{5}+4x^{2}\]

q.show()

\[\displaystyle 2x^{}+7x^{2}\]

p.mult(q).show()

\[\displaystyle 6x^{6}+21x^{7}+8x^{3}+28x^{4}\]

más axiomas:

axiom 12: $new().grade() ::= error$
axiom 13: $new().add\_term(c,e).grade() ::= e$
axiom 14: $P.add\_term(c,e).add\_term(d,f).grade() ::= P.add\_term(c,e).grade()$ if $e>f$ else $P.add\_term(d,f).grade()$
axiom 15: $new().coef(f) ::= 0$
axiom 16: $P.add\_term(c,e).coef(f) ::= c+P.coef(f)$ if $e=f$ else $P.coef(f)$

y su implementación.

class Pol4(Pol3):
    
    def grade(self):
        return np.max([e for c,e in self.elements])
    
    def coef(self,f):
        return np.sum([c for c,e in self.elements if e==f])

p = Pol4().add_term(3,5).add_term(4,8).add_term(7,5)
p.show()

\[\displaystyle 3x^{5}+4x^{8}+7x^{5}\]

p.grade()

p.coef(5)

p.coef(8)

p.coef(2)

0.0

¿Cómo sería la definición axiomática más operativa de esta implementación?

axiom 17: $P.grade() ::== max(E)$
axiom 18: $P.coef(f) ::= \sum_{j|e_j=f} c_j$

finalmente añadimos un método para simplificar un polinomio

class Pol5(Pol4):
    
    def simplify(self):
        exps  = np.sort(np.unique([e for c,e in self.elements]))
        coefs = [self.coef(f) for f in exps]
        return Pol5 ([(c,e) for c,e in zip(coefs, exps)])

p = Pol5().add_term(3,5).add_term(4,8).add_term(7,5).add_term(-2,8).add_term(2.87, 3)
p.show()

\[\displaystyle 3x^{5}+4x^{8}+7x^{5}-2x^{8}+2.87x^{3}\]

p.simplify().show()

\[\displaystyle 2.87x^{3}+10x^{5}+2x^{8}\]

y verficamos propiedades

p = Pol5().add_term(3,5).add_term(4,8).add_term(7,5).add_term(-2,8).add_term(2.87, 3)
q = Pol5().add_term(2,1).add_term(7,2)

p.show()

\[\displaystyle 3x^{5}+4x^{8}+7x^{5}-2x^{8}+2.87x^{3}\]

q.show()

\[\displaystyle 2x^{}+7x^{2}\]

p.mult(q).show()

\[\displaystyle 6x^{6}+21x^{7}+8x^{9}+28x^{10}+14x^{6}+49x^{7}-4x^{9}-14x^{10}+5.74x^{4}+20.09x^{5}\]

p.mult(q).simplify().show()

\[\displaystyle 5.74x^{4}+20.09x^{5}+20x^{6}+70x^{7}+4x^{9}+14x^{10}\]

p.simplify().mult(q).show()

\[\displaystyle 5.74x^{4}+20.09x^{5}+20x^{6}+70x^{7}+4x^{9}+14x^{10}\]

Ejercicios propuestos¶

Modifica add_term para ignorar términos con coeficiente 0. Esto repararía el comportamiento del método grade

Polinomios con restricciones

Define axiomas para un polinomio con restricciones en el que sólo hay un término por exponente y los términos deben de estar ordenados de manera descendente por exponente.

P.ej. si tenemos el polinomio $4x^8 + 5x^6 – 4x^3 + 2x$ la forma como se representa según nuestra definición de polinomio con restricciones es:

$new().add\_term(2,1).add\_term(-4,3).add\_term(5,6).add\_term(4,8)$

el término con menor exponente será el más interno y el término con mayor exponente será el más externo, es decir, el término con mayor exponente es el correspondiente a $c$ y $e$ de acuerdo a la forma general definida.

Con base en esta decisión, las definiciones de los axiomas correspondientes a las funciones grado y suma se facilitan respecto al polinomio sin restricciones.

axiom: $new.grade() ::= error$
axiom: $new().add\_term(c,e).grade() ::= e$

axioms:

new().sum(Q) ::= Q

P.sum(new()) ::= P

P.add_term(c,e).sum(Q.add_term(d,f)) ::=

  P.sum(Q.add_term(d,f)).add_term(c,e) if e>f else:

  P.add_term(c,e).sum(Q).add_term(d,f) if e<f else:
  
  P.sum(Q) if (c+d)==0 else P.sum(Q).add_term(c+d,e)

Después de realizar el laboratorio

implementa la multiplicación para la implementación v1
implementa la resta y la división para ambas implementaciones
mide y compara los rendimientos de add_term de la implementación v1 y v2
mide y compara los rendimientos de sum de la implementación v1 y v2
¿qué equilibrio hay entre rendimiendo de CPU y de memoria?

Introducción a Algoritmos y Estructuras de Datos

Polinomios

Contents

Polinomios¶

Objetivo del módulo¶

Preguntas básicas¶

Introducción¶

Ejercicios propuestos¶