leçon 2: polynômes à une indéterminée

Le fichier de ce qui suit est ici. 
Marc m'a déjà corrigé ma copie là :)

# Polynômes à une indéterminée: \( \mathbb{R} [X] \) 

# 1. Représentation des polynômes
# on représente le polynôme \(a_nX^n+...a_1X+a_0\) par la liste de ses
# coefficients jusqu'à un certain degré, étant entendu qu'après ce degré
# les coefficients sont nuls
# on les ordonne par degré croissant:
# \([a_0,a_1,...,a_n]\)
# par exemple, soit p1 le polynôme \(2X^2-3X+1\)

# en python une liste est une suite d'éléments entre crochets,
# séparés par des virgules
p1=[1,-3,0,2]   # le polynôme 2X^3-3X+1
p2=[1,-3,0,2,0] # le même polynôme
p3=[1,3,5]      # le polynôme 5X^2+3X+1

# p1 et p2 représentent le même polynôme, mais pour python ce sont des listes différentes.

# quelques fonctions utiles sur les listes:
# range(n) produit la liste des entiers de 0 à n-1: [0,1,2,...,n-1]
# len(s) donne la longueur d'une liste s
# + concatène deux listes

# on accède à l'élément de rang k de la liste p par la syntaxe p[k]
# le premier rang étant le rang 0
p1[0]
p1[1]
p1[2]

# ca tombe bien pour les polynômes: p[k] donne le coefficient de X^k dans p

# mais on peut désirer connaître le coefficient de p pour un degré donné sans connaître le degré de p, il faut donc écrire une fonction qui calcule cela

def coef(p,k):
  if k<len(p): return p[k]
  else: return 0

# calculons le degré d'un polynôme: c'est le plus grand degré tel que le coefficient correspondant est non nul, et il est borné par la longueur de la liste qui représente p

def deg(p):
  d=0
  # l'instruction suivante est une boucle for:
  # elle exécute les instructions qui la suivent et qui sont décalées
  # par rapport à elle,
  # ceci pour chaque valeur de k dans la liste qui est donnée
  # ici c'est range(len(p))
  for k in range(len(p)):
    if p[k]<>0: d=k # cette instruction est décalée par rapport à
                    # l'instruction for:
                    # elle est exécutée pour chaque valeur de k
  return d # cette instruction n'est pas décalée par rapport à
           # l'instruction for: elle est exécutée quand la boucle for
           # est terminée

deg(p1)
deg(p2)
deg(p3)

# 2. Addition des polynômes

# pour calculer p+q, on additionne les coefficients de même degré
# cela correspond à additionner les termes de même rang des listes représentant
# les polynômes 

def plus_poly(p,q):
  # la variable res va contenir la liste représentant le polynôme somme
  # de p et q, on va lui ajouter des éléments au fur et à mesure que l'on 
  # va calculer les sommes des coefficients de p et q, degré par degré
  # au début elle est vide:
  res=[]
  # parcourons les deux listes p et q, degré par degré
  # du degré 0 au degré maximum, qui est max(deg(p),deg(q))
  # ne pas oublier le range(n) se termine avec n-1 et pas n
  for k in range(max(deg(p),deg(q))+1):
    res=res+[coef(p,k)+coef(q,k)]
  return res

plus_poly(p1,p3)

# plus concis:
# une expression [f(k) for k in A] va calculer la liste des valeurs de f(k)
# pour chaque k de la liste A

def plus_poly(p,q):
  return [coef(p,k)+coef(q,k) for k in range(max(deg(p),deg(q))+1)]

plus_poly(p1,p3)

# 3. Affichage des polynômes

# voir un polynôme sous sa forme en liste n'est pas très parlant, 
# on va programmer qui affiche un polynôme comme on en a l'habitude en maths

# nous aurons besoin de fonctions d'une des bibliothèques python
import sys

# on définit une fonction qui imprime à l'écran une suite de caractères
# (on dit <<chaîne>> en informatique, sans le retour à la ligne que met 
# la fonction standard print

def imprime_chaine(s):
  sys.stdout.write(s)

# et d'une fonction qui fait demême avec un nombre
# pour cela on convertit le nombre en chaîne avec la fonction str

def imprime_nombre(x):
  imprime_chaine(str(x))

# allons-y

def imprime_poly(p):
  deja=False # pour savoir si on déjà imprimé quelque-chose du polynôme
  for k in range(deg(p)+1): 
    c=coef(p,k)
    if c<>0: # toutes les instructions jusqu'à l'instruction deja=True
             # sont décalées: elles sont donc exécutées si c<>0
             # celles d'après ne le sont plus donc sont exécutée 
             # indépendamment de la valeur de c
      if c>0: 
        if deja: imprime_chaine('+')
      else: imprime_chaine('-')
      c=abs(c)
      if c<>1 or k==0: imprime_nombre(c)
      if k>=1: imprime_chaine('X')
      if k>1: 
        imprime_chaine('^') 
        imprime_nombre(k)   
      deja=True
  # fin de la boucle for, car il n'y a plus de décalage 
  # par rapport à l'instruction for 
  if deja==False: imprime_nombre('0')
  imprime_chaine('\n')

imprime_poly(p1)
imprime_poly(p3)
imprime_poly([])
imprime_poly([0,-1])

# 4. Multiplication

# 4.1. Multiplication par une constante a

def mult_constante(a,p):
  return [a*coef(p,k) for k in range(deg(p)+1)]

# 4.2. Multiplication par un monôme X^d

def mult_monome(p,d):
  return ([0 for k in range(d)]+p)

# 4.2. Mutiplication des polynômes

def mult_poly(p,q):
  res=[]
  for k in range(deg(p)+1):
    res=plus_poly(res,
                  mult_constante(coef(p,k),
                                 mult_monome(q,k)))
  return res

p4=[1,1]
imprime_poly(p4)
imprime_poly(mult_poly(p4,p4))

# 4.4. Puissances d'un polynôme

def puis_poly(p,n):
  if n==0: return [1]
  else: return mult_poly(p,puis_poly(p,n-1))

for n in range(13):
  imprime_poly(puis_poly(p4,n))

imprime_poly(puis_poly(p4,500))

leçon 1: départ, nombres entiers et algorithme d'Euclide

Je travaille dans l'environnement cygwin sous Windows, python (version 2) y est par défaut, et j'édite mes fichiers python avec emacs.
Sinon, python (version 2) s'installe sous windows 7: ici. Lancer IDLE (Python GUI). 

Le fichier python contenant ce qui suit est là.



sh-4.1$ python
Python 2.7.3 (default, Dec 18 2012, 13:50:09) 
[GCC 4.5.3] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 

# Tout ce qui est après un dièse est considéré par python
# comme un commentaire, donc ignoré

# L'algorithme d'Euclide

# 1. La division euclidienne

# 1.1. Le quotient

# on définit une fonction quotient qui prend deux arguments a et b (1ere ligne)
# puis on teste la condition logique a<b (ligne 2)
# si la condition est vérifiée, alors on exécute ce qui suit les 2 points,
# qui consiste à donner la valeur dans cas de quotient(a,b) (ligne 3)
# si la condition n'est pas vérifiée, on exécute ce qui suit
# le mot-clé else (ligne 4): le résultat est obtenu en calculant
# la fonction quotient pour les arguments a-b et b.
# Il s'agit d'un calcul récursif, comme lorsque l'on définit une
# suite par récurrence: u_n+1 = f(u_n).

# pour exécuter la définition de la fonction qui suit, la copier
# et la coller sur la ligne de commande de python, puis finir par
# un retour chariot (Entrée)

def quotient(a,b):
  if a<b:  return 0
  else: return 1+quotient(a-b,b)

quotient(7,2)

# les entiers de python ne sont pas bornés

quotient(500000000000000000000000000000,21111111111111111111111111111)

quotient(-7,2)

# problème, on a pas traité les nombre négatifs, redéfinissons la fonction

def quotient(a,b):
  if a<0: return - quotient(-a,b)
  elif b<0: return - quotient(a,-b)
  elif a<b: return 0
  else: return 1+quotient(a-b,b)

quotient(7,2)
quotient(-7,2)
quotient(7,-2)
quotient(-7,-2)

# remarquer les tests successifs: 
# if ...:... elif ...:... elif ...:... else:...

# 1.2. Le reste

def reste(a,b):
  return a-b*quotient(a,b)

reste(7,2)
reste(-7,2)
reste(7,-2)
reste(-7,-2)


# cette définition du reste et du quotient pour les nombres négatifs n'est pas la seule possible...

# 2. L'algorithme d'Euclide

# il consiste à diviser a par b, ce qui donne un reste b1,
# s'il est non nul on divise b par b1, ce qui donne un reste b2,
# puis ainsi de suite jusqu'à arriver à un reste nul.
# Le dernier reste non nul est alors le pgcd de a et b.

def pgcd(a,b):
  if b==0: return a
  else: return pgcd(b,reste(a,b))

pgcd(6,4)
pgcd(24,15)
pgcd(24543543543,155435434)

# on peut, en se servant des quotients dans cet algorithme,
# calculer les coefficients de Bezout u et v tels que
# u a + v b = pgcd(a,b)
# le resultat de cette fonction est une liste à deux éléments uv=[u,v]
# on accède au premier par la syntaxe uv[0] et au second par uv[1]

def bezout(a,b):
  if b==0: return [1,0]
  else:
    uv= bezout(b,reste(a,b))
    return [uv[1],uv[0]-uv[1]*quotient(a,b)]

bezout(3,4)
bezout(8,5)    

# 3. Un exemple avec la suite de Fibonacci

# on définit cette suite par
# f_0 = 0 et f_1 = 1, f_n+2 = f_n+1 + f_n
# posons fib(n) = f_n

def fib(n):
  if n==0: return 0
  elif n==1: return 1
  else: return fib(n-1)+fib(n-2)

fib(10)

# le pgcd de f_a et f_b est f_c où c est le pgcd de a et b

pgcd(fib(18),fib(27))
fib(9)

Exercices:
1. programmer une fonction qui calcule la factorielle d'un entier n
2. programmer une fonction qui calcule la suite de Collatz:
si $u_n$ est pair, $u_{n+1} = \cfrac {u_n} 2$, sinon $u_{n+1} = 3 u_n+1$.