Chapitre 2

2.6.1

• algo1:
  

1. 36
   
2. cet algorithme n'est pas récursif
   
3. il calcule la somme des n premiers nombres impairs (qui vaut n²)
4. O(n)

• algo2:

1. 36
2. pas récursif
3. retourne n²
4. O(1)

• algo3:

1. 36
2. récursif
3. comme algo1
4. O(n)

•  algo4:

1. 12
2. récursif
3. calcule : si n est impair, la somme des (n+1) / 2 premiers nombres impairs ; si n est pair, la somme des n/2 premiers nombres pairs
4. O(n)

2.6.2

• algo6 est le seul algorithme qui fonctionne correctement ; les autres ne s’arrêtent jamais.
• Il recalcule plusieurs fois la même chose inutilement et prend un temps exponentiel pour s’exécuter.
• Sa sortie est simplement n (tout ça pour ça !).

2.6.3

1. Pour la solution linéaire : il suffit d’essayer toutes les valeurs une à une :

  L’algorithme met effectivement n + 1 étapes à s’arrêter. C’est bien un algorithme linéaire.

  2. Pour une version sous-linéaire, toute la difficulté consiste à trouver une borne supérieure à la taille, car une fois que l’on a une telle borne supérieure, on peut simplement rechercher par dichotomie entre, par exemple,1 et cette borne ; cette recherche ayant une complexité logarithmique. La question est donc de savoir si l’on peut trouver une borne supérieure à la taille n de L en un temps moindre que linéaire n.
La réponse est oui : on peut le faire en un temps logarithmique (ce qui donnera au final une complexité logarithmique pour l’algorithme complet).
Prenons pour cela une constante K > 1 (par exemple K = 2) et demandons si a_element(L, Kⁱ), pour i partant de 1 et augmentant tant que c’est vrai. Nous aurons besoin de poser ⌊log_K(n)⌋ + 1 fois cette question. Une fois le i final trouvé, nous pouvons rechercher la taille par dichotomie entre K^{i -1} et Kⁱ.
Au total, notre algorithme effectuera O(log n) opérations. Formellement, avec K = 2, on peut écrire l’algorithme comme ceci :

avec

L'idée de cet algorithme est de chercher la taille entre a inclus et b exclu.

2.6.4

2.6.5

Cet algorithme récursif effectue une recherche par dichotomie presque exactement comme présenté dans le chapitre 1 du livre. La seule différence est qu’ici on compare aussi avec « l’élément du milieu » (c dans l’algorithme).
Sans autre contraintes sur a et b, l’algorithme proposé n’est pas correct dans tous les cas. Si en entrée   a > b, il peut arriver qu’il ne termine pas en raison d’un nombre infini d’appels récursifs. Par ailleurs, si a est plus grand que le nombre d’éléments dans la liste, « le a-ième » ou « le c-ième élément de L » ne sont pas définis. De plus, la contrainte a ≤ b n’est même pas garantie dans tous les cas dans l’algorithme lui-même ! En effet, si x < L[a] et b = a + 1 alors on lancera devinette(L, x, a, a - 1) ! Essayez par exemple avec L = {2, 3}, x = 1, a = 1 et b = 2.
Le plus simple serait donc d’ajouter un test au début de l’algorithme pour garantir 1 ≤ a ≤ b ≤ taille(L) et répondre 0 sinon.

2.6.6

1. a) Lorsque m = « 3 : » et n = 3 :
   3 : ,3
   3 : ,2,1
   3 : ,1,2
   3 : ,1,1,1
   b) Lorsque m = « 4 : » et n = 4 :
   4 : ,4
   4 : ,3,1
   4 : ,2,2
   4 : ,2,1,1
   4 : ,1,3
   4 : ,1,2,1
   4 : ,1,1,2
   4 : ,1,1,1,1
2. L’algorithme affiche toutes les permutations avec répétition de séquences de nombres entre 1 et n dont la somme est n.

2.6.7

Au lieu de garder toute la table en mémoire, l’idée est de ne garder que (la partie non triviale de) la ligne du calcul courant. Mais il faut alors procéder « à reculons » (j décroissant) pour ne pas écraser des valeurs encore nécessaires au calcul courant :

Note : pour simplifier, les k - 1 cases nécessaires sont notées ligne[2] à ligne[k] ; ligne[0] et ligne[1] n’existent pas dans l’algorithme ci-dessus. On pourrait faire avec k, voire k + 1, cases en les intégrant facilement à l’algorithme proposé.