Algorithmique Avancée 2021

Projets

Le choix des projets sera fait le lundi 8/11/2021 à 13h30.

Vous trouverez à la fin des énoncés des fonctions permettant de

• remplir une grande matrice inversible
• générer un graphe non pondéré
• générer un graphe pondéré.

Vous devrez rendre la version complète de votre projet.

Il faut fournir une version électronique.

Cette version comprend, a minima, un rapport sur votre travail (choix, faits, problèmes rencontrés, code d'illustration, mode d'emploi, exemple d'utilisation, discussion…), le code lui-même (un ou plusieurs fichiers y compris le Makefile correspondant).

Le projet doit fonctionner sur l’une au moins des machines du Bocal.

• Avant le samedi 11 décembre, 12h, et le présenter le lundi 13 décembre à partir de 13h30, avec un bonus de 2 points.
• Avant le mardi 4 janvier, 16h, et le présenter le lundi 10 janvier à partir de 13h30, sans bonus.
• Après le mardi 4 janvier, 16h, avec un malus de 2 point par jour de retard entamé.

Il est possible d’améliorer votre travail pratiquement jusqu’à la présentation.

Présentation de vos travaux

Les présentations devront être préparées de façon à ne pas dépasser dix minutes. Elles peuvent inclure des diapositives et une démonstration…

Droites 

Dans tous les cas, il faut :
• Programmer un algorithme de référence, par exemple Bresenham’65.
• Programmer l’algorithme demandé.
• Comparer en temps et en utilisation mémoire les deux algorithmes.
  
• Améliorer significativement l’algorithme demandé.
  

  NB Attention, il faut que votre travail permette de vérifier que les valeurs données sont les bonnes et aussi de mesurer le temps, donc avec des données assez grandes et répétitives. Le temps d’affichage venant grêver ces valeurs, l’affichage sera omis lors du test de temps.

1. Berstel (   )
   
2. Dulucq-Bourdin (  )
   
3. Boyer-Bourdin’2000 (Auto-Adaptative)(  )
   
4. Boyer-Bourdin’1999 (  )
   
5. Triple pas. (    )
   
6. Castle et Pitteway (    )
   
7. Angel et Morrisson (  )

   Compression d’images

   Attention, les projets concernant la compression d’images doivent être faits en utilisant uniquement les bibliothèques standard plus OpenGL, GLUT et/ou SDL et GL4D. La base du programme sera celle donnée ci-dessus, ou celle donnée dans le cours de Programmation Graphique. Il n’est donc absolument pas question de réécrire le programme lui-même, ce que vous avez à faire est simplement d’ajouter des fonctions à ce programme.

   Dans la suite on tentera de compresser une image. Il faudra le faire, ainsi que la décompression associée, et valider la méthode en termes de :
   • temps de calcul, compression et décompression,
   • perte en qualité éventuelle,
   • ratio de compression.
   
    
   
8. Compression par gestion de surfaces unies (    )
   En dessin, par exemple en BD, il est fréquent de trouver de grands à-plats de couleur. Plutôt que de compresser l’image elle-même, pixel par pixel, il faut ici détecter ces taches de couleur, et les traiter individuellement.
   Trouver les taches consiste à trouver et numéroter les zones connexes ayant la même couleur.
   Une bonne méthode consisterait à commencer par trouver tous les pixels connexes ayant une certaine couleur, ils forment une tache. Puis à réitérer ce processus pour tous les pixels.
   On a donc toutes les taches, si elles ont été listées.
   On peut alors mémoriser l’image comme une liste de zones (données par leur contour et la couleur).
   Mettre en place cet algorithme.
   Mettre en place l’algorithme de décompression/affichage d’une telle image.
   Étudier le gain, en temps et en espace.
   

9. Par gestion de graphe non orienté. (  )
   Ce projet représente en fait quatre projets différents. Les projets A, B, C et D, voir plus bas.
   Nous considérons ici qu’une image est un graphe où chaque pixel est un noeud lié au plus à ses quatre voisins. Nous rajoutons une contrainte : un pixel p est lié à son voisin v, si et seulement si p et v sont effectivement voisins (au sens des quatre voisins) et ont la "même" couleur.
   Étudier ce graphe consiste à le gérer, avec son million de noeuds.
   Mettez en place une méthode de recherche des parties connexes du graphe.
   Votre méthode doit vous avoir fourni un numéro pour chaque partie connexe.
   Il suffit maintenant de parcourir une partie connexe en cherchant les sommets qui n’ont pas quatre successeurs, ce sont les sommets de la frontière de la région. Ces sommets seront conservés dans une liste (ou un vecteur). Il est conseillé de se souvenir aussi des pixels liés ou des pixels non liés (au choix).
   La liste de ces listes compose les pixels de bords des regions. Ils organisent donc une partition de l’image. Avec cette liste de listes et la couleur qui y est associée, vous créez une nouvelle façon de stocker l’image.
   Il faut maintenant, mettre en place un système de sauvegarde et un système de restauration de l’image.
   A) Utilisez Mco(    )
   B) Utilisez Lis(    )
   C) Utilisez Vec(    )
   D) Utilisez Brin(    )
   

10. Compression d’une image couleur par l’agorithme des quadtrees.(    )
    Mettre en place la méthode, bien connue pour les images en noir et blanc.
    La tester en temps et en taille de fichier sur de nombreuses images.
    Si les résultats ne vous semblent pas concluants, tentez d’améliorer la méthode.
    

11. RLE(    )
    Mettre en place et testez le run-length-encoding.
    On devra en particulier :
    • Tester le RLE à partir des trois plans R, puis G, puis B.
    • Tester le RLE en ayant transformé l’image en mode HSV et en séparant les champs de H, de S et de V.
    • Écrire dans chaque cas la fonction qui code en mode RLE, la fonction qui fait la sauvegarde et la fonction qui permet d’afficher une image ainsi sauvegardée.
    • Essayer votre méthode sur un bon nombre d’images et comparer les résultats obtenus, en particulier par rapport à des méthodes concurrentes (LZW...).
    
    

12. LZW (     )
    Programmer l’algorithme LZW, pour la compression et pour la décompression. L’appliquer aux images selon les modalités suivantes :
    • Directement au niveau du fichier ppm.
    • En séparant le fichier en quatre parties, entête, les octets de rouge, les octets de vert et les octets de bleu. Puis en appliquant LZW sur chacun de ces quatre fichiers.
    • En transformant l’image pour passer en mode HSV. Puis en séparant le fichier en quatre parties, entête, les octets de hue, les octets de saturation et les octets de value. Puis en appliquant LZW sur chacun de ces quatre fichiers.
    Comparer sur de nombreuses images, les résultats obtenus, en particulier face à des algorithmes concurrents (RLE...).
    

13. Par fenêtres. (     )
    Le principe est, ici, brutal : il s’agit de parcourir l’image par fenêtres de tailles nxn et conservant uniquement un groupe de quatre pixels pour chaque fenêtre. Choisir, pour chaque fenêtre, efficacement, les couleurs de ces quatre pixels.
    Dans ce cas le ratio est connu, c’est 4/(nxn). Par contre ce qui ne l’est pas, c’est la qualité de l’image produite.
    Mettre en place un système de mesure de la qualité de l’image (on peut chercher sur le web).
    Mettre en place une procédure subjective, questionnaire, de mesure de la qualité de l’image produite.
    Discuter les résultats produits.
    

14. Compression d’images par ondelettes.. (    )
    

    Programmer et utiliser l’algorithme des ondelettes (cf. Wikipedia https://fr.wikipedia.org/wiki/Compression_par_ondelettes) Pour faire de la compression d’images. Il faudra utiliser l’algorithme sur l’image en RGB et sur l’image en HSV.

    Compression et décompression seront implémentées et il faudra tester les deux approches sur suffisamment d’images pour discuter les résultats produits.

15. Par simplification. (    )
    Pour toute fenêtre (nxn) de l’image, on trouve une valeur minimale de chacune des couleurs. Puis pour chaque pixel de la fenêtre, la couleur est donnée par un écart sous la forme de quelques chiffres binaires avec la couleur minimale. Par exemple 3 bits pour le vert, 3 pour le rouge et 2 pour le bleu. On a donc, par fenêtre, une couleur puis uniquement un octet pour chaque pixel.
    
    1. Mettre en place cette méthode pour compresser l’image.
    2. Mettre en place cette méthode pour décompresser et afficher l’image.
    3. Comparer la qualité des images (cf. ci-dessus).
    4. Améliorer la méthode en donnant aux chiffres binaires utilisés des valeurs autres que directement +1, +2... +8, car l’écart peut être beaucoup plus important.

    Compression d’images par "color quantization"

    Dans la suite on tentera de compresser une image par réduction du nombre de couleurs utilisées. Il faut, évidemment, programmer la compression et la décompression. On pourra appliquer un algorithme de Dithering pour minimiser les erreurs faites en simplifiant le nombre de couleurs.
    Il faudra valider la méthode en termes de :
    • temps de calcul, compression et décompression,
    • perte en qualité éventuelle,
    • ratio de compression.

    On commencera bien sûr par transformer l’image en passant par une table d’indirection de couleurs (C-LUT).

16. Halftoning and Dithering (  )
    

    Dans ce projet, on réduit à, par exemple, quelques niveaux pour chaque composante (R, G et B). Par exemple on pourra utiliser 64 couleurs avec des niveaux simples (0, 85, 170, 255 pour chaque composante). On utilise alors une CLUT de 64 entrées, sur 6 chiffres binaires.

    1. mettre en place une telle compression/décompression d'image.
    2. On se rend compte qu'en utilisant une telle méthode, une erreur est faite avec le choix d'une couleur simplifiée au lieu de la couleur sur 256 niveaux initiale. Pour corriger cette erreur, mettez en place une méthode de diffusion d'erreur vue en cours (dithering).
17. Limiter le nombre de couleurs par la méthode des octrees.(    )
    

18. Limiter le nombre de couleurs par les BSP.(   )
    

19. Limiter le nombre de couleurs par la méthode de k-means.(   )
    

20. Limiter le nombre de couleurs par une adaptation de l’algorithme de Voronoi.(    )
    

    Graphes 

    Nous avons vu cinq structures pour stocker les graphes : matrice, matrice compacte, vecteur des successeurs, tableaux de brins, liste de successeurs. Nous les notons, dans la suite, respectivement, Mat, Mco, Vec, Brin, Lis.
    

    Vous devrez mettre en place les méthodes demandées avec les structures demandées et discuter des résultats en terme de temps de calcul et de taille de la mémoire utilisée.

21. Composantes connexes 1(    )
    Sur de grands graphes (plus de 10000 noeuds) remplis par la méthode creer , mettre en place les algorithmes de recherche du plus court chemin et de composantes connexes avec Vec et Brin.
    

22. Composantes connexes 2(    )
    Sur de grands graphes (plus de 10000 noeuds) remplis par la méthode creer , mettre en place les algorithmes de recherche du plus court chemin et de composantes connexes avec Lis et Brin.
    

23. Composantes connexes 3(    )
    Sur de grands graphes (plus de 10000 noeuds) remplis par la méthode creer , mettre en place les algorithmes de recherche du plus court chemin et de composantes connexes avec Mco et Brin.
    

24. Voyageur 1(    )
    Résoudre aussi bien que possible le problème du voyageur de commerce, Brin et Mco.
    

25. Voyageur 2(    )
    Résoudre aussi bien que possible le problème du voyageur de commerce, Lis et Vec.
    

26. Voyageur 3(    )
    Résoudre aussi bien que possible le problème du voyageur de commerce, Brin et Vec.
    

27. Voyageur 4(    )
    

    Vous prendrez sur le site national les données concernant les adjacences des villes françaises (https://www.data.gouv.fr/fr/datasets/liste-des-adjacences-des-communes-francaises/). Vous travaillerez sur un seul département, le Val d’Oise. Résoudre aussi bien que possible le problème du voyageur de commerce, Lis et Brin.

28. Voyageur 5(    )
    

    Vous prendrez sur le site national les données concernant les adjacences des villes françaises (https://www.data.gouv.fr/fr/datasets/liste-des-adjacences-des-communes-francaises/). Vous travaillerez sur un seul département, la Seine Saint-Denis. Résoudre aussi bien que possible le problème du voyageur de commerce, Mco et Vec.

29. Shannon 1(  )
    Soit un graphe donné, (le correcteur en proposera un pendant la présentation), le séparer en deux arbres recouvrant disjoints. Mat et Brin.
    Avec ces structures proposer un jeu de Shannon.
    

30. Shannon 2(    )
    Soit un graphe donné, (le correcteur en proposera un pendant la présentation), le séparer en deux arbres recouvrant disjoints. Vec et Mco.
    Avec ces structures proposer un jeu de Shannon.
    

31. Shannon 3(    )
    Soit un graphe donné, (le correcteur en proposera un pendant la présentation), le séparer en deux arbres recouvrant disjoints. Lis et Vec.
    Avec ces structures proposer un jeu de Shannon.
    

32. Canton (    )
    Gérer un réseau de transports en commun, par exemple le métro de Séoul, via un graphe (Lis et Mco). Résoudre dans ce cas le problème du plus court chemin, algorithme de Dijkstra.

33. Madrid(    )
    Gérer un réseau de transports en commun, par exemple le métro de Mexico, via un graphe (Mco et Brin). (  )
    Résoudre dans ce cas le problème du plus court chemin, algorithme de Dijkstra.
    

34. London(    )
    Gérer un réseau de transports en commun, par exemple le métro de Londres, via un graphe (Lis et Vec). (  )
    Résoudre dans ce cas le problème du plus court chemin, algorithme de Dijkstra.
    

35. Limoges(    )
    

    Gérer un réseau de transports en commun, par exemple les 35 lignes de bus de Limoges, via un graphe (Vec et Brin).

    Résoudre dans ce cas le problème du plus court chemin, par exemple avec l’algorithme de Dijkstra.

36. Monte-Carlo(    )
    Gestion aléatoire d’un réseau de transports en commun. La structure du métro pourra être récupérée de l’un des projets précédents. La méthode de recherche du plus court chemin sera basée sur la méthode de Monte-Carlo.
    

37. Analyse d’un programme 1. (    )
    Un programme peut être considéré comme un graphe orienté où chaque fonction est un noeud. Prendre un programme important (plusieurs dizaines de fichiers, plusieurs dizaines de milliers de lignes de code) et l’analyser sous la forme d’un graphe (Mco, Lis). On doit chercher les composantes connexes et les cycles.
    

38. Analyse d’un programme 2.(  )
    Un programme peut être considéré comme un graphe orienté où chaque fonction est un noeud. Prendre un programme important (plusieurs dizaines de fichiers, plusieurs dizaines de milliers de lignes de code) et l’analyser sous la forme d’un graphe (Mco, Vec). On doit chercher les composantes connexes et les cycles.
    

39. Analyse d’un programme 3.(  )
    Un programme peut être considéré comme un graphe orienté où chaque fonction est un noeud. Prendre un programme important (plusieurs dizaines de fichiers, plusieurs dizaines de milliers de lignes de code) et l’analyser sous la forme d’un graphe (Mat, Brin). On doit chercher les composantes connexes et les cycles.
    

40. Analyse d’un programme 4.(  )
    Un programme peut être considéré comme un graphe orienté où chaque fonction est un noeud. Prendre un programme important (plusieurs dizaines de fichiers, plusieurs dizaines de milliers de lignes de code) et l’analyser sous la forme d’un graphe (Lis et Vec). On doit chercher les composantes connexes et les cycles.
    

    Analyse numérique

    Vous trouverez creer une fonction de remplissage de matrices carrées de grandes tailles. Utilisez-la pour faire les travaux suivants :
     
    
41. Comparaison de méthodes permettant de calculer le déterminant de la matrice (méthode classique, triangulation...).(     )
    

42. Stockage (  )
    Comparaison de méthodes de stockage de la matrice. Mat, Mco, Vec. Il faut commencer par mettre en place ces méthodes et, avec les matrices ainsi structurées, faire des multiplications de matrices, des multiplications matrice/vecteur, etc.
    Commenttez vos résultats en temps et mémoire utilisée.
    

43. Résolution de systèmes linéaires de grande taille par la méthode du pivot de Gauss.(    ) 
    

44. Résolution de systèmes linéaires de grande taille par la méthode dite LU.(  )
    

45. Résolution de systèmes linéaires de grande taille par la méthode de Cholesky.(   )
    

46. Résolution de systèmes linéaires de grande taille par la méthode LU réduite aux "contours".(  )
    

47. Résolution de systèmes linéaires de grande taille par la méthode QR.(  )
    

48. Résolution de systèmes linéaires de grande taille par la méthode de raffinement itératif de la solution.(  )
    

Fonctions utiles

• Remplir une grande matrice

  #include <stdio.h> #define MAXMAT 1000 typedef float matrice [MAXMAT] [MAXMAT]; struct matrfloat { int n; matrice m; } ; typedef struct matrfloat mat_t; mat_t creer (int nb) { mat_t m; int i, j, k, l, z, zi; m.n = nb; for (i = 0, k=nb; i < nb; i++, k--) { l = k; m.m[i][i] = (float) l; l >>= 1; for (j = i+1, z=1, zi = 0; j < nb; j++) { if (z == zi) { m.m[i][j] = (float) l; m.m[j][i] = (float) l; l >>= 1; z <<= 1; zi = 0; } else { m.m[i][j] = 0.0; m.m[j][i] = 0.0; zi++; } } } return m; } int main () { mat_t m; int nb; nb = 60; m = creer(nb); }

• Créer un graphe non pondéré

  #include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> typedef short unsigned Shu; struct graphe { int nbs; Shu * tab; } ; typedef struct graphe graphe; graphe creegraphe (int nbs) { Shu i, j, max, num; float v, taux; graphe g; g.nbs = nbs; max = nbs * nbs; taux = 25.0; num = nbs / 10; while (num > 1) { num /= 5; taux /= 3.0; } taux /= 100.0; printf("taux %g\n", taux); g.tab = (Shu *) malloc (max * sizeof(Shu)); memset(g.tab, 0, max); srand(time(NULL)); for (num = 0, i = 0; i < nbs; i++) for (j = 0; j < nbs; j++) { v = (float) rand () / RAND_MAX; g.tab[num++] = v < taux ? 1 : 0; } return g; }

• Créer un graphe pondéré

  graphe creegraphe (int nbs) { Shu i, j, max, num; float v, taux; graphe g; g.nbs = nbs; max = nbs * nbs; taux = 25.0; num = nbs / 10; while (num > 1) { num /= 5; taux /= 3.0; } taux /= 100.0; printf("taux %g\n", taux); g.tab = (Shu *) malloc (max * sizeof(Shu)); memset(g.tab, 0, max); srand(time(NULL)); for (num = 0, i = 0; i < nbs; i++) for (j = 0; j < nbs; j++) { v = (float) rand () / RAND_MAX; g.tab[num++] = v < taux ? (Shu) (v * 1000.) : 0; } return g; }

  ---

  Dernière mise à jour : 29/11/2021 (15h : précisions sur le rapport à rendre)