Travaux Pratiques du L5 1999-2000

Les sujets seront traités en une ou deux séances. Pour chaque sujet, les étudiants rédigent un petit rapport de synthèse clair, concis et précis ( 4 pages au plus ). Quelques lignes de codes particulièrement intéressantes pourront être incluses dans le document qui ne doit contenir aucun listing.

[ Oct. 99] QuickSort

[ Nov. 99] Gestion d'une liste de symboles

[ Nov. 99] Compression de Huffman

[ Dec. 99] Parcours Hamiltonien-Backtracking

[ Dec. 99] Gestion des Ensembles Disjoints

ETUDE DE QUICK SORT

    L'objectif de cette feuille de travaux pratiques est de vous faire analyser les performances du tri rapide QuickSort. Trois expériences  sont proposées. Dans la première, vous devez mettre en évidence le comportement non homogène du tri rapide QuickSort. Dans la seconde, vous  déterminerez la performance de votre implantation de QuickSort. La troisième est un  petit challenge :  usez de toute votre astuce pour créer un programme optimal. A vous de jouer !

mots clefs : la commande  times, le tri rapide QuickSort, et le hasard.

Expérience I.

Soit T une table de nombres, de longueur n. Un couple d'indices (i,j) est un dérangement de la table T si  i < j et  T[j] < T[i]. Le nombre de dérangement de T est compris entre 0 et  n(n-1)/2. On constate qu'un  tableau trié est un tableau sans dérangements.
 
  1. Implanter une version  TriRapideCompteur(T) qui trie la table T par une version de QuickSort qui  renvoie le nombre de comparaisons effectuées au cours de la procédure de tri.
  2. Ecrire une procédure  Derangements(T) qui calcule le nombre de dérangements de la table $T$.
  3. Ecrire une procédure  GMT( n, p ) qui construit une table sans dérangements, lui applique p permutations aléatoires avant de la retourner.
  4. Pour une valeur de n assez grande effectuée l'expérience décrite ci-dessous.  Faire une représentation graphique et commenter.
        p = 0;
        m = n*(n-1)/2;
        REPETER
             table = GMT(n, p)
             cpt   = TRI-RAPIDE-COMPTEUR( table)
             der   = DERANGEMENTS( table)
             DETRUIRE( table )
             IMPRIMER( der / m , cpt / m )
             INC( p );
        JUSQUA ( p n/4)

Expérience II

Vous utiliserez la fonction  X-MUL(vec )  définie par

 unsigned long int X-MUL(unsigned long int x )
        {
        x = x << 1;
        if ( x < ( 1 << 30) ) return(x);
        return( x ^ 1073741907 );
        }

  1. Implanter un algorithme de TriRapide, TriRapide( t ).
  2. On pose  x[0] et on construit la suite  x[i] = X-MUL( x[i-1] ) . La suite obtenue est  périodique, pourquoi ? N'essayez pas de trouver la période!
  3. Ecrire une procédure GMrandT(n) qui construit une table de longueur n définie par  T[ i ] = x [ i ]   pour les indices i compris entre 0 et n-2. Observez-les tableaux retournés par GMrandT(n) , commentaires ?
  4. Repéter plusieurs fois l'expérience ci-dessous,  pour quelques valeurs de n bien choisies.
  5. Placez les valeurs obtenues dans une table, puis en déduire les facteurs cachés de votre algorithme.
  6. En théorie, quelle serait est la dimension de la plus grande table que pourrait trier votre implantation du tri rapide en moins d'une heure ?
        table = GMrandT(n )
        temps de TRI-RAPIDE( table)
        DETRUIRE( table );
        IMPRIMER( temps , n )
 

Expérience III

Procédez à toutes les optimisations pour améliorer les performances de votre procédure de tri rapide. Quelle est la taille de la plus grande table que vous arrivez à trier en moins de 5 minutes ?

GESTION D'UNE TABLE DE SYMBOLES

mots clefs : la commande  flex,  liste chaînée, fonction de hachage.
 

Expérience I.

Utilisez la commande unix flex pour construire un analyseur lexical capable de reconnaître les mots dans un fichier de caractère.
 

Expérience II.

Incorporez une gestion de liste de symboles à votre analyseur lexical de sorte à donner la liste des mots qui apparaissent dans le fichier source, en précisant leur fréquence.
 

Expérience III.

Implantez la fonction de hachage modulaire de base B et de module M.
 

Expérience IV.

Ecrire un analyseur lexical pour expérimenter les différentes fonctions de hachages modulaires. Cet analyseur prend en entrée un fichier de caractères et retourne la distribution des hachés des mots du texte source. Choisissez un fichier de mots assez important puis procédez à des expériences faisant varier M et B. Commentaires ?

COMPRESSION DE HUFFMAN

mots clefs : arbres binaires,  code préfixes et codage de Huffman,  manipulation de bits.

Il s'agit d'écrire un logiciel de compression de texte. Les étudiants se répartiront en cinq groupes. Un groupe se charge de l'animation, organise le travail préliminaire et rédige un cahier des charges. Les quatre autres groupes développent un des quatre modules : construction de l'arbre de Huffman, compression, décompression et finalisation d'un produit. Les mangeurs de pizzas se mettront au travail une fois d'accord sur les choix des structures, des procédures et fonctions à développer.

PARCOURS HAMILTONIEN-BACKTRACKING

mots clefs : graphe, chemin et cycle Hamiltonien, backtracking, heuristique.

Soit E un échiquier n x n est un tableau indexé par les couples d'entiers [0,n[ x [0, n[. Conformément aux règles du jeu d'échecs, un cavalier peut se déplacer de la case (x,y) vers la case (x', y') si :

(x' - x )*( y' - y ) = + ou - 2.

Un parcours de cavalier qui passe par toutes les cases de l'échiquier une et une seule fois est un parcours Hamiltonien, si un dernier déplacement permet de revenir sur la case de départ, on dit que c'est un cycle Hamiltonien. Pour en savoir un petit peu plus sur  les graphes, problèmes et terminologie.

http://www-leibniz.imag.fr/GRAPH/francais/apercu.html
 

  1. Ecrire deux procédures ParcoursHamiltonien( org: case ) et CycleHamiltonien( org : case) pour déterminer tous les parcours  et cycles  Hamiltonien partant de la case org.
  2. Faire une table des valeurs trouvées
  3. Donner une expression de la complexité de votre algorithme.
  4. Expliquez comment votre algorithme se perd dans des analyses inutiles, donner un exemple.
  5. Réécrire votre algorithme en privilégiant les déplacements vers les cases les plus contraignantes.
  6. Alors ?

GESTION DES ENSEMBLES DISJOINTS

mots clefs :  graphes, composantes connexes, ensembles dijoints.

Il sagit d'implanter et discuter les différentes heuristiques  abordées en cours dans le cadre de la recherche des composantes connexes d'un graphe  par  la méthode des ensembles disjoints. On considere une  famille de graphes alétoires G(K,M)  parametree par des couples d'entiers. Les sommets  du graphe G(K,M) sont les entiers compris entre 0 et M-1.  Pour chaque couple (x,y), on decide avec une pobabilité K/M de créer  une arete de x vers y.

COMPOSANTES-CONNEXES( X , A)
n   =  CARDINAL(X);
ed = TABLEAU de n ENSEMBLES DISJOINTS;

POUR CHAQUE x DANS X
     ed [ x ] = SINGLETON( x)
POUR CHAQUE  (x,y) DANS A
     SI  REPRESENTANT( ed[x] ) <> REPRESENTANT( ed[y])
         ALORS  UNION( ed[x], ed[y] )
 

[ 1 ]    Quel est le nombre de composantes connexes de G(K,M) , pour  1<=K<=M<=100.
[ 2 ]    Mesurer le temps de calcul de votre programme de recherche de composante connexes applique a G(3, M) pour les valeurs  voisines
de 10000.  Considerer 4 implantations : sans heuristique,  union par rang, compression de chemins et en combinant union par rang et
la compression de chemins.
[ 3 ]      Commenter les  temps d'exécutions.