[PDF] Marches permutations et arbres binaires aléatoires

View - Download Marches permutations et arbres binaires aléatoires

Previous PDF

Next PDF

Marches, permutations et arbres binaires aléatoires Épreuve pratique d"algorithmique et de programmation Concours commun des Écoles Normales Supérieures Durée de l"épreuve: 4 heures - Coefficient: 4 Juillet 2003N"oubliez en aucun cas de recopier votreu0

clairement encadré au début de votre copie.Notes.Lorsque la description d"un algorithme est demandée, celle-ci doit

être courte et précise.Vousnedevezenaucuncasrecopierlecodedevosprocéduressurvotrecopie! Quand on demande le temps de calcul d"un algorithme en fonction d"un paramètren, on demande son ordre de grandeur en fonction du paramètre, par exemple :O(n2),O(nlogn),... Il est recommandé de commencer par lancer vos programmes sur des petites valeurs des paramètres. Les questions sont assez largement indépendantes entre elles, et ne dépendent principalement que des algorithmes de génération des structures étudiées. Les sections 2, 3 et 5 sont totalement indépendantes des précédentes.

1 Préambule

La suite(un)n?0suivante est dite "pseudo-aléatoire» car ses valeurs sont raisonnablement uniformes et indépendantes. Cette suite sera utilisée dans les sections suivantes pour construire nos structures "aléatoires». •u0est donné sur votre table.Àreporterenhautdevotrecopie!!! •un= (16383×un-1) modulo 59047, pourn?1. Question 1Que valentu996etu9547? Combien il y a-t-il d"indicesi,

0?i <100000, tels queui= 18 modulo 27? Combien il y a-t-il d"indicesi,

1?i <100000, tels queui= 18 modulo 27etui-1= 15 modulo 27?

1

2 Marches aléatoires

On appellemarche aléatoireyde longueurn, une suite den+ 1entiers (y(i))0?i?n, telle que : y(0) = 0et|y(i+ 1)-y(i)|= 1,pour tout0?i < n. Nous considérons des marches aléatoires de longueurn?10000. À toute marche aléatoirey, on associe la marche positive|y|, telle que|y|(i) =|y(i)|. On appellerecordd"une marche aléatoireytout indicei?>0, tel que y(i)< y(i?)pour touti < i?. On se donne un paramètre entierb?1. On définit la marche(yb(i))0?i?10000 suivante : y b(0) = 0 et pour0?i <10000:yb(i+ 1) =yb(i)-1 + 2×(ub×i+10modulo 2). Question 2Combien la marche|y1|a-t-elle de records? Quel est l"avant- dernier record de|y1|? Quel est la distance maximale entre deux records consécutifs? Mêmes questions pour|y3|, et|y5|. Décrivez succinctement (ra- pidement) vos algorithmes et donnez leurs temps de calcul en fonction de n. On appellesous-suite strictement croissantede longueur?d"une marche (y(i))0?i?ntoute suite d"indices0?i1< i2< ... < i??ntelle que y(i1)< ... < y(i?). Question 3Quelles sont les longueurs des plus longues sous-suites stricte- ment croissantes de|y1|, de|y3|et de|y5|? Expliquez rapidement la méthode que vous avez utilisée et donnez son temps de calcul en fonction den. Question 4Quelles sont les longueurs des plus longues sous-suites stricte- ment croissantes dey1, dey3et dey5? Détaillez et justifiez l"algorithme que vous avez utilisé et donnez son temps de calcul en fonction den.

3 Permutations aléatoires

On se propose de générer des permutations aléatoires sur{0,...,n-1}, où

1?n?10000.

3.1 Premier algorithme de génération

On suppose ici quen?100. On se donne un paramètre entierb?1. Voici l"algorithme proposé : soitxi=ub×i+10modulon2pour0?i < n; s"il existei?=jtels quexi=xj, alors renvoyer un message d"erreur; sinon, on noteπn,bl"unique permutation telle quexπn,b(0)< ... < xπn,b(n-1). 2 Question 5Quel est le plus petitb?1, notéb?50, tel que la procédure renvoie une permutation pourn= 50? Que vautπ50,b?50(37)? Quel est le nombre de points fixes deπ50,b?50◦π50,b?50? Mêmes questions pourn= 100. Question 6Décrivez rapidement les algorithmes et les structures de don- nées que vous avez utilisés. Donnez pour chaque algorithme son temps de calcul en fonction den. Nous rappelons que l"orbite d"un entierisous l"action d"une permutationπ

est l"ensemble de ses itérés{i,π(i),π◦π(i),π◦π◦π(i),...}. L"orbite d"un

élément sous l"action d"une permutation est un cycle. Question 7Quelle est la longueur de la plus longue orbite deπ50,b?50? de

100,b?100? Donnez le plus petit élément de ces deux orbites. Décrivez rapide-

ment les algorithmes que vous avez utilisés, et donnez le nombre d"opérations

élémentaires effectuées en fonction den.

3.2 Second algorithme de génération

On suppose maintenant1?n?10000. On se donne un paramètre en- tierb?0. Nous construisons la permutationσn,bsur{0,...,n-1}, pour

1?n?10000, ainsi. Partant de la permutation identité, on itère le proces-

sus suivant pouriallant de1àn-1, dans cet ordre : échanger dans la permutation courante les images des entiersiet(ui+bmodulo (i+1)). Puis, renvoyer la permutation obtenue.

Question 8Quelle est la permutationσ5,2?

Question 9Quelle est la longueur de la plus grande orbite deσ9537,0? Don- nez un élément de cette orbite. Mêmes questions pourσ9564,1etσ9337,12. Question 10Quelle est la longueur de la plus longue sous-suite strictement croissante de la suite(σ100,0(i))0?i?99? Donnez la liste des éléments d"une telle sous-suite maximum. Détaillez précisément et justifiez de façon concise l"algorithme que vous avez utilisé. Donnez son temps de calcul en fonction de la longueurnde la suite. Question 11Quelles sont les longueurs des plus longues sous-suites strictement croissantes des suites(σ200,0(i))0?i?199,(σ500,0(i))i=0?i?499et (σ1000,0(i))0?i?999? Donnez les 5 premiers éléments d"une telle sous-suite maximum pour chacune. 3

4 Excursions

On appellechemin de Dyck bilatère, une marche aléatoiredde longueur2n telle qued(2n) = 0, c"est-à-dire qui compte autant de pas montants que de pas descendants. On se donne un paramètre entierb?0. On propose de générer un chemin de Dyck bilatère aléatoiredn,bde longueur2nainsi : générer la permutation

2n,b; les positions des pas montants dedn,bsontσ2n,b(0),...,σ2n,b(n-1);

et celles des pas descendants dedn,bsontσ2n,b(n),...,σ2n,b(2n-1).

Question 12Donnezd5,2.

Question 13Quelle est la valeur ded3270,0(1557)? ded4351,3(1346)? Quelle est la distance maximale entre deux records consécutifs ded3270,0? ded4351,3? On appelleexcursion, un chemin de Dyck bilatère positif, i.e., une marche aléatoiree, telle que :e(2n) = 0, ete(i)?0pour tout0?i?2n. On se donne un paramètre entierb?0. Nous définissons l"excursionen,bde la façon suivante : soit0?i-<2n, le plus petit indice qui correspond au minimum dedn,b(i.e.,dn,b(i)> dn,b(i-)pouri < i-, etdn,b(i)?dn,b(i-) pouri?i-); l"excursionen,best obtenue en "coupant» le chemin de Dyck bilatèredn,bau pointi-, et en échangeant les deux moitiés de chemins ob- tenus. La construction deen,best illustrée sur la figure ci-dessous.d n,b (i) i i e n,b (i) i Un chemin de Dyck bilatère...... et son excursion associéeQuestion 14Donneze5,2. Question 15Quelles sont les valeurs dee2051,0(1342),e2057,23(1546)? Quelle est la distance maximale entre deux records consécutifs pour ces deux excursions?

5 Génération incrémentale d"arbres binaires

Nous supposonsn?5000. Nous proposons dans cette partie de générer des arbres binaires. Unarbre binaireest un arbre dont les sommets ont 0 ou 2 fils. Les sommets ayant zéro fils sont appelésfeuilleset les sommets ayant

2 fils,sommets internes. On démontre, par récurrence immédiate, que tout

4 arbre binaire avecnsommets internes, a exactementn+1feuilles, et compte donc2n+ 1sommets exactement. À défaut de liste chaînée, un arbre binaire pourra, par exemple, être codé par trois tableaux d"entierspere,fils_g, etfils_d, et une variableracine. On se donne un paramètre entierb?0. On se propose de construire l"arbre binaireAn,bà2n+ 1sommets, de la façon suivante. Les sommets sont nu- mérotés à partir de0, par ordre de création. On commence avec un arbre réduit à un sommet (numéroté0). Puis, pouriallant de1àn: - on sélectionne le sommet n ◦j, avecj=ui+bmodulo (2i-1); - on crée deux nouveaux sommets numérotés2i-1et2i; - le sommet n ◦2i-1prend la place du sommet n◦j, - et le sommet n ◦jdevient le fils droit (resp. gauche) du sommet n◦2i-1, siui+2best pair (resp. impair); - le sommet n ◦2iest une feuille et c"est l"autre fils du sommet n◦2i-1; - les relations entre les autres sommets restent inchangées. La figure ci-dessous illustre une étape de la génération. Les sommets internes y sont représentés par des cercles, et les feuilles par des carrés. Les nouveaux sommets et nouvelles arêtes sont représentés en gras.n°jn°jn°2i-1n°2i (ici, u i+2b est impair) Début de l'étape iFin de l'étape iQuestion 16Donnez l"arbreA4,1(qui compte9sommets). Lahauteurh(x)d"un sommetxest définie récursivement par :h(x) = 1, six est une feuille; eth(x) = 1 + max(h(fg),h(fd))sinon, oùfgetfddésignent respectivement les fils gauche et droit dex. Laprofondeurp(x)d"un sommet xest sa distance à la racine (en nombre d"arêtes). Question 17Quels sont le père, et les fils gauche et droit du sommet nu- méroté57dans l"arbreA130,2? Quelles sont sa hauteur et sa profondeur? Même question pour le sommet numéroté1430dans l"arbreA2450,3.

Question 18Calculez pour l"arbreA250,3:

H

250=500?

i=0h(i)etP250=500? i=0p(i). 5

Calculez pour l"arbreA2435,1:

H

2435=4870?

i=0h(i)etP2435=4870? i=0p(i).

6 Excursions et arbres binaires

Il existe une bijection entre les excursions de longueur2net les arbres binaires ànsommets internes (etn+1feuilles). SoitAun arbre binaire ànsommets internes. Associons à chaque sommetiun entierval(i)? {-1,1}. Si le som- metiest interne alorsval(i) = 1; sinon, c"est une feuille etval(i) =-1. Soit σ(0),...,σ(2n)les numéros des sommets deAparcourus en ordre préfixe (moi-puis-gauche-puis-droite). On démontre, par récurrence immédiate, que la suite(?A(i))i=0..2ndéfinie par?A(i) =?i-1 j=0val(σ(j)), est une excursion. NotonsE:A?→?Ala fonction qui à un arbre binaire associe son excursion. Remarquez que si on prolonge?Aen2n+ 1, on a?A(2n+ 1) =-1, indé- pendamment deA, car il y a toujours une feuille de plus que de sommets internes. La figure suivante donne un exemple de l"excursion associée à un arbre binaire.ABEDIJCHFGKLMABCDEFGHIJKLM Un arbre binaire...... et son excursion associée Les sommets sont étiquetés alphabétiquement

dans l'ordre du parcours préfixe de l'arbreQuestion 19Donnez l"excursion associée à l"arbreA4,1de la question 16.

Question 20Soite, l"excursion associée à l"arbreA130,2. Quelles sont les valeurs dee(121)ete(200)? Quel est la distance maximale entre deux records consécutifs dee? Mêmes questions pour les excursions associées aux arbres A

250,1etA2435,1.

La fonctionE:A?→?Aest en fait une bijection des arbres binaires àn sommets internes sur les excursions de longueur2n(on admet ce résultat). On s"intéresse maintenant à la fonction réciproqueE-1. 6 Question 21Déterminez les arbres binaires correspondants aux excursions eete?définies par : -e(i) =ipour0?i?n, ete(i) = 2n-ipourn?i?2n. -e?(i) = 0siiest pair, ete?(i) = 1siiest impair. Question 22Proposez un algorithme implémentant la fonction réciproque E -1deE, qui prend une excursion de longueur2net renvoie l"arbre binaire à nsommets internes associé. Justifiez votre algorithme et évaluez son nombre d"opérations en fonction den. Question 23Soitαl"arbre associé à l"excursione25,1(définition section 4). Quelle est la hauteur deα? Donnez la valeur de la somme cumulée des hau- teurs des sommets deα, et la somme cumulée des profondeurs des sommets deα. Mêmes questions pour les arbres associés àe250,1,e2051,0ete2057,23. - FIN - 7quotesdbs_dbs44.pdfusesText_44

[PDF] arbre binaire java

[PDF] retour ? l'unité proportionnalité

[PDF] le timbre d'un son

[PDF] psychologie criminelle cours pdf

[PDF] passage ? l'acte psychologie

[PDF] cours de criminologie générale pdf

[PDF] livre criminologie pdf

[PDF] tétraèdre régulier propriétés

[PDF] passage ? l'acte

[PDF] tétraèdre propriétés

[PDF] grille d'estimation de la dangerosité d'un passage ? l'acte suicidaire pondération

[PDF] intervenir auprès de la personne suicidaire ? l'aide de bonnes pratiques

[PDF] grille estimation dangerosité suicidaire

[PDF] grille d'évaluation de l'urgence suicidaire

[PDF] rapport d'intervention auprès de la personne suicidaire