Fermetures tunnels 2015 03 26

Leçon 65
Algorithmes
Pour cette leçon, il faut un plan, une problématique. Ce ne doit pas être un listing d'algorithmes. Le
plan proposé ici est autour des thèmes mathématiques. Il est possible d'en choisir un autre, à vous de
voir.
1. Arithmétique
3
, dont les dénominateurs sont entre 10000 et
4
20000 et qui sont des carrés parfaits. (programme en pièce jointe)
Exemple 1 : Lister toutes les fractions égales à
Exemple 2 : algorithme fournissant les facteurs premiers d'une entier supérieur à 1. (à faire)
Exemple 3 : Algorithme d'Euclide
Donner un algorithme qui permet de trouver le pgcd de deux nombres.
En langage naturel
entiers naturel a, b, r;
saisir a, b;
r = reste de la division euclidienne de a par b;
tant que (b > 0)
r = reste de la division euclidienne de a par b
a=b
b=r
fin tant que
afficher le pgcd : a;
Sur calculatrice
2. Fonctions :
Exemple 1 : Résolution approchée d'équation f ( x )=0 (Tle) par dichotomie (programme en pièce
jointe)
Soit f une fonction définie par f ( x )=x 3 + x−1 , x appartenant à ℝ.
1) Montrer que l'équation f (x )=0 admet une solution unique α sur ℝ.
2) Justifier le fait que 0 < α < 1.
3) On veut déterminer une valeur approchée de cette solution α avec une précision de 10-2.
Écrire un algorithme utilisant la méthode de dichotomie pour déterminer cette valeur approchée.
4) Modifier l'algorithme pour obtenir une valeur approchée de α à 10-4 près.
Intérêt de l'algorithmique ici :
- Permet de répondre aux questions 3 et 4. On pourrait en effet donner une valeur approchée de α
à l'aide d'une résolution graphique, mais la valeur approchée obtenue n'aurait pas la précision
demandée.
- Algorithme simple mais qui demande la maîtrise des boucles et des tests "si".
Exemple 2 : algorithme de résolution de ax² + bx + c = 0 (niveau 1ère) (à faire)
Exemple 3 : Approximation d'une intégrale
Soit E la partie du plan délimitée pas la courbe d'équation y=√ ( x) , l'axe des ordonnées et la
droite d'équation x=1 , dans le plan muni d'un repère orthogonal.
k
On divise [0,1] en n intervalles de même amplitude par les réels x k = , 0⩽k ⩽n .
n
Sur [ x k ; x k +1 ] , on construit les rectangles de hauteurs f (x k ) et f (x k +1) pour 0⩽k ⩽n−1 . On
nomme a n l'aire des rectangles contenus dans E et b n l'aire des rectangles "contenant" E, en unité
d'aire (u.a).
1. Exprimer aire(E) à l'aide d'une intégrale.
2. Écrire un algorithme qui demande n et affiche les mesures a n et b n en u.a.
3. Le programmer et donner l'encadrement obtenu pour n=25 .
Éléments de réponse :
1. La fonction racine carrée étant toujours positive, et étant continue : aire(E) =
2. et 3. Voir fichier algobox.
1
∫0 √ x
3. Problème de dénombrement
Exemple 1 : Le paradoxe du Duc de Toscane (2nde)
A la cour de Florence, de nombreux jeux de société étaient pratiqués. Parmi ceux-ci, l’un faisait
intervenir la somme des numéros sortis lors du lancer de trois dés. Le Duc de Toscane, qui avait
sans doute observé un grand nombre de parties de ce jeu, avait constaté que la somme 10 était
obtenue légèrement plus souvent que la somme 9.
Le paradoxe du Duc réside dans le fait qu’il y a autant de façons d’écrire 10 que 9 comme somme
de trois entiers compris entre 1 et 6 :
9=1+2+6=1+3+5=1+4+4=2+2+5=2+3+4=3+3+3
10 = 1 + 3 + 6 = 1 + 4 + 5 = 2 + 2 + 6 = 2 + 3 + 5 = 2 + 4 + 4 = 3 + 3 + 4
1. On se demande si le Duc de Toscane a raison de dire que le nombre 10 apparaît plus souvent
que le 9. A l'aide de Xcas, trouver un algorithme qui permette de simuler un nombre n de
lancers. Tester cet algorithme pour n = 10 000. L'observation du Duc de Toscane semble-telle se confirmer ?
2. Démontrer ce résultat en vous aidant des résultats trouvés par le Duc.
Exemple 2 : algorithme de calcul des bornes de l'intervalle de fluctuation au seuil de 95 % d'une
loi binomiale B(n;p). (à faire, voir leçon 12).
4. Les suites.
Exemple 1 : Soit une suite (un) définie par u0 = 0 et un+1 = 3un - 2n + 3
1) Montrer que pour tout n, un > n
2) En déduire le sens de variation et la limite de (un)
3) Créer un algorithme qui prend en entrée un nombre A strictement positif et qui donne en
sortie le rang de la suite le plus petit tel que un > A
 Algorithme permet de conjecturer le sens de variation de la suite
 Calcul du n° terme très rapidement
 Modification de l’algorithme pour répondre à la question 3
Exemple 2 : Algorithme de Héron (à faire)
5. Géométrie
Exemple 1 : algorithme de calcul des coordonnées de D tel que ABCD soit un parallélogramme
connaissant A, B et C. (à faire)
Exemple 2 : algorithme dessinant un polygone régulier à n sommets et de rayon r. (à faire)
6. Graphe
Algorithme de Dijkstra (à faire) ….

Download Report