16 jui 2014 · SUJET + CORRIGE Le but de l'exercice est l'écriture d'un algorithme de tri de tableaux (a) Vision tabulaire (b) Vision arborescente (1 point) Dessiner l' arbre des appels récursifs lors de l'appel padovanRecursif(7)
| Previous PDF | Next PDF |
[PDF] Exercice corrigé Arbre de décision - Ensiwiki - Grenoble INP
Exo_corrige-arbre_decision.pdf
[PDF] Chapitre 1 Les arbres de décisions - Maria Malek
EXERCICE 4 1 Donner les arbres de décisions qui expriment les fonctions Quel le gain de l'attribut a2 Corrigé 1 En appliquant : I(n, p)=( p p + n ) log2( Comparer l'arbre de décision calculé par ID3 avec les hypothèses trouvées selon l'
[PDF] Module 7 - Arbres de décisions Exercices - Corrigé
Exercices - Corrigé Les arbres de décisions des ensembles de données sont : 1 Affichage de l'arbre de décision complète de la base d'apprentissage
[PDF] Dénombrement sur les arbres binaires
Corrigé du TD 8 : Dénombrement sur les arbres binaires Dans cet exercice on notera n le nombre de nœuds d'un arbre binaire, f son nombre de feuilles et h sa hauteur Dans un arbre de décision chaque nœud interne est étiqueté
[PDF] Corrigé
Corrigé Exercice 1 (10 points) : Soit l'ensemble D des entiers suivants : On veut construire un arbre de décision à partir des données du tableau, pour rendre
[PDF] Arbres de décision Exercice 1 Exercice 2
Construire l'arbre de décision en utilisant la fonction gain basée sur l'entropie Page 2 2 Exercice 3 Une banque dispose des informations suivantes sur un
[PDF] Algorithmique I - École normale supérieure de Lyon
and analysis of algorithms, contient les notes de cours et exercices (certains Il y a exactement n feuilles dans tout arbre de décision d'un algorithme qui trie n
[PDF] Corrigé type (contrôle S5) - Université Larbi Ben Mhidi OEB
13 jan 2019 · Construction du plus petit arbre de décision possible Exercice 1 (4 5pts) : soit la matrice de décision suivante : E1 E2 E3 E4 D1 -250 -200
[PDF] Examen - Pr Abdelhamid Djeffal
27 jan 2014 · Expliquer comment peut-on obtenir les r`egles de décision apr`es la construction d'un arbre de décision Exercice 1 Motifs fréquents (8 pts : 4 +
[PDF] SUJET + CORRIGE
16 jui 2014 · SUJET + CORRIGE Le but de l'exercice est l'écriture d'un algorithme de tri de tableaux (a) Vision tabulaire (b) Vision arborescente (1 point) Dessiner l' arbre des appels récursifs lors de l'appel padovanRecursif(7)
[PDF] cours arbre de décision
[PDF] classification par arbre de décision
[PDF] arbre de décision exemple
[PDF] arbre de décision cart
[PDF] construire un arbre de décision
[PDF] arbre de décision définition
[PDF] dénombrement cours 1ere s
[PDF] apollon et daphné résumé
[PDF] apollon et daphné leur histoire
[PDF] expression etre nature
[PDF] tp mise en évidence d'une réaction d'oxydoréduction
[PDF] apollon et daphné peinture
[PDF] apollon et daphné le bernin
[PDF] tp chimie réaction d oxydoréduction
Ann ee Universitaire 2013/2014DST de Printemps
Parcours :Licence LIMI201 & LIMI211
Code UE :J1MI2013Epreuve :Algorithmes et ProgrammesDate :Lundi 16 juin 2014Heure :16 heures 30
Duree :2 heures
Documents : non autorisesEpreuve de M. AlainGriffaultCollegeSciences
etTechnologiesSUJET + CORRIGEAvertissement
A chaque question, vous pouvez au choix repondre par un algorithme ou bien par un programme python. Les inden tationsdes f onctions ecritesen Pythondoivent ^etre res- pectees. L'espace laiss ep ourles r eponsese stsusan t(sauf si v ousutilisez ces feuilles comme brouillon, ce qui est fortement deconseille).QuestionPointsScoreLe tri par tas28
Suite de Padovan12
Total:40
Exercice 1 : Le tri par tas (28 points)
Le but de l'exercice est l'ecriture d'un algorithme de tri de tableaux base sur la notion detas. Les questions se suivent logiquement, mais beaucoup sont independantes. (a) Des fonctions elementairesp ourse d eplacerdans un tableau. indice01234567T[indice]52601915
(a) Vision tabulaire[0] : 5 [1] : 2 [3] : 0 [7] : 5[4] : 1[2] : 6 [5] : 9[6] : 1 (b) Vision arborescenteFigure1 { Deux vues dierentes d'un m^eme tableau
La gure 1 montre qu'un m^eme tableau peut ^etredessineavec des casescontigues, ou bien avec des cases
disperseesdans unearborescence. Avec la vuecontigue, on utilise generalement une variableiquiparcourt
les indices du tableau. Avec la vuearborescente, on peut evidemment utiliser une variableiquiparcourtles
indices du tableau, mais on utilise egalement trois fonctions qui permettent de suivre lesliens bidirectionnels
(reels ou virtuels) de l'arborescence: {gauche(indice)represente les lienspointille du haut vers le basde l'arborescence. Par exemple, dans la gure 1b,gauche(1)=3,gauche(4)=9etgauche(2)=5. {droite(indice)represente les liensen trait plein du haut vers le basde l'arborescence. Par exemple, dans la gure 1b,droite(1)=4,droite(3)=8etdroite(0)=2. {pere(indice)represente les liensdu bas vers le hautde l'arborescence. Par exemple, dans la gure 1b,pere(4)=1,pere(7)=3etpere(2)=0. Par contrepere(0)n'est pas deni, et sa valeur (null,-1,0,...) importe peu car jamais utilisee dans cet exercice. UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2013/2014Voici un algorithme et un programmePython, de complexites en temps et en espace de (1), possibles pour
la fonctiongauche(indice).Gauche(i){
retourner 2*i+1; }defgauche( i ): return2i+1 i. (1 p oint) Ecrire un programmePythonou un algorithmedroite(i)qui retourne un entierdtel qu'il existe un lienen trait plein du haut vers le basreliant les indicesiad. Les complexites en temps et en espace doivent ^etre en (1).Solution:
defdroite ( i ): return2( i+1)ii.(1 p oint) Ecrire un programmePythonou un algorithmepere(i)qui retourne un entierptel qu'il existe un liendu bas vers le hautreliant les indicesiap. Les complexites en temps et en espace doivent ^etre en (1).Solution:
defpere ( i ): return( i1)//2(b)Construction d'un tas apartir d'un tab leau.Denition 1Un tas est un tableau d'entiers tel que pour tous les indicesistrictement positifs, la valeur
deT[i]est inferieure ou egale a celle deT[pere(i)]Le but de cette partie de l'exercice est d'eectuer la transformation representee par la gure 2.[0] : 5
[1] : 2 [3] : 0 [7] : 5[4] : 1[2] : 6 [5] : 9[6] : 1 (a) Vue arborescente du tableau initial[0] : 9 [1] : 5 [3] : 2 [7] : 0[4] : 1[2] : 6 [5] : 5[6] : 1 (b) Tas obtenu par constructionFigure2 { Construction d'un tas
i. (3 p oints) Ecrire un programmePythonou un algorithmeestunTas(T)qui retourneVraisi le tableauTest un tas,Fauxsinon.
La complexite en temps doit ^etre en
(1);O(n) avecn=longueur(T), et celle en espace doit ^etre en (1).Solution:
defestUnTas(T): foriinrange (1 , len (T)): ifT[ pere ( i )]Solution:
defmaximum(T, i , limite ): assert(0<=iandiT[ i ] = T[ j ]
T[ j ] = aux
Completer l'arborescence avec les valeurs du tableau apres l'appelentasserRecursif(T,0,8)Solution : [0] : 5 [1] : 5 [3] : 2 [7] : 0[4] : 1[2] : 9 [5] : 6[6] : 1 (a) Avant entasser[0] : 9 [1] : 5 [3] : 2 [7] : 0[4] : 1[2] : 6 [5] : 5[6] : 1 (b) Apres entasserFigure3 { Entasser(T,0,8)iv.(3 p oints)La fonction entasserRecursif(T,i,limite)est recursive terminale.
Ecrire un programmePythonou un algorithme iteratifentasser(T,i,limite)equivalent.Solution:
defentasser (T, i , limite ): iMax = maximum(T, i , limite ) whileiMax!= i : echange (T, i , iMax) i = iMaxiMax = maximum(T, i , limite )v.(1 p oint)Donner les complexit esen tem pset en espace (meilleur des cas e tpire des cas) d ev otre
algorithmeentasser(T,i,limite).Page 3 sur 7
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2013/2014Solution:
Les complexites sont :
en temps en (1) ;O(log2(n)) avecn=longueur(T),en espace en (1). vi.(4 p oints)L'algorithme entasser(T,i,limite)echange des valeurs du tableau de haut en bas,en
suivant une branche de l'arborescence. Cela a pour eet de fairedescendredes petites valeurs, et defairemonterles grandes valeurs. Il est donc possible de construire un tas, en iterant cet algorithme sur
les indices decroissants du tableau. En utilisantentasserRecursif(T,i,limite)ouentasser(T,i,limite), ecrire un programmePython ou un algorithmeconstruireTas(T)qui transforme un tableau en un tas.Solution:
defconstruireTas (T): #for i in range( len (T)1,1,1): peut etre optimise en foriinrange (( len (T)1)//2,1,1):entasser (T, i , len (T))vii.(1 p oint)Donner les complexit esen temps et en espace ( meilleurdes cas et pire des cas) de v otre
algorithmeconstruireTas(T).Solution:
Si l'on utilise l'algorithme iteratif pourentasser, les complexites sont : en temps en ( n) siTest deja un tas,O(nlog2(n)) avecn=longueur(T), en espace en (1). (c)T rid'un tas.Le but de cette partie de l'exercice est d'eectuer la transformation representee par la gure 4.[0] : 9
[1] : 5 [3] : 2 [7] : 0[4] : 1[2] : 6 [5] : 5[6] : 1 (a) Tas initial[0] : 0 [1] : 1 [3] : 2 [7] : 9[4] : 5[2] : 1 [5] : 5[6] : 6 (b) Vue arborescente du tableau trieFigure4 { Tri d'un tas
i. (4 p oints)Dans un tas, la v aleurmaximale est ala racine de l'arborescence, donc enT[0]. Dans le tableau trie, cette valeur doit ^etre enT[len(T)-1]. Il sut donc d'echanger ces deux valeurs pourprogresser vers la solution. Une fois cette echange fait, si l'on exclut la derniere valeur du tableau, le tas
est peu change. En faitentasser(T,0,len(T)-1)va creer un nouveau tas pour les valeurs du tableau dont les indices sont inferieurs alimite = len(T)-1. Il sut donc d'iterer ces deux etapes (echange, entasser) pour trier un tas. Ecrire un programmePythonou un algorithmetrierTas(T)qui transforme un tas en un tableau trie en ordre croissant.Solution:
deftrierTas (T): foriinrange ( len (T)1,0,1): echange (T,0 , i ) entasser (T,0 , i )Page 4 sur 7 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2013/2014 ii. (1 p oint)Donner les complexit esen temps et en espace (meilleur des cas et pire d escas) de v otre algorithmetrierTas(T).Solution:
Si l'on utilise l'algorithme iteratif pourentasser, les complexites sont : en temps en ( n) si toutes les valeurs deTsont egales,O(nlog2(n)) avecn=longueur(T), en espace en (1). (d)T rid'un tableau al'aide de tas. i. (3 p oints) Ecrire un programmePythonou un algorithmetriParTas(T)qui trie un tableau d'entiers Ten construisant d'abord un tas, puis en le triant.Solution:
deftriParTas (T): construireTas (T)trierTas (T)ii.(1 p oint)Donner les complexit esen temps et en espace (meilleur des cas et pire d escas) de v otre
algorithmetriParTas(T).Solution:
Si l'on utilise l'algorithme iteratif pourentasser, les complexites sont : en temps en ( n) si toutes les valeurs deTsont egales,O(nlog2(n)) avecn=longueur(T), en espace en (1). iii.(1 p oint)V otrealgorithme triParTas(T)eectue t-il un tri stable? Justier.Solution:
Non, car il eectue des echanges de valeurs avec des indices non consecutifs.Exercice 2 : Suite de Padovan (12 points)
La suite (ou fonction) de Padovan d'un entier naturel est denie par :Padovan(n) =8
>:1 sin= 01 sin= 1
1 sin= 2
Padovan(n2) +Padovan(n3) sinon
(a) i . (3 p oints) Ecrire un programmePythonou un algorithme recursifpadovanRecursif(n)qui retourne la valeurPadovan(n).Solution:
defpadovanRecursif (n ): assert (n>=0) ifn<3: return1 else:returnpadovanRecursif (n2) + padovanRecursif (n3)ii.(1 p oint)Dessiner l'arb redes app elsr ecursifslors de l'app elpadovanRecursif(7).
Solution:Page 5 sur 7
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2013/2014 pad(7) : 5pad(5) : 3pad(3) : 2pad(1) : 1pad(0) : 1 pad(2) : 1 pad(4) : 2pad(2) : 1pad(1) : 1 iii.(1 p oint)En in terpretantl'arbre d esapp elsr ecursifset notammen tla longueur de ses branc hes,donner
un encadrement du nombre d'appels recursifs, pour en deduire la complexite (temps et espace) de votre
algorithme recursif.Solution:
La plus longu ebranc he(la plus agau che)d el'arbre des app elsa une longueur de n=2. Le nombre d'appels est donc inferieur a 2 n=2 La plus courte branc he(la plus adroite) de l'arbre des app elsa une longueur de n=3. Le nombre d'appels est donc superieur a 2 n=3La complexite :
en temps est comprise en tre 3p2 n) etO(p2 n). en espace est de ( n). non demande :La complexite en temps est en ( n) avec denommele nombre plastique, quiest l'unique solution reelle deX3=X+ 1, et environ egal a 1;3247179572.(b)(4 p oints)P aranalogie a vecla fonction Fibonacci(n)vue en cours, il est possible de transformer cette fonc-
tion recursive en une fonction recursive terminale. Pour cela, il faut ajouter trois parametres qui contiennent
trois valeurs consecutives de la suite. A chaque appel recursif : deux son tmo diespar decalage,le troisi emeest obten upar l'addition de deux parmi les trois. Ecrire un programmePythonou un algorithme recursif terminalpadovanRecTerminal(n,u,v,w)qui re-
tourne la valeurPadovan(n), et preciser l'appel initial.Solution:
defpadovanRecTerminal(n, u=1, v=1, w=1): assert (n>=0) ifn==0: returnu elifn==1: returnv elifn==2: returnw else:returnpadovanRecTerminal(n1,v ,w, v+u)(c)i. (2 p oints)T ransformerautomatiquementvotre solution recursive terminale, an d'obtenir un pro-
grammePythonou un algorithme iteratifpadovanIteratif(n)qui retourne la valeurPadovan(n).Solution:
defpadovanIteratifAutomatique (n ): assert (n>=0) u=1 v=1 w=1 whileTrue : ifn==0: returnu elifn==1: returnvPage 6 sur 7 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2013/2014 elifn==2: returnw else: # n,u,v ,w = n1,v ,w, v+u n = n1 aux = u u = v v = ww = u+auxii.(1 p oint)Donner les complexit esen temps et en espace (meilleur des cas et pire d escas) de v otre
solution iterative.