Chap 2. Fondement de l'analyse de données

Question 1

principe d’invariance

Answer 1

deux implémentations
différentes du même algorithme ont un temps (réel) d’exécution qui ne
diffère que d’une constante multiplicative

Question 2

opération élémentaire

Answer 2

est une opération dont le temps d’exécution est
majoré (c’est-à-dire borné supérieurement) par une constante qui dépend
uniquement de l’implémentation, du langage de programmation ou de la
machine utilisée

Question 3

Instance

Answer 3

Forme de l’entrée d’un algorithme (pas sa taille !)

Question 4

Une opération de base d’un algorithme (Baromètre)

Answer 4

est une 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 5

Si le temps d’exécution est déterminé par un polynome..

Answer 5

il est en Θ du degré le plus élevé.

Question 6

Quand doit on chercher le temps moyen

Answer 6

Si on a un pire cas et un meilleur cas différents.

Question 7

Dérivé de √(n)

Answer 7

(1/2)n^-½ ou autrement dit 1 / 2.√(n)

Question 8

Quelle est la classe d’efficacité typique des algorithmes diviser pour règner ?

Answer 8

n.log(n)

Question 9

L’analyse des algorithmes non récursifs reviennent à résoudre des ..

Answer 9

Sommation

Question 10

L’analyse des algorithmes récursifs reviennent à résoudre des ..

Answer 10

relations de récurrences

Question 11

Déf: temps d’exécution moyen

Answer 11

la moyenne des temps d’exécution sur toutes les instances de taille n

Question 12

• Soit C(x) le temps d’exécution sur l’instance x.
• Dénotons la taille de l’instance x par |x|.
• Nous nous intéressons à
  toutes les instances x telles que |x| = n.
  Le temps d’exécution moyen Cavg(n) des instances de taille n est alors
  donné par

Answer 12

l’espérance des temps d’exécution:

C_avg (n) = ∑ P(x)C(x)
x:|x|=n

P(x) = probabilité d’observer l’instance x (parmi les instances de taille n)

Question 13

Log(n)

est-elle harmonieuse ?

Answer 13

Oui 
car log(2n) = log(2) + log(n) est en  Θ(n)

Question 14

n^k

est-elle harmonieuse ?

Answer 14

Oui
car (2n)^k = 2^k . n^k est en Θ(n^k)

Question 15

2^n

est-elle harmonieuse ?

Answer 15

Non

car 2^2n = (2^2)n = 4^n qui n’est PAS en Θ(2^k)

Question 16

n!

est-elle harmonieuse ?

Answer 16

Non

car (2n)! n’est PAS en Θ(n!)

Question 17

Théorème (règle de l’harmonie)

Answer 17

Si C(n) est éventuellement non
décroissante, si f(n) est harmonieuse et si C(n) ∈ Θ(f(n)) pour n = b^k
avec k ∈ N alors C(n) ∈ Θ(f(n)) ∀ n ∈ N