Travaux Pratiques

Consignes

Introduction à la complexité

Les exercices suivants sont à faire dans l’ordre à l’occasion des deux séances de TP. Pour l’un d’entre eux, préparer une illustration de deux minutes sur un point spécifique de votre choix. En fin de chaque séance, deux ou trois étudiants présenterons leurs illustrations au reste du groupe (cf. TP de la première semaine pour les instructions pour envoyer votre feuille de travail).

Objectifs

L’objectif de ce TP est d’acquérir de bonnes pratiques de programmation, notamment en vue de préparer efficacement des illustrations logicielles robustes le jour de l’oral.

Organisation du code

  1. Écrire des fonctions dans un fichier séparé et les charger dans Jupyter;

  2. Écrire des fonctions avec documentations et tests;

  3. Écrire du code modulaire.

Correction des programmes

  1. Cahier des charges d’une fonction: Préconditions, postconditions et invariants de boucles;

  2. Exécuter les tests de manière automatique,

Complexité pratique des programmes

  1. Mesurer un nombre d’opérations, un temps d’exécution;

  2. Représenter la complexité dans un graphique.

Exercice 1: Test et correction des algorithmes de recherche

  1. Implanter une fonction recherche(liste, valeur) renvoyant la première position de valeur dans la liste, ou None si valeur n’est pas dans la liste.

  2. Tester votre fonction avec les exemples ci dessous:

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,21,69,65,21,66,1,74,50], 21)
recherche([9,20,3,40,37,42,21,69,65,21,66,1,74,50], 69)
recherche([9,20,3,40,37,42,21,69,65,21,66,1,74,50], 5)
recherche([1,3,9,20,21,37,40,42,50,65,66,69,74], 1)
recherche([1,3,9,20,21,37,40,42,50,65,66,69,74], 74)
  1. Téléchargez le fichier annexe recherche.py et enregistrez le dans un dossier de votre choix, comme par exemple ~/Agregation/OptionC/TP2/recherche.py. L’ouvrir avec l’éditeur de texte de votre choix (par exemple gedit, ou l’éditeur intégré dans Jupyter. Vous y retrouvez la fonction plus_grand_element du cours, avec sa documentation et ses exemples. Un des exemples est faux: c’est volontaire! Voir ci-dessous.

  2. Chargez le fichier recherche.py dans une feuille de travail Jupyter à l’aide de la commande:

%run recherche.py

Attention, cela présuppose que la feuille de travail Jupyter est dans le même répertoire que le fichier recherche.py; par exemple parce qu’elle a été créé depuis SageMath lancé dans le même répertoire:

cd ~/Agregation/OptionC/TP2/
sage -notebook jupyter
  1. Essayez la fonction plus_grand_element

plus_grand_element([1, 2])
  1. Il est possible de tester automatiquement les exemples dans la documentation de plus_grand_element. C’est ce est utilisé dans la bibliothèque de Sage pour vérifier que tous les exemples de la documentation sont corrects. Pour lancer les tests:

!sage -t --optional=sage recherche.py
Vous noterez qu'une erreur est affichée pour le dernier
exemple. Corrigez-le et relancez les tests.
  1. Ajoutez votre fonction recherche dans le fichier afin de mettre en pratique les deux premiers objectifs du TP:

    • documentez votre fonction recherche,

    • incorporez les tests effectués «à la main» dans la question précédente,

    • écrivez en commentaires l’invariant de boucle pour votre fonction recherche. Si pertinent, précisez dans la documentation les préconditions (quelles propriétés doivent être vérifiées par les entrées: ici la liste doit être non vide), et les postconditions (quelles propriétés sont vérifiées par les sorties.

    • chaque fois que possible, traduire ces commentaires sous forme exécutable par la machine, en utilisant la commande:

assert <condition>
  1. Rechargez le fichier recherche.py et vérifiez que vous pouvez maintenant utiliser les fonctions qui y sont présentes.

  2. Testez les exemples dans la documentation de votre fonction recherche

  3. Reprenez toutes les étapes précédentes avec la recherche dichotomique, en supposant que la liste en argument est triée. Prenez le temps de bien écrire votre invariant de boucle, cela va s’avérer crucial. Utilisez deux bornes inf et sup, vérifiant à chaque étape l’invariant inf <= i < sup, où i est la première position de la valeur dans la liste, si elle y est présente.

Exercice 2: Complexité pratique des algorithmes de recherche

  1. Utiliser la fonctionalité de Python pour mesurer le temps d’exécution de vos fonctions recherche sur diverses entrées:

%time recherche([1,2,3],5);

Lancer cette commande plusieurs fois; que constatez vous?
Pour obtenir un temps moyenné automatiquement sur plusieurs exécutions, vous pouvez aussi utiliser:

%timeit recherche([1,2,3],5);

Ces deux commandes ont l’inconvénient d’afficher leur résultat plutôt que de le renvoyer, ce qui ne permet pas de récupérer les valeurs automatiquement pour, par exemple, en faire un graphique.
Pour automatiser le processus, il faut donc en revenir à la fonction \( time.time \) qui renvoie l’heure actuelle (en secondes depuis le premier janvier 1970):

import time
avant = time.time(); recherche([1,2,3], 5); apres = time.time()
apres-avant             # random

Dans l’exercice 5 on verra une bibliothèque plus avancée pour automatiser le processus.

  1. Seconde méthode de mesure: instrumenter vos fonctions de 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()
sage: compteur

Votre programme ainsi modifié contient une variable globale et doit donc être chargé avec:

%run -i recherche.py

(voir la documentation de %run pour les détails).

  1. Complexité pratique: faire quelques statistiques sur le nombre de comparaisons en moyenne et au pire utilisées par vos fonctions de recherche, en fonction de la taille de la liste; représenter graphiquement les résultats. Comparer l’efficacité des deux méthodes de recherche en les présentant dans un même graphique.
    Indications:

  2. Voir randint() pour créer une liste aléatoire.

  3. Définir une fonction 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.

  4. Voir point() pour afficher un nuage de points. Que fait l’exemple suivant?

point( [ [i, i^2] for i in range(10) ] )
  1. Pour trier une liste:

sorted(['c', 'b', 'a'])
  1. Évaluer la taille maximale d’une liste dans laquelle on peut faire une recherche en moins d’une heure et d’une semaine.

Exercice 3: Implantation de quelques algorithmes de tri

Le but de cet exercice est de mettre en pratique les compétences acquises dans les exercices précédents, dans un cadre un peu plus élaboré.

Pour chaque algorithme de tri, bien prendre le temps de spécifier les invariants, tracer des courbes statistiques de complexité au pire et en moyenne. Comparer avec les courbes théoriques et comparer l’efficacité relative des différents algorithmes.

Vous pouvez partir du fichier annexe tris.py.

Un premier algorithme de tri

Ce premier tri est décrit par son invariant de boucle, à vous de trouver l’algorithme! Cela devrait vous convaincre qu’une fois le bon invariant écrit, la programmation en découle assez simplement.

L’invariant est: «à l’étape \( k \), les \( k \) premiers éléments de la liste sont les \( k \) plus petits éléments de la liste originale, et sont triés».

Tri à bulle en place

Le tri à bulle porte ce nom en référence à l’intuition derrière l’algorithme: les éléments légers (plus petits) remontent tels des bulles dans un liquide plus lourd. On peut aussi le voir dans l’autre sens: les éléments les plus lourds (plus grands) coulent au fond de la liste.

Plus formellement, on parcourt la liste, et dès que l’on trouve une paire successive \(l_{i-1} > l_i\) mal ordonnée, on échange \(l_{i-1}\) et \(l_i\), puis on procède de même entre \(l_{i-2}\) et \(l_i\) et ainsi de suite pour faire remonter \(l_i\) tant que nécessaire.

Tri fusion

Ce nouveau tri, ainsi que le suivant utilisent le principe de diviser pour régner. Ce paradigme de programmation consiste en 3 étapes:

  • Diviser le problème en sous-problèmes plus simples à résoudre;

  • Résoudre les sous-problèmes;

  • Reconstruire la solution au problème de départ à partir des solutions aux sous-problèmes.

Dans le cas du tri, l’étape 1 consiste à couper la liste en plusieurs morceaux, l’étape 2 consiste à trier chaque morceau, et pour la dernière étape on recolle les morceaux de liste comme il faut pour que le tout reste trié. Cette dernière étape dépend évidement de la façon dont on a coupé la liste à l’étape 1.

Pour le tri fusion, l’étape \( 1 \) est brutale: on coupe la liste à la moitié. En supposant les deux sous-listes triées, comment les fusionner pour maintenir le tri ? Cette étape de fusion doit être réalisée en \( |L_1|+|L_2| \) opérations, où \( L_1 \) et \( L_2 \) sont les listes triées à fusionner.

Indication: utiliser une fonction récursive; si nécessaire, s’entraîner en implantant au préalable une fonction récursive pour calculer \( n! \)

Tri rapide

Ici c’est l’inverse, on souhaite que l’étape 3 soit la plus simple possible: on veut qu’il suffise de concaténer les listes. Pour cela, on choisit un élément dit «pivot» dans la liste de départ, et nos deux sous-listes sont obtenues respectivement à partir des éléments strictement plus petits et plus grands que le pivot.

Autres tris

Pour les plus rapides, vous pouvez implanter les tris suivant:

  • tri insertion en place,

  • tri par tas. Indication: utiliser le module heapq de Python,

  • tri par insertion dans un Arbre Binaires de Recherche. Indications:
    1. consulter la documentation de `LabelledBinaryTree` pour trouver comment construire des arbres binaires étiquetés. 1. Définir une fonction récursive `insere(arbre, i)` qui insère un nombre `i` dans un arbre binaire de recherche.

Exercice 4: Complexité de l’algorithme de tri de Python

Estimer la complexité de la fonction suivante:

def fusion(l1, l2):
    return sorted(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

Exercice 5: bancs d’essais au chronomètre

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()

Voici comment en faire un graphique:

points( BB.averages().items() )

De même, on peut accéder au min, max, ainsi qu’à l’intégralité des temps de calculs avec:

BB.mins()
BB.maxes()
BB.timings()