Ce document dans d'autres formats: feuille de travail, source RST.
Je recherche le nom «Zorro» dans un annuaire en utilisant la méthode suivante:
Problème
Combien est-ce que cela va me prendre de temps?
On s'est donné un problème (rechercher un mot dans un dictionnaire), un algorithme pour le résoudre (recherche exhaustive). Puis on a introduit un modèle de calcul:
Dans ce modèle, on a cherché le nombre d'opérations élémentaires effectuées par l'algorithme pour un problème de taille $n$. C'est ce que l'on appelle la complexité de l'algorithme.
En fait, on a vu deux variations:
À partir de cette information, et en connaissant le temps nécessaire pour de petites instances du problème on peut évaluer le temps nécessaire pour résoudre n'importe quelle instance du problème.
Autres variations:
Donner des algorithmes et leur complexité au pire et en moyenne pour les problèmes suivants:
def plus_grand_element(liste):
"""
Renvoie le plus grand élément de la liste
EXAMPLES::
sage: plus_grand_element([7,3,1,10,4,10,2,9])
10
sage: plus_grand_element([7])
7
"""
resultat = liste[0]
for i in range(1, len(liste)-1):
# Invariant: resultat est le plus grand element de liste[:i]
assert resultat in liste[:i]
assert all(resultat >= x for x in liste[:i])
if liste[i] > resultat:
resultat = liste[i]
return resultat
plus_grand_element([7,3,1,10,4,10,2,9])
**Note**
Digression: invariants, preuve et test
var('n')
xmax=10^9
ymax=10^19
op_per_seconds=10^9
funs = [n^0, log(n), sqrt(n), n, 1000*n, n*(log(n)), n^log(3,2), n^2, n^(2.3727.n(digits=5)), n^log(7,2), n^3, 2^n, 5^n, factorial(n), n^n]
colors = rainbow(len(funs))
def time_label(s, t): return text(s, (1,t), horizontal_alignment = "left")
time_labels = sum(time_label(t,s)
for t,s in [["seconde", 1], ["minute", 60], ["jour",24*3600],
[u"année",365*24*3600], [u"siècle",100*365*24*3600],[u"âge de l'univers",14*10^9*365*24*3600]])
def legend(f, color="black"):
label = "$" + latex(f) + "$"
options = {"fontsize": 14}
if f(n=100)/op_per_seconds >= ymax:
xshift=1.3^(len(funs)-2-funs.index(f))
return text(label, ((f/op_per_seconds-ymax).find_root(1,100)*xshift, 3*ymax), horizontal_alignment="center", **options)
return text(label, (1.1*xmax, f(n=xmax)/10^9), horizontal_alignment="left", **options)
p = sum( plot(f/op_per_seconds,
xmin=1, xmax=(100 if f(n=100)>ymax else xmax),
ymax=ymax,
scale="loglog", gridlines=True, gridlinesstyle = {"color":'LightGray'},
color=color) + legend(f, color=color)
for f,color in zip(funs, colors)) + time_labels
p
La plupart du temps, il suffit d'avoir un ordre de grandeur du nombre d'opérations: les constantes sont sans grande importance. Un algorithme en $1000\log_{2}n+50$ sera meilleur qu'un algorithme en $\frac{n}{1000}$ dès que l'on s'intéressera à des instances suffisamment grandes.
Mais voir aussi l'article Constant Time Factors do Matter
Définition
Soient $f$ et $g$ deux fonctions de $\NN$ dans $\NN$ (par exemple les complexités de deux algorithmes).
On note $f=O(g)$ si, asymptotiquement, $f$ est au plus du même ordre de grandeur que $g$; formellement: il existe une constante $a$ et un entier $N$ tels que $f(n)\leq ag(n)$ pour $n\geq N$.
On note $f=o(g)$ si, assymptotiquement, $f$ est négligeable devant $g$; formellement: pour toute constante $a$ il existe $N$ tel que $f(n)\leq ag(n)$ pour $n\geq N$.
Proposition
Quelques règles de calculs sur les $O()$ :
Exercice (Règles mixtes)
Simplifier les expressions suivantes:
Exercice
Donner quelques algorithmes et leur complexité pour le calcul du déterminant d'une matrice
Note
Digression: Complexité arithmétique versus complexité binaire
Exemple
On a vu un algorithme en $O(n)$ pour rechercher le plus grand élément d'une liste de nombres.
Existe-t-il un meilleur algorithme?
Définition
La complexité d'un problème est la complexité du meilleur algorithme pour le résoudre.
On dit qu'un algorithme est optimal si sa complexité coïncide avec celle du problème.
Exercices
On a une liste que l'on veut trier, mettons $[7,8,4,2,5,9,3,5]$.
Problèmes
Quelle est le meilleur algorithme de tri?
Les algorithmes de tris en $O(n\log n)$ sont-ils optimaux?
Théorème
Le tri d'une liste de taille $n$ est un problème de complexité $O(n\log n)$.
Exercices
Évaluer au mieux la complexité des problèmes suivants:
Les exercices suivant forment un menu à la carte. En choisir quelques uns. Pour l'un d'entre eux préparer une démonstration de deux minutes illustrant un point spécifique, pour la présenter au reste du groupe. (Cf. TP de la semaine dernière pour les instructions pour m'envoyer votre feuille de travail).
recherche(liste, valeur)
renvoyant la première position de valeur
dans la liste
, ou None
si valeur n'est pas dans la liste. Par exemple:recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 21)
recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 69)
recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 5)
Note: on remarquera que, comme ci-dessus, l'objet None
n'est pas affiché par Python:
None
On peut vérifier que c'est bien None
qui est renvoyé avec:
recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 5) == None
Ou, plus rapide:
recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 5) is None
Indication: utiliser les tests suivants:
recherche([],1)
recherche([2],1)
recherche([2],2)
recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 21)
recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 69)
recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 5)
recherche([1,3,9,20,21,37,40,42,50,65,66,69,74], 21)
recherche([1,3,9,20,21,37,40,42,50,65,66,69,74], 69)
recherche([1,3,9,20,21,37,40,42,50,65,66,69,74], 5)
recherche
en insérant un compteur pour le nombre de comparaisons effectuées lors d'un appel.Indication: essayer l'exemple suivant:
def f():
global compteur
compteur = 0
for i in range(10):
compteur += 1
return 42
f()
compteur
recherche
en fonction de la taille de la liste, et représenter graphiquement le résultat.Indications:
complexite_recherche(n)
qui lance recherche
sur un échantillon de listes de longueur $n$, et renvoie le nombre de comparaisons en moyenne et au pire. point( [ [i, i^2] for i in range(10) ] )
Des collègues sont en train d'implanter une bibliothèque pour faire très facilement des bancs d'essais, en particulier pour l'enseignement. C'est encore expérimental, mais ils sont preneurs de retour. En l'état, il n'est pas clair s'il sera possible d'avoir cette bibliothèque le jour du concours.
Si vous êtes partant pour essayer cette bibliothèque, télécharger le fichier bleachermark.py et le mettre dans le même répertoire que votre feuille de travail.
Voici un exemple d'utilisation dans lequel on fait un banc d'essai pour la fonction $sorted$ de Python pour différentes tailles de listes. On commence par écrire un générateur de listes aléatoires de taille donnée:
from random import randint
def random_list(n):
return [randint(0, n) for i in range(n)]
On construit le banc d'essai:
from bleachermark import *
BB = SimpleBleachermark(random_list, sorted, sizes=[2^k for k in range(10)])
On le lance:
BB.run()
On peut l'interrompre à tout moment et le relancer ultérieurement.
Ensuite on peut accéder à la moyenne du temps de calcul pour $sorted$ pour chaque taille:
BB.averages() # random
Voici comment en faire un graphique:
points( BB.averages().items() ) # not tested
De même, on peut accéder au min, max, ainsi qu'à l'intégralité des temps de calculs avec:
BB.mins() # not tested
BB.maxes() # not tested
BB.timings() # not tested
Même exercice précédement, mais en supposant que les listes sont triées et en utilisant une recherche dichotomique.
Indications:
sorted(['c', 'b', 'a'])
inf
et sup
, vérifiant à chaque étape l'invariant inf <= i < sup
, où i
est la première position (éventuelle) de valeur
dans la liste
.Comparer la courbe de complexité en moyenne pour cet exercice et l'exercice précédent. Évaluer la taille maximale d'une liste dans laquelle on peut faire une recherche en moins d'une heure et d'une semaine.
Télécharger le fichier annexe et le mettre dans un dossier de votre choix, comme par exemple ~/Agregation/OptionC/TP2/tris.py
.
Charger ce fichier dans Sage
avec:
%run tris.py
Cela suppose que sagemath
a été lancé dans le même répertoire, ou que la feuille de travail soit dans ce même répertoire.
Essayer la fonction tri
.
Dans un terminal, aller dans le dossier, et lancer:
sage -t tris.py
Ouvrir le fichier avec votre éditeur de texte favori (par exemple gedit
), et compléter les tests de la fonction tri.
En partant du squelette précédent, implanter des fonctions de tri utilisant chacun des algorithmes suivants. Commencer systématiquement par spécifier l'invariant. Pour chaque implantation, tracer des courbes statistiques de complexité au pire et en moyenne. Comparer avec les courbes théoriques.
Indication: utiliser une fonction récursive; si nécessaire, s'entraîner en implantant au préalable une fonction récursive pour calculer $n!$
Indication: utiliser le module heapq
Indications:
insere(arbre, i)
qui insère un nombre i
dans un arbre binaire de recherche.Estimer la complexité de la fonction suivante:
def fusion(l1, l2):
sort(l1+l2)
lorsque elle est appliquée à des listes aléatoires, respectivement triées.
Que peut-on en déduire?
Pour en savoir plus, voir l'article sur Tim sort