E3A Informatique MP 2006

Thème de l'épreuve Quatre algorithmes de tri sur les tableaux
Principaux outils utilisés tableaux, tris, arbres binaires

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


 \ E' 3 CONCOURS ENSAM - ESTP - EUCLIDE - ARCHIMEDE Epreuve d'Informatique MP durée 3 heures Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, d'une part il le signale au chef de salle, d'autre part il le signalesur sa copie et poursuit sa composition en indiquant les raisons des initiatives qu'il est amené à prendre. L'usage de la calculatrice est interdit Indiquer en tête de copie ou de chaque exercice le langage utilisé. On utilisera la notation t [i] pour accéder à l'élément n° i d'un tableau t. On indicera les tableaux à partir de 1, quitte à ne jamais prendre en compte l'élément d'indice 0 dans un langage où les tableaux sont indicés à partir de O. 1. Le tri par sélection ' Le tri (croissant) par sélection d'un tableau tde n éléments consiste à rechercher le plus grand élément, le permuter avec l'élément situé en fin de tableau, et à itérer le traitement avec un élément de moins, jusqu'à ce qu'il n'y ait plus qu'un seul élément. 1 . 1 . Écrire la fonction indiceMaxi données t : tableau d'entiers, n : entier; résultat : entier; qui recherche dans un tableau tde n entiers le plus grand entier et retourne son indice. S'il y a plusieurs maxima égaux, elle retourne l'indice du premier de ceux--ci. 1.2. Écrire la fonction ITÉRATIVE triSe1ecl donnée--résu1tat t : tableau d'entiers ; donnée n : entier; résultat : sans retour qui trie par sélection le tableau tde n entiers. 1.3. Écrire la fonction RÉCURSIVE triSe1ec2 donnée-résultat t : tabteau d'entiers ; donnée n : entier; résultat : sans retour qui trie par sélection le tableau t de n entiers. 1.4. Donner la complexité de ce tri. 2. Tri par insertion ' Le tri (croissant) par insertion d'un tableau tde n éléments consiste à rechercher itérativement la place d'insertion de l'élément n°i dans le sous-tableau précédent (indicé de 1 à i-1) supposé trié et à l'insérer à sa place. On commence à partir du deuxième élément et on termine quand tous les éléments ont été placés. La recherche de la place d'insertion peut se faire séquentiellement ou par dichotomie. 2. 1. Expliquer brièvement les deux principes de recherche (séquen tie/le et dichotomique) et donner leurs complexités (en moyenne et au pire). 2.2. Écrire la fonction posInserl données t : tableau d'entiers, n : entier, x : entier; résultat : entier; qui recherche séquentiellement dans un tableau t trié de n entiers la place d'insertion de x. 2.3. Écrire la fonction posInser2 données t : tableau d'entiers, n : entier, x : entier; résultat : entier; qui recherche par dichotomie dans un tableau ttrié de n entiers la place d'insertion dex. ' « 2.4. Écrire la fonction decale donnée-résultat t : tableau d'entiers ; données î : entier, j : entier; résultat : sans retour qui décale d'une position vers la droite tous les éléments du tableau t depuis l'indice i jusqu'à l'indice j (compris) 2.5. Écrire la fonction ITÉRATIVE triInser donnée--résultat t : tableau d'entiers ; donnée n : entier ; résultat : sans retour qui trie par insertion le tableau t de n entiers. 3. Tri rapide (quick sort) Le principe du quick sort est de partitionner le tableau à trier (s'il a au moins deux éléments) en trois sous--tableaux, le premier comprenant tous les éléments inférieurs ou égaux à un élément (l'élément pivot), le deuxième ne contenant qu'un seul élément (l'élément pivot) et le troisième contenant tous les éléments supérieurs ou égaux à l'élément pivot. Puis on réapplique récursivement le quick sort sur les premier et troisième sous--tableaux (l'élément pivot, lui, est à sa place définitive). Soit les fonctions partition donnée-résultat t : tableau d'entiers ; données f : entier, j : entier; résultat : entier qui opère sur le sous--tableau t compris entre les indices i et j, prend t[ü comme élément pivot, déplace les éléments inférieurs ou égaux au pivot en début de sous-- tableau, les éléments supérieurs ou égaux au pivot en fin de sous--tableau, positionne le pivot à sa place définitive et retourne la valeur de cette place et quicksort donnée--résultat t : tableau d'entiers ; données i : entier, j : entier; résultat : sans retour qui trie le tableau t entre les indices i et j (compris) Soit le tableau suivant: _ _ t ...E- 2 3 4 5 6 7 8 9 10 11 12 13 14 indice 1 3.1. Donner un contenu possible de t après l'appel à pa rti t i on( t , 1 , 14) , et la valeur de retour de la fonction 3.2. Avec quels paramètres doit--on appeler qu i ckso rt pour continuer le tri après cette partition ? 3.3. Écrire la fonction quicksort 3.4. Écrire la fonction partition On pourra utiliser deux parcours, l'un allant du début du sous--tableau vers la fin, et l'autre allant de la fin vers le début. Le parcours montant sera suspendu quand un élément sera supérieur au pivot ; le parcours descendant sera suspendu quand un élément sera inférieur au pivot. Les éléments seront alors échangés et les parcours reprendront jusqu'à ce qu'ils se rejoignent. La place du pivot sera alors déterminée, le pivot y sera mis, et sa place retoumée. 4. Le tri par tas (heap Sort) Le tri par tas consiste à interpréter le tableau comme un arbre binaire presque parfait, à le transformer en tas, puis itérativement, à permuter la racine de l'arbre avec la dernière feuille, puis, à reconstituer le tas avec un élément de moins et ce jusqu'à ce qu'il n'y ait plus qu'un élément à traiter. Définitions . Arbre :Un arbre est soit un arbre atomique (une feuille), soit un noeud (père) et une suite de sous-arbres (ses fils). Chaque noeud ou feuille de l'arbre est associé à une valeur. Graphiquement, on peut représenter un arbre comme suit: Ici, par exemple, le noeud m; a pour fils ne, ng et n... et pour père n3. m est appelé la racine de l'arbre et les feuilles en sont n2, ne, ne, ng, n..., n... et n.... . Arbre binaire (AB) : arbre où chaque noeud est associé au maximum à deux sous-- arbres . Arbre binaire presque complet (ABPC) : arbre binaire dans lequel tous les niveaux de profondeur, sauf peut--être le dernier contiennent le maximum de noeuds, et les feuilles du dernier niveau sont toutes à gauche. Exemple d'arbre binaire presque complet Un ABPC peut être représenté par un tableau (représentation tabulaire) et réciproquement, un tableau peut être interprété comme un arbre binaire presque complet. Ici, le tableau t-------------- ,indice1 23456 78910 peut être interprété comme l'ABPC de la figure. . Tas : Un tas est ABPC dans lequel chaque noeud est dominant (valeur supérieure ou égale à celles de son ou ses fils). 4.1. Dessiner l'arbre représente parle tableau suivant: U..."flflfl 1 2 3 4 5 6 7 8 9 10 indice 4.2. Écrire la fonction indiceFilsG donnée i : entier, résu1tat : entier retourne l'indice du fils gauche (supposé existant) d'un noeud d'indice i dans la représentation tabulaire d'un ABPC 4.3. Écrire la fonction indiceFilsD donnée i : entier, résu1tat : entier retourne l'indice du fils droit (supposé existant) d'un noeud d'indice i dans la représentation tabulaire d'un ABPC 4.4. Écrire la fonction indicePere donnée i : entier, résultat : entier retourne l'indice du père (supposé existant) d'un noeud d'indice i dans la représentation tabulaire d'un ABPC 4.5. Écrire la fonction estFeuille données i : entier, , n : entier; résultat : booléen qui retourne Vrai si iest l'indioe d'une feuille (noeud sans fils) dans la représentation tabulaire d'un ABPC de taille n, et Faux sinon. 4.6. Écrire la fonction estPerel données i : entier, n : entier; résultat : booiéen qui retourne Vrai si i est l'indice d'un noeud n'ayant qu'un seUI fils dans la représentation tabulaire d'un ABPC de taille n, et Faux sinon. 4.7. Écrire la fonction estPere2 données i : entier, n : entier; résultat : booiéen qui retourne Vrai si i est l'indice d'un noeud ayant deux fils dans la représentation tabulaire d'un ABPC de taille n, et Faux sinon. 4.8. Écrire la fonction estDominant données t : tableau d'entiers; ' 1 : entier, n : entier; résultat : booléen qui retourne Vrai si i est l'indice d'une feuille ou d'un noeud dominant (noeud de valeur supérieure ou égale à celles de son ou ses fils) dans la représentation tabulaire t d'un ABPC de taille n, et Faux sinon. 4.9. Écrire la fonction retablirTas donnée--résultat t : tableau d'entiers; données 1 : entier, n : entier; résultat : sans résultat qui opère sur le sous-arbre de t (représentation tabulaire d'un ABPC) à partir de l'indice i pour en faire un tas, avec comme hypothèse que les fils de i (s'ils existent) sont des tas. Par exemplet: indice retabli rTas (t , 22 , 10) transformera l' 67arbre en indice 4. 10. Écrire la fonction construireTas donnée--résultat t : tableau d' entiers; donnée n : entier; résultat : sans résultat qui opère sur t (représentation tabulaire d'un ABPC) pour en faire un tas. Par exemple: ---------u-un indice const ru1reTas(t2,10)3 transformera l"arbre en -fl-u-fl---- indice AL11.ÉËmÜeiafbncfion heapSort donnée--résultat t : tableau d'entiers; donnée n : entier; résultat : sans résultat qui trie par tas le tableau t de n entiers.

Extrait du corrigé obtenu par reconnaissance optique des caractères


 E3A Informatique MP 2006 -- Corrigé Ce corrigé est proposé par Guillaume Batog (ENS Cachan) ; il a été relu par Benjamin Monmege (ENS Cachan) et Vincent Puyhaubert (Professeur en CPGE). Cette épreuve propose d'implémenter quatre algorithmes de tri sur des tableaux et d'étudier la complexité des plus simples d'entre eux. · La première partie porte sur le tri par sélection. Il s'agit exclusivement de questions de cours de première année, à savoir l'écriture itérative puis récursive de l'algorithme de tri, ainsi que l'analyse de sa complexité. · La deuxième partie concerne le tri par insertion. Elle est de même nature que la première. On y aborde entre autres les approches séquentielle et dichotomique de la recherche de la position d'insertion. · La troisième partie porte sur le tri rapide. La principale difficulté tient à la compréhension de l'algorithme présenté dans l'énoncé. Les premières questions consistent simplement à appliquer cet algorithme sur un exemple. L'implémentation de la fonction de partition est la plus difficile du sujet car elle nécessite une part d'initiative, notamment dans l'écriture de sous-programmes. · La quatrième partie, la plus longue, concerne le tri par tas. Dans cette méthode, un tableau s'interprète comme un arbre binaire presque complet que l'on munit d'une structure de tas. Les opérations de base sur les tas sont utilisées pour trier le tableau en retour. Les premières questions, plutôt faciles, permettent de se familiariser avec la structure de tas à travers de nombreux tests. L'implémentation de l'algorithme de tri n'a lieu qu'au cours des trois dernières questions, plus difficiles car les algorithmes ne sont pas présentés dans l'énoncé. Depuis 2007, le format de l'épreuve d'informatique des E3A a changé. Bien que ce sujet ne soit plus représentatif, il constitue un entraînement à la programmation sur les tableaux. Ses trois premières parties peuvent être traitées en n'utilisant que le programme de première année. Indications 1.2 Programmer l'algorithme présenté en début de partie. 1.3 Traduire la boucle for de triSelec1 sous forme récursive avec let rec. 1.4 Dénombrer les comparaisons effectuées lors d'un appel à la fonction indiceMaxi. 2.1 Au cours d'une recherche séquentielle, le tableau est parcouru de gauche à droite. Pour le calcul de la complexité en moyenne, les positions d'insertion sont supposées équiprobables. 2.2 2.3 2.4 2.5 3.3 3.4 Le principe de la dichotomie consiste à ce qu'un problème sur une donnée se réduit au même problème sur une sous-donnée de taille moitié. Montrer que, quel que soit le tableau de taille n, le nombre T(n) de comparaisons effectuées par l'algorithme dichotomique vérifie n j n k l n mo ,T T(n) 6 1 + max T 2 2 Ne pas déborder du tableau pendant son parcours. Écrire une fonction auxiliaire récursive réalisant la recherche dichotomique et ayant deux arguments qui représentent les extrémités du sous-tableau considéré. Prendre garde à ne jamais écraser les valeurs du tableau. Programmer l'algorithme présenté en début de partie. Faire attention au cas où un des sous-tableaux de la partition est vide. Utiliser la fonction partition comme une « boîte noire ». Implémenter les sous-programmes préconisés par l'énoncé. · parcoursMontant et parcoursDescendant réalisent chacun un seul parcours décrit dans l'énoncé. Chaque fonction retourne la position à laquelle le parcours s'est arrêté. · parcoursDouble applique successivement les deux parcours précédents jusqu'à ce qu'ils se rejoignent. Cette fonction retourne la position où le pivot doit être placé. Dans un premier temps, écrire les programmes en supposant que les valeurs du tableau sont deux à deux distinctes, afin d'écarter d'éventuels problèmes portant sur les inégalités larges ou strictes dans les tests. 4.1 Remplir successivement les différents niveaux de l'arbre en parcourant le tableau de gauche à droite. 4.2 Conjecturer le résultat sur l'exemple précédent. 4.4 4.5 4.6 4.7 4.8 4.9 Chercher une même fonction « inverse » pour indiceFilsG et indiceFilsD. Écrire la condition d'être une feuille à l'aide de indiceFilsG. Écrire la condition correspondante à l'aide de indiceFilsD et estFeuille. Écrire la condition correspondante à l'aide de indiceFilsG. Distinguer les cas où un noeud a 0, 1 ou 2 fils. Faire descendre le noeud courant jusqu'à ce que la condition de domination soit respectée. Justifier que, lors d'une descente, le noeud courant doit être échangé avec son fils de valeur maximale. 4.10 Les feuilles sont des tas mais leurs pères ne le sont pas forcément. 4.11 Programmer l'algorithme présenté en début de partie. Selon le rapport du jury, la discrimination entre les compositions s'est surtout faite sur les points suivants : · une mauvaise lecture de l'énoncé ; · des réponses inutilement compliquées ; · les exercices inhabituels (parties 3 et 4) délaissés et les exercices familiers (parties 1 et 2) traités à la va-vite ; · l'absence de commentaires, la programmation obscure et la mauvaise présentation des programmes (le rapport conseille de donner des noms parlants aux identificateurs et d'adopter un style d'indentation clair). Rappelons que l'élément d'indice 0 d'un tableau ne sera jamais pris en compte tout au long du sujet. La longueur des tableaux est toujours en paramètre des fonctions à programmer. C'est pourquoi il n'est aucunement nécessaire d'utiliser la fonction vect_length. 1. Le tri par sélection 1.1 La fonction indiceMaxi parcourt le tableau t de gauche à droite à la recherche du maximum. L'invariant de la boucle for s'énonce ainsi : à la fin de l'étape i, · !max contient le maximum des entiers stockés entre les positions 1 et i ; · !res est la position du maximum le plus à gauche entre ces mêmes positions. L'inégalité stricte t.(i) > !max évite de modifier la position du maximum le plus à gauche si ce maximum est rencontré une nouvelle fois. let indiceMaxi t n = let res = ref 0 and max = ref 0 in for i = 1 to n do if t.(i) > !max then begin max := t.(i); res := i end done; !res;; Le rapport du jury mentionne une erreur à ne pas commettre : « Plusieurs candidats ont commis la faute de chercher la valeur du plus grand élément (algorithme sans doute traité en classe), puis faire un deuxième parcours pour trouver le plus grand indice. » 1.2 La fonction triSelec1 traduit directement l'algorithme de tri par sélection présenté en début d'énoncé. L'appel permute t i j réalise la permutation des entiers aux positions i et j du tableau t. La variable de stockage stock permet de ne pas perdre l'entier t.(i) lors de la première affectation. let permute t i j = let stock = t.(i) in t.(i) <- t.(j); t.(j) <- stock;; let triSelec1 t n = for i = n downto 1 do let j = indiceMaxi t i in permute t i j done;; Dans la description de triSelec1 de l'énoncé, la mention donnée-résultat pour le tableau d'entiers signifie que la fonction modifie ce tableau au cours de son exécution : elle effectue un tri sur place. Ainsi il est inutile de réserver un espace mémoire supplémentaire pour construire le tableau trié. 1.3 Le programme suivant est l'écriture récursive de la boucle for de triSelec1. let rec match | 0 | _ triSelec2 t n = n with -> () -> let j = indiceMaxi t n in permute t n j; triSelec2 t (n-1);; 1.4 Calculons le nombre de comparaisons d'entiers effectuées lors de l'algorithme. Elles ont lieu uniquement au cours de la recherche d'un maximum dans un tableau. Pour un tableau de taille i, il y en a exactement i. Puisque l'algorithme consiste à rechercher un maximum dans des tableaux de taille successivement n, n - 1, . . ., 1, le nombre total de comparaisons vaut n P i=1 i= n(n + 1) 2 Le tri par sélection effectue (n2 ) comparaisons d'entiers. La complexité d'un algorithme porte sur le nombre d'opérations élémentaires effectuées lors de son exécution et exprime un ordre de grandeur de ce nombre, lorsque la taille des données devient importante (c'est-à-dire, lorsque cette taille tend vers l'infini, d'où l'utilisation des notations de Landau). C'est pourquoi il faut préciser les opérations élémentaires dénombrées. Pour le tri par sélection, le nombre de comparaisons effectuées est toujours égal à n(n + 1)/2 sur un tableau de taille n. La notation (n2 ) traduit le fait que la complexité est quadratique à la fois dans le pire des cas et dans le meilleur des cas. Rappelons que an = (bn ) signifie que an = O(bn ) et bn = O(an ). C'est un « équivalent large » en quelque sorte : il existe et tels que pour n assez grand, an 6 bn 6 an .