Centrale Option Informatique MP 2016Sujet, corrigé et rapport du jury

Pas encore noté

Structures de données (listes, arbres, tas binaires)
Algorithmique du tri
Analyse de la complexité
Programmation récursive en Caml

Explorer les annales

BanqueCentrale Année2016 FilièreMP MatièreInformatique

Annales Centrale MP Informatique Centrale MP 2016 MP Informatique Informatique 2016

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Corrigé 2

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Difficulté moyenne

Étude d'un algorithme de tri performant sur des listes presque triées, à base de tas binaires

Le sujet étudie un algorithme de tri dont l'intérêt est d'avoir une bonne complexité lorsque la liste à trier est presque triée. Sa mise en œuvre s'appuie sur la manipulation d'arbres, de listes et de tableaux, avec plusieurs études de complexité. Le problème présente d'abord des algorithmes sur les listes et les arbres (tas binaires, décomposition parfaite d'un entier, création d'une liste de tas, tri des racines, extraction), puis une implantation en place dans un tableau pour réduire la complexité spatiale.

1I. PrésentationPrésenter les motivations du problème, les notations et les préliminaires nécessaires.
2II. Algorithme sur des arbresÉtudier le tri par insertion, les tas binaires, la décomposition parfaite d'un entier, la création d'une liste de tas, le tri des racines et l'extraction des éléments.
3III. Implantation dans un tableauReprendre l'algorithme en réduisant la complexité spatiale à l'aide d'un tri en place dans un tableau.

Difficulté moyenne. Le rapport indique que le sujet a été correctement compris, qu'un nombre significatif de candidats a pu le traiter dans son ensemble et que le niveau global des candidats est satisfaisant, avec une fraction notable de copies tout à fait excellentes.

Ce qu'a observé le jury

5 erreurs relevées

Parcours de liste inutiles nuisant à la complexité · Confusion entre types construits · Incohérence entre algorithme décrit, code Caml et résultat sur exemples

Le sujet, raisonnablement progressif et de longueur volontairement raisonnable, a été correctement compris par les candidats. Le caractère progressif de la mise en œuvre de l'algorithme a permis d'éviter les blocages et les signatures des fonctions Caml imposées ont été bien respectées. Le niveau moyen est satisfaisant, même si des difficultés persistent sur l'usage des types construits et la justification des calculs de complexité.

Les erreurs les plus sanctionnées

1
Parcours de liste inutiles nuisant à la complexité
Pour que les complexités soient correctes, il ne fallait pas introduire de parcours de liste inutile, comme compter le nombre d'éléments simplement pour tester l'égalité de ses deux premiers éléments.
2
Confusion entre types construits
Le jury observe de grandes difficultés dans l'usage des types construits : affectations incorrectes, confusion entre la déclaration de type Vide de l'arbre et la liste vide [].
« confusion entre la déclaration de type Vide de l'arbre et la liste vide »
3
Incohérence entre algorithme décrit, code Caml et résultat sur exemples
De nombreux candidats traitent la description d'un algorithme, sa transcription en Caml et son résultat sur des exemples de façon totalement indépendante, avec des solutions différentes pour chacun.
4
Percolation inutile de tous les tas
Dans le tri des racines, beaucoup de candidats cherchent à percoler tous les tas alors que l'objectif est d'obtenir une bonne complexité globale sans tout reconstruire.
5
Récursivité terminale mal gérée
L'usage systématique et mal géré de la récursivité terminale a conduit certains candidats à obtenir des listes à l'envers, empêchant l'algorithme de fonctionner correctement.

Ce qui a été bien réussi

Les signatures des fonctions Caml imposées ont été bien respectées par les candidats.
La partie sur l'extraction des éléments, qui produit la liste triée, a été globalement bien comprise par les candidats qui l'ont abordée.
Une fraction notable des candidats a rendu des copies tout à fait excellentes, avec des codes élégants et clairs.

Conseils du jury

Vérifier la cohérence globale entre les différentes fonctions programmées, notamment lorsqu'un cas particulier n'est volontairement pas traité dans l'une d'elles.
Prendre le recul nécessaire pour comprendre l'objectif de complexité visé avant d'implémenter chaque étape de l'algorithme.
Écrire des codes clairs et commentés, en réutilisant les éléments précédemment définis plutôt qu'en multipliant les fonctions auxiliaires.
S'exercer à la pratique sur machine pour s'approprier les réflexes de programmation et écrire des programmes lisibles sans l'aide d'un compilateur.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

Un algorithme de tri

I Présentation

I.A - Motivation

Trier des données est un problème récurrent dans tous les systèmes d'information. Dans un système travaillant en temps réel (par exemple un système de freinage d'une voiture) ou un système pouvant être soumis à des attaques (par exemple un serveur web), on s'intéresse à la complexité dans le pire des cas.
Or, dans une application réelle, les données que l'on veut trier ne sont pas quelconques mais suivent une certaine distribution aléatoire, qui est loin d'être uniforme : ainsi, il est fréquent que les données soient déjà presque triées. De plus, de nombreux algorithmes de tris (même les plus performants) atteignent leur complexité maximale lorsque les données sont déjà triées.
Le but de ce problème est d'étudier un algorithme de tri, proche du tri par tas mais présentant avec lui quelques différences significatives et notamment des performances intéressantes lorsque les données qu'il reçoit sont presque triées.
Dans tout le problème, on triera, par ordre croissant, des valeurs entières.
Dans toutes les questions de complexité en temps, la mesure de complexité à considérer est le nombre de comparaisons par la relation d'ordre

⩽

entre entiers.

I.B - Notations et préliminaires

Dans la suite, si un objet mathématique est noté

t

, on notera t l'objet Caml qui l'implante et, si

t

appartient à un ensemble

T

implanté en Caml par le type T , on écrira de manière équivalente

t \in T

t : T

. Par exemple, pour signifier que

l

désigne une liste d'entiers, on notera

l

: int list.
Étant donné deux fonctions

f

g

à valeurs positives, on note :

$f = O(g)$ pour exprimer qu'il existe une constante $C$ telle que, pour tout $n$ suffisamment grand, $f(n) ⩽ Cg(n)$ ;
$f = Ω(g)$ pour exprimer qu'il existe une constante $C > 0$ telle que pour, tout $n$ suffisamment grand, $f(n) ⩾ Cg(n)$ ;
$f = Θ(g)$ pour exprimer qu'on a $f = O(g)$ et $f = Ω(g)$ .

On tiendra compte dans la suite que la structure à trier n'est pas un ensemble, car le même élément peut être répété plusieurs fois. Ainsi on sera amené à manipuler en Caml des listes ou des vecteurs dans lesquels un même élément peut apparaitre plusieurs fois, et des arbres dans lesquels la même valeur peut étiqueter plusieurs sommets différents. Dans la suite, lorsqu'il s'agira de déterminer le minimum d'une telle structure, il pourra être atteint plusieurs fois ; de même, lorsqu'on triera ou « réunira » deux telles structures, ce sera toujours en tenant compte des répétitions, c'est-à-dire sans perte d'éléments. Ainsi, par exemple, pour les listes

l_1 = (7, 4, 2, 8, 2, 7, 3)

l_2 = (5, 2, 3, 9)

, le minimum de

l_1

est 2 , trier

l_1

consiste à renvoyer la liste

[2; 2; 3; 4; 7; 7; 8]

et «réunir»

l_1

l_2

consiste à renvoyer la liste

[7; 4; 2; 8; 2; 7; 3; 5; 2; 3; 9]

.
De manière générale, lorsqu'on dira que deux structures de données contiennent les mêmes éléments, ce sera toujours en tenant compte des répétitions. Par exemple les listes

[1; 2; 2]

[2; 1; 2]

contiennent les mêmes éléments mais pas les listes

[3; 4; 4]

[4; 3; 3]

II Algorithme sur des arbres

II.A - Tri par insertion

II.A.1) Écrire la fonction insere : int

\to

int list

\to

int list insérant un élément dans une liste supposée triée, c'est-à-dire telle que pour toute liste u supposée triée et tout élément x , (insere x u) renvoie une liste v telle que

v contient les mêmes éléments que $x : u$ ;
v est triée.
II.A.2) Écrire la fonction tri_insertion : int list $\to$ int list triant la liste reçue en argument en utilisant la fonction précédente.
II.A.3) Pour $n \in ℕ$ , on note $P_I(n)$ le nombre de comparaisons effectuées par l'appel (tri_insertion l) dans le cas le pire pour une liste 1 de longueur $n$ . On note de même $M_I(n)$ le nombre de comparaisons effectuées dans le cas le meilleur.
Déterminer $P_I(n)$ et $M_I(n)$ .

II.B - Tas binaires

On appelle arbre un arbre binaire étiqueté par des éléments de

ℕ

. Un tel arbre est implanté en Caml à l'aide de la déclaration de type suivante:

type arbre =
    | Vide
    | Noeud of int * arbre * arbre ;;

On définit la hauteur et la taille (appelée aussi nombre d'éléments) d'un arbre

a

, notées respectivement haut(a) et

|a|

par induction sur la structure de l'arbre:

- haut(Vide) = 0

et haut(Noeud(x,a1,a2))=1+max{haut(a1),haut(a2)}

- |

Vide

|=0

|

Noeud

(x, a1, a2)| = 1 + |a1| + |a2|

pour tous arbres binaires a1 et a2 et tout entier x .
x , a1 et a2 sont appelés respectivement la racine, le fils gauche et le fils droit de l'arbre a.
On dit que deux arbres ont mêmes éléments s'ils ont les mêmes ensembles d'étiquettes et que chaque étiquette présente apparait le même nombre de fois dans chacun des arbres.
On dit qu'un arbre binaire est parfait s'il s'agit de l'arbre vide Vide, ou s'il est de la forme Noeud(

x, a1, a2

) où a1 et a2 sont deux arbres parfaits de même hauteur.
On dit qu'un arbre binaire est un tas binaire parfait (ou simplement un tas parfait) si c'est un arbre parfait et que la valeur étiquetant chaque nœud de l'arbre est inférieure ou égale à celle de ses fils.
On dit qu'un arbre binaire est un quasi-tas si c'est un arbre de la forme Noeud(x,a1,a2) et que a1 et a2 sont des tas binaires parfaits de même taille : aucune contrainte d'ordre n'est donc imposée sur l'étiquette de la racine x . Étant donné un arbre non vide

a

, on note

min_A(a)

le minimum des éléments qu'il contient.
II.B.1) Pour

k \in ℕ

, on note

m_k

la taille d'un arbre binaire parfait de hauteur

k

. Déterminer

m_k

pour tout

k \in ℕ

. On justifiera la réponse en exprimant

m_(k + 1)

en fonction de

m_k

.
II.B.2) Écrire la fonction min_tas: arbre

\to

int telle que pour tout tas binaire parfait a non vide, (min_tas a) renvoie

min_A(a)

. On fera en sorte que la complexité en temps de min_tas soit constante.
II.B.3) Écrire la fonction min_quasi: arbre

\to

int tel que pour tout quasi-tas a, (min_quasi a) renvoie

min_A(a)

en temps constant.
II.B.4) Écrire la fonction percole: arbre -> arbre telle que (percole a) renvoie a si a est l'arbre vide et, si a est un quasi-tas, renvoie un tas binaire parfait contenant les mêmes éléments. Donner la complexité de percole dans le cas le pire, en fonction de la hauteur

k

du quasi-tas a.

II.C - Décomposition parfaite d'un entier

L'algorithme de tri que l'on va étudier repose sur une propriété remarquable des nombres

m_k

obtenus à la question II.B.1.
Étant donné un entier naturel

r

, on dit qu'un

r

-uplet (

k_1, \dots, k_r

) d'entiers naturels non-nuls vérifie la propriété QSC (pour «quasi strictement croissant») si l'une des trois conditions suivantes est vérifiée:

- r ⩽ 1

;

ou $r = 2$ et $k_1 ⩽ k_2$ ;
ou $r ⩾ 3$ et $k_1 ⩽ k_2 < k_3 < \dots < k_r$ .

En particulier, on convient qu'il existe un unique 0 -uplet, noté () et que ce 0 -uplet vérifie la propriété QSC.
La propriété remarquable des nombres

m_k

qui nous intéressera est alors la suivante :

pour tout entier naturel non nul $n$ , il existe un unique entier $r$ et un unique $r$ -uplet $(k_1, \dots, k_r)$ d'entiers naturels non nuls vérifiant la propriété QSC et tel que $n = m_(k_1) + \dots + m_(k_r)($ cette somme étant par convention nulle si $r = 0)$ .

Une telle écriture

n = m_(k_1) + \dots + m_(k_r)

où (

k_1, \dots, k_r

) vérifie la condition QSC est appelée une décomposition parfaite de

n

. Par exemple, les entiers de 1 à 5 admettent les décompositions parfaites suivantes :

1 = m_1

;

2 = m_1 + m_1; 3 = m_2; 4 = m_1 + m_2; 5 = m_1 + m_1 + m_2

.
On peut remarquer que, du fait de la stricte croissance de la suite d'entiers

(m_k)_(k \in ℕ)

, un

r

-uplet d'entiers naturels

(k_1, \dots, k_r)

vérifie la propriété QSC si et seulement si le

r

-uplet (

m_(k_1), \dots, m_(k_r)

) vérifie également cette propriété. L'unicité d'une décomposition parfaite ne nous préoccupe pas ici (on l'admettra donc), mais seulement son existence. Plus précisément, l'outil dont nous aurons besoin par la suite est un algorithme récursif d'obtention d'une décomposition parfaite.
II.C.1) Donner la décomposition parfaite des entiers

6, 7, 8, 9, 10, 27, 28, 29, 30, 31, 100

et 101.
II.C.2) Soit

n

un entier naturel admettant une décomposition parfaite de la forme

n = m_(k_1) + \dots + m_(k_r)

. Montrer qu'alors

n + 1

admet une décomposition parfaite de la forme:

n + 1 = {m_(k_1 + 1) + (m_(k_3) + m_(k_4) + ⋯ + m_(k_r)), si r ⩾ 2 et k_1 = k_2; m_1 + m_(k_1) + ⋯ + m_(k_r), sinon

II.C.3) Écrire la fonction decomp_parf : int

\to

int list telle que, pour tout entier naturel n, (decomp_parf n) renvoie la liste (

m_(k_1), \dots, m_(k_r)

) des entiers apparaissant dans la décomposition parfaite de n (dans cet ordre). Cette fonction devra avoir une complexité temporelle en

O(n)

II.D - Création d'une liste de tas

On appelle liste de tas une liste de couples de la forme (

a, t

) où

a

désigne un arbre binaire parfait et

t = |a|

est la taille de l'arbre

a

: il existe donc un entier naturel

k

tel que

t = m_k

.
Une liste de tas est implantée en Caml par le type (arbre * int) list.
Étant donnée une liste de tas

h

de la forme précédente, on définit:

la longueur de $h$ , notée long(h), par

long(h) = {0, si h est la liste vide; r, si h = ((a_1, t_1), …, (a_r, t_r))

la taille de $h$ , notée $|h|$ , par

|h| = {0, si h est la liste vide; |a_1|_()_(= t_1) + ⋯ + |a_r|_()_(= t_r), si h = ((a_1, t_1), …, (a_r, t_r))

la hauteur de $h$ , notée haut(h), par

haut(h) = {0, si h est la liste vide; max{haut(a_1), …, haut(a_r)}, si h = ((a_1, t_1), …, (a_r, t_r))

le minimum de $h$ , noté $min_H(h)$ , par

min_H(h) = {+ ∞, si h est la liste vide; min{min_A(a_1), …, min_A(a_r)}, si h = ((a_1, t_1), …, (a_r, t_r))

Comme pour les arbres binaires, on dit que deux listes de tas ont mêmes éléments si les deux listes des arbres les constituant font apparaitre exactement les mêmes étiquettes avec exactement le même nombre d'apparitions de chaque étiquette. De même, une liste

l

d'entiers naturels et une liste de tas constituée d'arbres dont les étiquettes appartiennent à

ℕ

ont mêmes éléments si les deux structures font apparaitre exactement les mêmes éléments avec le même nombre d'apparitions de chaque élément.
On dit qu'une liste de tas

h = ((a_1, t_1), \dots, (a_r, t_r))

vérifie la condition

TC

(pour «tas croissants») si le

r

-uplet d'entiers naturels

(t_1, \dots, t_r)

vérifie la propriété QSC . On peut remarquer qu'une liste de tas

h

vérifie la condition TC si et seulement si

|h| = t_1 + \dots + t_r

est une décomposition parfaite de

|h|

. En particulier, la liste de tas vide vérifie la condition TC ; on constate enfin que toute liste de tas de la forme

h = ((a, |a|))

vérifie la condition TC.

II.D.1)

a) Si

h

est une liste non vide de tas, a-t-on nécessairement haut

(h) = O(log_2|h|)

? A-t-on nécessairement

long(h) = O(log_2|h|)

? Justifier.
b) Même question si

h

est une liste de tas vérifiant la condition TC.
II.D.2) Considérons un arbre réduit à sa racine (c'est-à-dire un couple (

a, 1

) correspondant à un tas binaire parfait) et une liste de tas

h = ((a_1, t_1), \dots, (a_r, t_r))

vérifiant la condition TC. Si l'on ajoute le couple

(a, 1)

en tête de la liste

h

, on obtient bien une liste de tas

(a, 1) : h = ((a, 1), (a_1, t_1), \dots, (a_r, t_r))

, mais qui ne vérifie peut-être plus la condition TC. L'objectif de cette question consiste à concevoir, en utilisant les outils mis en œuvre dans les questions précédentes, un algorithme qui construit une liste de tas

h^'

ayant les mêmes éléments que

(a, 1) : h

telle que

h^'

vérifie la condition TC.
a) On considère

h_1 = ((a_1^1, 1), (a_1^2, 3), (a_1^3, 7))

h_2 = ((a_2^1, 3), (a_2^2, 3), (a_2^3, 7))

deux listes de tas vérifiant la condition TC, où les arbres

a_1^1, a_1^2, a_1^3

a_2^1, a_2^2, a_2^3

sont donnés figure 1 .

Figure 1

Expliquer de manière détaillée (à l'aide de représentations graphiques) comment on construit les listes de tas

h_1^'

h_2^'

lors de l'ajout de l'arbre

a

réduit à sa racine d'étiquette 8 dans chacune des listes de tas

h_1

h_2

.
b) Décrire le plus précisément possible un algorithme qui consiste à construire

h^'

à partir d'un arbre

a

réduit à sa racine et d'une liste de tas

h

vérifiant la condition TC. On fera en sorte que cet algorithme ait une complexité dans le cas le pire en

O(haut(a_1))

(où

a_1

est le premier tas de la liste

h

) et en

O(1)

dans le cas le meilleur. On justifiera soigneusement la correction de la fonction et brièvement sa complexité dans le cas le pire.
c) Écrire la fonction ajoute: int -> (arbre * int) list -> (arbre * int) list telle que (ajoute

\times h

) renvoie la liste de tas vérifiant la condition TC construite par l'algorithme de la question précédente à partir d'un arbre

a

réduit à sa racine x et une liste de tas

h

vérifiant la condition TC .
II.D.3) On définit la fonction suivante, de type int list

\to

(arbre * int) list:

let rec constr_liste_tas l = match l with
    | [] -> []
    | x :: r -> ajoute x (constr_liste_tas r)
;;

Il est clair que l'appel (constr_liste_tas l) renvoie une liste de tas vérifiant la condition TC et ayant les mêmes éléments que la liste 1 .
a) Montrer que le coût en temps de l'appel (constr_liste_tas l) pour une liste l: int list déjà triée de longueur

n

dans le cas le pire est en

O(n)

.
b) Montrer que, pour une liste 1 : int list de longueur

n

, (constr_liste_tas 1) a une complexité temporelle en

O(nlog_2 n)

dans le cas le pire.

^1

II.E - Tri des racines

On dit qu'une liste de tas

h = ((a_1, t_1), \dots, (a_r, t_r))

vérifie la condition

RO

(pour «racines ordonnées») si les tas présents dans la liste apparaissent par ordre croissant de leurs racines ou, ce qui est équivalent, par ordre croissant de leurs minimums :

min_A(a_1) ⩽ \dots ⩽ min_A(a_r)

.
On considère une liste de tas

h = ((a_1, t_1), \dots, (a_r, t_r))

vérifiant la condition TC et ne vérifiant pas nécessairement la condition RO. On veut réarranger les éléments apparaissant dans

h

de façon à obtenir une liste de tas

h^'

vérifiant à la fois la condition TC et la condition RO. Si l'on trie brutalement par insertion les tas de

h

dans l'ordre croissant des racines, on risque de perdre la condition TC. On va donc mettre en place un tri s'inspirant du tri par insertion mais consistant à échanger les racines des tas présents dans

h

plutôt que les tas eux-mêmes.
II.E.1) Écrire la fonction echange_racines: arbre

\to

arbre

\to

(arbre * arbre) de complexité constante telle que, si a1 et a2 sont deux arbres binaires non vides, (echange_racines a1 a2) renvoie le couple d'arbres passés en argument en se contentant d'échanger les étiquettes de leurs racines.
II.E.2) On considère une liste de tas non vide

h = ((a_1, t_1), \dots, (a_r, t_r))

vérifiant la condition RO et un quasi-tas

a

de taille

t

. Montrer que:
a) si

min_A(a) ⩽ min_A(a_1)

, alors (percole

a, t

):: h est une liste de tas vérifiant la condition RO;
b)

simin_A(a) > min_A(a_1)

et si on pose (

b, b1

) = (echange_racines a a1), alors b est un tas binaire parfait, b1 est un quasi-tas et

min_A(b) = min_A(a_1) ⩽ min_A(b1)

.
II.E.3) On examine maintenant trois exemples de couples (

a, h

) pour lesquels

a

est un quasi-tas et

h

est une liste de tas non vide vérifiant la condition RO. On souhaite à chaque fois faire évoluer la liste de tas

(a, |a|) : h

jusqu'à obtenir une liste de tas vérifiant la condition RO, en ne s'autorisant pour seules opérations

que d'éventuelles permutations entre des étiquettes d'un même arbre ou entre des étiquettes de deux arbres distincts (aucune modification de la forme ou de la taille d'aucun arbre en jeu n'est autorisée).
Les couples considérés sont notés

(a_1, h_1), (a_2, h_2)

(a_3, h_3)

, avec

h_1 = ((a_1^1, 7)), h_2 = ((a_2^1, 7))

h_3 = ((a_3^1, 3), (a_3^2, 7))

, où les arbres

a_1, a_1^1, a_2, a_2^1

a_3, a_3^1, a_3^2

sont donnés figure 2 .

Figure 2

Pour chacun de ces trois couples, détailler (à l'aide de représentations graphiques) les étapes de la transformation de la liste

(a, |a|) : h

en une liste de tas vérifiant la condition RO. Chaque étape devra être clairement identifiée comme faisant appel à un procédé précédemment décrit.
II.E.4) Décrire et justifier le plus précisément possible un algorithme qui, à partir d'un quasi-tas

a

, de sa taille

t

et d'une liste de tas

h

, renvoie une liste de tas

h^'

identique à (

a, t

) ::

h

à permutation près des étiquettes des arbres et tel que si

h

vérifie la condition RO, alors

h^'

vérifie la condition RO.
Montrer que sa complexité en temps est en

O(1)

a

est un tas non vide, que la liste de tas

h

vérifie la condition RO et que

min_A(a) ⩽ min_H(h)

.
Montrer que sa complexité en temps est en

O(k + r)

où

k = max{haut(a)

, haut

(h)}

r = long(h)

.
II.E.5) Écrire la fonction

insere_quasi: arbre -> int -> (arbre * int) list -> (arbre * int) list

telle que (insere_quasi ath) renvoie la liste de tas vérifiant la condition RO construite par l'algorithme de la question précédente à partir d'un quasi-tas a de taille

t

et une liste de tas

h

vérifiant la condition RO.
II.E.6) Écrire la fonction tri_racines: (arbre * int) list -> (arbre * int) list transformant une liste de tas

h

supposée vérifier la condition TC en une liste de tas

h^'

vérifiant à la fois la condition RO et la condition TC et telle que

h

h^'

aient mêmes éléments.
II.E.7) Montrer que la fonction tri_racines, appliquée à une liste de tas

h

vérifiant la condition TC, a une complexité temporelle en

O((log_2|h|)^2)

II.F - Extraction des éléments d'une liste de tas

On souhaite dans cette sous-partie récupérer une liste d'étiquettes à partir d'une liste de tas vérifiant les propriétés précédentes. Soit

h = (Noeud(x, a_1, a_2), t) : h^'

une liste de tas non vide vérifiant RO et TC. Pour supprimer

x

h

, si

a_1

a_2

ne sont pas vides, il suffit de construire

h^('') =

(insere_quasi

a_1|a_1|

(insere_quasi

a_2|a_2|h^'

)), où

|a_1|

|a_2|

peuvent se calculer en temps constant.
II.F.1) Montrer que

h^('')

vérifie RO et TC.
II.F.2) Donner la complexité temporelle de l'évaluation de (insere_quasi

a_1|a_1|

(insere_quasi

a_2|a_2|h^'

)) dans le cas le pire, sous la forme

O(f(|h|))

pour une fonction

f

que l'on précisera.
II.F.3) Écrire la fonction extraire: (arbre * int) list

\to

int list prenant en argument une liste de tas

h

vérifiant les conditions RO et TC et renvoyant la liste triée des éléments de

h

en utilisant les idées ci-dessus.
II.F.4) Montrer que la fonction extraire, appliquée à une liste de tas

h

vérifiant les conditions RO et TC, a une complexité temporelle en

O(hlog_2|h|)

dans le pire des cas.

II.G - Synthèse

II.G.1) Écrire la fonction tri_lisse: int list -> int list qui trie une liste en construisant une liste de tas intermédiaire vérifiant RO et TC avant d'en extraire les éléments.
II.G.2) Montrer que la complexité de cette fonction est en

O(nlog_2 n)

où

n

est la longueur de la liste donnée en argument.
II.G.3) Déterminer la complexité temporelle de la fonction tri_lisse dans le cas particulier où la liste passée en argument est déjà triée.

III Implantation dans un tableau

On s'intéressera dans cette partie à la complexité spatiale de certaines fonctions. Par complexité spatiale d'une fonction, on entend ici la quantité de mémoire dont elle a besoin pour s'exécuter, la place utilisée par les données qu'elle reçoit en argument n'étant pas prise en compte. Dit autrement, c'est la quantité de mémoire minimum qui doit rester disponible sur l'ordinateur au moment de l'appel de la fonction pour que son exécution ne provoque pas une erreur de capacité mémoire.
Le but de cette partie est de proposer un algorithme avec la même complexité temporelle que tri_lisse et une meilleure complexité spatiale.
III.

A

- Justifier brièvement que la complexité spatiale de tri_lisse sur une liste

l

de longueur

n

est un

Ω(n)

Au lieu d'utiliser comme précédemment une structure d'arbres persistante, on va utiliser une structure impérative : on représentera des arbres sous forme d'une partie d'un tableau

t

: si

a

est un arbre de taille

k

, on le représente dans les

k

cases de

t

commençant à l'indice

p

comme suit:

si $a$ est vide, la représentation de $a$ ne nécessite aucune place ;
si $a$ est de la forme $Noeud(x, a_1, a_2)$ , où $a_1$ et $a_2$ sont de tailles respectives $k_1$ et $k_2$ , on met $x$ dans la case $p$ du tableau, puis on représente $a_1$ dans les $k_1$ cases commençant à l'indice $p + 1$ , puis on représente $a_2$ dans le tableau $t$ dans les $k_2$ cases commençant à l'indice $p + 1 + k_1$ (cf. figure 3 ).

Figure 3

Au lieu de trier une liste d'entiers, on va trier un tableau d'entiers. Ce tableau servira à la fois à représenter les données initiales et les tas que nous manipulerons. Le tableau sera alors trié par échanges successifs.
Par la suite, tous les arbres que l'on représentera seront ou bien l'arbre vide, ou bien des quasi-tas (qui pourront éventuellement être des tas). On définit le type enregistrement suivant pour représenter l'arbre vide ou un quasi-tas stocké dans un tableau:

type tasbin = {donnees : int vect ; pos : int ; taille : int} ;;

Les champs donnees, pos et taille d'un tel l'enregistrement contiennent respectivement le tableau où sont stockés les éléments, la position de la racine dans le tableau et le nombre d'éléments du quasi-tas (si ce nombre d'éléments est nul, le tableau et la position n'ont aucune importance).
Si le tableau stocké dans le champ donnees de cet enregistrement est le tableau

t

à trier, dont la consommation mémoire n'est pas comptée, la place mémoire prise par un élément de type tasbin est constante.
Par la suite, tous les éléments

t

: tasbin que nous manipulerons partageront le même tableau

t

. donnees sous-jacent, qui sera le tableau à trier.
III.B - Écrire les fonctions fg: tasbin

\to

tasbin et fd: tasbin

\to

tasbin telles que si a représente un quasi-tas, ( fg a) et ( fd a) retournent respectivement une représentation de son fils-gauche et son fils-droit. Ces fonctions devront avoir une complexité constante.
III.

C

- Écrire les fonctions min_tas_vect et min_quasi_vect, de type tasbin

\to

int qui prennent en argument respectivement une représentation d'un tas binaire parfait non vide et une représentation d'un quasi-tas binaire et qui renvoient le minimum de leurs éléments.
III.

D

- Écrire la fonction percole_vect : tasbin

\to

unit tel que si a est un quasi-tas, (percole_vect a) échange des éléments dans le tableau a.data de façon que a devienne un tas avec préservation de l'ensemble des étiquettes aux répétitions près. Si a est un tas vide, (percole_vect a) ne fait rien.

Comme précédemment, on s'intéressera à des listes de tas. De plus, tous les éléments de type tasbin list que nous manipulerons seront soit la liste vide soit des listes de la forme (

a_1, \dots, a_r

) telles que pour tout

i ∈ {1, …, r − 1}, a_i

.pos

+ a_i

.taille

= a_(i + 1)

.pos et que

a_(r - 1)

.pos

+ a_(r - 1)

. taille

= n

où

n

est la longueur du tableau sous-jacent. La place mémoire occupée par une liste de tas est alors linéaire en sa longueur (et non en la longueur du tableau contenant ses éléments). Dans le cas où tous les éléments du tableau sont représentés dans la liste de tas, on aura de plus

a_1

.pos

= 0

Figure 4

III.E - Étant donné un tableau t , on va construire un h : tasbin en parcourant t de droite à gauche de la façon suivante: on démarre avec h vide et, pour

k

allant de

n - 1

à 0 inclus, on ajoute l'élément situé à l'indice

k

à h , de façon similaire à l'algorithme utilisé pour ajoute, de façon à garantir que la condition TC est préservée. À la fin, tous les éléments de t sont représentés dans h . On trie alors h , puis on extrait successivement le minimum de h .
Écrire la fonction ajoute_vect : int vect

\to

int

\to

tasbin

\to

tasbin analogue à la fonction ajoute précédemment définie et telle que (ajoute_vect d p h) ajoute l'élément d'indice p du tableau d à h. On supposera que

h

est vide ou que la position du premier tas de

h

est

p + 1

On définit alors la fonction constr_liste_tas_vect : int vect -> tasbin list, analogue à constr_liste_tas, comme suit :

(* constr_liste_tas_aux : int vect -> int -> tasbin -> tasbin
        ajoute les elements du tableau d d'indice i,
        pour i<p, a la liste de h.
        Precondition : h est vide vide ou la position du premier tas dans h
        est p. *)
let rec constr_liste_tas_aux d p h =
    if p = 0 then h
    else
        let h' = ajoute_vect d (p-1) h in
        constr_liste_tas_aux d (p-1) h
;;
let constr_liste_tas_vect d = constr_liste_tas d (vect_length d) [];;

III.F - Écrire la fonction echange_racines : tasbin -> tasbin -> unit échangeant les racines des tas qui lui sont donnés en argument.
III.

G

- Écrire la fonction insere_quasi_vect : tasbin

\to

tasbin list

\to

unit analogue de la fonction insert_quasi.
III.

H

- Écrire la fonction tri_racines_vect : tasbin -> tasbin list -> unit analogue de la fonction tri_racines.
III.I - Écrire la fonction extraire_vect : tasbin list

\to

unit analogue de la fonction extraire.
III.

J

- Écrire la fonction tri_lisse_vect : int vect -> unit triant un tableau en utilisant les fonctions précédentes.
III.

K

- Quelle est la complexité temporelle de tri_lisse_vect dans le cas le pire?
III.L - Quelle est la complexité temporelle de tri_lisse_vect pour un tableau déjà trié ?
III.

M

- Quelle est la complexité spatiale de tri_lisse_vect dans le cas le pire?

$^1$ On peut en fait démontrer que cette complexité est un $Θ(n)$ mais cela n'est pas demandé.

Questions fréquentes

3 questions

Sur quels chapitres porte le sujet d'option informatique Centrale MP 2016 ?

Le sujet porte sur les structures de données (listes, arbres, tas binaires), l'algorithmique du tri, l'analyse de complexité et la programmation récursive en Caml.

Le sujet d'option informatique Centrale MP 2016 est-il difficile ?

Le rapport indique un sujet correctement compris par les candidats, avec un niveau global satisfaisant et une fraction notable de copies excellentes, ce qui en fait un sujet de difficulté moyenne bien progressif.

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet d'option informatique Centrale MP 2016 ?

Le jury relève des confusions dans l'usage des types construits, des incohérences entre la description d'un algorithme et sa transcription en Caml, et une mauvaise gestion de la récursivité terminale.

Pas de description pour le moment

Commentaires• Centrale Option Informatique MP 2016

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...