1. Expériences

L’objectif de ce TP est de mesurer le nombre d’opérations réalisées dans trois algorithmes utilisant des stratégies différentes.

Vous apprendrez à générer des tests, introduire des compteurs de nombre d’opérations et afficher le résultat de ces décomptes grâce à Gnuplot.

Un expérimentateur réalise des expériences sur des marqueurs (par exemple différents échantillons de sang). Chaque expérience permet de tester une hypothèse (par exemple la présence anormale de globules blancs) et fournit un résultat soit positif, soit négatif.

Il dispose d’un certain nombre \(m\) de marqueurs et son protocole expérimental lui permet de récupérer la liste des marqueurs ayant fourni une réaction positive à l’expérience menée (et pas ceux ayant un résultat négatif). Le nombre de ces marqueurs «positifs» sera noté \(p\) (bien sûr \(p \leq m\)). Son objectif est de calculer les marqueurs «négatifs».

1.1. Préparation au travail

  1. Pour créer vos TP d’ASD et les rendre, nous adopterons la même méthodologie que celle utilisée en AP2 (rappel sur cette page).

  2. Récupérez les sources et copiez-les dans votre répertoire réservé à ASD.

    Vous trouverez un module experience. Ce module dispose d’une classe fournissant les méthodes permettant de créer une expérience. A partir de cette expérience, on peut obtenir les marqueurs ayant servi à l’expérience ainsi que les marqueurs postifis. Ces marqueurs sont représentés dans des tableaux NumPy (NumPy array).

    Vous trouverez également un module marker. Ce module dispose d’une classe fournissant les méthodes permettant de créer des marqueurs (dont vous n’avez pas besoin) mais surtout d’une méthode de comparaison de marqueurs.

    Un module sorting dispose d’une fonction implémantant le tri fusion.

    Vous obtiendrez également le programme de test test.py qui prend deux arguments : le nombre de marqueurs ayant fourni une réponse positive \(p\) et le nombre de marqueurs \(m\). Ce programme est fonctionnel (mais ne calcule bien sûr pas ce que vous dvez implanter durant le TP).

  3. Générez la documentation des modules fournis.

Note

Dans le fichier index.rst vous décrirez brièvement l’état de votre TP (ce qui est réalisé ou non).

Les réponses «en français» aux questions appelant ce type de réponse seront écrites dans le fichier index.rst tel que décrit dans la page livrée. Vous pourrez ainsi y mettre des liens vers les courbes produites.

1.2. Stratégie 1

Dans cette première phase, notre expérimentateur, qui n’a pas encore rencontré d’informaticien, utilise une approche naïve qui consiste pour chacun des \(m\) marqueurs à vérifier si le marqueur se trouve dans la liste des marqueurs positifs de manière itérative (il s’arrête tout de même dès qu’il a trouvé). Il ne dispose pas de la possibilité de modifier cette liste.

  1. Proposez une première solution implantant cette stratégie. Ecrivez le code de la fonction negative_markers1 retournant la liste des marqueurs négatifs. Testez le bon fonctionnement.
  2. Pour étudier la complexité de cet algorithme, quelle opération proposez-vous de compter ? (désignons par OP cette opération)
  3. Existe-t-il un pire des cas pour cet algorithme ? Si oui le décrire, sinon justifier.
  4. Exprimez \(c_1(m,p)\) le nombre exact d’opérations OP (pour le pire des cas ou dans le cas général suivant votre réponse à la question précédente) en fonction de \(m\) et \(p\).

1.3. Stratégie 2

Notre expérimentateur rencontre un élève informaticien qui fait la suggestion suivante : «Tu pourrais trier ton ensemble de marqueurs positifs avant de chercher dedans, je suis sûr que tu irais plus vite pour ta comparaison. Par contre une fois que c’est trié il y un truc à faire pour chercher, je ne me souviens plus quoi exactement».

  1. Proposez une seconde solution implantant cette stratégie où la liste des marqueurs positifs est triée. Écrivez le code de la fonction negative_markers2. Testez.
  2. Existe-t-il un pire des cas pour cet algorithme ? Si oui le décrire, sinon justifier. Trouvez une borne supérieure pour le nombre d’opérations \(c_2(m,p)\), en fonction de \(m\) et \(p\).

1.4. Stratégie 3

Notre expérimentateur rencontre alors un autre étudiant qui lui indique : «Mon camarade a raison, mais tu pourrais aller encore plus vite en triant à la fois tes marqueurs et tes marqueurs positifs».

  1. Proposez une troisième solution où à la fois les marqueurs ET les marqueurs positifs sont triés. Écrivez le code de la fonction negative_markers3. Testez.
  2. Existe-t-il un pire des cas pour cet algorithme ? Si oui le décrire, sinon justifier. Trouver une borne supérieure pour le nombre d’opérations \(c_3(m,p)\), en fonction de \(m\) et \(p\).

1.5. Recherche empirique des cas favorables

Nous allons maintenant réaliser des tests en faisant varier le nombre de marqueurs positifs des expériences pour observer la variation du nombre d’opérations. On utilisera la fonction experience qui permet d’obtenir un tableau de marqueurs positifs.

  1. Modifiez vos codes pour que l’on puisse compter le nombre d’opérations OP effectuées dans chacune des trois versions (réfléchissez bien, il n’y a quasiment rien à faire).

  2. Essayez de déterminer, pour chaque version, un exemplaire du problème (les valeurs de \(m\) et \(p\) suffiront) pour lequel une des versions est plus performante. Que constatez-vous ? Expliquez.

  3. Modifiez le programme de test pour qu’il permette de produire pour un nombre de marqueurs donné en argument et un nombre de marqueurs positifs d’une expérience variant de 1 au nombre de marqueurs, le décompte des opérations pour les 3 versions. Pour \(n=10\), votre programme produira une sortie du type (les chiffres donnés ici ne sont pas nécessairement ceux que vous trouverez) :

    10 1 10 10 39
    10 2 19 10 41
    10 3 27 11 43
    10 4 34 12 45
    10 5 40 13 53
    10 6 45 20 56
    10 7 49 24 60
    10 8 52 29 65
    10 9 54 26 62
    10 10 55 38 76
    

    où les colonnes correspondent respectivement à \(m\), \(p\) et aux décomptes.

  4. Créez 10 fichiers pour \(n=10,20,30,40,50,60,70,80,90,100\).

  5. Utilisez Gnuplot pour représenter ces données. Si vous avez redirigé la sortie de votre programme vers un fichier nommé tp1-10.dat pour \(n=10\) alors vous pourrez visualiser les résultats avec les commandes suivantes :

    set title '10 marqueurs'
    plot 'tp1-10.dat' using 2:3 title 'Strategie 1' w l, \
         '' using 2:4 title 'Strategie 2' w l , \
         '' using 2:5 title 'Strategie 3' w l
    

    La suite 2:3 indique que les points en seconde colonne sont les abscisses (\(p\)) et ceux de la troisième les ordonnées (\(m\)). w l (abréviation de with lines) indique de relier les points par une ligne.

    Produisez un graphique pour chaque valeur de \(n\).

  6. Dans le fichier answers.rst faites ce qu’il faut pour inclure vos graphiques et décrire les conclusions que vous en tirez.

    Note

    Pour sauvegarder une image sous Gnuplot, avant de taper la commande plot il suffit de taper les commandes suivantes :

    set term png
    set output 'tp1-10.png'
    

    pour que le graphique soit sauvegardé dans le fichier tp1-10.png au format PNG.