TP2 : Algorithmes et complexité

Effectifs cumulés

_images/TP2__Exemple_Effectifs.png _images/TP2__Exemple_Effectifs_cumulés.png

Documentation

TP2 au Lycée Lakanal (sujet rédigé par Arnaud Basson).

TP2.estPremier(n)[source]

Teste si l’entier \(n \geq 0\) est premier, par une méthode très naïve.

  • Complexité temporelle : \(O(\sqrt{n})\),
  • Complexité mémoire : \(O(1)\).
TP2.prochainPremier(n)[source]

Renvoie le plus petit nombre premier supérieur ou égal à n.

  • Complexité temporelle : on sait qu’on est au moins en \(O(n^{3/2})\) (mieux en vrai, car estPremier(n) est en \(O(n^{1/2})\) et on sait que \(n \leq next_{n} < 2n\)).
  • Complexité mémoire : \(O(1)\).
  • Remarque : cette procédure termine à tous les coups, car on sait que l’ensemble des nombres premiers est infini (cf. démonstration d’Euclide) et donc non borné.
  • Référence : http://villemin.gerard.free.fr/Wwwgvmm/Premier/densite.htm
TP2.comptePremiersPremiers(k)[source]

Compte le nombre de nombres premiers plus petit que k (naïvement avec la function estPremier).

TP2.crible(n)[source]

Construit la liste des nombres premiers plus petit que n, en écrivant la liste de tous les entiers de 2 à n, et en barrant les multiples de 2, puis les multiples de 3, etc.

TP2.crible2(n)[source]

Construit la liste des nombres premiers plus petit que n (du bas vers le haut), très mauvaise méthode.

TP2.comptePremiersPremiers_Opti(k)[source]

Compte le nombre de nombres premiers plus petit que k (en utilisant la méthode du crible).

TP2.chiffresDecimauxTriche(n)[source]

On triche en utilisant les fonctions str() et int().

TP2.chiffresDecimaux(n, reversed=False)[source]

Renvoie la liste des chiffres de l’écriture décimale de l’entier n, en temps et mémoire \(O(\log(n))\).

TP2.chiffresBasek(n, base=10, reversed=False)[source]

Généralise chiffresDecimaux() pour fontionner en base quelconque (base).

TP2.chiffresBinaires(n)
TP2.moyenneAutres(t, i)[source]

Calcul la moyenne des n-1 autres valeurs du tableau t d’indices différents de i, en temps \(O(n)\).

TP2.testMoyAutres(t)[source]

Teste si un des éléments du tableau vaut la moyenne des autres, naïvement en temps \(O(n^2)\).

TP2.testMoyAutres_Opti(t)[source]

Teste si un des éléments du tableau vaut la moyenne des autres, de façon maline en temps \(O(n)\).

Si sommeDesValeurs est la somme des valeurs du tableau t (sommeDesValeurs = sum(t)), on peut utiliser la relation suivante (par définition) : sommeDesValeurs - t[i] = moyenneAutres(t, i) * (n-1) donc on teste si un t[i] vaut (sommeDesValeurs - t[i]) / (n-1)

TP2.rechercheDicho(t, x)[source]

On suppose que t est trié de façon croissante, et la fonction est en O(log(n)).

TP2.rechercheDichoRec(t, i, gauche=0, droite=None)[source]

On suppose que t est trié de façon croissante, et la fonction est en \(O(log(n))\).

TP2.effectifs(t, m)[source]

Calcul des effectifs dans une liste de valeurs, en temps et mémoire \(O(n)\).

TP2.effectifsCumules(t, m)[source]

Calcul des effectifs cumulés dans une liste de valeurs, en temps \(O(n^2)\) et mémoire \(O(n)\).

TP2.effectifsCumulesOpti(t, m)[source]

Calcul des effectifs cumulés dans une liste de valeurs, qui ne sont autres que les sommes cumulées des effectifs, en temps et mémoire \(O(n)\).

TP2.ligneMin(a)[source]

Prend un tableau 2d de nombres entiers et qui renvoie l’indice de la ligne de somme minimale.

TP2.cumSum(t)[source]

Calcule la somme cumulées des valeurs de t, en \(O(n)\) en temps et espace.

TP2.calculePieces(terrain)[source]

Calcule le tableau auxiliaire pieces de même format que terrain, de telle sorte que pieces[i][j] soit égal au nombre maximal de pièces que l’explorateur peut récolter en se déplaçant de la case (0, 0) à la case (i, j).

  • \(O(n^2)\) en mémoire et en temps.
TP2.butinMax(terrain)[source]

Implémentation naïve du calcul de butin maximum, en suivant le sujet.

TP2.butinMax2(terrain)[source]

Calcule le butin optimal et un chemin y menant, en \(O(n)\) en temps et espace en plus du calcul du tableau pieces (donc en \(O(n^2)\) au total).


Sortie du script

$ python TP2.py
Chiffres decimaux de 2015 : [5, 1, 0, 2]
Chiffres de 31 pour son ecriture binaire : [1, 1, 1, 1, 1]
Chiffres de 32 pour son ecriture binaire : [0, 0, 0, 0, 0, 1]
Exemples de moyenneAutres avec le tableau t = [0, 1, 2, 3, 4, 5, 6]
moyenneAutres pour i = 0 vaut 3
moyenneAutres pour i = 1 vaut 3
moyenneAutres pour i = 2 vaut 3
moyenneAutres pour i = 3 vaut 3
moyenneAutres pour i = 4 vaut 2
moyenneAutres pour i = 5 vaut 2
moyenneAutres pour i = 6 vaut 2
testMoyAutres(t) vaut True
En effet, moyenneAutres(t, 3) = 3
rechercheDicho([1, 2, 4], 1)) donne 0
rechercheDicho([1, 2, 4], 3)) donne -1
rechercheDicho([1, 2, 4], 5)) donne -1
rechercheDicho([1, 2, 3, 4], 4)) donne 3
rechercheDichoRec([1, 2, 4], 1)) donne 0
rechercheDichoRec([1, 2, 4], 3)) donne -1
rechercheDichoRec([1, 2, 4], 5)) donne -1
rechercheDichoRec([1, 2, 3, 4], 4)) donne 3
Pour t = [1, 2, 1, 4, 1], ses effectifs sont : [0, 3, 1, 0, 1].
Pour un tableau aleatoire, ses effectifs sont [0, 118, 93, 111, 103, 107, 89, 92, 103, 93, 91]
Pour ce tableau aleatoire, ses effectifs cumules sont [0, 118, 211, 322, 425, 532, 621, 713, 816, 909, 1000]
Pour ce tableau aleatoire, ses effectifs cumules sont [0, 118, 211, 322, 425, 532, 621, 713, 816, 909, 1000]
Pour a = [[3, 2, 6], [4, 1, 4], [0, 5, 2]]
La liste des sommes de ses lignes est : [11, 9, 7]
Et donc l'indice de la ligne de somme minimale est : 2
Pour l'exemple du TP, terrain = [[3, 2, 6], [4, 1, 4], [0, 5, 2]]
Qui donne pieces = [[3, 5, 11], [7, 8, 15], [7, 13, 17]]
Pour l'exemple du TP, butinMax(terrain) = 17
Pour l'exemple du TP, butinMax2(terrain) = ([[3, 5, 11], [7, 8, 15], [7, 13, 17]], ['droite', 'droite', 'bas', 'bas'])

Le fichier Python se trouve ici : TP2.py.