Revenir
Revenir

Algorithme et programmation

Résoudre le problème accessible via le lien suivant :https://castor-informatique.fr/questions/2014/2...

Sommaire

Pour commencer...Activité CAPYTALE : dichotomieAttraper le monstreLiens utilesPrincipe
Étude de l'algorithmeAlgorithme « à la main »Nombre d'itérations
ImplémentationRésolution approchée de f(x)=0Résolution approchée de f(x)=kAdapter l'algorithme
Les perles du BACCentres étrangers, 2023, sujet 1Amérique du Sud, septembre 2023

Pour commencer...

Activité CAPYTALE : dichotomie

Attraper le monstre

Résoudre le problème accessible via le lien suivant :https://castor-informatique.fr/questions/2014/2014-FR-03-monster/index.html?options=%7B%22difficulty%22%3A%22hard%22%7D
Quelle méthode peut-on employer pour résoudre ce problème de manière optimale ?

Liens utiles

https://castor-informatique.fr/questions/2014/2014-FR-03-monster/index.html?options=%7B%22difficulty%22%3A%22hard%22%7D

https://castor-informatique.fr/questions/2014/2014-FR-03-monster/index.html?options=%7B%22difficulty%22%3A%22hard%22%7D

Principe

Pour résoudre le problème précédent, une technique consister à placer un barrage sur la cellule du milieu pour ainsi diviser la zone de recherche en deux. Suivant l'endroit où se trouvait le monstre, on plaçait alors le barrage suivant au milieu de la zone du haut ou du bas, et ainsi de suite.
Cette méthode intuitive peut également être utilisée pour rechercher la valeur approchée d'une solution de certaines équations sur un intervalle.
L'algorithme de dichotomie est un algorithme permettant de déterminer une valeur approchée d'une solution d'une équation du type 
f(x)=0
en divisant l'intervalle de recherche par 2 à chaque itération.
Soit 
f
une fonction définie et continue sur un intervalle
[a;b]
. On suppose que 
f(a)
et 
f(b)
sont de signe contraire. Le théorème des valeurs intermédiaires assure alors de l'existence d'une solution à l'équation 
f(x)=0
sur l'intervalle 
[a;b]
.
On considère alors
m=a+b2m=\dfrac{a+b}{2}m=2a+b​
. Deux cas de figure se présentent :
    • soit
f(a)f(a)f(a)
 et
f(m)f(m)f(m)
 sont de signes contraires. Dans ce cas, l'équation 
f(x)=0f(x)=0f(x)=0
admet une solution sur l'intervalle
[a;m][a;m][a;m]
 ;
    • soit 
f(b)f(b)f(b)
et 
f(m)f(m)f(m)
sont de signes contraires. Dans ce cas, l'équation
f(x)=0f(x)=0f(x)=0
 admet une solution sur l'intervalle 
[m;b][m;b][m;b]
.
On réitère alors le procédé en se plaçant sur l'intervalle 
[a;m][a;m][a;m]
ou
[m;b][m;b][m;b]
, selon le cas de figure.
Cette opération est alors répétée jusqu'à atteindre la précision désirée.

Étude de l'algorithme

Algorithme « à la main »

Exercice
On considère la fonction 
fff
définie pour tout réel 
xxx
par
f(x)=x3−3x+1f(x)=x^3-3x+1f(x)=x3−3x+1
.
1.Compléter la fonction ci-dessous permettant de calculer l'image d'un réel 
xxx
par la fonction
fff
. On rappelle qu'en Python, la puissance s'écrit à l'aide des symboles **.
def f(x):
    return ...
2.À l'aide de cette fonction, calculer 
f(1)f(1)f(1)
et
f(2)f(2)f(2)
.
3.Justifier l'existence d'une solution à l'équation
f(x)=0f(x)=0f(x)=0
 sur l'intervalle
[1;2][1;2][1;2]
.
4.Calculer alors
f(1,5)f(1,5)f(1,5)
. Sur quel intervalle l'équation 
f(x)=0f(x)=0f(x)=0
a-t-elle forcément une solution ?
5.Déterminer un intervalle d'amplitude 0,25 sur lequel l'équation 
f(x)=0f(x)=0f(x)=0
admet une solution.
Remarque
L'application de cette méthode peut sembler laborieuse au premier abord, les nombres obtenus lors des différentes itérations étant relativement complexes. Toutefois, pour un ordinateur, la division par 2 est aussi simple que la division par 10 pour un humain : il s'agit donc d'une opération très rapide à mettre en place.

Nombre d'itérations

Exercice
On s'intéresse désormais au nombre d'itérations à effectuer pour obtenir un intervalle d'amplitude désirée.
1.Justifier qu'après 
nnn
itérations, l'amplitude de l'intervalle de recherche d'une solution est de 
b−a2n\dfrac{b-a}{2^n}2nb−a​
.
2.Soit 
ppp
un entier naturel. Déterminer l'entier 
nnn
à partir duquel on a 
b−a2n⩽10−p\dfrac{b-a}{2^n} \leqslant 10^{-p}2nb−a​⩽10−p
.
3.En déduire le nombre d'itérations à effectuer si l'on cherche une valeur approchée à
10−310^{-3}10−3
près d'une solution de l'équation
f(x)=0f(x)=0f(x)=0
 sur l'intervalle
[1;2][1;2][1;2]
.

Implémentation

Résolution approchée de f(x)=0

Le principe de l'algorithme est donc le suivant.
Entrées
    • Une fonction 
fff
dont on cherche une valeur approchée d'une solution de l'équation 
f(x)=0f(x)=0f(x)=0
sur un intervalle.
    • Un réel
aaa
, borne inférieure de l'intervalle de recherche de la solution.
    • Un réel
bbb
, borne supérieure de l'intervalle de recherche de la solution.
    • Un entier naturel 
ppp
qui détermine la précision voulue (
10−p10^{-p}10−p
).
Sortie
Un intervalle d'amplitude inférieure à 
10−p10^{-p}10−p
comprenant une solution à l'équation
f(x)=0f(x)=0f(x)=0
.
Algorithme
Tant que 
b−ab-ab−a
est supérieur ou égale à 
10−p10^{-p}10−p
 :
    • on assigne à une variable 
mmm
la valeur 
b−a2\dfrac{b-a}{2}2b−a​
 ;
    • si 
f(a)f(a)f(a)
et 
f(m)f(m)f(m)
sont de même signe : on assigne à la variable 
aaa
la valeur de 
mmm
 ;
    • sinon, on assigne à la variable 
bbb
la valeur de 
mmm
.
On renvoie finalement les valeurs de 
aaa
 et 
bbb
.
Exercice
Compléter la fonction dicho ci-dessous en vous aidant du pseudo-algorithme ci-dessus pour que celle-ci permette d'obtenir une valeur approchée à 
10−p10^{-p}10−p
d'une solution de l'équation
f(x)=0f(x)=0f(x)=0
sur l'intervalle
[a;b][a;b][a;b]
.
À l'aide de cette fonction, déterminer une valeur approchée à
10−310^{-3}10−3
 près d'une solution de l'équation
x3−3x+1=0x^3-3x+1=0x3−3x+1=0
 sur l'intervalle
[1;2][1;2][1;2]
.
def f(x):
    return ...
def dicho(f, a, b, p):
    while b-a ...
        m = ...
        if ... :
            a = ...
        else :
            ...
    return a, b

Résolution approchée de f(x)=k

L'algorithme précédent permet de donner une valeur approchée d'une solution aux équations du type
f(x)=0f(x)=0f(x)=0
.
Toutefois, le même algorithme permet de donner une valeur approchée d’une solution aux équations du type 
f(x)=kf(x)=kf(x)=k
où 
kkk
est un réel. En effet, il suffit de dire qu'on a 
f(x)=kf(x)=kf(x)=k
si et seulement si 
f(x)−k=0f(x)-k=0f(x)−k=0
et l'on se ramène ainsi au cas précédent.
Exercice 
On considère la fonction
f:x↦(1−x)exf:x\mapsto (1-x)e^xf:x↦(1−x)ex
.
1.Calculer 
f(−3)f(-3)f(−3)
et 
f(0)f(0)f(0)
.
2.En déduire que l'équation 
f(x)=0,5f(x)=0,5f(x)=0,5
admet une solution sur l'intervalle
[−3;0][-3;0][−3;0]
.
3.À l'aide de l'algorithme de dichotomie, déterminer une valeur approchée à 
10−210^{-2}10−2
près d'une telle solution.
#Pour utiliser la fonction exponentielle
from math import exp
def g(x) :
    # Pour calculer la valeur de f(x)-0,5
    return ...
...

Adapter l'algorithme

Il existe de nombreuses manières d'implémenter l'algorithme de dichotomie, selon les informations que l'on peut avoir sur la fonction. 
Le principe reste toujours le même : on calcule la valeur de la fonction au milieu de l'intervalle de recherche, puis on compare avec la valeur de la fonction aux bornes de l'intervalle. On remplace alors une de ces bornes par la valeur milieu.
Ainsi, dans l'algorithme général de la dichotomie, on regarde si
f(a)f(a)f(a)
 et 
f(m)f(m)f(m)
 sont du même signe. 
Or, dans l'exemple précédent, on a une information supplémentaire : on sait que
f(a)<0f(a)<0f(a)<0
. Ainsi,dans cette situation, dire que 
f(a)f(a)f(a)
et 
f(m)f(m)f(m)
sont de même signe est équivalent à dire que 
f(m)f(m)f(m)
est également strictement négatif. Il suffit donc, dans ce cas, de calculer
f(m)f(m)f(m)
et de regarder son signe.
Notre algorithme de dichotomie peut alors s'écrire de la manière suivante.
def f(x):
    return x**3 - 3*x + 1
def dicho(f, a, b, p):
    while b - a > 10 ** (-p):
        m = (a+b)/2
        if f(m) < 0:
            a = m
        else :
            b = m
    return a, b
dicho(f,1,2,3)
L'algorithme est en tout point identique, mise à part la condition indiquée dans leif.
Cette condition peut être adaptée selon les informations qu'on a à disposition sur la fonction 
fff
étudiée.
Par ailleurs, selon ce que l'on souhaite, on pourra renvoyer seulement la valeur de
aaa
, de 
bbb
ou la dernière valeur de
mmm
, plutôt que d'avoir l'intervalle final.

Les perles du BAC

Centres étrangers, 2023, sujet 1

Soit deux réels 
aaa
et 
bbb
avec
a<ba<ba<b
#Proposition a
def racine(a,b) :
    while abs(b − a) >= 0.001 :
        m = (a +b)/2
        if f (m) < 0 :
            b = m
        else :
            a = m
    return m
# Proposition b
def racine(a,b) :
    m = (a +b)/2
    while abs(b − a) <= 0.001 :
        if f (m) < 0 :
            a = m
        else :
            b = m
    return m
# Proposition c
def racine(a,b) :
    m = (a +b)/2
    while abs(b − a) >= 0.001 :
        if f (m) < 0 :
            a = m
        else :
            b = m
    return m
#Proposition d
def racine (a,b) :
    while abs (b − a) >= 0.001 :
    m = (a +b)/2
        if f (m) < 0 :
            a = m
        else :
            b = m
    return m

Amérique du Sud, septembre 2023

On admet que l'équation
1+x2−2x2ln⁡(x)=01+x^2-2x^2\ln(x)=01+x2−2x2ln(x)=0
 admet une unique solution 
α\alphaα
dans l'intervalle
[1;+∞[[1;+\infty[[1;+∞[
 et que
α∈[1;e]\alpha \in [1;\text e]α∈[1;e]
.
On donne la fonction ci-dessous écrite en Python. L’instruction from lycee import * permet d’accéder à la fonction ln.
from math import log as ln
def f(x) :
    return 1+x**2-2*x**2*ln(x)
def dichotomie(p) :
    a=1
    b=2.7
    while b-a > 10**(-p) :
        if f(a)*f((a+b)/2) < 0 :
            b = (a+b)/2
        else :
            a=(a+b)/2
    return (a,b)
On écrit dans la console d’exécution :
> dichotomie(1)
Parmi les quatre propositions ci-dessous, recopier celle affichée par l’instruction précédente. Justifier la réponse (on pourra procéder par élimination)
  • Proposition A : (1.75, 1.9031250000000002)
  • Proposition B : (1.85, 1.9031250000000002)
  • Proposition C : (2.75, 2.9031250000000002)
  • Proposition D : (2.85, 2.9031250000000002)