VISI401 CMI : bibliographie scientifique

Responsable: Jacques-Olivier Lachaud

Ce module amène l'étudiant à effectuer des recherches bibliographiques sur un sujet donné, et à synthétiser ses résultats sous la forme d'un exposé construit.

L'étudiant, à partir d'un sujet et d'un ou plusieurs articles initiaux, doit approfondir le sujet, appréhender son historique, ses évolutions, et son état actuel.

A côté des ressources fournies par les bibliothèques, quelques pointeurs très utiles pour faire des recherches bibliographiques:

• Scholar Google (libre)
• ResearchGate (libre)
• MashSciNet (plus math)
• Springer (accès via USMB)
• Elsevier Sciencedirect (accès via USMB)
• SciHub lorsqu'on ne trouve pas

La synthèse bibliographique se fait en interaction avec le tuteur par des visites régulières et/ou des compte-rendus d'avancement par email. La synthèse finale fait l'objet d'un exposé final (15-20 minutes + questions) et d'un document de présentation.

travaux réalisés 2018-2019

Les exposés auront lieu le lundi 27 mai de 9h à 11h en salle 115 du chablais. Prévoyez 15-20min suivi de questions.

• T. Porteries: problèmes avec mémoire restreint, tuteur S. Tavenas
• R. Wagner: Reconstruction de surfaces à partir de nuages de points, tuteur J.-O. Lachaud
• N. Ruet: LISP, tuteur P. Hyvernat
• R. Bouvier: dancing links, tuteur P. Hyvernat

sujets 2018-2019

Les sujets 1-3 sont encadrés par J.-O. Lachaud, les sujets 4-5 par P. Hyvernat, le sujet 6 par S. Tavenas. Un encadrant encadre au max 2 étudiants.

1. Débruitage de surfaces maillées (mesh denoising): Etant donné une surface triangulées, dont la position des sommets est "bruité" (en général par les moyens d'acquisitions utilisés pour la fabriquer), ces algorithmes tentent de retrouver la surface initiale, en supposant par exemple qu'elle était lisse ou lisse par morceaux.
   • Bilateral mesh denoising, S Fleishman, I Drori, D Cohen-Or - ACM transactions on graphics (TOG), 2003 - dl.acm.org
   • Mesh denoising via L0 minimization, L He, S Schaefer - ACM Transactions on Graphics (TOG), 2013 - dl.acm.org
   • Variational mesh denoising using total variation and piecewise constant function space, H Zhang, C Wu, J Zhang, J Deng - IEEE transactions on …, 2015 - ieeexplore.ieee.org
2. Approximation de formes: il s'agit de fabriquer, à partir d'une surface maillée précise, une nouvelle surface composée de beaucoup moins de sommets qui l'approche et qui conserve ses caractéristiques principales. Cela sert aussi en compression de formes.
   • Progressive meshes, H Hoppe - Proceedings of the 23rd annual conference on SIGGRAPH, 1996 - dl.acm.org
   • Variational shape approximation, D Cohen-Steiner, P Alliez, M Desbrun - ACM Transactions on Graphics …, 2004 - dl.acm.org
3. Reconstruction de surfaces à partir de nuages de points: il s'agit de trouver comment fabriquer une surface qui approche un ensemble de points dans l'espace.
   • Delaunay triangulation based surface reconstruction.F Cazals, J Giesen - Effective computational geometry for curves and …, 2006 - Springer
   • State of the art in surface reconstruction from point clouds, M Berger, A Tagliasacchi, L Seversky, P Alliez… - EUROGRAPHICS star …, 2014 - hal.inria.fr
   • Bayesian point cloud reconstruction, P Jenke, M Wand, M Bokeloh… - Computer Graphics …, 2006 - Wiley Online Library
4. "dancing links" : l'algorithme X de Knuth est un algorithme élégant et "efficace" pour chercher une solution au problème combinatoire de la couverture exacte. Cet algorithme peut s'appliquer à des problèmes aussi divers que la résolution de sudoku ou le pavage par polyominos. Ce problème fait partie de la classe des problèmes NP-complets qui sont intrinsequement difficiles
   • "Dancing links" : description de l'algorithme X de Knuth et de quelques applications Millennial Perspectives in Computer Science : Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare, Palgrave, coll. « Cornerstones of Computing », 2000
5. Le langage LISP est un des plus vieux langages de programmation encore (un peu) utilisé. (LISP: 1958, C: 1972, Python: 1989). Il s'agit d'un langage fonctionnel avec une syntaxe très simple. La programmation fonctionnelle s'est ensuite developpé dans plusieurs directions, notamment avec la notion de typage fort (Hindley-Milner) utilisé par les langages de la famille ML (SML, Caml)
   • John McCarthy Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I description du langage LISP
   • Robin Milner, A Theory of Type Polymorphism in Programming : description de l'algorithme de typage d'un langage fonctionnel
6. Une question naturelle est de savoir quels sont les problèmes qui peuvent être résolus avec un espace mémoire restreint. Plus formellement, on notera L l'ensemble des problèmes que l'on peut résoudre en utilisant seulement un espace mémoire logarithmique. On s'intéresse à cette classe de problèmes, et plus particulièrement aux problèmes de connectivité dans un graphe.
   • Sylvain Périfel Complexité algorithmique : Un livre récent qui survole une grosse partie de la complexité algorithmique. Le chapitre 4 concerne la complexité en espace.
   • Omer Reingold Undirected Connectivity in Log-Space

travaux réalisés 2017-2018

Les exposés auront lieu le vendredi 25 mai 2018, à 9h. Prévoyez 15-20min suivi de questions.

• ray-tracing au path-tracing, Raphael Tournafond (PDF)
• "dancing links" et NP complétude, Ambroise Decouttere (PDF)

sujets 2017-2018

1. Du ray-tracing au path-tracing: il s'agit de comprendre l'évolution des algorithmes de rendu (dits "réalistes") et de mettre en avant les principales évolutions.
   • An introduction to ray tracing AS Glassner - 1989 - books.google.com
   • Energy redistribution path tracing, D Cline, J Talbot, P Egbert - ACM Transactions on Graphics (TOG), 2005 - dl.acm.org
   • et pour une introduction douce au ray-tracing: TP2 de http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO805/Tests/html/index.html
2. Débruitage de surfaces maillées (mesh denoising): Etant donné une surface triangulées, dont la position des sommets est "bruité" (en général par les moyens d'acquisitions utilisés pour la fabriquer), ces algorithmes tentent de retrouver la surface initiale, en supposant par exemple qu'elle était lisse ou lisse par morceaux.
   • Bilateral mesh denoising, S Fleishman, I Drori, D Cohen-Or - ACM transactions on graphics (TOG), 2003 - dl.acm.org
   • Mesh denoising via L0 minimization, L He, S Schaefer - ACM Transactions on Graphics (TOG), 2013 - dl.acm.org
   • Variational mesh denoising using total variation and piecewise constant function space, H Zhang, C Wu, J Zhang, J Deng - IEEE transactions on …, 2015 - ieeexplore.ieee.org
3. Approximation de formes: il s'agit de fabriquer, à partir d'une surface maillée précise, une nouvelle surface composée de beaucoup moins de sommets qui l'approche et qui conserve ses caractéristiques principales. Cela sert aussi en compression de formes.
   • Progressive meshes, H Hoppe - Proceedings of the 23rd annual conference on SIGGRAPH, 1996 - dl.acm.org
   • Variational shape approximation, D Cohen-Steiner, P Alliez, M Desbrun - ACM Transactions on Graphics …, 2004 - dl.acm.org
4. Reconstruction de surfaces à partir de nuages de points: il s'agit de trouver comment fabriquer une surface qui approche un ensemble de points dans l'espace.
   • Delaunay triangulation based surface reconstruction.F Cazals, J Giesen - Effective computational geometry for curves and …, 2006 - Springer
   • State of the art in surface reconstruction from point clouds, M Berger, A Tagliasacchi, L Seversky, P Alliez… - EUROGRAPHICS star …, 2014 - hal.inria.fr
   • Bayesian point cloud reconstruction, P Jenke, M Wand, M Bokeloh… - Computer Graphics …, 2006 - Wiley Online Library
5. "dancing links" et NP complétude : l'algorithme X de Knuth est un algorithme élégant et "efficace" pour chercher une solution au problème combinatoire de la couverture exacte. Cet algorithme peut s'appliquer à des problèmes aussi divers que la résolution de sudoku ou le pavage par polyominos. Ce problème fait partie de la classe des problèmes NP-complets qui sont intrinsequement difficiles
   • "Dancing links" : description de l'algorithme X de Knuth et de quelques applications Millennial Perspectives in Computer Science : Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare, Palgrave, coll. « Cornerstones of Computing », 2000
   • Classic Nintendo Games are (Computationally) Hard : preuve que Super Mario et d'autres jeux video classiques sont NP-complets Theoretical Computer Science, volume 586, 2015, pages 135–160.
6. Le langage LISP est un des plus vieux langages de programmation encore (un peu) utilisé. (LISP: 1958, C: 1972, Python: 1989). Il s'agit d'un langage fonctionnel avec une syntaxe très simple. La programmation fonctionnelle s'est ensuite developpé dans plusieurs directions, notamment avec la notion de typage fort (Hindley-Milner) utilisé par les langages de la famille ML (SML, Caml)
   • John McCarthy Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I description du langage LISP
   • Robin Milner, A Theory of Type Polymorphism in Programming : description de l'algorithme de typage d'un langage fonctionnel