AA2024

Jean-Jacques BOURDIN

E-mail :


jj NOSPAM @ up8.edu
(enlever le NO Spam)

Algorithmique Avancée 2024

Présentation et Complexité

  1. Présentation
  2. Constantes et complexité
    1. Calculs et mesures de complexité
    2. Constantes
    3. Exemple
  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. Codages
    2. Algorithmes
  5. Compression
    1. Rappels, champs de bits
    2. Bases
    3. Compression sans perte
    4. Compression avec perte
    5. Compression d'images
  6. Modélisation, Illumination, Rendus
    1. 2D/3D
    2. Modélisation
    3. Illumination
    4. Lumière
    5. Rendus, quelques effets
    6. Rendus Expressifs
    7. IA et jeux
      2. Algorithmes
  7. Projets

  1. Presentation

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

    L'objectif de ce cours, qui prend la suite des cours "Algorithmique et structures de données" 1 et 2 de l'année précédente, est d'introduire la complexité par l'exemple.
    De nombreux problèmes sont présentés et, pour chacun, différentes méthodes de résolution sont proposées et comparées, tant en pratique qu'en complexité théorique.

    This course aims to present a vivid introduction to algorithms' complexity. It takes place after courses Data Structures and Algorithms 1 and 2 presented during the previous year.
    Examples of problems, and algorithms will be presented with a measure of the improvements over the years.

    1. Bases nécessaires (prérequis)

      Être très à l'aise en programmation (langage C exclusivement). Si ce n'est pas encore le cas, réviser et faire les exercices et partiels des cours de programmation impérative.

    2. Objectifs
    3. Validation

  2. Complexité

    1. Calculs et mesures de complexité
    2. Constantes
    3. Multiplication
      4. Nous avons plusieurs méthodes pour réaliser la multiplication. 
      int mult (int a, int b) {
  if (b != 0)
    return a + mult(a, b-1);
  return 0;
}
int multrt (int a, int b, int acc) {
  if (b == 0)
    return acc;
  return multrt (a, b - 1, acc + a);
}
int multi (int a, int b) {
  if (b < 0)
    return - multrt(a, -b, 0);
  return  multrt(a, b, 0);
}
int qmul (int a, int b) {
  int res;
  res = 0;
  while (b) {
    if (b & 0x01)
      res += a;
    a <<= 1;
    b >>= 1;
  }
  return res;
}
int main () {
  int a, b, c;

  for (a = 3, b = 0; b < 11; b++) {
    c = mult(a, b);
    printf("%3d x %3d == %4d \t", a, b, c);
    c = multi (a, b);
    printf(" %4d \t", c);
    c = qmul (a, b);
    printf(" %4d \t", c);
    printf("\n");
  }
}

    4. 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 à la main 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, vérifiée et validée : 
      typedef unsigned long long int ullint;
struct paire {
  ullint fun;
  ullint fdeux;
} ;
typedef 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;
	/* car on cherche fib(n+1) */
  return res;
}
ullint fibo (int n) {
  paire res;
  if (n >= 0 && n < 92) {
	res = fiblog (n);
	return res.fun;
  }
  return (ullint) 0;
}

      Je teste ce programme, en enlevant la version récursive lourde et j'obtiens ce résultat, où la première colonne donne la valeur de n, la seconde le temps avec le for, la troisième avec le vecteur et la quatrième la version logarithmique vue ci-dessus : 
      JJBook : a.out 600
1	 lin : 8		 vec : 112	log : 11
31	 lin : 152		 vec : 347	log : 41
61	 lin : 249		 vec : 686	log : 63
91	 lin : 362		 vec : 1042	log : 77
121	 lin : 449		 vec : 1151	log : 6
151	 lin : 493		 vec : 1544	log : 6
181	 lin : 604		 vec : 1503	log : 3
211	 lin : 650		 vec : 1913	log : 3
241	 lin : 725		 vec : 1733	log : 3
271	 lin : 838		 vec : 2151	log : 3
301	 lin : 880		 vec : 1974	log : 3
331	 lin : 967		 vec : 2440	log : 5
361	 lin : 1060		 vec : 3409	log : 3
391	 lin : 1240		 vec : 3790	log : 4
421	 lin : 1352		 vec : 3190	log : 3
451	 lin : 1338		 vec : 4693	log : 3
481	 lin : 1406		 vec : 3240	log : 3
511	 lin : 1496		 vec : 3752	log : 4
541	 lin : 1597		 vec : 4740	log : 4
571	 lin : 1726		 vec : 4403	log : 3
JJBook :
      Et maintenant la fonction main qui permet de faire fonctionner tout cela. 
      #define ITER 1000
int main (int argc, char ** argv) {
  int n, i, j, resl, pas;
  ullint res;
  clock_t t0, t1, dt;

  if (argc < 2) {
	n = 30;
  }
  else {
	n = atoi(argv[1]);
  }
  if (n < 40) {
    /* jusqu a 40  on peut utiliser la recursivite lourde */
	for (i = 1; i < n; i+= 5) {
	  t0 = clock();
	  resl = fibexp(i);
	  t1 = clock();
	  dt = t1 - t0;
	  printf ("nb : %d\t exp : %d\t", i, (int) dt);
	  t0 = clock();
	  res = fiblin(i);
	  t1 = clock();
	  dt = t1 - t0;
	  printf ("lin : %d\t", (int) dt);
	  t0 = clock();
	  res = fibo(i);
	  t1 = clock();
	  dt = t1 - t0;
	  printf ("log : %d\n", (int) dt);
	}
  }
  else {
/* on va reiterer le calcul pour avoir des resultats significatifs*/
	pas = n / 20;
	for (i = 1; i < n; i+= pas) {
	  t0 = clock();
	  for (j = ITER; j--; ) {
		res = fiblin(i);
	  }
	  t1 = clock();
	  dt = t1 - t0;
	  printf ("nb : %d\t lin : %d\t", i, (int) dt);
	  t0 = clock();
	  for (j = ITER; j--; ) {
		res = fibo(i);
	  }
	  t1 = clock();
	  dt = t1 - t0;
	  printf ("log : %d\n", (int) dt);
	}
  }
}

      Que devons-nous en penser ?

    5. Binôme de Newton
      6. 	1  0  0  0  0  0
	1  1  0  0  0  0
	1  2  1  0  0  0
	1  3  3  1  0  0
	1  4  6  4  1  0
	1  5 10 10  5  1
	1  6 15 20 15  6

      Mettre en place cinq méthodes permettant de calculer une valeur (n,m) du triangle de Pascal (ou du binôme de Newton). Les évaluer en temps.
      les méthodes :

      1. Récursive classique où une valeur est la somme des deux de la ligne au-dessus.
      2. Itérative, dans un tableau, faire le calcul de chaque ligne, une à une.
      3. Itérative, dans un vecteur, faire le calcul d‘une ligne, puis utiliser cette ligne pour calculer la suivante et ainsi de suite.
      4. Itérative incrémentale, où on conserve dans un fichier les valeurs déjà obtenues et où on complète le fichier chaque fois que nécessaire.
      5. Par les factorielles.

      Testez ces méthodes en temps et en espace. Renvoyez par mail ce travail avant lundi 30 septembre 2024 à 12h00.

    6. Tris
      Testez de la même manière les différents algorithmes de tri, (tri par bulles, par tas, par insertion, quicksort...).
      On pourra utiliser la fonction suivante pour remplir un vecteur de taille n avec des nombres à virgule.
      Ci-dessous une fonction permettant de remplir un grand vecteur de flottants. 
      
struct vecfloat {
  int nbele;
  float * v;
} ;
typedef struct vecfloat vec_t;

vec_t creeretremplir (int nb) {
  vec_t w;
  int i;
  float x, y, z, *pt;
  if (nb < 2)
	nb = 10;
  w.nbele = nb;
  w.v = (float *) malloc (nb * sizeof(float));
  assert(w.v);
  x = 1.0;
  y = 0.13;
  z = 0.021;
  pt = w.v;
  for (i = 0; i < nb; i++) {
	*pt++ = x;
	x += y;
	y += z;
	if (x > 1.5) {
	  x -= 1.01;
	}
	if (x < 0.5) {
	  x += 0.499;
	}
	if (y > 1.) {
	  y = y - 1.01;
	}
	if (x < 0.5) {
	  y += 0.5001;
	}
  }
  return w;
}
      Dans le même état d‘esprit une fonction permettant de créer une vraiment grande liste : 
      
struct cellfloat {
  float v;
  struct cellfloat * nxt;
} ;
typedef struct cellfloat cellfloat_t;
typedef struct cellfloat * liste;


liste creer (int nb) {
  liste tete, crt;
  int i;
  float x, y, z;
  if (nb < 2)
	nb = 10;
  tete = NULL;
  x = 1.0;
  y = 0.13;
  z = 0.021;
  for (i = 0; i < nb; i++) {
    crt = malloc (sizeof (cellfloat_t));
    assert (crt);
    crt->v   = x;
    crt->nxt = tete;
    tete     = crt;
    x += y;
    y += z;
    if (x > 1.5) {
      x -= 1.01;
    }
    if (x < 0.5) {
      x += 0.499;
    }
    if (y > 1.) {
      y = y - 1.01;
    }
    if (x < 0.5) {
      y += 0.5001;
    }
  }
  return tete;
}
      Ci-dessous un exemple de programme incomplet permettant de tester sur de grandes listes trois algorithmes différents. 
      
#include<stdlib.h>
#include<assert.h>
#include<time.h>

struct cellfloat {
  float v;
  struct cellfloat * nxt;
} ;
typedef struct cellfloat cellfloat_t;
typedef struct cellfloat * liste;


liste creer (int nb) {
  liste tete, crt;
  int i;
  float x, y, z;
  if (nb < 2)
	nb = 10;
  tete = NULL;
  x = 1.0;
  y = 0.13;
  z = 0.021;
  for (i = 0; i < nb; i++) {
    crt = malloc (sizeof (cellfloat_t));
    assert (crt);
    crt->v   = x;
    crt->nxt = tete;
    tete     = crt;
    x += y;
    y += z;
    if (x > 1.5) {
      x -= 1.01;
    }
    if (x < 0.5) {
      x += 0.499;
    }
    if (y > 1.) {
      y = y - 1.01;
    }
    if (x < 0.5) {
      y += 0.5001;
    }
  }
  return tete;
}

void affliste (liste l)  {
  while (l) {
    printf("%f \t", l->v);
    l = l->nxt;
  }
  printf("\n");
}
liste insere (liste lr, liste aplacer) {

	     
  return lr;
}
liste trii (liste l) {
  liste res, amettre;
  res = NULL;
  while (l) {
    amettre = l;
    l = l->nxt;
    amettre->nxt = NULL;
    res = insere(res, amettre);
  }
  return res;
}
liste bull (liste l) {

  return l;
}
      
int main (int argc, char ** argv) {
  int n;
  liste ll, lt, crt;
  clock_t td, ta;
  if (argc == 2)
    n = atoi (argv[1]);
  else
    n = 20;
  ll = creer(n);
  lt = NULL;
  td = clock();
  lt = trii (ll);
  ta = clock();
  printf("Tri insertion\t taille %d\t temps %d\n",n,(int) (ta - td));
  ll = creer(n);
  td = clock();
  lt = bull (ll);
  ta = clock();
  printf("Tri bulles\t taille %d\t temps %d\n",n,(int) (ta - td));
  ll = creer(n);
  td = clock();
  lt = qs (ll);
  ta = clock();
  printf("Quicksort\t taille %d\t temps %d\n",n,(int) (ta - td));
}
      Voici ce que donne l'utilisation de ce programme, j'espère que nous voyons tous les qualités des différents algorithmes présentés. 
      JJBook : a.out 100
Tri insertion	 taille 100	 temps 17
Tri bulles	 taille 100	 temps 71
Quicksort	 taille 100	 temps 12
JJBook : a.out 1000
Tri insertion	 taille 1000	 temps 850
Tri bulles	 taille 1000	 temps 5170
Quicksort	 taille 1000	 temps 128
JJBook : a.out 10000
Tri insertion	 taille 10000	 temps 128015
Tri bulles	 taille 10000	 temps 644317
Quicksort	 taille 10000	 temps 1462
JJBook : a.out 100000
Tri insertion	 taille 100000	 temps 31228784
Tri bulles	 taille 100000	 temps 128849142
Quicksort	 taille 100000	 temps 25852
      Arrivez-vous au même genre de résultats ?

      Testez ces méthodes en temps et en espace. Renvoyez par mail ce travail avant lundi 30 septembre 2024 à 12h00.

      Can you tell me why?

      Mais j‘ai aussi obtenu ceci : 
      Blanc14.local: gcc listes.c
Blanc14.local: a.out 100

Tri insertion	 taille 100	 temps 51
Tri bulles	 taille 100	 temps 2
Quicksort	 taille 100	 temps 62
Blanc14.local: a.out 1000

Tri insertion	 taille 1000	 temps 329
Tri bulles	 taille 1000	 temps 1
Quicksort	 taille 1000	 temps 935
Blanc14.local: a.out 10000

Tri insertion	 taille 10000	 temps 33957
Tri bulles	 taille 10000	 temps 31
Quicksort	 taille 10000	 temps 159903
Blanc14.local: a.out 100000

Tri insertion	 taille 100000	 temps 13296911
Tri bulles	 taille 100000	 temps 550
Quicksort	 taille 100000	 temps 46926130
      Pourtant je n‘ai pas beaucoup modifié le programme : 
      
int main (int argc, char ** argv) {
  int n;
  liste_t ll, lt, crt;
  clock_t td, ta;
  if (argc == 2)
    n = atoi (argv[1]);
  else
    n = 20;
  ll = creer(n);
  lt = NULL;
  td = clock();
  lt = trii (ll);
  ta = clock();
  printf("Tri insertion\t taille %d\t temps %d\n",n,(int) (ta - td));
  ll = creer(n);
  td = clock();
  lt = bull (lt);
  ta = clock();
  printf("Tri bulles\t taille %d\t temps %d\n",n,(int) (ta - td));
  ll = creer(n);
  td = clock();
  qs (<);
  ta = clock();
  printf("Quicksort\t taille %d\t temps %d\n",n,(int) (ta - td));
}

      Dernière mise à jour : 1/10/2024 (12h)