Chapitre 2

Question 1

Qu’est-ce qu’un algorithme?

Answer 1

Un algorithme est une procédure de calcul permettant de résoudre un problème bien spécifié. L’algorithme explique, de manière non ambigüe et dans un nombre d’opérations fini, comment, à partir d’entrants, obtenir l’ex- trant solution du problème.

Question 2

Un algorithme devrait contenir 5 caractéristiques. Lesquelles?

Answer 2

1) Finitude
2) Définition précise
3) Entrées
4) Sorties
5) Efficacité

Question 3

Qu’est-ce que la caractéristique de finitude?

Answer 3

Un algorithme doit toujours se terminer après un nombre fini d’étapes. Ce nombre peut toutefois devenir très grand.

Question 4

Qu’est-ce que la caractéristique définition précise?

Answer 4

Chaque étape d’un algorithme doit être définie préci- sément; les actions à réaliser doivent être spécifiées rigoureusement et sans ambigüité pour chaque cas.

Question 5

Qu’est-ce que la caractéristique entrées?

Answer 5

Un algorithme comporte aucune, une ou plusieurs entrées, des quantités fournies à l’algorithme avant qu’il ne commence ou qui sont allouées dynamiquement durant son exécution. Ces entrées proviennent d’un ensemble d’objets bien spécifié.

Question 6

Qu’est-ce que la caractéristique sorties?

Answer 6

Un algorithme comporte une ou plusieurs sorties : des quantités ayant une relation spécifiée avec les entrées

Question 7

Qu’est-ce que la caractéristique efficacité?

Answer 7

On s’attend généralement d’un algorithme qu’il soit efficace dans le sens où toutes les opérations qu’il doit accomplir sont suffisam- ment élémentaires pour pouvoir être en principe réalisées dans une durée finie par une personne munie de papier et d’un crayon.

Question 8

À quoi peut on comparer un algorithme?

Answer 8

Il est assez utile de le comparer à une recette de cuisine. Dans une recette, les entrées sont les ingrédients, la procédure les diverses étapes et la sortie, le plat pré- paré.

Question 9

Quelles sont les deux façons de présenter un algorithme?

Answer 9

1) En language naturel
2) En pseudocode

Question 10

Comment débute un algorithme?

Answer 10

L’algorithme débute par la signature de la fonction

Question 11

où est placé le code dans l’algorithme?

Answer 11

Le code est indenté (décalé vers la droite) après la signature de la fonction pour montrer qu’il fait partie du corps de la fonction.

Question 12

Qu’en est-il des conditions if/else de l’algorithme en pseudocode?

Answer 12

Le bloc délimité par les instructions Tant que (⟨condition⟩) et Fin Tant que forme une boucle dont le contenu — lui aussi indenté — est exécuté tant et aussi longtemps que la ⟨condition⟩ est vraie.

Question 13

Que fait l’instruction retourner?

Answer 13

L’instruction Retourner met immédiatement fin à la fonction, ici en retournant la valeur m.

Question 14

Qu’est-ce qu’une instruction conditionnelle?

Answer 14

Elles permettent d’effectuer différents calculs selon le résultat d’une condition booléenne (vraie ou fausse).

Question 15

Quels sont les quatre types d’instruction conditionnelle?

Answer 15

1) Instruction conditionnelle à un volet
2) Instruction conditionnelle à deux volets
3) Instruction conditionnelle imbriquée
4) La variante de l’instruction conditionnelle imbriquée

Question 16

Quelle est la forme d’une instruction conditionnelle à un volet?

Answer 16

Si ⟨condition⟩, alors ⟨conséquence⟩

Donc, la conséquence est effectuée si la condition est vraie. Si la condition est fausse, l’algorithme poursuit normalement

Question 17

Quelle est la forme d’une instruction conditionnelle à deux volets?

Answer 17

Si ⟨condition⟩, alors ⟨conséquence⟩,
sinon ⟨alternative⟩

ou bien la ⟨condition⟩ est vraie et la ⟨conséquence⟩ est évaluée, ou bien la ⟨condition⟩ est fausse et c’est alors l’⟨alternative⟩ qui est évaluée.

Question 18

Quelle est la forme d’une instruction conditionnelle imbriquée?

Answer 18

Si ⟨condition1⟩, alors ⟨conséquence1⟩, sinon si ⟨condition2⟩, alors ⟨conséquence2⟩, sinon ⟨alternative⟩

la ⟨conséquence1⟩ est évaluée lorsque la ⟨condition1⟩ est vraie; la ⟨conséquence2⟩ est évaluée lorsque la ⟨condition1⟩ est fausse et que la ⟨condition2⟩ est vraie; l’⟨alternative⟩ est évaluée lorsque la ⟨condition1⟩ et la ⟨condition2⟩ sont toutes les deux fausses.

Question 19

Quelle est la forme de la variante de l’instruction précédente qui facilite la lecture lorsqu’il y a un grand nombre d’actions possibles

Answer 19

Selon que
⟨condition1⟩, alors ⟨action1⟩;
⟨condition2⟩, alors ⟨action2⟩; ⟨condition3⟩, alors ⟨action3⟩;
…
autrement, ⟨action par défaut⟩

Seule l’⟨action⟩ correspondant à la ⟨condition⟩ vraie est exécutée. Si au- cune ⟨condition⟩ n’est vraie, c’est l’⟨action par défaut⟩ qui est exécutée.

Question 20

Qu’est-ce qu’un ET?

Answer 20

⟨e1⟩ ET ⟨e2⟩ est vraie lorsque les expressions ⟨e1⟩ et ⟨e2⟩ sont toutes deux vraies ; sinon la condition est fausse.

Question 21

Qu’est-ce qu’un OU?

Answer 21

⟨e1⟩ OU ⟨e2⟩ est vraie lorsque l’une ou l’autre des expressions ⟨e1⟩ et ⟨e2⟩ est vraie; la condition est fausse uniquement lorsque ⟨e1⟩ et ⟨e2⟩ sont toutes deux fausses.

Question 22

Qu’est-ce qu’un NON?

Answer 22

NON ⟨e⟩ est vraie lorsque l’expression ⟨e⟩ est fausse, et fausse autrement.

Question 23

Les ordinateurs sont excellents dans les processus répétitifs. Quels sont les deux types de processus répétitif?

Answer 23

1) Itératif
2) Récursif

Question 24

Si quelqu’un veut peinturer une cloture, quelle serait l’approche itérative?

Answer 24

nous indiquons à la personne d’appliquer de la peinture sur les planches de la première à la dernière. En supposant que les planches sont numérotées de 1 à 𝑛, cela revient à indiquer d’appliquer de la peinture sur la planche 𝑖, pour 𝑖 allant de 1 à 𝑛.

Question 25

Si quelqu’un veut peinturer une cloture, quelle serait l’approche récursive?

Answer 25

Le processus est divisé en deux étapes:
1) appliquer de la peinture sur une planche
2) peinturer une clôture de 𝑛 − 1 planches tant qu’il y a des planches à peinturer.

La personne qui suit les instructions récursives ne peut commencer à appliquer de la peinture tant qu’elle n’a pas rencontré la condition d’arrêt (l’extrémité de la clôture) puisque la description du travail à effectuer dé- pend d’elle-même.

Question 26

Si la personne du processus itératif devait arrêter son travail en plein milieu, est-ce qu’une personne pourrait reprendre le travail à la même place?

Answer 26

Oui, il pourrait simplement lui dire à quelle planche il s’est arrêter.

Question 27

Si la personne du processus récursif devait arrêter son travail en plein milieu, est-ce qu’une personne pourrait reprendre le travail à la même place?

Answer 27

la personne ne pourrait uniquement dire qu’elle en était à peinturer une clôture de 𝑚 planches, car elle aurait aussi bien pu se trouver dans la phase d’expansion que dans celle de contraction. Elle devrait donc aussi fournir des informations — qu’elle a mémorisées — sur l’« état » dans lequel elle se trouvait au moment d’interrompre son travail.

Question 28

La factorielle est une récession ou une itération?

Answer 28

Une récursion

Question 29

Que peut-on dire de la croissance de l’algorithme 𝑂(1)

Answer 29

Un algorithme d’ordre 𝑂(1) prend toujours le même temps pour effectuer ses calculs, peu importe la taille du problème. Il va sans dire que de tels algorithmes sont excessivement rares. Ils effectuent en général des tâches très simples.

Question 30

Que peut-on dire de la croissance de l’algorithme 𝑂(log 𝑛)

Answer 30

l’ordre de grandeur 𝑂(log 𝑛) survient dès lors que la taille du problème est divisée par deux à chaque étape.

Question 31

Que peut-on dire de la croissance de l’algorithme 𝑂(√𝑛)

Answer 31

Les algorithmes d’ordre 𝑂(√𝑛) sont rares. La fonction racine car- rée croit lentement, mais néanmoins plus rapidement que la fonction lo- garithme.

Question 32

Que peut-on dire de la croissance de l’algorithme 𝑂(𝑛)

Answer 32

Les algorithmes avec cette performance demeurent acceptables étant donné le rythme de croissance somme toute raisonnable de la fonction identité.

Question 33

Que peut-on dire de la croissance de l’algorithme 𝑂(𝑛 log 𝑛)

Answer 33

Les algorithmes qui répètent 𝑛 fois un calcul d’ordre 𝑂(log 𝑛) ont une performance d’ordre 𝑂(𝑛log𝑛). C’est le cas de plusieurs algo- rithmes de tri.

Question 34

Que peut-on dire de la croissance de l’algorithme 𝑂(𝑛2)

Answer 34

Les algorithmes qui effectuent un calcul pour toutes les paires d’entrées ont une performance 𝑂(𝑛2). Ici, ça commence à devenir lent.

Question 35

Que peut-on dire de la croissance de l’algorithme 𝑂(𝑛!)

Answer 35

Attention, danger. La fonction factorielle croit si rapidement qu’un algorithme ayant ce type de performance ne peut résoudre que de petits problèmes.