TP2 : Algorithmes et complexité

Effectifs cumulés

---

Documentation

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

• Date : mercredi 30-09 et jeudi 01-10 (2015),
• Auteur : Lilian Besson, pour le cours d’informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
• Licence : MIT Licence (http://lbesson.mit-license.org).

TP2.estPremier(n)

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)

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)

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

TP2.crible(n)

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)

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

TP2.comptePremiersPremiers_Opti(k)

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

TP2.chiffresDecimauxTriche(n)

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

TP2.chiffresDecimaux(n, reversed=False)

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)

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

TP2.chiffresBinaires(n)

TP2.moyenneAutres(t, i)

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

TP2.testMoyAutres(t)

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

TP2.testMoyAutres_Opti(t)

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)

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)

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

TP2.effectifs(t, m)

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

TP2.effectifsCumules(t, m)

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

TP2.effectifsCumulesOpti(t, m)

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)

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

TP2.cumSum(t)

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

TP2.calculePieces(terrain)

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)

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

TP2.butinMax2(terrain)

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.