Centrale Option Informatique MP 2001Sujet et corrigé

5,0(1 vote)

Explorer les annales

BanqueCentrale Année2001 FilièreMP MatièreInformatique

Annales Centrale MP Informatique Centrale MP 2001 MP Informatique Informatique 2001

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Corrigé 2

Lire en ligne LaTeX Word

Rapport du jury : non disponible

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

INFORMATIQUE

Les deux parties sont indépendantes et peuvent être traitées dans un ordre quel conque

Partiel - Algorithmes pour la sélection

Pour

x \in IR

, on note

⌊x⌋

la partie entièrede

x

, c'est-à-dire le plus grand entier inférieur ou égal à

x

, et

⌈x⌉

le plus petit entier supérieur ou égal à

x

.
On s'intéresse au problème suivant, appelé problème de la sélection : on a un ensemble E de

n

entiers positifs distincts, un entier i inférieur ou égal à

n

, et on recherche le i - ème élément de

E

classé dans l'ordre croissant, c'est-à-dire l'élément

x

E

tel qu'il

y

ait

i - 1

éléments de

E

strictement inférieurs à

x

n - i

strictement supérieurs à

x

.
Le médian d'un ensemble de n nombres est le

⌈n/2⌉

- ème lorsqu'ils sont rangés en ordre croissant.
On insiste sur le fait que dans toute la partie I, on considère des tableaux ou listes d'entiers distincts deux à deux.

I.A - Recherche des deux plus grands éléments

Les éléments de

E

sont donnés non classés dans un tableau

T

.
I.A.1) Soit

p \in IN^*

. On organise un tournoi entre

n = 2^p

entiers

e_1, \dots, e_n

au sens suivant : on constitue un arbre binaire parfait de hauteur

p

(i.e.: chaque noeud de profondeur < p possède exactement deux fils), dont les

2^p

feuilles sont étiquetées par les

e_i

. Ensuite, pour

h

allant de

p - 1

à 0 , les étiquettes des noeuds de profondeur

h

sont égales au maximum des étiquettes de leurs deux fils.
a) Donner le nombre de comparaisons nécessaires pour réaliser un tel tournoi.
b) Montrer qu'à l'aide de ce procédé, on peut trouver le maximum et le second plus grand élément des

e_i

en moins de

n + ln_2 n

comparaisons.
En fait, on peut montrer (mais cen'est pas demandé) qu'un tel algorithme est optimal.
c) Exemple : appliquer la méthode précédente à l'entrée:

= [3, 6, 8, 20, 2001, 1515, 17, 1].

d) Comment généraliser cette méthode lorsque

n

n'est pas de la forme

2^p

? Appliquer à l'entrée

= [1, 1024, 1515, 5, 12, 4].

I.A.2) On suppose qu'il existe un algorithme

𝒜

prenant en entrée n entiers, et retournant le plus grand de ces entiers. On suppose que cet algorithme exécute des comparaisons entre des éléments du tableau, et que le résultat retourné ne dépend que de l'ensemble des résultats des comparaisons effectuées. On suppose égal ement qu'il

Filière MP

existe une entrée

e = (e_1, \dots, e_n)

telle que

𝒜

exécute strictement moins de

n - 1

comparaisons, lorsqu'il est exécuté sur l'entrée e.
a) Si S est un ensemble fini non vide de cardinal

p \geq 2

dont les éléments sont appelés sommets

S = {S_1, …, S_p}

, on appelle arêtede

S

toute paire de sommets, c'est-à-dire tout ensemble

{s_i, s_j}

de deux sommets distincts. Par définition, un graphe (non orienté) est un couple (

S, A

) où

A

est un ensemble d'arêtes de

S

.
Un tel graphe est dit connexe lorsque pour toute paire de sommets

{s_i, s_j}

, il existe un entier

n \in 𝕀ℕ^*

et une suite de sommets

c_0, \dots, c_n

tels que

c_0 = s_i, c_n = s_j

{c_k, c_(k + 1)} ∈ A

pour tout

k \in [ [0, n - 1] ]

.
Montrer que si (

S, A

) est connexe, alors

|A| \geq |S| - 1

(où

|X|

désigne le cardinal de l'ensemble X ).
b) Construire une entrée

e^' = (e_1^', \dots, e_n^')

tellequel'algorithme

𝒜

ne retourne pas le plus grand élément de é. On pourra considérer le graphe (

[ [1, n] ], C

), où

C

est l'ensemble des paires

{i, j} ∈ [ [1, n] ]^2

tels que dans l'exécution de

𝒜

sur e, e a a été comparé au moins une fois à

e_j

.
c) Conclure.

I.B - Recherche systématique dans un tableau

Les éléments de

E

sont à nouveau donnés non dassés dans un tableau

T

.
I.B.1) On utilise l'algorithme suivant : en supposant

i \leq n/2

, on recherche le minimum du tableau, puis le deuxième plus petit élément, puis le troisième et ainsi de suite jusqu'au i-ème.
Calculer le nombre de comparaisons effectuées ; quel est son maximum lorsque i varie?
I.B.2) Indiquer un algorithmequi permettrait de résoudrele problème dela sélection pour un i quelconque en

O(nlnn)

comparaisons.

I.C - Tri rapide dans une liste chaînée

I.C.1) Écrire une fonction (ou une procédure) partition qui, étant donné une liste chaînée d'entiers liste, et un entier pivot (appartenant ou non à la liste) :

constitue deux listes avant et apres constituées des éléments de liste et telles que : $\forall(x, y) \in$ avant $x$ apres, $x \leq$ pivot $< y$ .
retourne les deux listes avant et apres, et le nombre d'éléments nb de la liste avant.

Les candidats rédigeant en Caml devront écrire une fonction de type:
partition : 'a liste 一>'a 一>'a list * 'a list * int = <fun>

Ceux rédigeant en Pascal utiliseront la déclaration de type
type
ptrliste=^element;
element=record
entier:integer;
suivant:ptrliste
end;
et ils écriront une procédure dédarée de la façon suivante:
procedure partition(liste:ptrliste; pivot:integer;
var avant,apres:ptrliste; var taille:integer);
I.C.2)
a) Écrire une fonction recherche récursive qui, pour un entier i et une liste d'entiers liste, retourne le i -ème élément de la liste
On utilisera la fonction/procédure partition précédente, en prenant comme pivot le premier élément de la liste. Les candidats ayant choisi Caml écriront une fonction de signature:
recherche : int一>'a list一>'a = <fun>
Ceux ayant choisi Pascal écriront une fonction déclarée:
fonction recherche (liste:ptrliste; i:integer) :integer;
b) J ustifier la terminaison et la correction de la fonction précédente.
c) Donner des indications sur son temps de calcul. On exhibera des «cas limites».
d) Si la distribution des entiers de E est uniforme dans un intervalle, comment choisir l'entier pivot pour réduire au mieux le temps de calcul ?

I.D - Recherche de l'élément médian

L' ensemble des éléments de

E

est donné sous la forme d'un tableau

T

d'entiers de Iongueur n indexé de 0 à

n - 1

. Dans cette partie du problème, on supposera pour simplifier que

n

est une puissance de 2 . On pose

n = 2^p

m = n/2 = 2^(p - 1)

.
On suppose que les deux sous-tableaux

T[0\dotsm - 1]

T[m\dotsn - 1]

sont triés par ordre croissant, donc que :

T_0 < T_1 < \dots\dots < T_(m - 1) et T_m < T_(m + 1) < \dots < T_(n - 1).

I.D.1)
a) En utilisant la fonction (supposée donnée) de fusion de deux tableaux triés, donner un algorithme déterminant le médian

μ

T

.
b) Évaluer son temps de calcul (on prendra en compte seulement le nombre de comparaisons de deux éléments).
I.D.2) On veut améliorer la recherche précédente en effectuant une recherche dichotomique simultanée sur les deux moitiés du tableau

T

.
a) Expliquer (éventuellement à l'aide de schémas) une stratégie à adopter pour déterminer le médian de

T

.
b) Donner le code d'une telle fonction. On introduira une fonction récursive de la forme recherche_dicho (

T, g1, d1, g2, t2

On rappellequela taille du tableau initial est une puissancede 2.
c) Prouver la validité du programme précédent.
d) Donner un ordre de grandeur de son temps de calcul (on prendra en compte seulement le nombre de comparaisons de deux éléments).

I.E - Utilisation d'arbres binaires de recherche

Afin de pouvoir insérer puis rechercher rapidement n'importe quel élément del'ensemble E , on organise les données selon une structure d'arbres binaires de recherche. On utilisera les types suivants:

En Caml :
    type arbre = vide | Noeud of Nd
        and Nd = {valeur : int; mutable taille : int;
                mutable gauche : arbre; mutable droit : arbre};;

En Pascal :
type

ptrNoeud=^Noeud;
Noeud = record
        valeur, taille : integer;
        gauche, droit : ptrNoeud;
    end;

Chaque noeud N de la structure d'arbres binaires contient la valeur d'un entier de E , la taille (comptée en nombre de noeuds non vides) de l'arbre de racine N , et des pointeurs vers les deux fils.
I.E.1) Pour tester le fonctionnement du programme, on utilise des nombres entiers engendrés par un processus pseudo-aléatoire, qui sont rangés, l'un à la suite de l'autre, dans l'arbre binaire initial ement vide.
a) On considère la suite de nombres pseudo-aléatoires

3; 4; 1; 2

. Donner un schéma de la structure de l'arbre binaire obtenu après insertion deces 4 éléments dans un arbreinitialement vide. Pour chaque noeud, on précisera la valeur de l'étiquette, et la taille.
b) Même question avec la séquence suivante:

7; 3; 5; 1; 13; 12; 14; 9; 4; 6; 1; 8; 10; 0; 2

I.E.2) Écrire une fonction (ou une procédure) insere, récursive, réalisant l'insertion d'un nouvel entier x dans l'arbre binaire a. Cette fonction/procédure devra retourner l'arbre dans lequel on a inséré l'entier x. Dans la mesure du possible, on modifiera les champs de l'arbre donné en paramètre, plutôt que d'en recréer un.

En Caml, la signature de insere sera:
    insere : int -> arbre -> arbre = <fun>
En Pascal, la déclaration sera:
    procedure insere (x:integer; var a : PtrNoeud)

I.E.3)

a) En supposant que l'arbre est bien équilibré (en un sens que l'on précisera), indiquer un ordre de grandeur du temps d'exécution de la fonction insere en fonction de la taille de l'arbre dans lequel on insère un nouvel élément.
b) Que se passe-t-il si l'arbre n'est pas équilibré ? Citer un cas où cela peut se produire.
I.E.4) Écrire une fonction recherche, récursive, déterminant le

k

-ème élément de l'ensemble des étiquettes d'un arbre binaire de recherche.
Si on appelle g la tailledu sous-arbregauche, on pourra considérer divers cas suivant la valeur de

g

par rapport à

k

.
En Caml, on aura :
recherche : int

\to

arbre

\to

int

=

<fun>
Et en Pascal :
function recherche (k:integer; a:PtrNoeud):integer;

Partie II - Portes Iogiques universelles

Rappels - notations - définitions

$ℬ$ désigne l'ensemble des booléens: $ℬ = {0, 1} = {$ F aux, Vrai $}$ avec l'analogie 0 = Faux et $1 =$ Vrai .
Les fonctions logiques sont les applications de $ℬ^k$ dans $ℬ^n$ , avec $k, n \in IN^*$ .
Les formules logiques sont construites à partir de variables, des connecteurs $\lor (ou)$ , $\land$ (et), $\neg($ non $)$ & $\oplus$ (ou exclusif), ainsi éventuellement que des constantes Vrai et Faux.
On rappellequ'à touteformule $φ$ construitesur les variables ( $v_1, \dots, v_n$ ), on associede façon naturel le unefonction $F_φ : ℬ^n \to ℬ$ .
Réciproquement, si $f$ est une application de $ℬ^k$ dans $ℬ$ , on sait qu'il existeune formule $φ$ construite avec les variables ( $v_1, \dots, v_k$ ) telleque $f = F_φ$ . Il n'y a pas unicité de $φ$ , mais on peut par exemple imposer à $φ$ de n'utiliser que les connecteurs $\land, \lor$ et $\neg$ . On dit quel'ensemble{ $\land, \lor$ et $\neg$ } est complet.
Présentons sommairement les circuits logiques : il s'agit d'assemblages orientés de portes logiques élémentaires disposant d'entrées et de sorties.
Uneporte $(n, p)$ est constituéed'entrées $(i_1, \dots, i_n)$ et desorties ( $o_1, \dots, o_p$ ); chaque $o_i$ prend une valeur fonction des $i_j$ . Traditionnellement, les entrées sont repré sentées à gauche et les sorties à droite
On disposedes portes élémentaires suivantes : la porteNON est detype ( 1,1 ), avec $o_1 = \negi_1$ . Les portes OU, ET et XOR sont de type ( 2,1 ), avec $o_1 = i_1 \lor i_2$ (resp. $o_1 = i_1 \land i_2$ et $o_1 = i_1 \oplus i_2$ ).

Les portes élémentaires

Chaque entrée de porte peut constituer une entrée du circuit global, ou bien être reliée à la sortie d'une autre porte, ou encore à une source, qui constitue une porte particulièresans entrée, avec une sortie constante égale à 0 ou 1 .
Chaque sortie de porte peut constituer une sortie du circuit global, ou bien être reliéeà l'entréed'uneautreporte, ou encoreà un puits, qui est uneporteparticulière sans sortie, avec une entrée: en somme, il s'agit d'une sortie «dont on ne tiendra pas compte».
L'assemblageest acycliqueau sens où en suivant I'orientation des portes, il n'existe pas de boucle dans le circuit.
Les duplicateurs sont des portes particulières à une entrée $i_1$ et deux sorties en $O_1$ et $O_2$ égales à $i_1$ . Ils sont représentés par un cerde plein. Les sources sont repré

Un duplicateur, une source de 1, et un puits. sentées par un carré et les puits par des cercles.

Un circuit C avec n entrées $(i_1, \dots, i_n)$ et k sorties ( $o_1, \dots, o_k$ ) calcule de façon naturell e une fonction $F_C : ℬ^n \to ℬ^k$ . Dans l'exemple qui suit, $C_0$ calcule la fonction $(i_1, i_2) \mapsto (\negi_1, i_1 \land i_2, (i_1 \land i_2) \lor 0)$
Deux circuits seront dits équivalents lorsqu'ils cal culent la même fonction.
Un ensemble E deportes sera dit universel Iorsquetout circuit est équivalent à un autre circuit constitué de portes de E, de duplicateurs, desources et de puits. Lorsque $E$ est réduit à un singleton ${P}$ , on dit que $P$ est une porteuniverselle
Enfin, uneporte $P$ detype ( $n, p$ ) sera diteréversiblelorsqu'il existeuneporte $Q$ de type ( $p, n$ ) telle quel'assemblage constitué dela porte $P$ suivie de la porte $Q$ calculela fonction identitéde $ℬ^n$ . Par exemple, la porteNON est réversible (prendre $Q = P$ ).
II.A - Donner deux formules logiques calculant les valeurs respectives de $o_1, o_2$ en fonction de $i_1, i_2$ et $i_3$ pour le circuit $C_1$ suivant:

II.B - Ensembles de portes universelles

II.B.1) Construire un circuit logique

C_2

permettant de calculer la fonction

φ : ℬ^3 \to ℬ^3, (i_1, i_2, i_3) \mapsto (i_1, i_1 \oplus (i_3, i_2 \land i_3)).

On utilisera uniquement des duplicateurs, sources, portes NON, OU et ET.
II.B.2)
a) Montrer que l'ensemble de portes {NON, ET} est universel.
b) Exemple : construire un circuit équivalent à

C_2

à l'aide des seules portes NON et ET , et de duplicateurs et sources.
II.B.3)
a) Montrer que l'ensemble de portes {XOR, OU } est universel.
b) Exemple: construire un circuit équivalent à

C_0

à l'aide des seules portes XOR et OU , et de duplicateurs et sources.
II.B.4)
a) Montrer que la porte

G_0

suivante est universelle:
b) Construire à partir de

G_0

(et de duplicateurs, sources et puits) un circuit

C_3

calculant la fonction de

ℬ^3

dans

ℬ^2

(i_1, i_2, i_3) \mapsto (i_1 \lor i_2, (\negi_1) \land (i_2 \lor i_3)).

c) Montrer que la porte

G_0

n'est pas réversible.

II.C - Portes réversibles

II.C.1) Montrer quesi une porte logique (

n, p

) est réversible, alors

n \leq p

.
II.C.2) Quelles sont les portes

(1, 1)

réversibles?
II.C.3) Donner deux exemples simples mais non triviaux (i.e. dont les fonctions associées ne sont pas l'identité) de portes ( 2,2 ) réversibles.
II.C.4) Combien existe-t-il de portes

(2, 2)

réversibles? Et de portes (

n, p

) réversibles? (il s'agit bien sûr de portes non équivalentes...).

II.D - Portes réversibles universelles

II.D.1) On se propose de montrer qu'il n'existe pas de porte (2, 2) réversible et universelle.
Soit G une porte réversible ( 2,2 ).
On note g la fonction de

ℬ^2

dans

ℬ^2

calculée par G .
a) Montrer que

g

est affine au sens suivant :

\foralli, i^' \in ℬ^2, g(i + i^') = g(i) + g(i^') + g(0),

où + désigne la somme dans

ℬ^2

(assimilé au groupe additif

V = (ℤ/2ℤ)^2

et 0 désigne

(0, 0)

). On pourra commencer par le cas où

i = i^'

, puis le cas où

i

i^'

vaut 0 .
On rappelle quesi

x \in V

, on a

x + x = 0

, et quesi

x, y, z

sont les trois éléments non nuls de V , alors

x = y + z

.
b) Montrer que tout circuit (

n, p

) construit à partir de G , de duplicateurs, sources et puits calcule une fonction affine de

ℬ^n

dans

ℬ^p

(pour la définition d'une fonction affine se reporter au II.D.1.a) en remplaçant

ℬ^2

par

ℬ^n

).
c) Conclure.
II.D.2) La porte de Toffoli est la porte logique

(3, 3)

suivante:
a) Montrer que la porte de Toffoli est réversible et universelle.
b) Vérifier que la fonction calculée par T n'est pas affine.

Porte de Toffoli

Pas de description pour le moment

Commentaires• Centrale Option Informatique MP 2001

Connectez-vous pour participer aux discussions

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

Chargement des commentaires...