Category ArchivePython

Les k plus proches voisins

Dans le programme de NSI, on abord l’algorithme des k plus proches voisins. Je vais tenter de vous expliquer avec un schéma ce que cela signifie que de trouver de tels voisins.

Prenons l’exemple de points dans un repère orthonormé dans le carré [0;10]x[0;10] : ils sont soit bleus, soit rouges. On dit que “bleu” et “rouge” sont les classes des points.

Si on met au hasard un point dans ce même carré, on peur se demander de quels points est-il le plus proche, ce qui donnera sa classe éventuelle.

J’ai fait un programme en Python qui:

  • choisit au hasard 10 points rouges et 10 points bleus et qui les affichent;
  • choisit un point vert au hasard;
  • qui détermine la distance entre le point vert et chacun des autres points;
  • qui détermine enfin la classe éventuelle du point vert et qui affiche les distances prises en compte.

On obtient par exemple :

Pour télécharger le programme Python, rendez-vous sur cette page.

Lemniscate et parabole

Le but est de créer le GIF suivant:

Code Python

tikz = open("tikz.tex", "w")
text = ''
      
x = -5
while x < 5:
    y = 1/x
    r = (x**2+y**2)**0.5
    if r<10 and abs(y)<10:
        text = text + '\\begin{tikzpicture}[>=latex]\\labase'
        k = -5
        while k <= x:
            p = 1/k
            rr = (k**2+p**2)**0.5
            if rr<10 and abs(p)<10:
                text = text+'\\draw[red] ('+str(k)+','+str(p)+') circle ('+str(rr)+' cm);\n'
            k += 0.1
        text = text + '\\end{tikzpicture}\n'
    x += 0.1

tikz.write(text)
tikz.close()

Ce script génère un fichier tikz.tex dans lequel les dessins sont faits.

Le fichier \(LaTeX\)

\documentclass{article}
\usepackage{tikz}
\usepackage[paperwidth=10cm,paperheight=10cm,margin=0cm]{geometry}
\setlength{\parindent}{0pt}
\newcommand{\labase}{%
\clip (-5,-5) rectangle (5,5);
\draw[->] (-5,0) -- (5,0);
\draw[->] (0,-5) -- (0,5);
\draw plot[domain=-5:-0.1,samples=100] (\x,{1/\x});
\draw plot[domain=0.1:5,samples=100] (\x,{1/\x});
\node[below left] at (0,0) {$O$};
}
\begin{document}
\include{tikz}
\end{document}

En compilant via PdfLaTeX (par exemple), on génère un PDF de 49 pages.

Construction du GIF

J’ai pour habitude d’utiliser GIMP en ouvrant le PDF, puis en inversant l’ordre des calques, puis en sauvegardant en tant qu’animation dans un fichier .gif. Et voilà !

Avec Pythontex

On peut bien entendu créer un tel GIF directement avec pythontex:

% en utilisant Pythontex
\documentclass{article}
\usepackage{tikz}
\usepackage{pythontex}
\usepackage[paperwidth=10cm,paperheight=10cm,margin=0cm]{geometry}
\setlength{\parindent}{0pt}
\newcommand{\labase}{%
\clip (-5,-5) rectangle (5,5);
\draw[->] (-5,0) -- (5,0);
\draw[->] (0,-5) -- (0,5);
\draw plot[domain=-5:-0.1,samples=100] (\x,{1/\x});
\draw plot[domain=0.1:5,samples=100] (\x,{1/\x});
\node[below left] at (0,0) {$O$};
}
\begin{document}
\begin{pycode}
x = -5
while x < 5:
    y = 1/x
    r = (x**2+y**2)**0.5
    if r<10 and abs(y)<10:
        print('\\begin{tikzpicture}[>=latex]\\labase')
        k = -5
        while k <= x:
            p = 1/k
            rr = (k**2+p**2)**0.5
            if rr<10 and abs(p)<10:
                print('\\draw[red] ('+str(k)+','+str(p)+') circle ('+str(rr)+' cm);')
            k += 0.1
        print('\\end{tikzpicture}')
    x += 0.1
\end{pycode}
\end{document}

Triangle de Pascal construit avec Python et \(\LaTeX\)

Le code Python

def trianglePascal(n):
    T = [[0] * (n+1) for p in range(n+1)]
    for n in range(n+1):
        if n == 0:
            T[n][0] = 1
        else:
            for k in range(n+1):
                if k == 0:
                    T[n][0] = 1
                else:
                    T[n][k] = T[n-1][k-1] + T[n-1][k]
    return T

T = trianglePascal(9)

Ce premier code est intéressant pour voir comment construire une matrice (dont les coefficients sont ceux du triangle de Pascal).

On commence par initialiser notre matrice T en la remplissant de “0”. Puis on la remplit selon la propriété bien connue : \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\).

Le code \(\LaTeX\)

On va utiliser PythonTeX :

% sous windows 
% pdflatex --shell-escape -synctex=1 -interaction=nonstopmode %.tex|python C:\Users\trash\AppData\Local\Programs\MiKTeX\scripts\pythontex\pythontex.py %.tex|pdflatex --shell-escape -synctex=1 -interaction=nonstopmode %.tex
% Sous Linux, remplacer "--shell-espace" par "-write18"

\documentclass[10pt,a0paper,landscape]{article}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{diagbox}
\usepackage{pythontex}
\usepackage{nopageno}
\usepackage{colortbl}
\usepackage{tikz}
\usepackage[margin=5mm]{geometry}
\setlength{\parindent}{0pt}
\newcommand{\dashed}{\tikz[baseline=1mm]\draw[gray!50,dashed](0,0)--(0,0.5);}
\begin{document}

\begin{pycode}
n = 50

def trianglePascal(n):
    T = [[0] * (n+1) for p in range(n+1)]
    for n in range(n+1):
        if n == 0:
            T[n][0] = 1
        else:
            for k in range(n+1):
                if k == 0:
                    T[n][0] = 1
                else:
                    T[n][k] = T[n-1][k-1] + T[n-1][k]
    return T


T = trianglePascal(n)

print('\\begin{tabular}{|>{\\columncolor{orange!10}}c|*{',n,'}{c!{\\dashed}}c|}\\rowcolor{orange!10}\\hline\\diagbox[height=8mm]{$n$}{$k$}')
for k in range(n+1):
    print('&',k)
    
for j in range(n+1):
	print('\\\\\\hline ',j)
	for k in range(n+1):
		if k == 0:
			print('&1')
		else:
			if T[j][k] != 0:
				print('&',T[j][k])
			else:
				print('&')

print('\\\\\\hline\\end{tabular}')
\end{pycode} 

\end{document}

Une précision ici : j’ai souhaité séparer chaque colonne par des pointillés. Pour cela, j’ai utilisé une macro TiKZ (pour si peu, ça fait un peu mal quand-même…) car le package arydshln (qui permet de le faire simplement) rentre en conflit avec diagbox… Il fallait donc en sacrifier un! (en fait, ils ne rentrent pas vraiment en conflit mais si on utilise des pointillés dans le tableau, une boîte noire apparaît à la place de l’étiquette “n”). On obtient le document suivant :

Pour les curieux, voici un aperçu des premières lignes et colonnes:

Aperçu du document affichant le triangle de Pascal pour n = 50

Construire le graphe d’une suite avec Python

Dans cet article, nous allons nous intéresser à la construction du graphe d’une suite définie par \(u_{n+1}=f(u_n)\).

Mon objectif est de créer un programme Python qui demande à la personne utilisatrice :

  • la fonction;
  • le premier terme de la suite;
  • le nombre de termes à construire;
  • la fenêtre \( (x_{\min}) \), \( (x_{\max}) \), \( (y_{\min}) \) et \( (y_{\max}) \);
  • le nom sous lequel la figure sera sauvegardée (vide si on ne souhaite pas la sauvegarder).

Les modules

import numpy as np
import matplotlib.pyplot as plt
from sympy import *
x=Symbol('x')
  • Nous aurons besoin du module numpy pour effectuer quelques calculs;
  • ensuite, matplotlib nous servira à effectuer les tracés;
  • le module sympy nous servira à interpréter la saisie de la fonction comme une fonction. À ce titre, on indique que le symbole de la variable est ‘x’.

Saisie de la fonction

def definite_function():
    fonction = input("Entrez l'expression de la fonction : ")
    # convertit la chaîne de caractères en 'fonction'
    f = lambdify(x,fonction,'math') # on utilise le module 'math' ici plutôt que 'numpy' car plus pratique
    fonction_latex = input('Syntaxe LaTeX : ')
    return f,fonction_latex

Ici, on demande de saisir d’une part la fonction (avec une syntaxe “classique”), chaîne de caractères que l’on s’empresse tout de suite de transformer en fonction avec la fonction lambdify du module simpy. Puis, on demande la syntaxe \(\LaTeX\) pour que l’affichage du titre soit plus joli. La fonction retourne un couple constitué de la fonction et de la syntaxe “latexienne” de la fonction.

Les autres saisies

def window():
    xmin = float(input('xmin = '))
    xmax = float(input('xmax = '))
    ymin = float(input('ymin = '))
    ymax = float(input('ymax = '))
    return xmin,xmax,ymin,ymax
    
def definite_first_term():
    u = float(input("Entrez le premier terme : "))
    return u

def definite_nb_terms():
    n = int(input('Nombre de termes à construire : '))
    return n

def definite_name():
    name = input("Entrez le nom de l'image à sauvegarder (appuyez sur [Entrée] si vous ne voulez pas sauvegarder l'image) : ")
    return name

Rien de bien compliqué pour ces quelques fonctions qui permettent de saisir le reste des paramètres.

La fonction de construction du graphe

Nous allons la nommer :

def construct_graph(xmin,xmax,ymin,ymax,f,fonction,u,n,name):

et pour commencer, nous allons nommer la figure:

fig = plt.gcf()

dans l’objectif de la sauvegarder (éventuellement) plus tard.

Tracé de la grille

# tracé du repère et de la grille
    ax = axes([xmin,ymin,xmax,ymax])
    ax.set_xlim(xmin,xmax)
    ax.set_ylim(ymin,ymax)
    ax.xaxis.set_major_locator(MultipleLocator(1.0))
    ax.xaxis.set_minor_locator(MultipleLocator(0.1))
    ax.yaxis.set_major_locator(MultipleLocator(1.0))
    ax.yaxis.set_minor_locator(MultipleLocator(0.1))
    ax.grid(which='minor', axis='x', linewidth=0.25, linestyle='--', color='0.75')
    ax.grid(which='minor', axis='y', linewidth=0.25, linestyle='--', color='0.75')

Tracé de la courbe

# tracé des courbes
    x = np.linspace(xmin, xmax, 201)
    y = [f(x) for x in [xmin+i*(xmax-xmin)/200 for i in range(201)]]
    plt.plot(x,y,color='green')
    plt.plot(x,x,color='red')

On trace ici la courbe représentative de la fonction f ainsi que la droite d’équation \(y=x\).

Construction des termes

for i in range(0,n):
        x = [u,u]
        y = [u,f(u)]
        plt.plot(x,y,linestyle='--',color='blue',linewidth=0.5)
        x = [u,f(u)]
        y = [f(u),f(u)]
        plt.plot(x,y,linestyle='--',color='blue',linewidth=0.5)
        if i != n-1:
            x = [f(u),f(u)]
            y = [f(u),0]
            plt.plot(x,y,linestyle='--',color='orange',linewidth=0.5)
        if i%2 == 0:
            yunder=-0.05
        else:
            yunder = -0.1
        plt.text(u-0.02,yunder,np.around(u,2))
        u = f(u)

On fait une boucle dont le nombre d’itérations est égal au nombre de points que l’on veut. Dans un premier temps, on trace en pointillés la ligne verticale qui va de (u,0) à (u,f(u)), dans un deuxième temps, la ligne horizontale qui va de (u,f(u)) à (f(u),f(u)) puis la ligne verticale qui va de (f(u),f(u)) à (f(u),0) pour avoir le terme suivant sur l’axe des abscisses.

Le titre

#params = {'mathtext.default': 'regular' }
#plt.rcParams.update(params) 
    plt.rc('text', usetex=True)
    plt.rc('font', family='serif')
    title = "Construction des "+str(n)+" premiers termes de la suite définie par\n$u_{n+1}=f(u_n)$ avec $f(x)="+fonction+"$"
    plt.title(title)
    if name != '':
        fig.savefig(name+'.png',dpi=100,bbox_inches='tight')
    plt.show()

On insère maintenant le titre; les deux premières lignes commentées affichent un titre avec une police de caractères par défaut sous Python (ce qui ne me convient pas, mais qui peut plaire à certaines personnes). Les deux lignes suivantes spécifient que l’on souhaite un affichage \(\LaTeX\).

Fonction principale

if __name__ == '__main__':
    f,fonction = definite_function()
    u = definite_first_term()
    xmin,xmax,ymin,ymax = window()
    n = definite_nb_terms()
    name = definite_name()
    construct_graph(xmin,xmax,ymin,ymax,f,fonction,u,n,name)

En exécutant ce programme avec les paramètres suivants:

Saisie

on obtient l’image suivante:

Résultat

Retrouvez le programme complet sur cette page.

Créer un fichier LaTeX avec Python

Dans un article précédent, je vous expliquais comment, dans un fichier \(\LaTeX\), on pouvait se servir de Python grâce à l’extension Pythontex.

Maintenant, je vais vous expliquer comment faire l’inverse, à savoir comment créer et compiler un fichier \(\LaTeX\) avec un programme Python.

L’objectif va être le même que dans l’article précédent (cas d’école) : créer 20 développements (avec double distributivité) aléatoires.

Créer un fichier TeX et le compiler sous Python

Importation des modules nécessaires

import os.path
import random
from sympy import Symbol
from sympy import expand
x=Symbol('x')

J’importe le module os car il va me servir à exécuter des commandes en lignes.

Ensuite, j’importe le module random car il est nécessaire dans notre contexte (dès lors qu’il y a choix aléatoire…).

J’utilise ensuite sympy pour les manipulations algébriques (c’est spécifique ici à ce que je souhaite faire). Je définis alors “x” comme le symbole désignant l’inconnue.

Construction du fichier

Le contenu du fichier va être défini par une succession de texte.

Définir le préambule

def preambule(*packages):
	p = ""
	for i in packages:
		p = p+"\\usepackage{"+i+"}\n"
	return p

Cette fonction a pour but d’appeler tous les packages nécessaires.

start = "\\documentclass[12pt,a4paper,french]{article}\n\\usepackage[utf8]{inputenc}\n"
start = start+preambule('amsmath','lmodern','babel')
start = start+"\\begin{document}\n\\begin{align*}\n"

end = "\\end{align*}\n\\end{document}"

On commence par définir la classe utilisée (avec les options souhaitées) ainsi que l’encodage. Puis, on appelle tous les packages souhaités. Enfin, on commence le document.

Génération des égalités

body = ""

for n in range(21):
    a = random.choice([1, -1]) * random.randint(2, 9)
    b = random.choice([1, -1]) * random.randint(2, 9)
    c = random.choice([1, -1]) * random.randint(2, 9)
    d = random.choice([1, -1]) * random.randint(2, 9)
    e = (a*x+b)*(c*x+d)
    eresultchain = str(expand(e)) # on convertit le résultat en chaîne de caractères
    eresultchain = eresultchain.replace('**','^') # on met au format TeX les exposants
    eresultchain = eresultchain.replace('*','') # on élimine les symboles '*'
    echain = str(e)
    echain = echain.replace('*','')

    body = body+echain+" & = "+eresultchain+"\\\\\n"

Il est ici nécessaire d’anticiper sur la syntaxe \(\LaTeX\) pour remplacer certains caractères…

Ecriture du fichier

container = start+body+end

file = "monfichier.tex"
if os.path.exists(file):
	os.remove(file)

fichier = open("monfichier.tex","x") # "x" pour la création et l'écriture
fichier.write(container)
fichier.close()

Compilation

Une fois le fichier créé, il est pratique de le compiler directement puis de l’afficher.

instructions = "pdflatex "+file#"
os.system(instructions)

readpdf = "START "+file[:-4]+".pdf"
os.system(readpdf)

Et voilà ! Une feuille d’exercices créée en à peine 2 secondes…

Le code complet

Les abonné.e.s de ce site trouveront le code complet sur cette page.

Python et fonction à nombre variable d’arguments

Voici une astuce qui pourra sans doute servir à plusieurs d’entre vous.

Une fonction peut quelques fois devoir prendre un nombre variable d’arguments. Par exemple, si l’on souhaite calculer le PGCD de plusieurs nombres, on aimerait que la fonction PGCD (par exemple) accepte 2, 3, 4, … arguments.

Voici sur un exemple comment faire:

def pgcd(*n):
	def _pgcd(a,b):
		while b!=0:
			a,b = b,a%b
		return a
	p = _pgcd(n[0],n[1])
	for x in n[2:]:
		p = _pgcd(p,x)
	return p

print(pgcd(165,515,225,65))

Alors ? On kiffe ?

Python et ensembles de Julia

L’ensemble de Julia est, pour un nombre complexe c donné, l’ensemble des points d’affixes \(z_0\) tels que la suite définie pour tout entier naturel n par \(z_{n+1}=z_n^2+c\) est bornée.

Selon les valeurs de c, on peut obtenir des ensembles plutôt jolis:

Pour les personnes abonnées à mathweb.fr, vous trouverez un code Python ainsi que les 10 images (sans marquage) sur cette page.

Un IDE Python sympathique

Quand on décide d’installer Python sur sa machine, il est par défaut accompagner d’un IDE (Integrated Development Environment) plus que basique. Il est suffisant, mais pas trop jolie et peu pratique (car si on ouvre une fenêtre contenant notre programme et si on exécute ce dernier, le résultat s’affiche dans la console, ce qui fait 2 fenêtres).

C’est la raison pour laquelle j’ai souhaité aujourd’hui changer d’IDE.

Quelques essais

Eclipse

J’ai commencé par télécharger Eclipse qui, soit-disant, est le must. Mais lors du lancement de l’installation, une fenêtre s’ouvrit pour me signaler qu’il fallait une plateforme JDK 7+. Je télécharge donc JDK11, mais même après cela, Eclipse ne put s’installer. N’étant pas du tout patient, je tenta un autre IDE…

Atom

Ayant entendu parlé d’Atom, je l’installai pour l’essayer… Mais je n’y ai rien compris (je ne dis pas que Atom est compliqué… je dis juste que je suis une grosse merde et que je n’ai pas réussi à comprendre comment compiler un programme Python). Moi, il me faut un truc simple et rapide d’utilisation car je n’ai pas que ça à faire de ma vie (rester des heures à essayer de comprendre comment fonctionne un logiciel); il faut que le bousin soit pédagogue avec ses utilisateurs, même les plus cons (comme moi), ce qui n’est pas le cas…

Sublime Text

Jamais 2 sans 3… J’essayai alors le logiciel au nom pourri… Et là ! Miracle !

Déjà, le téléchargement s’effectua en quelques secondes (programme très léger) et l’installation aussi. Et puis, en chargeant un programme Python, on voit tout de suite comment faire pour le compiler:

La compilation est rapide (un CTRL+B suffit), le design par défaut plus que correct (même si on peut le changer). Bref, cet IDE est top !

Malheureusement, il nécessite une licence. Pour le moment, il fonctionne mais on verra sur la durée… Je ne manquerai pas de vous tenir informé.e.s.

M.A.J. du 10 mai 2019 : cet éditeur s’avère en définitive très peu intéressant car on ne peut pas compiler les scripts qui nécessitent d’entrer au clavier des données… Ce qui est plus que fâcheux ! Donc je le déconseille.

Spyder

Après avoir testé Sublime Text, je jette mon dévolu sur Spyder.

Je vais donc sur la page https://www.anaconda.com/distribution/ afin d’installer le tout. Bon, là, je me suis fait arnaqué car ça m’installe Anaconda Navigator ainsi que la dernière version de Python (3.7). Mais ça, c’est pas bien grave car je tournais avec Python 3.6 donc une petite M.A.J. ne fait pas de mal… Il faut prévoir quand-même pas mal de temps entre le téléchargement (plus de 600 Mo) et l’installation. Mais le résultat en vaut le coup !

Spyder 3
Aperçu de Spyder 3

C’est exactement ce que je cherchais : un cadre pour le code, un autre pour la console et en plus, il y en a un pour l’affichage divers (variables, fichiers). Et le tout est gratuit !

Ensemble de Mandelbrot et Python

Pour la faire courte, l’ensemble de Mandelbrot est l’ensemble des points du plan complexe d’affixe c tels que la suite définie par \( \left\lbrace\begin{array}{l} z_0=0\\z_{n+1}=z_n^2+c\end{array}\right. \) est bornée.

Cet ensemble peut être construit à l’aide de Python, et de son module pygame. La vitesse à laquelle l’ensemble est construit est remarquable! Sur mon ordinateur (16 Mo RAM, sous Windows, processeur Intel Core i5), cela ne met pas plus de 10 secondes pour afficher ceci:

Ensemble de Mandelbrot réalisé avec Python

Avec une autre suite, j’ai obtenu:

Fractale réalisée avec Python

Je vous l’accorde, elle est nettement moins esthétique que la première, mais je ne suis pas Julia, ni Fatou 🙂

Les abonné.e.s de mathweb.fr trouveront les codes Python de ces deux fractales sur cette page.

Initiation à la complexité algorithmique

Loin de moi l’idée de faire un article complet sur la notion de complexité, mais en travaillant sur le nouveau programme de NSI (qui entre en vigueur à la rentrée 2019), je me suis aperçu que cette notion allait pointer le bout de son petit museau perfide… Je voudrais donc par cet article familiariser les élèves avec elle.

C’est quoi la complexité d’un algorithme ?

C’est le nombre d’opérations et d’affectations faites. On appelle cela des opérations élémentaires. Prenons le programme Python suivant:

def convert(n):
    h = n // 3600
    m = (n - 3600*h) // 60
    s = n % 60
    return h,m,s

n = 102152

print("{} secondes = {} h {} min {} sec.".format(n,convert(n)[0],convert(n)[1],convert(n)[2]))

Dans la fonction “convert”, il y a :

  • 3 affectations (h, m et s)
  • 5 opérations (n//3600, 3600*h, n-3600*h, (n-3600*h)//60 et n%60)

La complexité de cette fonction est donc égale à 8.

Exercice 1

Montrer que la complexité de la fonction suivante est égale à 5.

def myFunction(n):
    if n%3 == 0:
        p = n/3 + 2
    else:
        p = n*2 + 1
    return p

Solution

il y a d’abord un test (if) dans lequel il y a une opération (n%3), ce qui nous fait pour le moment une complexité de 2.

Ensuite, quelle que soit l’issue du test, il y a 1 affectation (p) et 2 opérations (pour calculer p), soit une complexité augmentée de 3.

Au final, on obtient bien une complexité de 5.

Structures itératives

Dans un programme, il y a souvent des boucles. Nous allons voir un exemple avec une boucle “for”:

def recherche(l,x):
    for i in range(len(l)):
        if l[i]==x:
            return i
    return -1

l = "Bonjour."
x = "p"

print(recherche(l,x))

La fonction recherche a pour but d’afficher le rang où se trouve le caractère “x” dans la chaîne de caractères “l”, et affiche “-1” si ce dernier n’est pas trouvé.

  • Au niveau de la boucle for, il y a 1 addition (sur i), une affectation (i) et une comparaison (test si i<len(l));
  • dans la boucle for, il y a un test (if l[i]==x).

Au final, si n est la longueur de la chaîne de caractères, il y a 4n opérations élémentaires, qui correspond à la complexité de la fonction recherche.

Exercice 2

Calculer la complexité de la fonction somme définie dans ce programme:

def somme(n):
    s = 0
    for i in range(n+1):
        s += i
    return s

print(somme(100))

Solution

Il y a :

  • au début, 1 affectation (s = 0);
  • au niveau de la boucle for, 3 opérations élémentaires (affectation sur i, opération d’incrémentation sur i, test sur i);
  • dans la boucle for, il y a 2 opérations élémentaires (1 affectation sur s et une opération sur s).

Ainsi, il y a 5 opérations élémentaires dans la boucle, répétées n fois, plus la première (hors boucle). La complexité de la fonction somme est donc égale à 5n+1.

En général, on appelle T la complexité (initiale de Time).

Exercice 3

Calculer la complexité de la fonction mystere du programme suivant:

def mystere(n):
    m = 0
    for i in range(n):
        for j in range(i):
            m += i+j
    return m

print(mystere(100))

Solution

  • Il y a avant tout 1 affectation dès le début (m=0);
  • ensuite, au niveau de la boucle sur i, 3 opérations élémentaires;
  • au niveau de la boucle sur j, il y a 3 opérations élémentaires répétées i fois;
  • dans la boucle sur j, il y a 3 opérations élémentaires (1 affectation sur m, une somme sur m et une somme de i et j).

Ainsi, à part la première affectation, il y a 9 opérations élémentaires pour chaque valeur de j possible. Il y a:

  • 1 valeur possible de j quand i=0 (j=0);
  • 1 valeur possible de j quand i=1 (j=0);
  • 2 valeurs possibles de j pour i=2 (j=0 et j=1):
  • etc.
  • n-1 valeurs possibles de j pour i=n-1.

La complexité est donc égale à:$$\begin{aligned} & 1+9\times(1+1+2+3+\cdots+(n-1))\\=\ & 10+\frac{9n(n-1)}{2}\\=\ & \frac{1}{2}(9n^2-9n+20).\end{aligned}$$

Ordre de grandeur de la complexité

Nous le voyons dans l’exemple précédent, la complexité peut s’exprimer par un polynôme. Dans un tel cas, si n est relativement grand, on pourra assimiler la complexité à son ordre de grandeur. Par exemple ici, la complexité de la dernière fonction est de l’ordre de \(n^2\). On écrira alors:$$T_n=O(n^2).$$On dira ici que la complexité est quadratique.

Pour l’exercice 2, \(T_n=5n+1=O(n)\). On dira que la complexité est linéaire.

Fonction récursive

Une des fonctions récursives la plus simple est celle qui permet de calculer n! (la factorielle de n), c’est-à-dire \(2\times3\times\cdots\times n\).

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

Il y a un test pour commencer (sur n). Si le test est vrai, on s’arrête, sinon on effectue une opération (un produit) en faisant appel à la même fonction. Ainsi, si n est non nul, il y a 2 opérations élémentaires + le nombre d’opérations élémentaires de la fonction au rang n – 1.

Si \(T_n\) représente la complexité de la fonction factorielle(n) alors:$$T_n=T_{n-1}+2,\quad T_0=1.$$

La complexité est donc donnée par une suite arithmético-géométrique. C’est toujours le cas pour les fonctions récursives.

On peut alors montrer que \(T_n=2n+1=O(n).\)

Généralités

Si on considère une fonction toto(n) dans laquelle on fait appel à cette même fonction a fois et dans laquelle il y a b opérations élémentaires, si on note \(T_n\) sa complexité alors:$$T_n=aT_{n-1}+b.$$Ainsi, \(T_n=O(a^n)\). La complexité est alors exponentielle.

Exercice 4

Quelle est la complexité de la fonction suivante:

def fibo(n):
    if n<2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

Solution

Il y a 2 opérations élémentaires (un test sur n et une addition de fibo(n-1) et fibo(n-1)) donc:$$T_n=T_{n-1}+T_{n-2}+2,\quad T_0=T_1=1.$$ La complexité est donc une suite linéaire d’ordre 2 et d’équation caractéristique:$$r^2-r-1=0$$ de solutions \(r_1=\frac{1+\sqrt5}{2}\) et \(r_2=\frac{1-\sqrt5}{2}\). Comme \(|r_1|>|r_2|\), une propriété nous dit que la complexité de la fonction fibo(n) est:$$T_n=O(r_1^n).$$La complexité est alors exponentielle.