Introduction
Il est très souvent possible d'écrire des algorithmes totalement différents pour effectuer une tâche, résoudre un problème.
Comment comparer ces différentes solutions si elles donnent le même résultat ?
Le but de cette partie va être d'aborder la notion de complexité : ce qu'elle signifie et comment on la détermine.
Enfin, nous verrons comment s'assurer qu'un algorithme simple donnera toujours une solution correcte.
Partie 1 - Complexité⚓︎
I - Algorithmes de recherche⚓︎
Cliquez sur Fiche algorithmes01.pdf pour récupérer l'énoncé du TD.
Travail préalable :
créer une fonction alea_liste(n) qui retourne une liste de n nombres entiers aléatoires xi, avec 0 ≤ xi ≤ n dans le second cas
Affiche l'algorithme
Il est possible d'écrire cette fonction en une seule ligne, mais l'import de la fonction randint(début,fin) présente dans le module random est nécessaire.
from random import randint
def alea_liste(n):
return [randint(0,n) for i in range(n)]
1) Algorithmes de parcours d'un tableau⚓︎
Pour les exercices suivants, on utilisera la liste :
test=[19, 16, 28, 26, 50, 16, 0, 36, 1, 45, 38, 27, 37, 16, 45, 41, 3, 19, 49, 43, 19, 44, 40, 23, 33, 25, 30, 38, 28, 49, 31, 37, 8, 48, 34, 12, 25, 6, 37, 23, 32, 36, 44, 45, 36, 29, 17, 11, 32, 27]
a. Écrire une fonction indice(liste,valeur) qui retourne l’indice de la premiere occurrence de valeur dans liste.
Exemple : indice(test,36) doit retourner la valeur 7, car test[7]=36.
Affiche l'algorithme
def indice(liste,valeur):
for i in range(len(liste)):
if liste[i]==valeur:
return i
return -1
Remarque : il est nécessaire de prévoir le cas où la valeur ne serait pas présente.
Il peut être dangereux de retourner False car cela risquerait d'être considéré comme la valeur 0. D'où le choix de retourner un nombre négatif.
b. Écrire une fonction maximum(liste) qui retourne la plus grande valeur contenue dans liste.
Quelle valeur maximum(test) doit-elle retourner ?
Affiche l'algorithme
def maximum(liste):
maxi=liste[0]
for i in range(len(liste)):
if liste[i]>maxi:
maxi=liste[i]
return maxi
c. Écrire une fonction moyenne(liste) qui retourne la moyenne des valeurs contenues dans liste.
Affiche l'algorithme
def moyenne(liste):
somme=0
for i in liste:
somme+=i
moyenne=somme/len(liste)
return moyenne
III- Evaluation du coût d'un algorithme⚓︎
1) Mesure expérimentale⚓︎
Le module time contient une fonction time_ns() retournant le temps écoulé en nanosecondes depuis le 01/01/1970. Il est possible grâce à elle d’évaluer le temps que met une série d’instructions à se réaliser :
a. En combien de temps moyenne(test) s’est executé ? b. Mesurer maintenant le temps que met moyenne(test) pour des listes plus grandes (générées à l’aide alea_liste(n)) c. Que constatez-vous ? Les résultats sont-ils toujours les mêmes ?
Affiche l'algorithme
from time import time_ns
def bench(fonction,liste):
chrono=time_ns()
fonction(liste)
return time_ns()-chrono
Avec la fonction précédente, on se rend compte qu'il est impossible sur une machine récente de mesurer le temps que met la fonction moyenne(liste) à s'executer !
Il est donc nécessaire d'utiliser des listes plus longues pour pouvoir mesurer le temps d'execution :
Affiche l'algorithme
from time import time_ns
from matplotlib import pyplot as plt
def bench(fonction,l_liste):
liste=alea_liste(l_liste)
chrono=time_ns()
fonction(liste)
return time_ns()-chrono
def bench_fonctions(liste_fonctions,depart,fin,pas,nb_tests=1,labels=False):
k=0
plt.ylabel("temps (ns)")
plt.xlabel("nombre d'éléments")
for fonction in liste_fonctions:
x=[]
y=[]
increment=depart
while increment<fin:
print(increment)
increment+=pas
x.append(increment)
y.append(moyenne([bench(fonction,increment) for i in range(nb_tests)]))
if labels is False:
lab=str(k)
else:
lab=labels[k]
plt.plot(x,y,label=lab)
k+=1
<em>#recherche relation de proportionnalité par méthode des moindres carrés</em>
sum_xi2,sum_xi_yi=0,0
for i in range(len(x)):
sum_xi2 +=x[i]**2
sum_xi_yi +=x[i]*y[i]
a=sum_xi_yi/sum_xi2
plt.plot(x,[a*x[i] for i in range(len(x))])
<em>#fin du tracé de la droite</em>
plt.legend(loc="upper left")
plt.show()
La fonction bench_fonctions va tester une liste de fonction sur un pour des valeurs à définir, puis tracer le graphe du temps de calcul en fonction de la longueur de la liste.
En utilisant les fonctions précédentes, et en lançant la commande
bench_fonctions([moyenne],100,1e5,1000,10,["temps de calcul"])
on obtient le graphique suivant :
On remarque que si les valeurs sont irrégulières (en effet un ordinateur effectue beaucoup d'autres tâches pendant qu'il exécute un script en python), elles sont cependant en accord avec une relation de proportionnalité : Le temps d'éxécution semble proportionnel au nombre d'éléments présents dans la liste.
2) Vérification⚓︎
Il n'est pas possible à notre niveau de déterminer exactement combien de temps va prendre le calcul dans le cas de python et d'un ordinateur de bureau, cependant on peut compter le nombre d'opération que fait l'algorithme dans le cas d'une moyenne.
→ Pour chaque indice de la liste en entrée, il va ajouter à la variable somme la valeur présente à l'indice. Il réalise cette opération n fois et on suppose qu'elle prend un temps t1. Ensuite, il divise somme par le nombre d'éléments, cela prend un temp t2.
On a donc un temps total de l'ordre de :
ttotal = n × t1 + t2
Si n est suffisamment grand, on peut négliger le temps pris par la division, on retrouve bien un temps proportionnel au nombre d'éléments.
Définition
On dit alors que la complexité est en O(n) ("grand O (la lettre o) de n").
On ne connait pas forcément le coefficient de proportionnalité, qui dépend notamment des caractéristiques de la machine, mais on peut affirmer que si un calcul pour n éléments (et n suffisamment grand) a pris un temps t alors pour 2×n éléments, le calcul prendra un temps 2×t.
IV- Algorithmes de tri⚓︎
Il existe plusieurs façons de trier une liste :
Le tri par sélection
Celle qui me semble la plus simple est de chercher le maximum d’une liste, puis une fois celui-ci trouvé, échanger sa position avec l’élément en première position de la liste (tri décroissant) ou dernière position (tri croissant).
Affiche l'algorithme
En pseudo-code cela donne :
procédure tri_selection(tableau t)
n ← longueur(t)
pour i de 0 à n - 2
min ← i
pour j de i + 1 à n - 1
si t[j] < t[min], alors min ← j
si min ≠ i, alors échanger t[i] et t[min]
Le tri par insertion
on peut aussi prendre consécutivement les éléments de la liste et les remplacer correctement un à un parmi les éléments déjà ordonnés de la liste.
Affiche l'algorithme
procédure tri_insertion(tableau T)
n ← taille(T)
pour i de 0 à n - 1
# mémoriser T[i] dans x
x ← T[i]
# décaler vers la droite les éléments de T[0]..T[i-1] qui sont plus grands que x en partant de T[i-1]
j ← i
tant que j > 0 et T[j - 1] > x
T[j] ← T[j - 1]
j ← j - 1
# placer x dans le "trou" laissé par le décalage
T[j] ← x
Le tri à bulles
On peut enfin balayer progressivement la liste en inversant 1 à 1 chaque couple de nombres consécutivement de façon à ce qu’ils soient dans l’ordre de rangement, et cela jusqu’à ce que la liste soit ordonnée.
Affiche l'algorithme
procédure tri_insertion(tableau T)
n ← taille(T)
pour i de 0 à n - 1
pour j de 0 à i - 1
si T[j] > T[j + 1]
temp = T[j]
T[j] ← T[j + 1]
T[j + 1] ← temp
Implémenter ces 3 algorithmes en python
tri par sélection
def tri_selection(liste):
for i in range(len(liste)):
maxi=liste[0]
indice=0
for j in range(len(liste)-i):
if liste[j]>maxi:
maxi=liste[j]
indice=j
liste[indice],liste[len(liste)-i-1]=liste[len(liste)-i-1],liste[indice]
return liste
tri par insertion
def tri_insertion(liste):
for i in range(1,len(liste)):
temp=liste[i]
for j in range(1,i):
if liste[i]<liste[j]:
for k in range(i-j):
liste[k+1]=liste[k]
liste[j]=temp
break
return liste
tri à bulles
def tri_bulle(liste):
for i in range(len(liste)):
for j in range(len(liste)-i-1):
if liste[j+1]<liste[j]:
liste[j+1],liste[j]=liste[j],liste[j+1]
return liste
Ces trois algorithmes retournent une liste correctement ordonnée, comment les classer ?
- Par taille, on constate que le tri à bulle est le plus concis
- Par nombre de calculs, on constate que le tri à bulles recommence systématiquement et inverse les positions une à une, là où les deux autres algorithmes n'inversent qu'un certain nombre de valeurs, voire une seule.
- Par temps d'exécution : il est possible d'utiliser la fonction
bench_fonctions([tri_selection,tri_insertion,tri_bulle],125,2.5e3,125,10,["tri par sélection","tri par insertion","tri à bulles"])
On obtient alors le graphique suivant :
Le tri à bulles est (beaucoup) plus lent que les deux autres méthodes !
On remarque également que le temps de calcul n'est plus proportionnel au nombre d'éléments de la liste mais augmente plus vite que le nombre d'éléments.
Pour voir si ce temps augmente bien en fonction de n2, il suffit de changer l'axe vertical : au lieu de tracer t en fonction de n, on peut tracer √t en fonction de n.
Dans cette représentation, les relations proportionnelle à n2 sont visibles :
A savoir
Même si le tri à bulles est le moins efficace, ces trois tris ont une complexité en O(n2)
Remarque
Ces 3 tris ne sont pas considérés commes efficaces, il existe des tris bien plus rapides, comme le tri fusion ou le tri rapide dont la complexité est inférieure à O(n2).
Partie 2 - Mini-Projets⚓︎
I- Le morpion⚓︎
Le morpion est un jeu à 2 joueurs sur une grille de 3 × 3 cases.
Chaque joueur place tour à tour une marque dans une case vide, le premier à aligner 3 de ses marques a gagné.
Le fichier suivant contient un script avec l'ossature du programme ainsi que les directives pour le remplir :
Voir le code
# liste de liste définissant le plateau de jeu
# la valeur 0 correspond à une case vide
grille=[[0 for i in range(3)] for j in range(3)]
""" Fonction se chargeant d'afficher le plateau de jeu
"""
def affiche():
for j in range(3):
print("{}|{}|{}".format(grille[j][0],grille[j][1],grille[j][2]))
if j<2 : print("-|-|-")
def jeu():
fini=False
while not fini:
""" tour du joueur 1 """
# le jeu attend que le joueur indique les coordonnées de la case dans laquelle il compte placer sa marque
# Supposons que les cases portent chacune un numéro compris entre 0 et 8 ou entre 1 et 9, à votre convenance
# ainsi la variable coup doit correspondre au numéro de la case à marquer
coup=input("joueur 1")
# A la place de ce commentaire, vous devez écrire la partie qui se charge de :
#- vérifier que la case est libre
#- modifie le tableau 'grille' pour indiquer que la case est prise par le joueur 1
#- vérifie que le joueur 1 a gagné, ou non. Dans le cas d'une victoire, on peut interrompre la boucle while
# avec la commande break
""" tour du joueur 2 """
# faire de même que pour le joueur 1
coup=input("joueur 2")
# faire de même que pour le joueur 1
pass #commande à enlever lorsque vous aurez écrit votre programme
#Afficher le résultat de la partie : joueur vainqueur ou match nul
affiche()
Un tableau est créé : il s'agit d'une liste contenant 3 sous-listes (une par ligne) contenant elles-mêmes 3 valeurs :
grille=[[0 for i in range(3)] for j in range(3)]
La grille sera modifiée en cours de jeu avec les valeurs suivantes : - 0 si vide - 1 si case remplie par le joueur 1 - 2 si case remplie par le joueur 2
Le travail :
- Décider de la façon dont les joueurs vont indiquer la case choisie.
- Interpréter la réponse du joueur en fonction, et vérifier que la case est jouable, et faire rejouer le joueur si nécessaire jusqu'à ce qu'il propose une case jouable.
- Ajouter une fonction gagne() se chargeant de vérifier que la grille n'est pas dans une situation gagnante.
Voir le corrigé
Détails du programme
La fonction jeu
def jeu():
while True:
coup_valide=False
while not coup_valide:
coup=int(input("joueur 1 : indiquez la case numérotée de 0 à 8"))
if grille[coup//3][coup%3]==0:
coup_valide=True
grille[coup//3][coup%3]=1
affiche()
if jeu_gagnant():
print("joueur 1 a gagné !")
break
if grille_pleine():
print("Grille complète, pas de gagnant")
break
- La fonction contient une boucle "tant que" qui tourne a priori à l'infini. En réalité, en cas de victoire ou d'égalité, les break vont stopper la boucle.
- Pour faire en sorte que le joueur ayant la main joue un coup valide, on met une autre boucle "tant que" qui se répétera tant que le coup ne sera pas valide. On considère le coup valide lorsque le joueur demande une case vide.
- La lecture de la case est donné par grille[coup//3][coup%3], pourquoi cela ?
- J'ai choisi de numéroter les cases de 0 à 8 de gauche à droite puis de haut en bas. Imaginons que je souhaite jouer la case de la 2eme ligne tout à droite : elle porte le numéro 5. vous pouvez vérifier que 5//3=1 et 5%3=2, ce qui correspond bien à la case.
- Une fois le coup joué et placé, on affiche la grille, puis on vérifie si l'on est dans une configuration gagnante : à ce point de la fonction, si une configuration gagnante est détectée, c'est nécessairement celle du joueur 1.
- On vérifie enfin que la grille n'est pas vide avant de continuer : en effet, la grille ayant 9 cases, c'est nécessairement le joueur 1 qui remplira la dernière case.
La fonction jeu_gagnant()
def jeu_gagnant():
for i in range(3):
if grille[i][0]==grille[i][1]==grille[i][2] and grille[i][0]!=0:
return True
if grille[0][i]==grille[1][i]==grille[2][i] and grille[0][i]!=0:
return True
if grille[0][0]==grille[1][1]==grille[2][2] and grille[0][0]!=0:
return True
if grille[0][2]==grille[1][1]==grille[2][0] and grille[2][0]!=0:
return True
return False
- Il y a 8 configurations gagnantes : 3 lignes verticales, 3 horizontales et les 2 diagonales.
On peut tester les 6 lignes avec une boucle et les 2 diagonales à part - La fonction verifie que les 3 cases alignées ont la même valeur, mais doit également vérifier que cette valeur n'est pas nulle.
- Enfin si aucune situation n'est gagnante, la fonction retourne False