corrigé ds 2 info ancien sup0001 .pdf


Nom original: corrigé ds 2 info ancien sup0001.pdf
Auteur: PB

Ce document au format PDF 1.4 a été généré par DPE Build 5072, et a été envoyé sur fichier-pdf.fr le 13/05/2013 à 23:02, depuis l'adresse IP 85.169.x.x. La présente page de téléchargement du fichier a été vue 413 fois.
Taille du document: 1.1 Mo (2 pages).
Confidentialité: fichier public


Aperçu du document


Option info/MPSI
1

Corrigé du OS du 15 février 20121

1

let

retourne t i=
let rec reto j k= match k-j with
p when p <1 -> ()
Ip -> let tampon = t.(k)
in t.(k)
reto (j+1) (k-1)
in reto i (n-1);;

Exercice

<- t. (j);

11

t.(j)

<- tampon;

3°)

n - i si cet entier est pair, n - i - 1 sinon.

4°)

En au plus deux retournements:

5°)

On cherche la plus grande rondelle, et on applique le principe ci-dessus à la partie concernée de la pile.

d'abord on met cette rondelle en haut, puis on retourne l'ensemble.

let

place t i=
let iO = ref i in
for j=i+1 to n-1 do
if t.(liO)
<t.~)
then iO:=j
retourne t liO ; retourne t i;;

let

7°)

tri

t = for

done;

i=O to n-2 do place

t i done;;

Chaque appel à place nécessite deux retournements. Au total, il faut 2n - 2 retournements.

1

Exercice 2

1°)

Il ya troi
. bri
,
L e couût est de '\'
rOISbouc 1es lm
nquees.
L..,O~i~j~n-l

2°)

On complète par
let

(J. - Z. + 1) -- '\'
L..,O~j~n-l

sUffi= ref 0 in
for j = i to n-l do
sum := Isum+t.(j);
-

2

Le coût est alors en ~ .

3°)

cumarr i est la somme des éléments du tableau entre 0 et i - l.
Il faut donc compléter par
let

sum = cumarr.(j+l)-cumarr.
,

2

Le cout est encore en ~ .

(i)

in

1

j(Hl)
2

3

rv

n


a) On complète par
let

k -> let

s = supg t. (i+l)

j in max 0

(t . (i)+s)

rec supd t i j = match j-i with
1 -> max 0 t. (i)
Ik -> let s = supd t i (j-l)
+ (max 0 s)

b) On complète par
1

1-

o t. (i)
k= (i+j)/2
in
let sg = supg t k j and sd
supd i k in
let g = maxconsprov i k and d = maxconsprov k j in
max (max g d ) (sg + sd) in

-> max
-> let

c) On aurait pu envisager d'ajouter le cas de base 0 -> 0, mais si le tableau est non vide, et
donc ce cas ne servirait jamais.

J -i > 1, on ai < k < J,

d) Comme supg et supd sont de coût linéaire, on a
C(n)
donc C(n)
5°)

=

2C(n/2)

+ O(n)

= 8(nlogn).

On complète par
maxendinghere

:= max (!maxendinghere

+ t. (i))

1

let

0;

Exercice 3

1

rec selection
l i=
let u,v = decoupe l (hd 1) in (*la tete sert de pivot*)
let k= list_length
u in (* le nb d'éléments
< hd 1*)
match i ",ith
Ii when i=k -> hd l (*l'élément
cherché est le pivot*)
Ii ",hen i<k -> selection
u i (*l'élément
cherché est dans u*)
Ii -> selection
v (i-k-l);;
(*il est dans v*)

2°)

selection fonctionne (et notamment termine) quand la liste est de longueur l et i = 0, car alors k = O.
Si i = k, l'élément cherché est le pivot, puisqu'il y en a exactement k plus petits que lui.
Si i < k, il est dans u et toujours en i-ème position.
Si i > k" il est dans v en i - k - l-ième position, puisque les k éléments de u et le pivot ont disparu.
De plus à chaque appel de selection,
la liste est strictement plus courte, on arrive donc au cas de base.

3°)

Coût moyen: T(n) = T(n/2) + O(n), donc T(n) = O(n).
Le tri rapide donnait T(n) = 2T(n/2) + O(n), car il fallait traiter les deux moitiés; ici on ne s'occupe que d'une seule.
Le pire des cas se produit pour une liste décroissante et dans ce cas le coût vérifie T(n) = T(n - 1) + O(n), soit
T(n) = O(n2).


corrigé ds 2 info ancien sup0001.pdf - page 1/2
corrigé ds 2 info ancien sup0001.pdf - page 2/2

Télécharger le fichier (PDF)










Documents similaires


collection1 corrige
programmationavanceeserie1
dossier pai
candidature pole bmx bourges 2018
corrige ds 2 info ancien sup0001
prezi css documentation

Sur le même sujet..