Description

Brian.Pulfer@unige.ch
Remarques:
Veuillez suivre attentivement les sp´ecifications de l’´enonc´e.
• R´eponses – Essayez d’ˆetre exhaustif dans vos r´eponses. Les r´eponses comme ”oui” et ”non” ne permettent pas d’´evaluer vos connaissances.
• Trac´es – Mettez toujours des ´etiquettes d’axe et des titres pour les trac´es.
• Impl´ementation – Veuillez utiliser exactement les noms fournis pour les fonctions. Vous pouvez utiliser pytest avec le script de test donn´e pour v´erifier votre impl´ementation.
• Soumission
Merci de t´el´echarg´e vos devoirs sur moodle:
– NomPrenom.pdf avec votre rapport pour tout les exercices – tp1.py avec votre implementations
– Pas d’autres fichiers (.pyc, .ipynb, DS Store, pycache , …)
• Pour toute questions et remarques, merci d’utiliser le forum moodle.
1 El´ement majoritaire (3.5 Points)´
Dans une liste d’´el´ements, il y a un ´el´ement majoritaire si plus de la moiti´e des ´el´ements de la liste sont les mˆemes.
1.1 Impl´ementation
Veuillez impl´ementer l’algorithme de page 25 en impl´ementant et utilisant les fonctions suivantes:
• is_majority(A, element) – Indique si element est l’´el´ement majoritaire de A (True ou False).
• reduce(A) – Convertit la liste en une liste plus courte en comparant les ´el´ements par paires.
• dandc(A) – Utilize la technique divide and conquer pour retourner la valeur de son ´el´ement majoritaire s’il y en a un, None sinon.
Note: Dans dandc(A), l’op´eration de r´eduction est effectu´ee autant de fois que possible (par exemple avec r´ecursivit´e).
1.2 Analyse
1.2.1 Un ´el´ement majoritaire dans A est-il n´ecessairement aussi un ´el´ement majoritaire dans reduce(A)? Pourquoi? Donner un exemple.
1.2.2 Un ´el´ement majoritaire dans reduce(A) est-il n´ecessairement aussi un ´el´ement majoritaire dans A? Pourquoi? Donner un exemple.
1.2.3 Consid´erant le pire sc´enario pour les deux cas, en pratique, l’algorithme va-t-il s’ex´ecuter plus rapidement avec 2n ´el´ements ou avec 2n−1 ´el´ements pour n> 2? Pourquoi? Donner un exemple.
1.3 Comparaison d’ex´ecution
Impl´ementez la fonction compare_naive_and_dandc. La fonction doit afficher le trac´e comparant les temps d’ex´ecution de votre algorithme et de l’algorithme na¨ıf fourni pour des tableaux de taille 1’000, 2’000, 3’000, …10’000. Les tableaux doivent ˆetre g´en´er´es de mani`ere al´eatoire, ou` chaque ´el´ement a un possibilit´e de 50% d’ˆetre 0 et n’importe quel nombre entre [1-9] sinon. N’oubliez pas d’ajouter des ´etiquettes d’axe, un titre et une l´egende. Quel est le r´esultat? Commentez.
2 Exponentiation (1.5 Points)
Nous nous int´eressons dans cet exercice aux algorithmes capables de calculer des puissances enti`eres quelconques de la forme basep
2.1 Algorithme na¨ıf
Ecrire un algorithme na¨ıf d’exponentiation´ exp_naive(base, p) qui multiplie le nombre base par luimˆeme p fois. Quelle est la complexit´e de cet algorithme?
2.2 Algorithme D&C
Tous les nombres r´eels positifs peuvent ˆetre exprim´e comme une somme de puissances de 2. Par exemple:
53 = 32 + 16 + 4 + 1 = 25 + 24 + 22 + 20
Appliquer cette information `a l’exposant pour cr´eer un algorithme d’exponentiation diviser pour r´egner (exp_dandc(base, p)) avec complexit`e logarithmique.
2.3 Comparaison
Impl´ementer la fonction compare_exp pour comparer les deux algorithmes. Tracez le temps d’ex´ecution pour les deux algorithmes lors de l’exponentiation de 2 aux puissances suivantes : [1000, 2000, 3000, 4000, 5000]. N’oubliez pas d’ajouter des ´etiquettes d’axe, un titre et une l´egende. Quel est le r´esultat? Commentez.