EA4 – Éléments dalgorithmique Examen de 2e session

8 juin 2006 3 Arbres binaires de recherche (ABR). Exercice 4 (Insertion). Décrire en quelques lignes le principe de l'algorithme d'insertion d'un.

Cours dAlgorithmique et structures de données 1

29 janv. 2012 2.3 Règles de calcul de la complexité d'un algorithme . ... 4.2 Les arbres binaires de recherche . ... 8 Sujets d'examens.

Arbres et récursivité

1 juil. 2020 Écrire un algorithme qui insère rB à la première place trouvée dans A (à la place d'un fils Nil). Exercice 3 (Arbres binaires de recherche (ABR)).

TP 8 : Arbres binaires de recherche

Exercice 1. Définir une structure struct noeud_s permettant de coder un n÷ud d'un arbre binaire contenant une valeur entière. Ajouter des typedef pour

Algorithmique & programmation en langage C - vol.2 - Archive

14 juil. 2015 Le volume horaire d'un (ou même de deux) cours classique(s) ne permet ... 15 Algorithmes pour l'arithmétique ... Arbre binaires de recherche.

Algorithmique I - Cours et Travaux Dirigés L3 Ecole Normale

1.7 Exercices . 6.2.3 Arbres binaires de recherche . ... hauteur : log3!n ? nlog3n donc la complexité dans le pire cas de l'algo est de : ?(n × logn).

Algorithmique I - Cours et Travaux Dirigés L3 Ecole Normale

Question 3.9 Donner un algorithme en temps O(n3) pour construire un arbre binaire de recherche optimal pour une séquence dont les nombres d'acc`es aux clés sont

Algorithmique Les arbres

Pour tout arbre binaire de taille n et de hauteur h : h ? n ? 2h ? 1. Page 31. 19 de 1.

Examen (2 heures)

Ces détails sont à lire après l'examen (ou pendant si vous vous ennuyez). ... structure(a1a2) qui teste si deux arbres binaires ont la même structure

EA4 – Éléments dalgorithmique Examen de 2e session – 23 juin 2016

Exercice 7 : autour des 2D-arbres. Un 2D-arbre est un arbre binaire dont chaque nœud r contient un point (xryr)

L2 Informatique Année 2015-2016

EA4 - Éléments d"algorithmique

Examen de 2

esession - 23 juin 2016

Durée : 3 heures

Aucun document autorisé excepté une feuille A4 manuscrite Appareils électroniques éteints et rangés PréliminairesTous les exercices proposés ici sont des applications directes du cours,

ou ont déjà été posés en TD, au partiel ou en première session; vous devriez donc savoir

répondre à toutes les questions; si ce n"est pas le cas, mieux vaut vous abstenir plutôt que

d"écrire n"importe quoi; en particulier, pensez à vérifier sur un (ou des!) exemple(s) que vos algorithmes ont le comportement attendu; veillez également à ne pas contredire fron-

talement les théorèmes du cours; et bien entendu,lisezl"énoncé pour éviter de répondre

à des questions différentes de celles posées. Sauf mention contraire explicite, toutes les réponses doivent être justifiées. En l"absence de précision, les complexités demandées sont les ordres de grandeur()des complexités en temps dans le pire cas des algorithmes concernés. Vous êtes libres du langage utilisé pour décrire les algorithmes demandés, du moment que la description est suffisamment précise et lisible : python, pseudo-code, français, java...

Exercice 1 : algorithmes de tri

1.Rappeler, sans démonstration, les complexités en temps

(a) dans le pire des cas (b) dans le meilleur des cas (c) en moyenne des algorithmes de tri par sélection, par insertion, par fusion, tri rapide et tri par tas. 2. a. Rappeler, sans démonstration, quelle est la hauteur moyenne des ABR obtenus par insertion successive des entiers de 1 ànselon toutes les permutations de taillen. b.Expliquer comment en déduire la complexité moyenne du tri rapide pour les ta- bleaux de taillen.

Exercice 2 : hachage

On considère deux tables de hachageH1etH2de longueur11, dans laquelle on place des valeurs entières, en utilisant la fonction de hachageh(x) =xmod 11. H

1est une table à adressage fermé, pour laquelle les collisions sont résolues par chaînage.

2est une table à adressage ouvert, avec résolution des collisions par sondage linéaire.

Répondre aux questions suivantes pour chacune des deux tables : a.Insérer successivement les entiers26;7;34;20;38;49;18;15. b.Combien de comparaisons nécessite alors l"insertion de la valeur 37 dans la table? c.Comment supprimer la valeur 49 de la table? d.Comment se passe ensuite la recherche de la valeur 37? 1

L2 Informatique Année 2015-2016

Exercice 3 : répétitions

On s"intéresse (encore et toujours) au problème suivant : étant donné une listeLden éléments, compter les valeurs qui apparaissent au moins deux fois dansL. L"exercice se base cette fois-ci sur certain de vos algorithmes (incorrects, hélas) de première session.

1.Pourquoi l"algorithme suivant est-il incorrect?

def repetitions_naif(L) : cpt, l = 0, len(L) for i in range(l) : for j in range(i+1, l) : if L[i] == L[j] : cpt += 1 return cpt

2.À quelle condition surLl"algorithme suivant est-il correct? Calculer sa complexité

dans ce cas, en précisant quelles opérations élémentaires sont prises en compte. def repetitions_par_comptage(L) : cpt, m = 0, max(L)+1 tab = [0] * m for elt in L : tab[elt] += 1 for nb in tab : if nb >=2 : cpt += 1 return cpt

3.Proposer une version corrigée derepetitions_naif, puis calculer sa complexité, en

précisant à nouveau quelles opérations élémentaires sont prises en compte.

4.Proposer un algorithme inspiré derepetitions_par_comptageadapté au cas général.

Quelle est sa complexité dans le pire cas? Rappeler (sans démonstration) sa complexité en moyenne.

5.Proposer enfin un algorithme de complexité strictement meilleure dans le pire cas, et

justifier sa complexité.

Exercice 4 : fusion de listes triées

1.Rappeler (sans démonstration) l"algorithme optimal de fusion de deux listes triées.

2.En déduire un algorithme de complexité(kn)permettant de fusionnerklistes triées,

oùnest la longueur de la liste fusionnée,sans créer d"autre liste que la liste fusionnée.

3.En utilisant un tas auxiliaire, proposer un algorithme plus efficace. Quelle est sa com-

plexité?

4.Comment obtenir la même complexité sans tas auxiliaire, en s"autorisant à créer des

listes intermédiaires? 2

L2 Informatique Année 2015-2016

Exercice 5 : minimum d"un tableau circulairement trié On considère ici des tableauxTd"entierssans doublonetcirculairement triés, c"est-à-dire pour lesquels il existe un indiceitel queT[i:] + T[:i]est trié (en ordre croissant).

Dans la suite,Tdésigne un tel tableau.

1.Décrire un algorithmeminimum_naif(T)de complexité linéaire en la longueur deT

pour déterminer l"indice de son élément minimum.

2.Comment tester la monotonie d"un sous-tableauT[i:j]deTen temps constant?

3.On suppose qu"il existe un indicektel queT[:k]est monotone mais pasT[k:]. Que

peut-on en déduire? Étudier les autres cas possibles.

4.En déduire un algorithme de complexité strictement meilleure queminimum_naif(T)

pour déterminer l"indice du minimum d"un tableau circulairement trié. Justifier sa complexité. Exercice 6 : création de tas-max et tri par tas Comme promis, un exercice pour expliquer pourquoi l"algorithme classique de création de tas ne consiste pas en une succession d"ajouts.

1.On considère un arbre binaireparfaitAde hauteurh.

a.Combien cet arbreApossède-t-il de feuilles? de sommets (noeuds et feuilles)? b.Soitsun sommet quelconque deA. Donner un majorant de la profondeur et de la hauteur des. En déduire une borne pour l"ordre de grandeur de la somme des profondeurs (ou celle des hauteurs) des sommets deA. c.Quelle est la profondeur d"une feuille deA? En déduire que la somme desprofondeurs des sommets est en (h2h). d.Rappeler (sans démonstration) quel est l"ordre de grandeur de la somme deshau- teursdes sommets deA.

2.Rappeler l"algorithmeajout_tas(elt, tas)d"ajout d"un élément dans un tas, ainsi

que sa complexité.

3.En déduire la complexité de l"algorithme suivant :

def creation_tas(T) : tas = [] for elt in T : ajouter(elt, tas) return tas

4.Rappeler enfin l"algorithme de création de tas vu en cours, ainsi que sa complexité.

Conclure.

5.Et enfin, question bonus : pourquoi un tas-max et non un tas-min pour le tri par tas?

L2 Informatique Année 2015-2016

Exercice 7 : autour des 2D-arbres

Un 2D-arbre est un arbre binaire dont chaque noeudrcontient un point(xr;yr), tel que : si rest situé à uneprofondeur paire, alors tout point contenu dans son sous-arbre gauche a une abscissex < xr, et tout point contenu dans son sous-arbre droit a une abscissex > xr; si rest situé à uneprofondeur impaire, alors tout point contenu dans son sous-arbre gauche a une ordonnéey < yr, et tout point contenu dans son sous-arbre droit a une ordonnéey > yr.

1.Expliquer pourquoi l"arbre de hauteur 3 ci-dessousn"est pasun 2D-arbre.profondeur0profondeur1profondeur2profondeur3(8,1)(7,4)(3,7)(13,5)(4,2)(1,8)(10,6)(en grisé, les noeuds à profondeur impaire; la racine est à profondeur 0, donc paire)

Dessiner deux 2D-arbres contenant les mêmes points que cet arbre, l"un de hauteur minimale, l"autre de hauteur maximale.

2.Décrire un algorithme (récursif)recherche2Darbre(A, p)testant l"appartenance d"un

pointpà un nuage représenté par un 2D-arbreA. Quelle est sa complexité siAest de taillenet de hauteurh?(il pourra être commode d"utiliser un paramètre optionnel supplé- mentaire pour tenir compte du niveau :recherche2Darbre(A, p, niveau = 0))

3.SoitNun tableau denpoints, etAun 2D-arbre de hauteurminimalecontenant les

mêmes points queN. Quelle est la hauteur deA? Quel pointrse trouve à sa racine? Quels pointsgetdsont à la racine de son sous-arbre gauche et de son sous-arbre droit? Rappeler, sans démonstration, la complexité (au pire et en moyenne) de l"algorithme vu en cours permettant de calculerrà partir deN.

4.Pour faciliter le calcul der,getd, on suppose queNa été préalablement trié selon les

abscisses croissantes (tableauNx)etselon les ordonnées croissantes (tableauNy). Avec quelle complexité peut-on alors trouverr? Décrire un algorithme de partitionnement deNxetNypermettant de faire de même pour trouvergetd. Quelle est sa complexité?

5.En déduire un algorithmeconstruire2Darbre(P)permettant de construire un 2D-

arbre de hauteur minimale à partir d"un tableau de pointsPet déterminer sa com- plexité. 4quotesdbs_dbs45.pdfusesText_45

[PDF] EA4 – Éléments dalgorithmique Examen de 2e session – 23 juin 2016

L2 Informatique Année 2015-2016

EA4 - Éléments d"algorithmique

Examen de 2

Durée : 3 heures

Exercice 1 : algorithmes de tri

1.Rappeler, sans démonstration, les complexités en temps

Exercice 2 : hachage

1est une table à adressage fermé, pour laquelle les collisions sont résolues par chaînage.

2est une table à adressage ouvert, avec résolution des collisions par sondage linéaire.

L2 Informatique Année 2015-2016

Exercice 3 : répétitions

1.Pourquoi l"algorithme suivant est-il incorrect?

2.À quelle condition surLl"algorithme suivant est-il correct? Calculer sa complexité

3.Proposer une version corrigée derepetitions_naif, puis calculer sa complexité, en

4.Proposer un algorithme inspiré derepetitions_par_comptageadapté au cas général.

5.Proposer enfin un algorithme de complexité strictement meilleure dans le pire cas, et

Exercice 4 : fusion de listes triées

1.Rappeler (sans démonstration) l"algorithme optimal de fusion de deux listes triées.

2.En déduire un algorithme de complexité(kn)permettant de fusionnerklistes triées,

3.En utilisant un tas auxiliaire, proposer un algorithme plus efficace. Quelle est sa com-

4.Comment obtenir la même complexité sans tas auxiliaire, en s"autorisant à créer des

L2 Informatique Année 2015-2016

Dans la suite,Tdésigne un tel tableau.

1.Décrire un algorithmeminimum_naif(T)de complexité linéaire en la longueur deT

2.Comment tester la monotonie d"un sous-tableauT[i:j]deTen temps constant?

3.On suppose qu"il existe un indicektel queT[:k]est monotone mais pasT[k:]. Que

4.En déduire un algorithme de complexité strictement meilleure queminimum_naif(T)

1.On considère un arbre binaireparfaitAde hauteurh.

2.Rappeler l"algorithmeajout_tas(elt, tas)d"ajout d"un élément dans un tas, ainsi

3.En déduire la complexité de l"algorithme suivant :

4.Rappeler enfin l"algorithme de création de tas vu en cours, ainsi que sa complexité.

Conclure.

5.Et enfin, question bonus : pourquoi un tas-max et non un tas-min pour le tri par tas?

L2 Informatique Année 2015-2016

Exercice 7 : autour des 2D-arbres

1.Expliquer pourquoi l"arbre de hauteur 3 ci-dessousn"est pasun 2D-arbre.profondeur0profondeur1profondeur2profondeur3(8,1)(7,4)(3,7)(13,5)(4,2)(1,8)(10,6)(en grisé, les noeuds à profondeur impaire; la racine est à profondeur 0, donc paire)

2.Décrire un algorithme (récursif)recherche2Darbre(A, p)testant l"appartenance d"un

3.SoitNun tableau denpoints, etAun 2D-arbre de hauteurminimalecontenant les

4.Pour faciliter le calcul der,getd, on suppose queNa été préalablement trié selon les

5.En déduire un algorithmeconstruire2Darbre(P)permettant de construire un 2D-