Algorithmique Avancée 2021

Présentation et Complexité

Présentation
Constantes et complexité
1. Calculs et mesures de complexité
2. Constantes
3. Exemple
De la Droite Discrète
1. Algorithme trivial
2. DDA et accélération
3. Mots de trace
4. Algorithme rapide
Compression
1. Rappels, champs de bits
2. Bases
3. Compression sans perte
4. Compression avec perte
5. Compression d'images
Graphes
1. Codages
2. Algorithmes
Modélisation, Illumination, Rendus
1. 2D/3D
2. Modélisation
3. Illumination
4. Lumière
5. Rendus, quelques effets
6. Rendus Expressifs
Projets

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 du cours de programmation impérative.
2. Objectifs
3. Validation

Complexité

Calculs et mesures de complexité
Constantes

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 : 2340	log : 5
361	 lin : 1060		 vec : 3409	log : 3
391	 lin : 1230		 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.

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 ?

Binôme de Newton

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 mardi 22 septembre 2021 à 16h00.

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) {
  liste crt, pred;
  if (! lr)
    return aplacer;
  if (lr->v > aplacer->v) {
    aplacer->nxt = lr;
    return aplacer;
  }
  crt  = lr->nxt;
  pred = lr;
  while (crt) {
    if (crt->v <= aplacer->v) {
      pred = crt;
      crt = crt->nxt;
    }
    else {
      break;
    }
  }
  aplacer->nxt = crt;
  pred->nxt = 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) {
  liste crt, suiv, prec;
  int flag;
  if (! l || ! (l->nxt))
    return l;
  flag = 1;
  while (flag) {
    crt  = l->nxt;
    prec = l;
    flag = 0;
    //    affliste(l);
    if (prec->v > crt->v) {
      /* intervertir les deux premiers */
      prec->nxt = crt->nxt;
      crt->nxt = prec;
      l = crt;
      crt  = l->nxt;
      prec = l;
      flag = 1;
    }
    suiv = crt->nxt;
    while (suiv) {
      if (suiv->v < crt->v) {
	prec->nxt = suiv;
	crt->nxt  = suiv->nxt;
	suiv->nxt = crt;
	crt = suiv;
	suiv = crt->nxt;
	flag = 1;
      }
      prec = crt;
      crt = suiv;
      suiv = suiv->nxt;
    }
  }
  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

Dernière mise à jour : 30/09/2021 (19h)

Algorithmique Avancée 2021

Présentation et Complexité

Presentation

Complexité