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
1) Algorithmes de parcours d'un tableauâïž
Pour les exercices suivants, on utilisera la liste :
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
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
c. Ăcrire une fonction moyenne(liste) qui retourne la moyenne des valeurs contenues dans liste.
Affiche l'algorithme
III- Evaluation du coĂ»t d'un algorithmeâïž
1) Mesure expĂ©rimentaleâïž
Le module time contient une fonction time() 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
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
# recherche relation de proportionnalité par méthode des moindres carrés
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))])
# fin du tracé de la droite
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
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).
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.
Implémenter ces 3 algorithmes en python
tri par sélection
def indice_mini(liste):
indice = 0
minimum = liste[0]
for i in range(len(liste)):
if liste[i] < minimum:
indice = i
minimum = liste[i]
return indice
def tri_selection(liste):
for i in range(len(liste)):
i_mini = indice_mini(liste[i:])
liste[i], liste[i + i_mini] = liste[i + i_mini], liste[i]
return liste
tri par insertion
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 :
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