Feuille 3 : complexité

19. Feuille 3 : complexité#

Le symbole \(\blacksquare\) indique les exercices ou questions obligatoires. Commencez pas ceux-là.
Les symboles \(\star\) et \(\star \star\) indiquent les exercices ou questions de difficulté relative plus importante.

Focus

complexité : analyses et approches expérimentales

Compétences

Avoir les idées claires

Connaitre le principes de l’analyse de la complexité en temps : modèle de calcul, mesure et paramètre de la complexité, meilleur et pire cas
Savoir exprimer et exploiter une complexité asymptotique : principales complexités, interprétation pratique de ces complexités
(\(\star\)) Savoir établir la complexité d’algorithmes itératifs simples ou récursifs terminaux (algorithmes étudiés en cours)

Savoir-faire

Connaitre des exemples significatifs d’algorithmes de complexité polynomiale et logarithmique (complexité, pires et meilleurs cas)
Savoir identifier (sans nécessairement le prouver) la complexité, les meilleur-pire cas d’un algorithme

19.1. Objectif 10#

19.1.1. \(\blacksquare\) QCM (Extrait de CC)#

Dans les questions de cet exercice, le terme ‘’complexité’’ (seul) désigne la complexité en temps.

Une analyse de complexité en temps mesure le temps d’exécution d’un programme sur les ordinateurs des salles info. (Vrai/Faux)
Dans une analyse de complexité en temps, le coût d’une multiplication de 2 entiers codés sur 32 bits est de 1 unité tandis que celui de la multiplication de 2 nombres flottants codés sur 64 bits est de 2 unités. (Vrai/Faux)
Lors d’une analyse de complexité en temps, le coût d’une répétition \t{while} est égal à trois fois celui du \t{for} à cause du compteur géré de manière explicite : incrémentation et comparaison. (Vrai/Faux)
Citer un exemple d’algorithme avec une complexité constante dans le meilleur cas et linéaire dans le pire cas.
Citer un exemple d’algorithme avec une complexité quadratique dans le pire cas.
Quel est le meilleur cas dans une recherche séquentielle itérative ?
Quel est le meilleur cas dans une recherche dichotomique dans \(n\) valeurs triées ?
Un algorithme a une complexité temporelle cubique en la taille de son entrée, que peut-on dire de son temps d’exécution si l’on double la taille de l’entrée ?
La fonction de complexité \(C(n) = 4n^3 + 25n^2 + 10^2\) est asymptotiquement linéaire? quadratique ? ou cubique ? Pourquoi?

19.1.2. \(\blacksquare\) Exercice#

Dérouler l’algorithme suivant en explicitant les valeurs de l’ensemble de ses variables.

for i in range (4): 
    for j in range(i,4): 
        k = i + j

Même question en remplaçant la ligne 2 par :
```
 for j in range(i+1,4):
```
Compter le nombre d’additions dans chacun des deux cas.
Coder une vérification de ces deux questions.

19.1.3. \(\blacksquare \) Exercice#

On reprend l’exercice précédent en introduisant un nombre arbitraire \(n\) d’itérations de chaque boucle.

Quelle est une mesure naturelle de la complexité de cet algorithme ? Quel est le paramètre de cette complexité ?
Pour chacun des cas suivants : compter le nombre d’additions effectuées à chaque itération de la boucle intérieure. En déduire le nombre total d’additions. Quelle est la complexité asymptotique de cet algorithme ?

a. On modifie la ligne 1 :
```
1for i in range(n): 
2	for j in range(i,4):
```
b. on modifie maintenant la ligne 2 :
```
1for i in range(4): 
2	for j in range(n):
```
c. ou aussi :
```
1for i in range(4): 
2	for j in range(i,n):
```
d. Avec les lignes 1 et 2 suivantes :
```
1for i in range(n): 
2	for j in range(n):
```
e. ou aussi les lignes 1 et 2 suivantes :
```
1for i in range(n): 
2	for j in range(i,n):
```

Rappel. Il est utile de connaitre la valeur de la somme des \(n\) premiers entiers et son équivalent asymptotique :

\[1+2 + \dots + n = \sum_{k=1}^n k = n(n+1)/2 \approx n^2/2.\]

Complexité asymptotique : ainsi cette somme à une tendance asymptotique (polynomiale) quadratique.

19.1.4. \(\blacksquare \) Exercice#

On rappelle la spécification des fonctions est_egal() et nb_communs() d’abord sur des tableaux de dimension 1 (vecteurs) (cf. feuille 2).

La fonction est_egal() compare deux tableaux de dimension 1 et retourne le booléen correspondant. On convient que deux tableaux sont égaux si leurs tailles sont égales et si leurs valeurs sont égales deux à deux.
La fonction nb_communs() retourne le nombre de valeurs communes entre deux tableaux de dimension 1. Ici aussi la comparaison s’effectue “deux à deux” (valeurs de même indice).

Effectuer l’analyse de la complexité de ces fonctions.
Ces fonctions s’étendent à des tableaux 2D ou de façon plus générale à des tableaux multi-dimensionnels. L’égalité entre tableaux multi-dimensionnels suppose l’égalité des dimensions, des tailles deux à deux dans chaque dimension, et des valeurs deux à deux pour toutes les valeurs du tableau. Effectuer l’analyse de la complexité de ces fonctions pour des tableaux 2D.

19.1.5. Exercice (palindrome … toujours) extrait d’examen#

Cet exercice reprend l’exercice sur les palindromes des feuilles 1 et 2.

Effectuer l’analyse de complexité en temps de la version itérative de la vérification qu’un mot est ou non un palindrome (feuille 1). Veillez bien à répondre aux points suivants : para-mètre et mesure de la complexité, meilleur cas et pire cas, expression de cette complexité, comportement asymptotique, effet sur temps de traitement si le paramètre de complexité est doublé.
Même question pour la version récursive vue dans la feuille 2.

19.1.6. Exercice (extrait d’examen)#

On s’intéresse à la complexité en temps de la fonction suivante.

    def mystere(n: int) -> int:
       m = 0
       for i in range(n):
          for j in range(i):
             m = m + i + j
       return m 

Quel est le paramètre de cette complexité ?
Quelles sont les instructions significatives de cette complexité ?
Quelle est une mesure de sa complexité ?
Donner l’expression de cette complexité.
Combien y a-t-il d’opérations arithmétiques dans l’exécution de cette fonction pour un paramètre effectif \(N\) donné. ?
Quelle est sa complexité asymptotique ?

19.2. Objectif 20#

19.2.1. Exercice (extrait d’examen)#

Considérons la fonction f() suivante.

    def f(a:int, n: int)->int:
       assert n >= 0
       x = a
       y = 1
       while n > 0:
          if n % 2 == 1:
             y = y * x
          x = x * x
          n = n // 2
      return y 

Que valent f(3, 0), f(3, 1), f(3, 2), f(3, 3) et f(3, 4) ?
Que vaut f(3, \(2^p\)) pour \(p\) entier positif ?
De même, que vaut f(3, \(2^p\)+1) ?
Que calcule f(a, n) ?
Préciser la mesure et le paramètre de la complexité de cette fonction.
Donner une expression précise de sa complexité quand \(n=2^p\). Détailler votre réponse.
Quelle est sa complexité asymptotique ?

19.2.2. Exercice#

Effectuer une analyse expérimentale de la complexité pour comparer l’efficacité des algorithmes de recherche itérative et dichotomique (cas de l’entrée triée). Dégager les comportements dans le meilleur cas, dans le pire cas de chacun d’entre eux.

19.2.3. Exercice – qui commence en Objectif 10 et finit en Objectif 20#

Note : Cet exercice fait appel à la fonction python append() qui ajoute une valeur à une liste.

Premier algorithme.
1. Quel traitement effectue l’algorithme suivant ?
```
 1n = int(input()) 
 2l1 =  [ ] 
 3for i in range(n+1): 
 4    ok = False 
 5    for j in range(n+1): 
 6        for k in range(n+1): 
 7            if i == j ** 2 + k ** 2: 
 8                ok = True 
 9    if ok == True: 
10        l1.append(i)
```
2. Estimer la complexité de cet algorithme : préciser le paramètre de complexité et estimer de la façon la plus précise possible le nombre de chaque opération arithmétique exécutée, estimation qui sera exprimée comme une fonction de ce paramètre.
3. Quelle est la complexité asymptotique de cet algorithme ?

Deuxième algorithme.

Justifier que l’algorithme suivant résout le même problème que l’algorithme précédent.

n = int(input()) 
l2 =  [ ] 
for i in range(n+1): 
    ok = False 
    j = 0
    while j  < n+1 and (ok == False): 
        k = 0 
        while k  < n+1 and ok == False: 
            if i == j ** 2 + k ** 2: 
                l2.append(i) 
                ok = True 
            else: 
                k = k + 1 
        j = j + 1 

Estimer la complexité de cet algorithme : préciser le paramètre de complexité et estimer de la façon la plus précise possible le nombre de chaque opération arithmétique exécutée, estimation qui sera exprimée comme une fonction de ce paramètre.
Quelle est la complexité asymptotique de cet algorithme.
Que conclure ?

(\(\star \star\))Troisième algorithme.
1. Justifier que l’algorithme suivant résout le même problème que les algorithmes précédents.
```
 1from math import sqrt 
 2
 3n = int(input()) 
 4l3 =  [ ] 
 5for i in range(n+1): 
 6    ok = False 
 7    j = 0 
 8    while j<= int(sqrt(i)) and ok == False: 
 9        k = 0 
10        while k<= int(sqrt(i - j ** 2)) and (ok == False):
11            if i == j ** 2 + k ** 2: 
12                l3.append(i) 
13                ok = True 
14            else: 
15                k = k + 1 
16        j = j + 1 
```
2. Estimer la complexité de cet algorithme : préciser le paramètre de complexité et estimer de la façon la plus précise possible le nombre de chaque opération arithmétique exécutée, estimation qui sera exprimée comme une fonction de ce paramètre.
3. En utilisant les indications suivantes, déduire la complexité asymptotique de cet algorithme.
  
  Indications : On peut montrer les comportements asymptotiques suivants.
  1. \(\sum_{i=0}^{n} \sqrt{i} \sim \frac{2}{3} n \sqrt{n} \); ainsi la tendance asymptotique de cette somme est semi-linéaire, et plus précisément “en \(n^{3/2}\)”.
  2. \(\sum_{i=0}^{n} [1+ \sum_{j=0}^{\sqrt{i}} (1+\sqrt{i-j^2})] \sim \frac{\pi}{8} n^2\) ; ainsi la tendance asymptotique de cette somme est quadratique. .
4. Que conclure ?
(\(\star\)) Quatrième algorithme.
1. Justifier que l’algorithme suivant résout le même problème que les algorithmes précédents.
```
 1from math import sqrt 
 2
 3n = int(input()) 
 4l4 =  [ ] 
 5for i in range(n+1): 
 6    ok = False 
 7    j = 0 
 8    while j <= int(sqrt(i)) and (ok == False): 
 9        c = i - j ** 2 
10        s = int(sqrt(c)) 
11        if s * s == c:
12            l4.append(i) 
13            ok = True 
14        j = j + 1 .
```
2. Estimer la complexité de cet algorithme : préciser le paramètre de complexité et estimer de la façon la plus précise possible le nombre de chaque opération arithmétique exécutée, estimation qui sera exprimée comme une fonction de ce paramètre.
3. (\(\star\star\))En utilisant un logiciel de calcul formel (comme SageMath) ou les relations précédentes, en déduire la complexité asymptotique de cet algorithme.
4. Que conclure ?
(\(\star\)) Cinquième algorithme.
1. Justifier que i) l’algorithme suivant résoud le même problème que les algorithmes précédents, mais ii) effectue un traitement différent de ces derniers.
```
1from math import sqrt, floor 
2
3n = int(input()) 
4l5 =  [ ] 
5for i in range(floor(sqrt(n))+1): 
6    for j in range(i, floor(sqrt(n - i ** 2))+1): 
7        r = i ** 2 + j ** 2 
8        l5.append(r) 
```
2. Estimer la complexité de cet algorithme : préciser le paramètre de complexité et estimer de la façon la plus précise possible le nombre de chaque opération arithmétique exécutée, estimation qui sera exprimée comme une fonction de ce paramètre.
3. (\(\star \star\)) En utilisant le logiciel SageMath, en déduire la complexité asymptotique de cet algorithme.
4. Que conclure ?

19.2.4. Exercice#

Effectuer une analyse expérimentale de la complexité des cinq algorithmes précédents pour des valeurs de \(n\) choisies de façon adaptée entre 10 et 10 000.

19.2.5. (\(\star\)) Exercice#

Note : La question 2 fait appel à la récursivité.

Rappeler l’algorithme (classique) du produit de deux matrices carrés de taille \(n\) et sa complexité asymptotique
(\(\star\)) Sur wikipedia chercher algorithme de Strassen, le comprendre et noter sa complexité asymptotique
Coder ces deux algorithmes et effectuer une analyse expérimentale de leurs complexités pour \(n\) variant raisonnablement.
(\(\star\)) Qu’en conclure ?