Intro Algorithmique

Question 1

Def : Analyse de complexité/efficacité des algorithmes

Answer 1

Déterminer les ressources utilisées pour exécuter l’algorithme.

Question 2

Déf : Comment se mesure l’Efficacité des algorithmes

Answer 2

Se mesure par la quantité de ressources
utilisées.

● Le temps d’exécution

● L’espace mémoire utilisé

● La bande passante utilisée

Question 3

Définition: le temps d’exécution d’un algorithme

Answer 3

est nombre d’opérations

élémentaires qu’il doit effectuer pour accomplir sa tâche.

Question 4

Déf : Une opération élémentaire

Answer 4

est une opération non divisible.

Question 5

Notation O

Answer 5

Détermine une borne supérieure éventuelle

Question 6

Notation Ω

Answer 6

Détermine une borne inférieure éventuelle

Question 7

Interprétation de

lim f(n)/g(n)
n->∞

Answer 7

● = c > 0 alors f(n) en Θ(g(n))

● = 0 alors f(n) ∈ O(g(n)) et pas en Θ(g(n))

● = +∞ alors f(n) ∈ Ω(g(n)) et pas en Θ(g(n))

Question 8

La règle de l’Hôpital

Answer 8

lim f(n)/g(n)
n->∞

=

lim f’(n)/g’(n)
n->∞

Question 9

Déf : Opération baromètre

Answer 9

opération élémentaire qui, À UNE CONSTANTE PRÈS, est effectuée au moins aussi souvent que n’importe quelle
autre opération élémentaire de l’algorithme.

Question 10

Déf : Temps d’exécution en “Pire cas”

Answer 10

est le temps d’exécution

maximal parmi toutes les instances S de taille n.

Question 11

Déf : Temps d’exécution en “Meilleur cas”

Answer 11

est le plus petit temps

d’exécution parmi toutes les instances S de taille n.

Question 12

Déf :Le temps d’exécution moyen

Answer 12

est la moyenne des temps

d’exécution parmi toutes les instances S de taille n

Question 13

Quand avons nous Tworst(n) = Tbest(n) = Tavg(n).

Answer 13

Lorsque le temps d’exécution ne dépends que de la taille n de l’instance
(et seulement dans ces cas)

Question 14

Déf : Relation de récurrence

Answer 14

est une relation entre une fonction f
: N → R+ et elle même, évaluée sur une entrée plus petite.

Ex: f(n) = f(n-1) + 1.

Question 15

Déf : Éventuellement non décroissante

Answer 15

Une fonction non négative f : N → R+ est dite
éventuellement non décroissante s’il existe n0 telle que f(n) ≤ f(n+1)
pour tout n ≥ n0.

Question 16

Déf : Fonction harmonieuse sur R+

Answer 16

est dite harmonieuse lorsqu’elle est

éventuellement non décroissante et que f(2n) ∈ Θ(f(n)).

Question 17

n³ est harmonieuse ?

Answer 17

Oui.
car f(2n) = (2n)³ = 8n³ = 8f(n) ∈ Θ(f(n))

Question 18

log(n) est harmonieuse ?

Answer 18

Oui.
car log(2n) = log(2)+log(n) ∈ Θ(log n)

Question 19

Théorème: Soit f(n) une fonction harmonieuse. Si T(n) est
éventuellement non décroissante et que T(n) ∈ Θ(f(n)) pour n = bk avec
b ≥ 2, alors …

Answer 19

alors T(n) ∈ Q(f(n)) (pour toutes les autres valeurs de n
infiniment grandes).

Question 20

Déf : Algorithme Récursif

Answer 20

● L’algorithme résout un (ou des) cas particulier(s) du problème d’une
façon simple et non récursive.
● Le cas général est solutionné par des appels récursifs successifs qui
doivent converger au(x) cas particulier(s).
● Il y a donc une condition d’arrêt qui permet de toujours
arrêter la cascade d’appels récursifs afin de