Jean-Jacques BOURDIN

E-mail :
Jean-Jacques.Bourdin NOSPAM @ ai.univ-paris8.fr
(enlever le NO Spam)


Algorithmique Avancée


Automne 2017
Fall 2017


Ce cours fait partie de l'U.E. "Informatique V" de la troisième année de la Licence Informatique.
This course takes place on the third year of Computer Science curriculum.


Les cours du jeudi auront lieu :



  1. Présentation
  2. Constantes et complexité
    1. Calculs de complexité
    2. Mesures de complexité
    3. Constante
  3. De la Droite Discrète
    1. Algorithme trivial
    2. DDA et accélération
    3. Mots de trace
    4. Algorithme rapide
  4. Graphes
    1. Codage
    2. Algorithmes
  5. Compression
    1. Bases
    2. Compression sans perte
    3. Compression avec perte
    4. Compression d'images
  6. Quelques rappels de programmation C
  7. Remplir une grande matrice
  8. Projets


  1. Presentation

    It is possible for this course to be taught in english, would you mind?

    1. Bases nécessaires (prérequis)
    2. Objectifs
    3. Validation

  2. Complexité

    1. Fibonacci
      Regardons les différentes méthodes pour calculer la n-ième valeur de la suite de Fibonacci.
      
        f(0) = 1
        f(1) = 1
        f(n) = f(n-1) + f(n-2)
      
      c'est non seulement une définition mais une façon de faire le calcul. Essayez-la et vous verrez qu'elle n'est pas si efficace que ça.
      Une autre, avec des vecteurs :
      	  f[0] = 1
      	  f[1] = 1
      	  for (i = 2; i <= n; i++)
      		f[i] = f[i-1] + f[i-2]
      
      Une autre, où on compte de gauche à droite :
            a = 1;
            b = 1
            for (i = 1; i < n; i++) {
                 c = a + b;
                 b = a;
                 a = c;
            }
      
      et enfin la plus sérieuse :
      typedef unsigned long long int ullint;
      struct paire {
        ullint fun;
        ullint fdeux;
      } ;
      tyepdef struct paire paire;
      
      paire fiblog (int n) {
        paire mi, res;
        ullint fi;
        int i;
      
        if (n < 2) {
      	res.fun = (ullint) 1;
      	res.fdeux = (ullint) 1;
      	return res;
        }
        i = n >> 1;
        mi = fiblog(i);
        if (n & 0x01) {
      	res.fdeux = mi.fun * mi.fun + mi.fdeux * mi.fdeux;
      	res.fun = (mi.fun + mi.fdeux + mi.fdeux) * mi.fun;
      	return res;
        }
        res.fun = mi.fun * mi.fun + mi.fdeux * mi.fdeux;
        res.fdeux = (mi.fun + mi.fun - mi.fdeux) * mi.fdeux;
        return res;
      }
      ullint fibo (int n) {
        paire res;
        if (n >= 0 && n < 92) {
      	res = fiblog (n);
      	return res.fun;
        }
        return (ullint) 0;
      }
      
    2. Tris
      Testez de la même manière les différents algorithmes de tri, (tri par bulles, par tas, par insertion, quicksort...).
  3. De la Droite Discrète

    1. Définition
      De droite il n'est pas question, de chemin discret approximant un segment de droite entre deux points, oui.
    2. De l'évidence à la référence
      void droite (int x0, int y0, int x1, int y1) {
        int x, y;
        float yf;
        
        for (x = x0; x <= x1; x++) {
           yf = (float) (x - x0) * (y1 - y0);
           yf /= (x1 - x0);
           yf += y0;
           y = (int) (yf + 0.5);
           affiche(x,y);
        }
      }
      					
      Est à la fois simple et peut efficace. Jack Bresenham a présenté un travail fort différent en 1962 (publié en 1965) :
      void droite_br (int u, int v) {
         int x, y, delta, incD, incH;
      
         incH   = v << 1;
         delta  = incH - u;
         incD   = delta - u;
         for (x = 0, y = 0; x <= u; x++) {
            affiche(x, y);
            if (delta > 0) {
               y++;
               delta += incD;
            }
            else {
               delta += incH;
            }
         }
      }
      
    3. Améliorer la référence
      1. Angel et Morrison (CG&A 1991) via le pgcd
        • Calculer g le pgcd de u et v.
        • Calculer ug= u/v et vg= v/g
        • Calculer la droite de pente (ug, vg).
        • Pour l'affichage, réitérer g fois le chemin trouvé.
      2. Rokne, Wyvill et Wu (CG&A 1993) via le pas de deux
        Vous trouverez cet article dans le catalogue de la bibliothèque. Il faut se connecter à votre compte sur le portail de l'Université, puis, dans l'onglet BU en ligne, tout en bas, consulter les bases de données. La seconde est "l'ACM digital library", vous y aller et, là, en haut à gauche vous trouvez un champ recherche, tapez le titre "Fast line scan-conversion" et c'est la permière entrée.
      3. Graham et Iyengar (CG&A 1994) via le pas de trois : "Double- and triple-step incremental generation of lines"
        Vous le trouverez de la même manière.
      4. Gill (CG&A 1994) via le pas de 4, ou 5 ou N
      5. B. et B. (CG&A 2000) via le pas auto-adaptatif.
      Exercice : tester les algorithmes précédents en temps et qualifier le gain effectif.
    4. Chercher ailleurs
      1. "Sous les pavés"
      2. Euclide et applications
        1. Berstel

          Une fois connue la décomposition de la fraction dy/dx en série de fractions continues

          dy/dx = [u0; u1, u2, u3, ..., un]

          l'algorithme suivant peut être utilisé.

                 w(0) = 0
                 w(1) = 0^(u1-1) . 1
                 w(i) = w(i-1)^ui . w(i-2)  (i impair)
                 w(i) = w(i-2) . w(i-1)^ui  (i pair)
                 
          . est l'opérateur de concaténation tandis que "w^n" est la duplication n fois du mot w. Exemple d'utilisation : soit la droite de pente 3/11. La décomposition est [0; 3, 1, 2]. On a :
          	   w(0) = 0
          	   w(1) = 0 0 1
          	   w(2) = 0 0 0 1
          	   w(3) = 0 0 0 1 0 0 0 1 0 0 1
          	   
          Reste à savoir comment on obtient la décomposition d'une fraction en série de fractions continues.
          D'abord remarquons que, dans ce qui nous intéresse, la fraction v/u est plus petite que 1. Donc la fraction v/u=0+1/(u/v)
          Mais u/v c'est u divisé par v plus u modulo v divisé par v.
          vi/ui = 1/(mi + vj/uj), avec
          j = i + 1
          mi = (int) (ui / vi)
          vj = ui % vi
          uj = vi
          On continue ainsi jusqu'à ce que vj soit inférieur à 2.
          la suite [m0; m1, m2, m3,...,mn] est une représentation de la fraction v/u.
        2. Green and Pitteway
                 droite (dx, dy) {
                    dx -= dy;
                    s = "0";
                    t = "1";
                    while (dx != dy) {
                       if (dx > dy) {
                          dx -= dy;
                          t = s . t;
                       }
                       else {
                          dy -= dx;
                          s = s . t;
                       }
                    }
                    return ( s . t ) ^dx;
                  }
                  
                 droitebest (dx, dy) {
                    dx -= dy;
                    s = "0";
                    t = "1";
                    while (dx != dy) {
                       if (dx > dy) {
                          dx -= dy;
                          t = s . t ^(-1);
                       }
                       else {
                          dy -= dx;
                          s = t . s ^(-1);
                       }
                    }
                    return ( s . t ^ (-1) ) ^dx;
                  }
                  
        3. Dulucq et Bourdin Principe général :
          • la fonction phi de m transforme un 1 en une plage de m 0 suivis d'un 1.
          • la fonction phi de m transforme un 0 en une plage de (m+1) 0 suivis d'un 1.
          • la fonction psi de m transforme un 0 en un 0 suivi d'une plage de m 1.
          • la fonction psi de m transforme un 1 en un 0 suivi d'une plage de (m+1) 1.
          • la fonction db traite des cas particuliers, pour éviter les nombreuses fois où on voudrait relancer une récursivité inutile.