3GSI Département Informatique, Faculté des Sciences, USDB 2013-2014
Rattrapage Algorithmique 2
Durée 1,5 H
Documents Interdits
Version A
Matricule Nom Prénom Groupe
Exercice 1 (4 points): Relier les bonnes réponses
1. Trouver la O-notation de chaque classe de complexité (1 point)
a. Polynomiale A. O(n)
b. Linéaire B. O(nP)
c. Quasi-linéaire C. O(n2)
d. Quadratique D. O(n log(n))
e. Logarithmique E. O(an)
f. Exponentielle F. O(log(n))
2. Trouver le principe de chaque algorithme de tri (1.75 point)
a. Placer le plus petit élément au début du tableau, puis le second plus A. Tri par ABR(Arbre
petit élément du tableau à la deuxième position et ainsi de suite jusqu'à Binaire de
ce que le tableau soit entièrement trié. Recherche)
b. Insérer un élément dans une liste d'éléments déjà triés. B. Tri à bulles
c. Inverser deux éléments successifs s'ils ne sont pas classés dans le bon C. Tri par Insertion
ordre et de recommencer jusqu'à ce qu’on ne peut plus inverser.
d. Faire un parcours infixe d’un arbre binaire de recherche. D. Tri par TAS
e. Permuter tous les éléments de telle sorte que tous ceux qui sont E. Tri Rapide
inférieurs au pivot soient à sa gauche et que tous ceux qui sont
supérieurs au pivot soient à sa droite.
f. Fusionner deux tableaux triés de sorte à ce que le tableau final soit trié. F. Tri par Sélection
g. Transformer le tableau en un arbre binaire complet dont le minimum se G. Tri par Fusion
trouve à la racine.
Aroussi Bon Courage
3. Trouver la bonne description de chaque paradigme de programmation (0.5 point)
a. Combiner les solutions de sous-problèmes communs par A. Dérécursivation
une approche ascendante
b. Définir un algorithme en fonction de lui-même. B. Approche gloutonne
c. Construire la solution optimale pas à pas. C. Récursivité
d. Transformer un algorithme récursif en un algorithme D. Diviser pour régner
itératif.
4. Trouver la définition de chaque type de récursivité (0.75 point)
a. Algorithme contient un seul appel récursif dans son corps. A. Simple
b. Algorithme fait un appel récursif à l'intérieur d'un autre appel B. Multiple
récursif.
c. Algorithme n’effectue aucun traitement à la remontée d'appel C. Mutuelle
récursif.
d. Algorithme contient plus d'un appel récursif dans son corps. D. Imbriqué
e. Algorithmes récursifs dépendent les unes des autres. E. Terminal
f. Algorithme effectue un traitement à la remontée d'appel F. Non terminal
récursif.
Exercice 2 (9 points): cocher la ou les bonnes réponses
1. Comment calcule-t-on généralement la complexité d'un algorithme récursif ? (0.25 point)
A. On lance plusieurs fois l'algorithme avec différentes tailles de données.
B. On établit puis on résout une formule de récurrence.
C. On traduit l'algorithme en algorithme itératif et on regarde les boucles.
D. On calcule des probabilités.
2. La recherche par dichotomie dans un tableau de taille n se fait en ……. étapes. (0.25 point)
A. Log2(n) A. n B. n2 C. 2n
3. Parmi ces algorithmes de tri, lesquels utilisent le paradigme "Diviser pour Régner" ? (0.5 point)
A. Bulles C. Rapide E. Fusion G. ABR
B. Insertion D. Sélection F. TAS
4. Parmi ces algorithmes de tri, lesquels s'exécutent en temps quadratique? (1.25 point)
A. Bulles C. Rapide E. Fusion G. ABR
B. Insertion D. Sélection F. TAS.
Aroussi Bon Courage
3GSI Département Informatique, Faculté des Sciences, USDB 2013-2014
5. Parmi ces algorithmes de tri, lesquels s'exécutent en temps quasi-linéaire? (0.75 point)
A. Bulles C. Rapide E. Fusion G. ABR
B. Insertion D. Sélection F. TAS
6. Parmi ces algorithmes de tri, lesquels transforment le tableau initial à un arbre binaire? (0.5 point)
A. Bulles C. Rapide E. Fusion G. ABR
B. Insertion D. Sélection F. TAS
7. Quelle est, approximativement, la hauteur d'un arbre binaire équilibré à n nœuds ? (0.25 point)
A. Log2 n. B. n/2. C. 2n. D. n.
8. Lesquelles de ces structures d’arbre garantit une complexité au pire en O(log 2n) pour l’insertion de n
éléments ? (0.75 point)
A. Arbre binaire de recherche (ABR). C. Arbre rouge-noir
B. Arbre AVL D. TAS
9. L'intérêt du tri par tas, comparativement aux autres algorithmes de tri, est : (0.25 point)
A. sa complexité en meilleur cas C. sa complexité en pire cas
B. sa complexité moyenne D. la place mémoire nécessaire.
10. Combien de nœuds possède un arbre binaire complet de n feuilles ? (0.25 point)
Aucune réponse n’est juste
A. 2n+1 B. 2n − 1 C. 2n D. 2n+1 – 1
11. Un problème de décision est un problème: (0.25 point)
A. dont la réponse est oui/non C. qui cherche une solution optimale
B. qui optimise une fonction objectif D. NP-Complet
12. La classe P regroupe tous les problèmes de décision qui peuvent être résolus par : (0.25 point)
A. un algorithme déterministe de complexité polynomiale
B. un algorithme non déterministe de complexité polynomiale
C. un algorithme déterministe de complexité exponentielle
D. un algorithme non déterministe de complexité exponentielle
13. Un algorithme déterministe est un algorithme dont la solution est : (0.25 point)
A. Déduite à partir de ses spécifications. C. Introuvable
B. Devinée puis vérifiée. D. Difficilement trouvable
Aroussi Bon Courage
14. Un algorithme est efficace si sa complexité en temps est : (0.75 point)
A. Polynomiale B. Linéaire C. Quadratique D. Quasi-linéaire
15. Un algorithme non déterministe est un algorithme dont la solution est : (0.25 point)
A. Déduite à partir de ses spécifications. C. Introuvable
B. Devinée puis vérifiée. D. Difficilement trouvable
16. La classe NP regroupe tous les problèmes de décision qui peuvent être résolus par : (0.25 point)
A. un algorithme déterministe de complexité polynomiale
B. un algorithme non déterministe de complexité polynomiale
C. un algorithme déterministe de complexité exponentielle
D. un algorithme non déterministe de complexité exponentielle
17. Quelle est la relation entre les deux classes P et NP ? (0.5 point)
A. P= NP B. P≠NP C. P NP D. NP P
18. Si le problème A se réduit au problème B, alors (0.5 point)
A. A est plus facile que B. C. B est plus difficile que A.
B. B est plus facile que A. D. A est plus difficile que B.
19. Parmi ces propositions, lesquelles sont vraies ? (0.5 point)
A. Si A B, et si B P alors A P. C. Si A B, et si B P alors A P.
B. Si A B, et si A P alors B P. D. Si A B, et si A P alors B P.
20. Un problème E est dit NP-complet, si (0.5 point)
A. E NP B. E NP C. F NP, F E D. F NP, E F
Exercice 3 (3, 2, 1, 1 points):
On considère le problème consistant à rendre n centimes (d'euro) en monnaie, en utilisant le moins de
pièces possible.
1. Décrire un algorithme glouton permettant de rendre la monnaie en utilisant des pièces de cinquante,
vingt, dix, cinq et un centime. Calculer sa complexité.
Trier les valeurs de pièces par ordre décroissant. Pour chaque valeur de pièce, maximiser le nombre de
pièces choisies
Soient M la monnaie, E ensemble des pièces, S ensemble de solution
Aroussi Bon Courage
Trier (E) //en ordre décroissant
Init (S) //Initialiser la solution à 0 (nbi = 0)
i1
Tant que (i n) faire // La solution est complète après avoir parcouru tous les éléments de E
S[i] M div E[i] // Ajouter la solution
M M mod E[i]
i ++
FTQ
Complexité: T (n) = Ttrier (n) + Tinit(n) + n c1 + c2 = Ttrier (n) + n c0 + n c1 + c2
O (T) = O(Ttrier) soit O (n2) soit O (nlogn) selon l’algorithme de trie
2. Démontrer que l’algorithme précédent aboutit à une solution optimale.
Choix glouton : la valeur de pièce la plus grande
Si M ≥ 50 toute solution optimale contient au moins une pièce de 50 c’est le premier
choix glouton.
Si s < 50, l’algorithme fait un bon premier choix ( au plus deux pièce de 20, une pièce de
10, une pièce de 5, au plus quatre pièces de 1)
Toute solution optimale contient donc un choix glouton
Propriété de sous-structure optimale :
Soient S une solution optimale pour la somme M et C S un choix glouton (la plus grande pièce)
alors S’ = S- {C} est une solution optimale pour M- Valeur (C) tel que Valeur (C) = NbC x PièceC.
Preuve par absurde
Supposant que:
H1: S une solution optimale pour la somme M
H2: C S un choix glouton (la plus grande pièce)
H3: S’ = S- {C} est une solution non optimale pour M- valeur (C)
Aroussi Bon Courage
Alors il existe une solution S’’ meilleure que S’ pour M-valeur (C), i.e.
Donc, S’’ {C} est meilleure que S’ {C} pour s car
i.e, S = S’ {C} n’est pas optimale (contradiction avec l’hypothèse H1).
3. On suppose que les pièces disponibles ont pour valeur B0, B1, ..., Bk pour deux entiers B > 1 et k ≥1
donnés. Montrer que l'algorithme glouton aboutit toujours à une solution optimale sur un tel jeu de
pièces.
Tout nombre naturel peut être écrit dans une base B quelconque comme suit :
Ainsi, l’algorithme glouton consiste à écrire la somme de monnaie (en décimale) dans la base B.
4. Donner un ensemble de valeurs de pièces pour lesquelles l'algorithme glouton ne donne pas une
solution optimale. Justifier votre réponse.
E = {5, 4, 1}:
La solution optimale existe toujours mais l’algorithme Glouton peut trouver des solutions non optimales
comme par exemple M=8
Aroussi Bon Courage
