Chapitre 1

Question 1

Définition d’un algorithme:

Answer 1

Enchaînement d’actions permettant l’accomplissement d’une tâche. Description de procédures permettant de faire des opérations sur des nombres (addition, soustraction, multiplication et division).

Question 2

Nommer les ressources utilisées pour mesurer l’efficacité d’un algorithmes.

Answer 2

• Le temps d’exécution.
• L’espace mémoire utilisé.
• La bande passante utilisée.

Question 3

Expliquer l’approche empirique.

Answer 3

Consiste à essayer l’algorithme sur différents jeux de données bien choisis.
(On ne retiens pas cette approche)

Question 4

Nommes les avantages et les inconvénients de l’approche empirique.

Answer 4

Avantages:
- Ne nécessite aucune connaissance en algorithmique.
- Résultats réalistes pour les instances testées dans l’environnement de test.

Inconvénients:
- Pas toujours généralisable aux instances non testées.
- Couteux et long (nécessite beaucoup de tests)
- Dépend de l’environnement d’exécution (le processeur, l’OS, la charge, l’implémentation…)

Question 5

Expliquer l’approche algorithmique.

Answer 5

Consiste à analyser le cout d’exécution d’un algorithme. (On retiens cette approche)

Question 6

Expliquer le cout d’exécution d’un algorithme.

Answer 6

Le cout d’exécution est défini par le nombre d’opérations élémentaires effectuées durant son exécution,

Une opération élémentaire est une opération non divisible.
- Exemple d’opérations élémentaires: comparaison, addition, multiplication d’une donnée élémentaire…
- Exemple d’opérations non élémentaires: tri d’un tableau, recherche d’un élément, exécution d’un autre algorithme…

Question 7

Expliquer les avantages et les inconvénients de l’approche algorithmique.

Answer 7

Avantages:
- Résultats généraux: ne dépend pas de l’environnement d’exécution.
- Estimation rapide et peu couteuse.

Inconvénients:
- Nécessite la compréhension de notions algorithmiques.

Question 8

Qu’est-ce que la notation O?

Answer 8

Détermine la borne supérieur d’une fonction dans la notation asymptotique.

Question 9

Qu’est-ce que la notation Ω?

Answer 9

Détermine la borne inférieure d’une fonction dans la notation asymptotique.

Question 10

Qu’est-ce que la notation θ?

Answer 10

Si la notation O et la notation Ω alors la fonction est de notation θ dans la notation asymptotique.

Question 11

Définition d’une opération baromètre.

Answer 11

Opération élémetaire 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 12

Donner l’ordre des classes de complexité pour le temps d’exécution d’un algorithme en ordre croissant.

Answer 12

O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n^2) < O(2^n) < O(10^n) < 0(n!)

Question 13

Nommer les avantages et les inconvénients d’une solution récursive.

Answer 13

Avantages:
- Formulation compacte, claire et élégante.
- Solution naturelle et facile à concevoir.
- Maîtrise des problèmes dont la nature même est récursive.

Inconvénients:
- Possibilité de grande occupation de mémoire.
- Temps d’exécution peut être plus long.
- Estimation parfois difficile de la profondeur maximale de la récursivité.