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:
On obtient par exemple :
Pour télécharger le programme Python, rendez-vous sur cette page.
Voici un exercice inédit, tout droit sorti de mon imagination machiavélique. Il est ici question de probabilités continues (avec la loi exponentielle), d’étude de fonction (oui oui !), de loi normale et d’intervalle de fluctuation… Tout ça en un seul exercice ! Avec son corrigé… bien sûr !
Amusez-vous bien !
Je ne sais pas ce qu’il en est pour vous, mais les programmes de sauvegardes qui existent ne me satisfont pas trop car ne répondant pas à mes attentes bien spécifiques.
Aussi ai-je souhaité créer un programme de sauvegarde qui fait exactement ce que je veux.
Voici une vidéo qui vous montre comment faire, en espérant qu’elle vous inspire pour que vous aussi vous puissiez faire le vôtre.
Pour les abonné.e.s de mathweb, le programme se trouve sur cette page.
Nous allons voir dans cet article comment trouver la section d’un cube par un plan quand on connaît 3 points sur 3 arêtes de ce cube, chacun des points n’étant pas sur une face où se trouve l’un des deux autres.
Ici, on va projeter le point J sur [BF] car [BF] est contenue dans une face où se trouve K. On obtient un point que l’on nomme \(P_1\).
Ici, on trace \(AP_1\) et \(AJ\). Elles se coupent en un point \(P_2\).
Les points K et \(P_2\) appartiennent à la même face (ABFE) donc la droite \((KP_2)\) coupe l’arête [AE] (car elles ne sont pas parallèles). On obtient alors le point \(P_3\).
On a ainsi l’intersection des plans (IJK) et (ADHE):
ainsi que celle des plans (IJK) et (ABFE):
On trace maintenant la droite parallèle à \((KP_3)\) passant par J : elle coupe l’arête [DC] en \(P_4\):
On trace ensuite \([IP_4]\) qui est un autre côté de la section cherchée:
Puis la parallèle à \((IP_3)\) passant par J, qui coupe [GF] en \(P_5\):
On trace enfin \([KP_5]\) qui ferme la section cherchée:
La section du cube par le plan (IJK) est le polygone \(KP_5JP_4IP_3\):
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 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 :
La complexité de cette fonction est donc égale à 8.
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
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.
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 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.
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))
Il y a :
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).
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))
Ainsi, à part la première affectation, il y a 9 opérations élémentaires pour chaque valeur de j possible. Il y a:
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}$$
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.
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).\)
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.
Quelle est la complexité de la fonction suivante:
def fibo(n):
if n<2:
return n
else:
return fibo(n-1) + fibo(n-2)
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.
Je ne suis pas très fan du module turtle, car je préfère la programmation numérique, mais il faut bien avouer que ce module est pratique pour dessiner des schémas récursifs, comme les fractales.
Je me suis donc mis à la recherche d’un code donnant un tel schéma pour tenter de me familiariser avec le module. J’avais une idée bien précise : celle d’un arbre fractal, que j’avais vu quelque part.
Après quelques recherches, je suis enfin tombé sur le code suivant (que je me suis permis de commenter):
from turtle import *
angle = 30
color('#3f1905')
def arbre(n,longueur):
if n==0:
color('green')
forward(longueur) # avance
backward(longueur) # recule
color('#3f1905')
else:
width(n)
forward(longueur/3) #avance
left(angle) # tourne vers la gauche de angle degrés
arbre(n-1,longueur*2/3)
right(2*angle) # tourne vers la droite de angle degrés
arbre(n-1,longueur*2/3)
left(angle) # tourne vers la gauche de angle degrés
backward(longueur/3) # recule
hideturtle() # cache la tortue
up() # lève le stylo
right(90) # tourne de 90 degrés vers la droite
forward(300) # avance de 300 pixels
left(180) # fait un demi-tour
down() # pose le stylo
arbre(11,700) # exécute la macro
showturtle() # affiche la tortue
mainloop()
qui donne ceci:
Mais attention… Le dessin met un certain temps avant d’être fini (par exemple, sur mon ordinateur 16 Mo de RAM, processeur Intel Core i5, il met une vingtaine de minutes… arf !)
Si on modifie l’angle (disons pour le mettre à 50°), on obtient ceci:
Et avec un angle de 110° :
N’est-il pas choupinou ? 🙂
Vous pouvez remarquer dans le code la fonction récursive : c’est une notion que l’on verra en NSI (nouveau lycée)… mais prévue en cycle de maturité (en Terminale quoi !)… même si je n’ai pas pu résister à l’envie d’en mettre dans mon livre d’exercices corrigés qui sortira en version papier pour la rentrée 2019.
Une fonction récursive est une fonction qui fait appel à elle-même dans sa définition. On retrouve ce genre de fonction par exemple pour calculer le pgcd de deux nombres:
def pgcd(a,b):
if b==0:
return a
else:
r=a%b
return pgcd(b,r)
print(pgcd(56,42))
Ici, la récursivité s’appuie sur la propriété du pgcd qui stipule que:$$\text{pgcd}(a,b)=\text{pgcd}(b,r)$$où \(a = bq + r,\ 0\leq r < b\).
Les mathématiques sont donc très importantes pour construire des algorithmes (et par suite des programmes) performants. En effet, on aurait très bien pu calculer le pgcd de la manière suivante:
def pgcd(a,b):
while b<>0:
r=a%b
a,b=b,r
return a
print(pgcd(56,42))
Pour comparer deux algorithmes, on parle souvent de complexité. Cet article ne parle pas de cette notion, mais sachez tout de même que la complexité d’une fonction récursive est donnée par une suite arithmético-géométrique. Dans la fonction pgcd, il y a 2 instructions élémentaires (le test sur b et l’affectation de r). La complexité \(C_n\) est donc égale à \(2+C_{n-1}\), où \(C_{n-1}\) est celle de la fonction pgcd(b,r). On démontre alors que la complexité de la fonction récursive est de l’ordre de O(n) [complexité linéaire]. En fait, la complexité est linaire dans le pire des cas (quand a et b sont deux nombres successifs de la suite de Fibonacci), car dans les autres cas, la complexité est logarithmique [O(ln(n))].
L’évaluation moyenne de la complexité de l’algorithme d’Euclide version récursive est assez compliquée. Le nombre d’appels moyen de la fonction pgcd est:$$\frac{12\ln(2\ln n)}{\pi^2}+1,47.$$
http://imss-www.upmf-grenoble.fr/prevert/Prog/Complexite/euclide.html
La complexité de l’algorithme non récursif est quasi-identique à sa version récursive.
https://www.labri.fr/perso/betrema/deug/poly/euclide.html
La version récursive de l’algorithme d’Euclide est peut-être un peu plus facile à écrire que la version itérative. Les deux versions ont fondamentalement la même complexité, avec un petit avantage à la version itérative, car l’appel d’une fonction n’est pas gratuit.
Mais là, je m’égare… Saint-Lazare !
Voici un article qui est abordable dès le lycée.
Imaginons une suite de nombre qui commence par “1” et “1”.
On souhaite que le nombre qui vient juste après soit égal à la somme des deux derniers nombres. Ainsi, le 3ème nombre est égal à 1+1, soit “2”. Après “2”, il y a 2+1=3, puis après ce “3”, il y a 3+2=5.
Comprenez-vous maintenant comment on calcul les termes de cette suite de nombres ? On prend toujours les deux derniers, on les ajoute et ça nous donne le suivant.
Comme ce procédé est répétitif, on va pouvoir utiliser un programme pour trouver tous les nombres de cette suite. En Python, cela donne :
F = [1,1]
for n in range(30):
F.extend([F[n+1]+F[n]])
print(F)
La première ligne définie une liste (de nombres) que l’on initialise avec les deux nombres desquels on part (donc ici, “1” et “1”). On a ainsi F[0]=1 et F[1]=1 (le premier item d’une liste est toujours indicé à 0).
Ensuite, on créé une boucle “Pour” afin de calculer ici 30 termes de plus : quand on écrit “for n in range(30)“, cela signifie que la variable n va prendre 30 valeurs entières en partant de 0.
Dans cette boucle, on calcule la somme des deux derniers termes de la liste L, puis on ajoute le résultat à la liste (c’est la méthode extend : on étend la liste avec la valeur trouvée).
Une fois sorti.e.s de la boucle, on affiche la liste, ce qui nous donne:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309]
Maintenant, comme je suis quelqu’un de très bizarre (no comment, thanks!), j’ai envie de calculer les quotients successifs de deux termes consécutifs de cette suite. Je vais utiliser le code suivant:
for n in range(31):
print(F[n+1]/F[n])
ce qui m’affiche:
1.0
2.0
1.5
1.6666666666666667
1.6
1.625
1.6153846153846154
1.619047619047619
1.6176470588235294
1.6181818181818182
1.6179775280898876
1.6180555555555556
1.6180257510729614
1.6180371352785146
1.618032786885246
1.618034447821682
1.6180338134001253
1.618034055727554
1.6180339631667064
1.6180339985218033
1.618033985017358
1.6180339901755971
1.618033988205325
1.618033988957902
1.6180339886704431
1.6180339887802426
1.618033988738303
1.6180339887543225
1.6180339887482036
1.6180339887505408
1.6180339887496482
Ne remarquez-vous pas quelque chose ? Ces quotients semblent se rapprocher d’un nombre, dont la valeur approchée au millième est 1,618. C’est ce nombre que l’on appelle le nombre d’or.
Dans la mesure où Python affiche 16 décimales, je me demande à partir de quel rang j’obtiendrai une valeur approchée du nombre d’or avec une précision de \(10^{-16}\). Je vais utiliser ce code:
F = [1,1,2,3]
n = 3
while (abs(F[n-2]/F[n-3]-F[n]/F[n-1])>10**(-16)):
u = F[n]+F[n-1]
F.extend([u])
n +=1
print(F[n]/F[n-1])
Je demande ici à calculer les termes successifs de la suite de Fibonacci tant que la valeur absolue de la différence de deux quotients consécutifs est supérieure à \(10^{-16}\).
Ainsi, la valeur affichée sera une valeur approchée du dernier quotient calculé, qui sera aussi une valeur approchée du nombre d’or.
On obtient ici:
1.618033988749895
Ce nombre d’or est noté par la lettre grecque: \[ \varphi \approx 1,618033988749895.\]
On peut dire beaucoup de choses sur le nombre d’or, mais on peut aussi préciser qu’il existe un nombre d’argent (appelé ainsi par Gilles HAINRY, professeur à l’université du Mans à l’époque des faits, donc en 1996). Dans un cas général, on parle de nombres de métal.
Pour en savoir plus, je vous invite à regarder l’excellent ouvrage “Ainsi de suites”, écrit par…. Oh tiens ! Ecrit par moi 🙂 ! Il est téléchargeable gratuitement sur ce site sur la page suivante :https://www.mathweb.fr/euclide/ouvrages-personnels-de-mathematiques/
Les mots que l’on utilise en mathématiques m’ont toujours fasciné : je me suis souvent demandé d’où ils venaient et pourquoi ils étaient utilisés.
Cet article tente de réunir le plus de mots possibles parmi ceux qui, à mes yeux, sont les plus utilisés par tout le monde.
Bien le bonjour l’ami.e. !
Comme j’ai bossé pendant pas mal de temps sur cette fiche, je t’en fais profiter.
Et pour les membres de ce site, en plus, je joins le fichier source \(\LaTeX\).
La fiche : Le second degré
Les sources : sur cette page
Combien de fois ai-je voulu générer automatiquement des exercices similaires (par exemple, de développement) ? Vous ne le savez pas, mais moi, je le sais : beaucoup trop !
Encore aujourd’hui, j’ai voulu générer une série de multiplications pour faire réviser ses tables une de mes élèves.
Comme je me suis mis à Python il n’y a pas longtemps, et comme dans la foulée je me suis aussi mis à PythonTeX, j’ai forcément pensé à tout ça pour faire ma feuille d’exercices (plutôt que d’inventer et de taper plus de 90 opérations).
Nous allons voir comment.