UNIVERSITE SAAD DAHLAB _ BLIDA
1
FACUI -., I DES SCIENCES
DEPARTEMCNT D'INFORMATQUE
CONCQURS D'ACCES A LA FORMATION DE
TROISIEME CYCLE
EN vUE DE L'OBTENTION DU DOCTORAT E,N
INFORMATIQUE
AU TTIRE DE T,'ANIIEE UNIVERSTTAIRE 20T9,/2020
EPREUVE D'ALGORITHMIQUB AVAI\CE]O
ExerciceI(f0pts)
Y Daa" Ies quesaons à choix rcponses.
Y oans une guestion à répon éIimtne uaetépwe ju*e.
1' comment calcule-t-on ra complexité d'u' algorithme
récursif ?
A. On iance plusieurs fois I'algorithme avec différentes taillss de
données.
B. on établit puis on résout une formure de récurrence.
c' on traduit I'algorithme en algorithme itératif et on regarde les boucles.
D. On calcr:le des probabilités.
2. un algorithme déterminisre est un algorithme dont la sorurion est :
A. Déduite à partir de ses spécifications. C. [Link]
B. Devinée puis vérifiée. D. Diffrcilement rrouvable
3. Un algorithme non détermin;ste est un algorithme
dont Ia solution est i
A Déduite à parrir de ses spécifications. C. Introuvable
B. Devinée puis vérifiée. D. Difficilement rrouvab,le
-)
La classe P regroupe tous les problèmes de décision
qui peuvent être résolus
A. un algorithme déterministe de complexité polynomiale
p'r:
B. un algorithme déterministe de comp
C. u:r algorithme non déterministe de c a_le
D. un algorithme non déterministe de cor,,pi.-rité e>gonenr_ielle
5' La classe NP regroupe tous les problèmes de décision
qui peuvent être résolus par:
lynomiale
onenrielle
é polynomiale
é exponentielle
6' soient A et B deux problèmes de décision d.e classe Np, et supposons qu,on connnisse
transfonnation polynomiale (une réduction) de un€
A en ts. Lesqueues de ces propositjLons sonr waies ?
A' A est plus difficile que B' D. si on
B. SiAe PalorsBe p. une ffansforrnation
"oo',"it
de B en A alors A et B sont
c. siA eNp-compleralorsB eNp_compre'.,a +-- :iffiïie
E. B est plus difficile que A,
r/4
F. SiBePalorsAe p. H. Si A et B sonr Np-Co,mplet alors il
G. Si B eM-complet alors A eM_complet. existe
u-ne tansformation polynomiale de B en A
7. Soient les classes de cdmplexité suivanres: p.
NP, NP-cornplet et Np-diffici-le, lesquelles de
propositions sont vraies ? ces
A. P cNP F. NPcp
B. NP c NP-Compler
G. NP-Complet c Np
C. NP-Compler n Np-Diffrcile = A
H. NP-Complet n Np-D jiffrctle + A
D. P rr NP- Complet= e
L PnNP-Complet+A
E. P c NP- M-Completc Np_Difficile
I. NP- Difficile c NP-CompletcNPcp
8' Da's u'' problème K-SAT, toutes les crauses {{}.rtiennent
A. au moins k littéraqx B. au plus k littéraux C. exar:tement k littéraux
9' Dans u,l problème MAx-sAT, il s'agit de trouver ule affectation des variables bocùéennes qui
A. minimise le nombre des clauses à faux. C. évalue toutes les clauses à wai.
B. maximise le nombre des clauses à faux. D. évalue toutes les clauses à faux.
10. Soit la clause C= p v e. Elle est équivalente à
A. (P v Qvyl) n (-.yl vp ve)
C. (P v -Y1) n (yt ve)
B. PvQvT D. Q.
1i. Poru un problème 3-SAT contenant n variables
booléennes et m clauses, on peut construire u:r graphe
3-coloriable qui contient :
A. (3+2n+5m>sommets. D. u2n+5m>sommets.
B. <2m+lutriangles. E. o2n+1>triangles,
C. ( m ) motifs 3-coloriable, F. < n >motifs B-coloriable.
,? description de chaque paradi
a. panitiomrer èmes inrlépendants qui
dynamique sont résolus d ombiner leurs solutions
pour résor;,L, : le problème [Link]
B. Diviser pour régner b. Définir .;.1igorithme en toncrion de lui_même.
C. Récursivité c. Construire la solution optimale pas à pas,
D. Approche d' Partitionaer le problème en sous-problèmes q'i
gloutonne ne sonr pas
forcément indépendants, puis combiner leurs
solutions pour
résoudre le problème initial.
13. Trouver Ieprincipe de chaque algorithme de tri
A. Tri par a' Permuter tous les éIéments de telre èotte que tous ceux qui
Sélection sont
inférieurs au pivot soient à sa gauche et que
tous ceux qui sont supérieurs
au pivot soient à ca droite.
B. Tri à bulles b. Insérer un él{",-1;ir dans une Ii r d'éléments déjà triés.
C. Tri par c. Inverser deux éléme'ts successifs s'ils ne sort pas classés dans
Insertion Ie bon
ordre et de recommenceï jusqu'à ce qu'on ne peut plus
inverser.
2/4
D, Tri par TAS )
{.1.
en un binaire dle
E. Tri Rapide de I'ar
e.
Ieauàh;JJ:,,. '"lm:
le tableau soit entièrement
F. Tri par ABR trié.
G. Tri par Fusion :' j*"ï* deux tabreaux triés de sorte
à ce que le tabreau final
soit trié.
" Ë' lransïorner r-, ,*bleau en
un al'bre binaire parfait clont
le minimum se
à la racine, ensuite exrraire
la racinË;[Link],i ;;q,re t,arbre
ï::* soir
14. Parmi ces algorithmes
de tri, lesquels utilisent le paradigme ,'Diviser
A. Bulles pour Régner" ?
c' RaPide E. Fusion
B. Insertion D. Sélection G. ABR
F, TAS H. Aucun
15. Une heuristique
A. est une règle empirique basée
sur l,expérience.
basée sur des concepts théorigues.
Ë. écificité du pr.r,hle.r;re traité.
D. re absûaire, san, f"ire appel
à un problème spécifique.
16' Trouver la bonne description
de chaque rnéthode pour
A' Méthode résoudre
exa*e problème d,optimisation
a, penner de rrouver iorr;o*, ra sorution
'n optimare.
, b. pennet trouver ule bonae solution (presque
d.e
optimale).
c. nécessite un temps d,exécution
raisonnable.
B' méta-
Méthode d. nécessire un remps d,exécution prohibirif.
heuristique
e' se base sur une exploration complète
de respace de sojution.
f ' se base rH
lrl"
,,:xprorarion pru derJe
et guidée cle l,espace de solution.
I"es parties soat indépndantes
1' Expliquer la propriété d'ordre
(la relation d'ordre entre
stnrcture'e de chacua de ces ia vareur du père et ses flrs)
arbres : AVL, TAS.i. et B-arbre et la propriété
d,ordre m.
Arbres À'n-rl-o
AVT
Propriété sructortt.
I4Ér."--
B-arhro À'n-À-^
2. Qgelie est Ia complexité
arbres : AVL, TASnin er B ion et de suppression de chacul
de ces
L nombre des næuds et << m >
pré Parml ces propositions lio n u présente le
A. O(n) îc' o(n-m)
B. o(m) ^, E. o(tog^n)
D. O (n + m)
F. O (tognm)
3/4
Arbres ion d'Insertion Upératiou de suDoressin-
AVI.
TAS,u
B-arbre
@tfqle arbres suivanrs:
ARBRE 1
[Link]-!
43TBE!
A. ABR (Arbre Binaire de Recherche)
C. AVL
B. AMR (Arbre M-aire de Recherche)
D. TAS
2. Donnsl I'ordre de chacrrn E. B_arbr,e
de ces arbres.
3. Insérer la valeur < 60
> [Link] chacu_n a" arbres tout en préservant leur rype (Montrer
étapes uécessaireq). "u, toutes les
4. Supprimer la valeur o 30 , de chacun
leur type (Montrer toutes out en préservant
les étapes nécessaires)
4/4
