quelques algorithmes qui pourraient bien être au programme des CPGE l'an prochain

Programmation en python d'algorithmes simples et utiles.
(le fichier est ici: algos_au_programme.py)

1. recherche dans une liste

def recherche_dans_liste(x,l):
    for k in range(len(l)):
        if x == l[k]: return(True)
    return(False)

        (aparté pour les informaticiens:

        # pour tester agréablement les fonctions lorsqu'on

        # exécute le fichier dans python(x,y) par exemple 

        # test(f,a1,...,an) affiche le résultat de f(a1_,...,an)

        # précédé du nom de f et de ses arguments 

        import re

        def test(f,*args):

            s = str(f)

            nomf = re.split(' ',s)[1]

            print(nomf, args)

            print('donne: '+ str(f(*args)))

        fin de l'aparté)

# testons la fonction recherche_dans_liste
test(recherche_dans_liste,'charlie',[4,2,'charlie',6])
# on note au passage que les listes de python ne sont pas homogènes
test(recherche_dans_liste,0,[2,1,2,3])

2. recherche du maximum dans une liste de nombres

def maximum_liste(l):
    m = None # j'avais mis -sys.maxint, Marc a mieux
    for x in l: m = max(m,x)
    return(m)
    
test(maximum_liste,[3,5,0,4])
test(maximum_liste,[])

3. calcul de la moyenne et de la variance.

def moyenne_liste(l):
    return(sum(l)/len(l))
    
Si $l=[x_1,\ldots,x_n]$, la variance de $l$ est $\sigma^2=\cfrac 1 n \sum_{i=1}^n (x_i - x)^2$, avec $x=\cfrac 1 n \sum_{i=1}^n x_i$ la moyenne de $l$ (révisons pour l'année prochaine...:)).

def variance_liste(l):
    m = moyenne_liste(l)
    return(sum([(x-m)**2 for x in l])/len(l))
    
test(moyenne_liste,[1,2,3,4,5])
test(variance_liste,[1,2,3,4,5])

3. recherche par dichotomie dans un tableau trié.
On va dire que tableau = liste
Rend i tel que t[i] = x

def recherche_dans_tableau_trie(x,t):
    if len(t) == 0: return(None)
    a = 0
    b = len(t)-1
    while a <= b: 
        c = int((a+b)/2)
        if x == t[c]: return(c)
        elif x < t[c]: b = c - 1
        else: a = c + 1
    return None
    
test(recherche_dans_tableau_trie,2,[0,1,2,3,4])
test(recherche_dans_tableau_trie,2,[0,1,3,4])
test(recherche_dans_tableau_trie,2,[])

4. recherche par dichotomie du zéro d’une fonction continue et monotone.
f est la fonction, [a,b] est l'intervalle de recherche
et p est la précision: on s'arrête quand b-a < 10^(-p)

def recherche_zero_dichotomie(f,a,b,p):
    precision = 10**(-p)
    if f(a)*f(b) > 0: return(None)
    while b-a > precision: 
        c = (a+b)/2.
        if f(a)*f(c) > 0: a = c 
        else: b = c
    return(a) 

# en python, la fonction x |---> 1-x s'écrit lambda(x): 1-x
test(recherche_zero_dichotomie,lambda(x): 1-x,0,2,5)
test(recherche_zero_dichotomie,lambda(x): log(x)-1,1,3,10)

5. méthodes des rectangles et des trapèzes pour le calcul approché d’une intégrale sur un segment.
La précision est la largeur maximale des rectangles: 10^(-p)

def integrale_approchee_rectangle(f,a,b,p):
    dx = 10.**(-p)
    n = int((b-a)/dx)
    aire = 0.
    k = 0
    while k < n: # on aurait pu utiliser un for mais le range aurait pu
                 # être trop gros et faire planter le système ...
        aire = aire + f(a+k*dx)*dx
        k = k+1
    return(aire)
    
test(integrale_approchee_rectangle,lambda x: x,0,1,5) 
# calcul de Pi
test(integrale_approchee_rectangle,lambda x: 4/(1+x**2),0,1,6) 

def integrale_approchee_trapeze(f,a,b,p):
    dx = 10.**(-p)
    n = int((b-a)/dx)
    aire = 0.
    k = 0
    while k < n: 
        ak = a+k*dx
        aire = aire + (f(ak)+f(ak+dx))/2*dx
        k = k+1
    return(aire)
    
test(integrale_approchee_trapeze,lambda x: x,0,1,5) 
# calcul de Pi, bien meilleur qu'avec les rectangles
test(integrale_approchee_trapeze,lambda x: 4/(1+x**2),0,1,6) 

6. recherche d’un mot dans une chaîne de caractères.
Rend le rang dans la chaîne où commence le mot m s'il existe, sinon rend None

def recherche_mot(m,s):
    p = len(m)
    n = len(s)
    for k in range(n-p+1):
        i = 0
        while i < p:
            if m[i] != s[k+i]: i = p
            elif i == p-1: return(k)
            else: i = i+1
    return(None)

test(recherche_mot,'ab',' ab')
test(recherche_mot,'charlie','ou est charlie dans cette phrase?')

test(recherche_mot,'charline','ou est charlie dans cette phrase?')

polynômes de Hermite: calcul avec sympy et tracé avec matplotlib

Avec
$$\phi(x)=e^{-\cfrac {x^2} 2}$$
 on pose
 $$P_n(x)=\cfrac {(-1)^n} {n!} e^{\cfrac {x^2} 2} \phi^{(n)} (x)$$

pour calculer facilement ces polynômes, si l'on n'a pas l'expression de leurs coefficients, on peut dériver plusieurs fois formellement, et sympy s'impose:

from sympy import symbols, diff, exp, factorial, simplify, expand
import sympy as sp

def phi(x):
  return(exp(-x**2/2))

X = sp.symbols('X')

def hermite(n):
  P = (-1)**n/factorial(n)*exp(X**2/2)*diff(phi(X),X,n)
  return(expand(simplify(P)))


on obtient par exemple:

print([(n,hermite(n)) for n in range(5)])
>>> [(0, 1), (1, X), (2, X**2/2 - 1/2), (3, X**3/6 - X/2), (4, X**4/24 - X**2/4 + 1/8)]

d'où
$$P_4 = \cfrac {X^4} {24} - \cfrac {X^2} 4 + \cfrac 1 8$$

 Pour le tracé, utilisons matplotlib, plus souple (*).

Le code python est ici: polynomes_hermite.py
Le tracé:

Note: si on veut faire cohabiter sans problème sympy et matplotlib, il faut les importer avec précautions, pas tout d'un bloc:

from sympy import symbols, diff, exp, factorial, simplify, expand
import sympy as sp

import numpy as numpy
import matplotlib.pyplot as pyplot

(*) par exemple, je ne sais toujours pas ajouter des textes dans les graphiques tracés avec le plot de sympy (à part le titre du graphique).

la méthode de Newton, avec sympy

On se sert de sympy pour dériver formellement une fonction python, et utiliser la dérivée dans la méthode de Newton. Le code, fondé sur celui d'un lecteur anonyme, est ici: newton.py
Le graphique associé, avec matplotlib:

courbes paramétrées avec Python(x,y) et matplotlib

Deux courbes paramétrées: ellipse et cardioïde (déformée), comme exemples de bords de parties convexes ou non du plan:

le code python est ici: partie_convexe.py

développements limités, graphiques avec sympy

Des développements limités avec sympy (le code python est ici).

Les fonctions rencontrées dans la suite:
series
limit
subs (plus un peu de programmation objet)
factor
solve
plot

1. Calculs

Allons-y (dans Python(x,y) par exemple)

from sympy import *
x, y, z, t = symbols('x y z t')

# la fonction à utiliser pour calculer un développement limité en sympy
# est series:
series(exp(x),x,0,10)

# comme sympy utilise $O(x^n)$ au lieu de $o(x^n)$ dans les développements
# limités, ajouter 1 à l'ordre usuel
# pour un DL de $e^x$ en 0 à l'ordre 3:
series(exp(x),x,0,4)

# mais python est un langage de programmation, on peut écrire une
# fonction convenable:
def DL(f,v,a,n):
   return (series(f,v,a,n+1))

# quelques exemples
series((sin(x)-x)/x**3, x, 0, 3)
DL((sin(x)-x)/x**3, x, 0, 2)
# on en déduit la limite:
limit((sin(x)-x)/x**3, x, 0)

# DL de $\sqrt{1+x^3}$ à l'ordre 6 en 0
DL(sqrt(1+x**3), x, 0, 6)

# DL de $\tan$ en 0 à l'ordre 5
dl=DL(tan(x), x, 0, 5)
print(dl)

Transformons le développement limité en polynôme en éliminant le $O(x^6)$.
Pour cela on utilise la programmation objet de python: l'objet dl possède une fonction propre à sa classe (comme une classe sociale ou une classe de lycée) qui s'appelle subs: on l'utilise sans donner l'objet dl en paramètre puisqu'elle le connaît déjà. Ce genre de fonction de classe s'appelle méthode.

p=dl.subs(O(x**6),0)
print(p)

# factorisons p
p1=factor(p)
print(p1)

#cherchons les racines de p1
sols=solve(p1,x)
print('polynome de degre '+str(p1.as_poly().degree())
      + ', '+str(len(sols))+ ' racines trouvees',
      sols)

# un DL nul en 0+
DL(exp(-1/x), x, 0, 3)
# en effet la limite suivante est nulle:
limit(exp(-1/x), x, 0, dir="+")

2. Graphiques

On va utiliser le module de tracé de courbes de sympy (documentation ici), qui permet de tracer des fonctions données par des expressions formelles, ce que matplotlib ne sait pas faire:


from sympy import *
x, y, z, t = symbols('x y z t')

La fonction de tracé de sympy s'appelle simplement plot,
elle rend en argument la fonction, puis un triplet qui indique la variable de la fonction et ses bornes de variation:

plot(sin(x), (x,-4*pi,4*pi), title='$\$$\sin(x)$\$$')

donne

on peut faire des tracés multiples, il suffit de mettre à la suite les fonctions. Ici $\sin$ et son développement limité à l'ordre 3:

plot(sin(x), series(sin(x),x,0,4).subs(O(x**4),0), (x,-pi,pi),
     title='$\$$\sin(x)$\$$ et son DL en 0 a l\'ordre 3')

donne

même chose à l'ordre 5:

plot(sin(x), series(sin(x),x,0,6).subs(O(x**6),0), (x,-pi,pi),
     title='$\$$\sin(x)$\$$ et son DL en 0 a l\'ordre 5')

donne

enfin avec plus de DL, où on voit bien l'approximation:

plot(sin(x),
     *[series(sin(x),x,0,2*n).subs(O(x**(2*n)),0) for n in
     range(1,5)]
     +[(x,-pi,pi)],
     title='$\$$\sin(x)$\$$ et ses developpements limites en 0
     aux ordres $1,3,5,7,9$')

donne

Je ne sais pas encore mettre des couleurs différentes aux courbes...

graphiques avec Python(x,y) et matplotlib: suite

Le théorème des accroissements finis:

- le code python à charger dans Python(x,y) et à exécuter: accroissements_finis.py (un peu commenté).
pour éviter de répéter des commandes matplotlib longues, j'ai programmé quelques petites fonctions: tracé d'un segment, d'une flèche, d'une double flèche de tangente, d'un texte. C'est un avantage de python par rapport à tikz où la programmation est fastidieuse (du moins le peu que j'en ai fait). J'utilise solve de sympy (calcul formel) pour trouver c tel que $f'(c)=\cfrac {f(b)-f(a)}{b-a}$.

- le schéma que cela donne:

graphiques avec Python(x,y) et matplotlib

matplotlib est intégré à Python(x,y), pas besoin de le télécharger.
C'est un ensemble de fonctions qui permettent de tracer des graphiques mathématiques.
La liste des fonctions et leur documentation est là (en anglais...)

1. Un premier essai: tracer la fonction sinus sur $[0,6\pi]$:

on charge les bibliothèques nécessaires:


from math import *
import numpy as numpy
import matplotlib.pyplot as pyplot

une courbe est une suite de points du plan reliés par des segments: s'il y en a beaucoup, on a l'illusion d'une courbe lisse.

on crée d'abord la liste t des abcisses de 100 points régulièrement répartis dans $[0,6\pi]$: 

t = numpy.linspace(0.,6*pi,100)

puis on trace la courbe en donnant la liste des ordonnées correspondant aux abcisses données dans la liste t:

pyplot.plot(t, [sin(x) for x in t],'k')

ensuite on définit les bornes du tracé:

pyplot.axis([0,6*pi,-1.5,1.5])

on trace l'axe des abcisses en noir:

pyplot.axhline(linewidth=1, color='k')

puis on insère la définition de la fonction au point $(2,1)$ du plan:

pyplot.text(2,1, r'$\$$x\mapsto\sin(x)$\$$', color='k')

finalement s'affiche cette fenêtre (si elle n'apparaît pas, c'est peut-être qu'elle se trouve cachée derrière une fenêtre, alors cliquer sur son icône dans la barre des tâches):

on peut enregistrer le graphique sous forme d'une image en cliquant sur l'icône en disquette, cela donne cette image:

Notez la possibilité d'écrire du Latex dans les textes du graphique, la classe!

2. Le théorème de Rolle:


# théorème de Rolle
from math import *
import numpy as numpy
import matplotlib.pyplot as pyplot

# les bornes des intervalles
a=0.5
b=2.5
a1=a-0.3
b1=b+0.3
h=4
# la fonction dérivable en question
def f(x):
  y=x-0.5
  return(0.5*(y**5-5*y**3+4*y)+2)

# la courbe de la fonction
t = numpy.linspace(a,b,100)
pyplot.plot(t, [f(x) for x in t],'k')

# le rectangle englobant le tracé
pyplot.axis([a1,b1,-1,h])
pyplot.axis('off') # pour virer le cadre pas très joli
pyplot.plot([a1,b1],[0,0],color='k')
pyplot.plot([a,b],[f(a),f(b)],color='k')
pyplot.plot([a,a],[0,f(a)],color='k')
pyplot.plot([b,b],[0,f(b)],color='k')

c1=.5439122558+0.5 # le point où la dérivée s'annule
pyplot.plot([c1,c1],[0,f(c1)],color='k')

# pour tracer la tangente en (c,f(c)) et ses flèches,
# pas très élégant
pyplot.arrow(c1-0.3,f(c1),2*0.3,0,
  shape='full',head_width=0.1,head_length=.05,fc='k',
  length_includes_head=True)
pyplot.arrow(c1+0.3,f(c1),-2*0.3,0,
  shape='full',head_width=0.1,head_length=.05,fc='k',
  length_includes_head=True)

# enfin les textes du schéma
pyplot.text(a,-0.4, r'$a$', color='k', size=20)
pyplot.text(b,-0.4, r'$b$', color='k', size=20)
pyplot.text(a-0.3,f(a), r'$f(a)$', color='k', size=20)
pyplot.text(c1,-0.4, r'$c$', color='k', size=20)

# sauvegarde le schéma dans un fichier
savefig('rolle.png',format='png')

donne cette image, une fois sauvegardé dans le fichier:

je crois bien que je vais laisser tomber tikz... :)

python facile sous Windows: Python(x,y)

Python(x,y), c'est python à la portée de tout le monde sous Windows.
Voici comment débuter facilement. Pour la suite, consulter ce guide par exemple.

1.Télécharger Python(x,y) ici (patience, ça fait 500 Mégas mais ça vaut le coup),
puis l'installer, en  exécutant le fichier Python(x,y)-2.7.3.1.exe (re-patience, c'est longuet, mais ... je l'ai déjà dit.)
Si on veut faire du calcul formel (genre Maple), il faut ajouter sympy à Python(x,y).
Pour cela télécharger le fichier sympy-0.7.2-1_py27.exe ici, puis l'exécuter.


2. Ensuite, lancer Python(x,y) (raccourci du bureau, ou menu démarrer-> Python(x,y)->Python(x,y))
Dans la fenêtre qui s'ouvre, cliquer sur le carré avec la toile d'araignée, en face de Spyder/Options...:

Ça lance l'interface Spyder (je l'ai un peu réduite pour que ça ne soit pas trop large):

Bon, à gauche, il y a une fenêtre appelée Éditeur: 

c'est un éditeur de fichier, on y écrit ses programmes, on les sauvegarde, charge, l'édition classique d'un fichier genre Openoffice ou Word.

À droite, en bas, la fenêtre appelée  Console est une fenêtre d'exécution, où on tape des commandes et Python les exécute, en affichant le résultat.

3. Un premier programme: la fonction factorielle.

Tapons dans l'Éditeur, sur la dernière ligne (la ligne 8):

def fact(n):
    if n==0: return(1)
    else: return(n*fact(n-1))

attention aux décalages en début de lignes, il sont importants pour python.

Testons ce programme, pour cela on l'exécute avec la touche F5,
comme c'est un nouveau programme, cela ouvre une fenêtre de sauvegarde classique (cliquer sur l'image pour zoomer):

on sauvegarde donc notre programme dans un fichier,
ensuite, python demande comment exécuter:

 cocher <<Exécuter dans l'interpréteur Python ou IPython actif>>, puis cliquer Exécuter,
(ces deux étapes n'arriveront plus ensuite, python se souviendra de nos choix pour ce fichier)

et on voit que python l'exécute dans la fenêtre Console, en bas à droite:

Python connaît donc maintenant la fonction fact que l'on vient de programmer, testons-la en tapant
 fact(3) puis Entrée dans la fenêtre Console, sur la dernière ligne non vide (!):

On obtient la réponse souhaitée :)
Testons fact(100):

Pas mal ;)

Voilà, avec ça on peut déjà programmer et tester confortablement avec python.

4. Calcul formel:
il suffit de charger sympy dans la console:
from sympy import *
et voilà. Définissons, toujours dans la console,
quelques symboles utiles:
x, y, z, t = symbols('x y z t')
k, m, n = symbols('k m n', integer=True)
f, g, h = symbols('f g h', cls=Function)
et testons:

Cool.

utiliser sympy sous windows

sympy est le module de calcul formel de python, très proche de Maple.
Voilà comment l'installer sous windows 7 (sous vista sans doute aussi).

1. on se contente de python 2.

Là c'est facile, il y a tout un environnement de programmation avec édition de fichiers de programmes, gestion de projets, environnement d'exécution, tout pour l'utilisateur néophyte.
Voir le message suivant.

2. on veut python 3.

Deux solutions:

a) avec cygwin.

On installe cygwin, et du coup on travaille comme sous linux (emacs, xterm, etc).
C'est ce que je fais, mais il faut être un peu informaticien.

b) on n'y connaît rien à linux.

Là, c'est plus spartiate:

- installer python 3:

télécharger http://www.python.org/ftp/python/3.3.0/python-3.3.0.msi
exécuter ce fichier, cela installe python 3.3.0, par défaut dans C:\Python33

- copier sympy:

décompresser ce fichier: sympy-0.7.2.zip
  et mettre le répertoire sympy-0.7.2 qu'il contient dans C:\Python33
télécharger ce fichier: sympy.bat et le mettre dans C:\Python33

Pour lancer sympy, double-cliquer sur C:\Python33\sympy.bat

on a une console pas très jolie, dans laquelle on navigue sur la ligne de commande avec les flèches <- et ->, et dans les commandes précédentes avec les flèches haut et bas. On copie/colle avec le click droit dans la fenêtre. On peut changer les couleurs de la console (texte, foncd) en cliquant droit sur le haut de la fenêtre et en réglant les propriétés.

- exemples de commandes:

expand((x+y)**5)


factor(x**5-y**5)

limit(1/x, x, oo)

solve(x**3 + 2*x + 3, x)

diff(x**2-1,x)

diff(x**2-1,x,2)

integrate(1/x**2,x)

series(sin(x),x,0,5)

series(ln(1+x),x,0,5)

summation(1/2**n, (n, 0, oo))

factor(summation(k, (k, 0, n)))


groebner([x**2 + 1, y**4*x + x**3], x, y, order='lex') #grevlex