Les algorithmes d'approximation
Chapitre7 : Les algorithmes d'approximation
Les algorithmes d'approximation
I- Prsentation
Un algorithme d'approximation permet de dterminer des valeurs
approches de la solution de certains problmes dont on ne peut pas
dterminer la valeur exacte de la solution.
Exemple: cas de calculer de la constant Pi
Un algorithme d'optimisation permet de trouver une solution
optimale (meilleur) un problme de minimisation ou de
maximisation.
Remarque :
Un algorithme d'approximation ne peut pas trouver une solution
optimale.
II- Problmes d'optimisation1. Activit: Soit un triangle
quilatral dont le cot mesure a en cm. On inscrit dans ce triangle
un rectangle MNPQ.
On pose BM=x
On se propose de dterminer la valeur de x tel que laire du
rectangle soit maximale.
2. Solution: SR = long * larg = MN * MQ = ((a-2x)*MQ
MQ =?
1er mthode
tg(angle MBQ)=tg(60)=QM/x= racine_carre(3)
QM=racine_carre(3) * x
Do S=racine_carre(3)*x * (a-2x)
( S=a*racine_carre(3)*x-2*racine_carre(3) * x
2me mthode
Sin 60 = /2
Sin 60= cot oppose / hypotinus = MQ/BQ ( MQ/BQ = /2 ( MQ = /2 *
BQ Thorme de TalasAQ/AB=AP/AC=QP/BC
AQ/a=(a-2x)/a
AQ=a-2x ( QB=a-(a-2x)=2x
( MQ = /2 * 2x = x
Conclusion : SR = (a-2x)*MQ= (a 2X) * xAnalyse de programme
principalRsultat = crire ("La valeur de x = ", Xmax, "donne une
surface = ",Smax)
Proc Recherche (a, pas, xmax, Smax)
a= donnePas = donneAlgorithme de programme principal0) Dbut
Calcul_surface1) Ecrire (" la longueur de cote ", a) Lire (a)
2) Ecrire (" la valeur de pas ", Pas) Lire (Pas)3) Proc
Recherche (a, pas, xmax, Smax)
4) crire ("La valeur de x = ", Xmax, "donne une surface =
",Smax)5) Fin Calcul_surface
Analyse de la procdure Recherche[X ( 0, Smax ( 0]
Rpter
X ( x + pas
S ( (a-2x)* x
Si S > Smax alors Smax ( S
Xmax ( X
Finsi
Jusqu (x > = a/2)
Algorithme de la procdure Recherche0) DEF PROC Recherche (a,
pas: rel; Var Xmax, Smax: rel)
1) X ( 0
2) Smax ( 03) Rpter
X ( x + pas
S ( (a-2x)* x
Si S > Smax alors Smax ( S
Xmax ( X
Finsi
Jusqu (x > = a/2)
4) Fin RechercheIII- Problmes d'optimisation1. Activit: Soit un
triangle ABC rectangle en A tel que AB = 3 cm et AC = 2 cm, on
place un point M sur le segment [AB] tel que AM = x.
N est la projection de M sur (BC) paralllement (AC)
P est la projection de N sur (AC) paralllement (AB)
B
MN
3 Cm
X
APC
2 Cm
On veut trouver la valeur (ou les valeurs) de x tel que AMNP ait
pour aire 1 Cm22. Solution: Pour rsoudre ce problme, on va suivre
la dmarche suivante :
Exprimer l'aire du rectangle AMNP en fonction de x,
Ecrire l'algorithme d'une fonction permettant de trouver les
valeurs de x qui donne une aire trs proche de 1 cm2.
Laire de rectangle AMNP = AM * AP
= x * AP (on pose AP =y)= x * y
Aire de triangle ABC = aire de triangle PCM + aire de triangle
MNB + aire de rectangle AMNP
= (PN * PC) + (MB * MN) + x * y= (x * (2 y)/2) + (y * (3 x) /2)
+ x * y
= x (x * y)/2 + 3/2 * y (x * y)/2 + x * y
= x + 3/2 * y
= 3
( y = 2 2/3 * xDo laire de rectangle AMNP = x * (2 2/3 * x) = 2
* x 2/3 x2 = 1
Analyse de programme principalRsultat = crire ("La meilleur
solution avec ce pas de variation est pour x = ", x, " laire = ",
A)
Proc recherche (P, x, A)P = donneAlgorithme de programme
principal0) Dbut Rectangle
1) Ecrire ("Donner la valeur du pas: ") Lire (P)2) Proc
recherche (P, x, A)
3) Ecrire ("La meilleur solution avec ce pas de variation est
pour X = ", X, "laire = ", A)
4) Fin Rectangle
Analyse de la procdure rechercheRsultat = [..] [x ( 0] Rpter
x ( x + PA ( 2 * x - 2/3 * x * xJusqu' (A >= 1)
Algorithme de la fonction valeur_x0) DEF proc recherche (P: rel;
var A, X: rel)1) x ( 02) Rpter
x ( x + PA ( 2 * x - 2/3 * x * xJusqu' (A >= 1)
3) Fin rechercheIV- ApplicationsApplication N1: Dans une feuille
de carton carre de 10 cm de cot, on dcoupe aux quatre coins quatre
carrs de cot X de telle faon quen relevant les quatre bords
restants, on obtienne une boite de forme paralllpipdique.
On veut trouver la valeur de X telle que le volume de la boite
ainsi forme soit maximum.
10 Cm
X
NB: Le volume du paralllpipdique = surface de base * hauteur=
(10 - 2 * X) * (10 - 2 * X) * XSolution : Analyse de programme
principalRsultat = Ecrire ("La meilleur solution avec ce pas de
variation est pour X = ", X, "le volume = ", V) Proc recherche (P,
X, V)
P = donne
Algorithme de programme principal
0) Dbut Volume_Max
1) Ecrire ("Donner la valeur du pas: "), Lire (P)
2) Proc recherche (P, X, V)3) Ecrire ("La meilleur solution avec
ce pas de variation est pour X = ", X, "le volume = ", V)
4) Fin Volume_Max
Analyse de procdure rechercheRsultat = [..]
[X ( 0, Vmax ( 0]
Rpter
X ( x + pas
V ( (10 2 * x) * (10 2 * x) * x
Si V > Vmax alors Vmax ( V Xmax ( X
Fin si Jusqu (x > = 5)
Algorithme de la procdure Recherche0) DEF PROC Recherche ( pas:
rel; Var Xmax, Vmax: rel)
1) X ( 0
2) Vmax ( 03) Rpter
X ( x + pas V ( (10 2 * x) * (10 2 * x) * x Si V > Vmax alors
Vmax ( V Xmax ( X
Finsi
Jusqu (x > = 5)
4) Fin RechercheProgramme Pascalprogram surface_maximale;
uses wincrt;
var p,xmax,smax:real;
procedure recherche (p:real; var xmax, smax:real);
var
x,s:real;
begin
x:=0;
s:=0;
repeatx:=x+p;
s:=s+sqr(10-2*x)*x;
if s>smax then
begin
smax:=s;
xmax:=x;
end;
until(x>=5/2);
end;
begin
write('saisir un entier '); read(p);
recherche(p,xmax,smax);
writeln('la valeur de x = ',xmax:10:6,' pour donner une surface
maximale = ',smax:10:6);
end.Application N2: Un disque de rayon R=5 cm est tangent deux
disques intrieurs tangents entre eux.
Les trois centres sont aligns. On veut dterminer la valeur du
rayon dun des deux disques intrieurs pour que laire comprise entre
le grand disque et les disques intrieurs soit maximum.
On se propose de dterminer une valeur approche du rayon.
R = r1 + r2 = 5 ( r2 = 5 r1
S = 25 - (r12 + (5-r1)2 )
S = 25 - r12 - (25 10 r1 + r12)
S = 25 - r12 - 25 + 10r1 r12
S=- 2 r12 + 10 r1 ( Variation de r1 ] 0 , r/2]
Algorithme de programme principal
0) Dbut Surface_vide1) Ecrire ("Introduire une valeur de
pas")
Lire (pas)
2) Proc recherche (pas, rmax, smax)
3) Ecrire ("Le rayon = ", rmax, " donne une surface vide =",
Smax)
4) Fin Surface_videAlgorithme de la procdure recherche
0) Procdure Calcul (pas: rel; Var rmax, smax: rel)
1) r1 ( 02) Smax ( 0
2) Rpter
r1 ( r1+ pas
S ( -2*Pi*r1*r1 + 10*Pi *r1
Si (S >Smax) Alors smax ( S
rmax ( r1
Finsi
Jusqu (r1 >= 2.5)
3) Fin CalculApplication N3:Soit C un cercle de rayon r=2cm.
On construit un rectangle ABCD inscrit dans C.
On veut trouver les dimensions du rectangle pour que son primtre
soit gal 5 cm.
Algorithme de programme principal0) Dbut dimension
1) Ecrire (" la valeur de pas ", Pas) Lire (Pas)
2) Proc Recherche (pas, xmax, Pmax)3) Ymax = 2- Xmax 4) crire
("La valeur de x = ", Xmax, ", la valeur de y = Ymax", donne un
primtre = ",Pmax)5) Fin Calcul_surface
Analyse de la procdure Recherche[X ( 0] Rpter
X ( x + pas
P ( 2*(x + )
Jusqu (P > = 5)Algorithme de la procdure Recherche0) DEF PROC
Recherche (pas: rel; Var x, P: rel)
1) X ( 0
2) Rpter
X ( x + pas
P ( 2*(x + )
Jusqu (P > = 5)
3) Fin RechercheProgramme Pascalprogram perimitre_maximale;
uses wincrt;
var p,x,s:real;
procedure recherche (p:real; var s,x:real);
begin
x:=0;
repeat
x:=x+p;
s:=s+2*x+sqrt(16-sqr(x));
until(s>=5);
end;
begin
write('saisir un entier '); read(p);
recherche(p,s,x);
writeln('la valeur de x = ',x:10:6,'la valeur de y =
',sqrt(16-sqr(x)):10:6);
write(' pour donner une surface maximale = ',s:10:6);
end.
r2
r1
R=5
S
T.D.O
ObjetsType / naturePmax, pas, xmax, Ymax
RechercheRel
procdure
y
x
r
T.D.O
ObjetTyper1, s relPi Constante = 3.14
T.D.O
ObjetTypePas, rmax, smax
rechercheRel
procdure
T.D.O
ObjetsType / natureX, SRel
T.D.O
ObjetsType/NatureP, X, V
rechercheRel
Procdure
A
C
B
Q
P
N
M
x
a
T.D.O
ObjetsType / naturea, pas, xmax, Smax
RechercheRel
procdure
T.D.O
ObjetsType / natureX, SRel
T.D.O
ObjetsType/NatureP, x, A
Valeur_xRel
Fonction
Page -6-
_1333652896.unknown
_1333895613.unknown
_1260109283.unknown
