Informatique

Algorithmes et programmes

Arithmétique

Diviseurs positifs d'un entier naturel non nul

Cet algorithme fournit la liste complète des diviseurs positifs d'un entier naturel non nul (en l'état, l'entier doit être inférieur ou égal à 200 000).

Primalité d'un entier naturel

Le petit programme fourni demande un entier naturel (supposé supérieur ou égal à 2. Cependant, on pourra facilement modifier le programme pour qu'il traite un entier quelconque) et précise s'il est ou non premier.

Décomposition d'un entier naturel (supérieur ou égal à 2) en facteurs premiers

Cet algorithme fournit la décomposition en facteurs premiers d'un entier naturel supérieur ou égal à 2. Chaque facteur premier apparaît dans la décomposition suivi de son exposant.

PGCD de deux entiers naturels non nuls

Cet algorithme détermine le plus grand diviseur commun positif de deux entiers naturels non nuls.

Chaînes amiables

A un entier naturel N non nul, on associe : la somme de ses diviseurs propres (c'est-à-dire les diviseurs positifs de N strictement inférieurs à N) s'il est différent de 1 ; 1 sinon. On recommence alors avec le nouvel entier ainsi obtenu. On détermine de la sorte une suite d'entiers qui peut être périodique. Dans ce cas (et si la suite n'est pas constante à partir d'un certain rang), on parle de "chaîne amiable". On fournit à l'algorithme l'entier initial et le nombre de termes de la suite à calculer.

Autour de la conjecture de GOLDBACH

La conjecture de GOLDBACH (qui date de 1742 et n'a toujours pas été démontrée) stipule que tout entier pair supérieur ou égal à 4 est la somme de deux entiers naturels premiers (cette décomposition n'étant pas forcément unique comme on s'en convaincra facilement). On fournit ci-dessous deux programmes en langage Python. Le premier (fichier GOLDBACH1.py) demande à l'utilisateur un entier supérieur ou égal à 4 et renvoie toutes les décompositions de cet entier comme somme de deux nombres premiers. Le second (fichier GOLDBACH2.py) détermine, pour chaque entier pair compris entre 4 et un entier pair fourni par l'utilisateur, le nombre des décompositions en somme de deux nombres premiers de cet entier. Le programme construit alors le nuage de points correspondant. On le nomme classiquement "la comète de GOLDBACH". Avec les entiers pairs compris entre 4 et 10 000, on obtient le nuage ci-dessous. Ce second programme fait appel à la bibliothèque matplotlib.

[Source Python #1]  [Source Python #2]

Second degré

Résolution de l'équation du second degré à coefficients réels

Cet algorithme résout les équations du second degré à coefficients réels. Ce problème est une situation intéressante pour la mise en oeuvre des tests. Lorsque le discriminant est strictement négatif, l'algorithme fournit les deux racines complexes.

Mise sous forme canonique d'un trinôme du second degré à coefficients réels

Cet algorithme fournit la forme canonique d'un trinôme du second degré à coefficients réels. Ce problème est une situation intéressante pour la mise en oeuvre des tests pour obtenir dans tous les cas un affichage soigné.

Fonctions

Résolution de l'équation f(x) = 0 par dichotomie.

Cet algorithme permet d'obtenir un encadrement de la solution (supposée unique) d'une équation de la forme "f(x) = 0" par dichotomie. Pour utiliser cet algorithme avec une autre fonction, téléchargez le fichier "Dichotomie.alg" en cliquant avec le bouton droit de la souris sur "Source AlgoBox" ou le fichier "Dichotomie.py".

[Source AlgoBox]

Résolution de l'équation f(x) = 0 par trichotomie.

Cet algorithme est voisin du précédent. On travaille avec les mêmes hypothèses mais à chaque itération, la longueur de l'intervalle courant est divisée par 3. La vitesse de convergence est plus rapide mais le codage un peu plus complexe.

Calcul de la valeur approchée d'une intégrale par la méthode des trapèzes.

Pour une fonction supposée définie et continue sur un intervalle de la forme [a ; b], cet algorithme donne une valeur approchée de l'intégrale grâce à la méthode des trapèzes. L'utilisation en ligne se fait avec la fonction carrée ; pour utiliser cet algorithme avec une autre fonction, téléchargez le fichier "IntegraleTrapezes.alg" en cliquant avec le bouton droit de la souris sur "Source AlgoBox".

[Source AlgoBox]

Approximation de l'exponentielle par la méthode d'Euler.

Cet algorithme permet d'obtenir des valeurs approchées de la fonction exponentielle sur l'intervalle [0 ; 1] grâce à la méthode d'Euler. On utilise seulement le fait que la fonction exponentielle est l'unique fonction dérivable sur l'ensemble des réels, dont la dérivée est égale à elle-même et vérifiant f(0)=1.

[Source AlgoBox]

Probabilités et statistiques

Intervalle de fluctuation et simulation

On considère ici une variable aléatoire suivant une loi binomiale dont on fournit les paramètres n et p. On détermine alors l'intervalle de fluctuation asymptotique au seuil de 95% : IF. Grâce à la fonction alea d'Algobox, on va générer un certains nombres d'échantillons de taille n. Pour chacun de ces échantillons, on calcule la fréquence empirique des succès (X/n). Pour l'ensemble des échantillons, on calcule finalement la proportion des fréquences empiriques appartenant à l'intervalle IF. Cette proportion est bien sûr proche de 0,95 ...

Estimation de π par une méthode de Monte-Carlo

La méthode de Monte-Carlo mise en oeuvre ici consiste à tirer aléatoirement des points dans un carré de côté 1. La probabilité que le point se trouve dans un certain quart de cercle incrit dans le carré vaut π/4. En tirant un grand nombre de points au hasard, on peut donc estimer π. Si cette estimation est loin d'être efficace pour obtenir une valeur approchée précise de π, l'algorithme est simple et intéressant. De surcroît, les possibilités graphiques d'AlgoBox sont utilisées pour faire apparaître les points de telle ou telle couleur suivant qu'ils se trouvent ou pas dans le quart de cercle.

Suites

Somme des n premiers entiers naturels non nuls

Cet algorithme calcule la somme des n premiers entiers naturels non nuls. Le résultat pouvant directement être exprimé en fonction de n, l'intérêt de l'algorithme est essentiellement pédagogique.

Premiers termes d'une suite arithmético-géométrique

Cet algorithme calcule, à partir de la relation de récurrence (dont on fournit les coefficients) d'une suite arithmético-géométrique u et de son premier terme u(0), les N termes u(1) à u(N). Pour une telle suite, on sait explicitement exprimer u(n) en fonction de n mais cette définition explicite n'est pas à proprement parler au programme de certaines classes de Terminale par exemple. Par ailleurs, disposer rapidement des premiers termes d'une telle suite peut-être pratique lorsque l'on cherche, par exemple, à résoudre certaines inéquations.

Courbe de Von KOCH

Cet algorithme permet de tracer une courbe de Von Koch (flocon) qui, à la limite (nombre d'itérations infini), est une courbe continue mais nulle part dérivable.

Divers

Problème des n dames.

Considérant un échiquier de nxn cases (traditionnellement n=8 !), on souhaite placer dessus n dames sans qu'aucune ne soit en position de prise. Le programme Python proposé fournit les solutions sous forme de tableaux où les cases vides sont représentées par des 1 et les cases occupées par des Dames par des 2. Toutes les solutions sont fournies INDEPENDAMMENT des symétries existantes. L'algorithme est essentiellement récursif : après avoir placé une dame, il convient de placer les dames restantes sur un nouvel échiquier comportant moins de cases autorisées que le précédent.

Ressources Geogebra

Approximation de la loi binomiale par la loi normale.

Ressources Python

Accès direct à la documentation Python (Version 3).	HTML
Une fiche PanaMaths sur les listes en Python.
Une introduction PanaMaths sur les tableaux de la bibliothèque numpy.

Ressources Xcas

Un tutoriel PanaMaths sur les fonctions avec Xcas.
Un tutoriel PanaMaths sur le calcul matriciel avec Xcas.