Tutorat en bio-informatique Le 21 novembre 2012. Exercices 2 et 3 (MAT1400) - solutions Chapitre 11.7, Analyse - concepts et contextes vol. 2 27) Cherchez

Tutorat en bio-informatique

Le 21 novembre 2012

Exercices 2 et 3 (MAT1400) - solutions

Chapitre 11.7, Analyse - concepts et contextes vol. 2

27) Cherchez le maximum et le minimum absolu de f sur l'ensemble D.

, D est la région bornée par la parabole

et la droite .

yxxyyxf 1),(2xy 4y





et la droite .

yxxyyxf 1),(2xy 4y

y = 4

y = x2

01'

01'

xf

yf

y

x





et la droite .

yxxyyxf 1),(2xy 4y

y = 4

y = x2

01'

01'

xf

yf

y

x (1,1) 0)1,1( f





et la droite .

yxxyyxf 1),(2xy 4y

y = 4

y = x2

01'

01'

xf

yf

y

x (1,1) 0)1,1( f

1)0,0( f





et la droite .

yxxyyxf 1),(2xy 4y

y = 4

y = x2

01'

01'

xf

yf

y

x (1,1) 0)1,1( f

1)0,0( f

94281)4,2( f





et la droite .

yxxyyxf 1),(2xy 4y

y = 4

y = x2

01'

01'

xf

yf

y

x (1,1) 0)1,1( f

1)0,0( f

94281)4,2( f34281)4,2( f





et la droite .

yxxyyxf 1),(2xy 4y

y = 4

y = x2

01'

01'

xf

yf

y

x (1,1) 0)1,1( f

1)0,0( f

94281)4,2( f34281)4,2( f

minimum

maximum



35) Déterminez trois nombres positifs dont la somme vaut 100 et dont le produit est maximum.

xyzzyxf

zyx

),,(

100




xyzzyxf

zyx

),,(

100

22100),(

)100(),(

100

xyyxxyyxf

yxxyyxf

yxz




xyzzyxf

zyx

),,(

100

22100),(

)100(),(

100

xyyxxyyxf

yxxyyxf

yxz

xyxxf

yyxyf

y

x

2100'

2100'2

2




xyzzyxf

zyx

),,(

100

22100),(

)100(),(

100

xyyxxyyxf

yxxyyxf

yxz

xyxxf

yyxyf

y

x

2100'

2100'2

2

22 21002100

0''

xxyxyxyy

ff yx




xyzzyxf

zyx

),,(

100

22100),(

)100(),(

100

xyyxxyyxf

yxxyyxf

yxz

xyxxf

yyxyf

y

x

2100'

2100'2

2

22 21002100

0''

xxyxyxyy

ff yx

Posons x = y dans l'une ou l'autre des dérivées.




yx

x

xx

xxf

xxxxyxxf

y

y

3/100

3100

3100

03100'

21002100'

2

2

222





yx

x

xx

xxf

xxxxyxxf

y

y

3/100

3100

3100

03100'

21002100'

2

2

222


3/1003/200100

100

z

yxz

Au programme…

• Algorithmes de recherche dans un tableau

• Algorithmes de tri dans un tableau

Algorithmes

• Qu'est-ce qu'un algorithme?

C'est un processus logique permettant la résolution d'un problème en programmation.

www.le-dictionnaire.com

Algorithmes

• On analyse la performance d'un algorithme en évaluant son temps d'exécution dans le pire cas.

• En effet, le meilleur cas ne se produit presque jamais dans la réalité, donc il n'est pas intéressant.

• Le cas moyen est souvent le plus difficile à calculer et il peut être peu représentatif du pire cas.

• L'analyse du temps d'exécution dans le pire cas nous donne la garantie que l'algorithme ne pourra être plus lent peu importe ce qu'on lui donne en entrée.

Algorithmes

• Soit T(n), la fonction qui définie les opérations effectuées par l'algorithme sur n, le nombre d'entrées. On dira que :

T(n) = O( f(n) ) si pour des constantes positives c et n0, on a T(n) <= cf(n) quand n >= n0

f(n) Temps

c constant

logn logarithmique

n linéaire

nlogn nlogn

n2 quadratique

n3 cubique

2n exponentiel

n! factoriel

Recherche dans un tableau non trié

• On doit parcourir toutes les positions du tableau jusqu'à ce qu'on trouve l'élément recherché (recherche directe)

function rechercheDirecte(tab, element){

for (var i = 0; i < tab.length; i++){

if (tab[i] == element){

return i;}

}return -1;

}

Pire cas :

temps linéaire ( O (n) )

Recherche dans un tableau trié• On peut parcourir toutes les positions du tableau jusqu'à

ce qu'on trouve l'élément recherché ou qu'on dépasse la valeur de l'élément recherché (recherche linéaire).

function rechercheLineaire(tab, element)

{

for (var i = 0; i < tab.length; i++)

{

if (tab[i] == element)

return i;

else if (tab[i] > element)

return -1;

}

return -1;

}

Pire cas :

temps linéaire ( O (n) )

Recherche dans un tableau trié• On peut faire une recherche binaire

function rechercheBinaire(tab, element){

var gauche = 0;var droite = tab.length - 1;while (gauche <= droite){

var centre = Math.floor((gauche + droite) / 2);if (tab[centre] == element)

return centre;else if (tab[centre] > element)

droite = centre - 1;else

gauche = centre + 1;}return -1;

}

Recherche dans un tableau trié• On peut faire une recherche binaire

function rechercheBinaire(tab, element){

var gauche = 0;var droite = tab.length - 1;while (gauche <= droite){

var centre = Math.floor((droite – gauche) / 2) + gauche;if (tab[centre] == element)

return centre;else if (tab[centre] > element)

droite = centre - 1;else

gauche = centre + 1;}return -1;

}

Pire cas :

dans O (log n)

Algorithmes de tri

• La meilleure façon de trier un tableau est de séparer notre tableau en deux parties : une partie triée et une partie non triée

• Il n'y aurait aucun avantage à créer un deuxième tableau : cela nécessiterait plus d'espace et plus d'opérations

Tri par sélectionfunction triSelection(tab){

for (var i = 0; i < tab.length-1; i++){

var posMin = i;for (var j = i + 1; j < tab.length; j++){

if (tab[j] < tab[posMin]){

posMin = j;}

}if (posMin != i){

var temp = tab[i];tab[i] = tab[posMin];tab[posMin] = temp;

}}

}

O(n2) dans tous les cas

Tri par insertion

function triInsertion(tab){

for (var i = 1; i < tab.length; i++){

var aPlacer = tab[i];

var j = i - 1; while (j >= 0 && tab[j] > aPlacer) {

tab[j+1] = tab[j];j--;

}

tab[j+1] = aPlacer;}

}

Ici, on peut faire mieux qu'avec le tri par sélection. Dans le meilleur cas (un tableau déjà trié), le tri par insertion prend un temps linéaire.

Toutefois, dans le pire cas (tableau trié en ordre décroissant), cet algorithme prendra aussi un temps quadratique.

Tri bullefunction triBulle(tab){

do{var inversionFaite = false;for(var i = 0; i < tab.length-1; i++){

if(tab[i] > tab[i+1]) {

var temp = tab[i+1];tab[i+1] = tab[i];tab[i] = temp;inversionFaite = true;

}}

} while(inversionFaite);}

Comme pour le tri insertion, dans le meilleur cas (un tableau déjà trié), le tri bulle prend un temps linéaire.

Toutefois, dans le pire cas (???), cet algorithme prendra aussi un temps quadratique.

Tri bullefunction triBulle(tab){

do{var inversionFaite = false;for(var i = 0; i < tab.length-1; i++){

if(tab[i] > tab[i+1]) {

var temp = tab[i+1];tab[i+1] = tab[i];tab[i] = temp;inversionFaite = true;

}}

} while(inversionFaite);}

Comme pour le tri insertion, dans le meilleur cas (un tableau déjà trié), le tri bulle prend un temps linéaire.

Toutefois, dans le pire cas (plus petit élément en dernière position), cet algorithme prendra aussi un temps quadratique.

Exercices (MAT1400)


19) Calculez le volume du solide dressé sur le rectangle

R = [-1, 1] x [-2, 2] et coiffé par le paraboloïde elliptique

.

23) Calculez le volume du solide du premier quadrant compris dans le cylindre et le plan x = 2.

19/4/ 22 zyx

29 yz

Référence

• Weiss, MA (2007). Data Structures and Algorithm Analysis in Java. Second Edition. Pearson Education, Boston, 555 pages.

Documents

Tutorat en bio-informatique Le 21 novembre 2012. Exercices 2 et 3 (MAT1400) - solutions Chapitre 11.7, Analyse - concepts et contextes vol. 2 27) Cherchez