VISI201 CMI : visite de laboratoire

• Cours du semestre 2 du parcours CMI Informatique (licence INFO).

• Responsables pour 2016--2017: Jacques-Olivier Lachaud

Contenu (2016-2017)

Une partie de ce module consiste à assister à des séminaires dédiés aux étudiants CMI Informatique et Mathématique (1 fois par mois, les jeudi après-midi). [Planning des séminaires CMI]

Ces séminaires "grand public" portent sur des sujets variées en informatique et mathématiques.

Les étudiants choisissent ensuite d'approfondir un sujet, dans la liste proposée ci-dessous, ou un sujet motivé de leur choix (en accord avec le responsable du module). Ce travail personnel tuteuré donne lieu à la rédaction d'une synthèse sur le sujet sous forme d'une page wiki/web, ainsi que d'un mini-exposé.

Sujets réalisés (2016-2017)

• Algorithme de rendu de scène 3D par Z-buffer
• Traitement d'image
• Nim et la théorie des jeux impartiaux
• Calculabilité et modèles de calcul
• Génération et résolution de labyrinthes

Sujets proposés (2016-2017)

Algorithme de rendu de scène 3D par Z-buffer

• Tuteur: Jacques-Olivier Lachaud
• Résumé: Le Z-buffer est un algorithme classique de rendu de scène 3D. C'est celui (avec quelques variantes) qui est implémenté dans nos cartes graphiques 3D et qui permet de visualiser des scènes extrêmement complexes en temps réel (typiquement 24 image/s).
• Objectifs:
  1. décrire le principe de la projection 3D vers 2D
  2. décrire la rastérisation des triangles sur une image en pixel
  3. expliquer le principe du Z-buffer qui permet de gérer le fait que certains objets sont cachés par d'autres
  4. expliquer comment les couleurs sont calculées par pixel
  5. indiquer les qualités et limitations de l'algorithme
• Pour aller plus loin
  1. mettre du code démo (WebGL) avec quelques explications sur le pipeline graphique OpenGL
  2. expliquer comment on peut utiliser cet algorithme pour calculer des ombres (shadow map)
• Liens pour démarrer
  • [Wikipedia]
  • [Scratch a pixel]

Traitement d'image

• Tuteur: Jacques-Olivier Lachaud
• Résumé: Le traitement d'image rassemble tous les algorithmes utilisés pour transformer les images, les améliorer, éliminer certaines perturbations, augmenter ou diminuer le contraste, changer les couleurs vers d'autres couleurs, éliminer le flou ou les yeux rouges, faire du cartooning pour un rendu moins photo-réaliste, etc.
• Objectifs:
  1. identifier les grandes familles de traitement: restauration, égalisation, élimination du flou de déplacement, segmentation, etc
  2. identifier les grandes familles de techniques: filtrage spatial, filtrage fréquentiel, optimisation, etc
  3. comprendre les points communs et différences entre le traitement des images noir et blanc et le traitement des images couleurs.
  4. choisir un ou deux algorithmes de traitement et les expliquer en détails
• Pour aller plus loin
  1. Coder un algorithme de traitement d'image simple (e.g, un filtrage médian, ou un algo qui transporte les couleurs d'une photo vers une autre photo)

• Liens pour démarrer
  • [Wikipedia]
  • [Image Processing on line] (permet de tester en ligne des algorithmes sur vos images)

Nim et la théorie des jeux impartiaux

• Tuteur: Pierre Hyvernat

• Étudiant : Luca Chapelle

• Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
• Objectifs:
  1. comprendre la théorie du jeu de Nim (et la programmer)
  2. comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
  3. regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
  4. programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux

• Liens pour commencer
  • jeu de Nim
  • théorème de Sprague Grundy
  • jeu de Grundy

La suite de Conway et la classification périodique des "éléments"

• Tuteur : Pierre Hyvernat
• La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
  • "1" : un "1" -> 11
  • "11" : deux "1" -> 21
  • "21" : un "2", un "1" -> 1211
  • "1211" : un "1", un "2", deux "1" -> 111221
  • etc.

Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".

• Objectifs :
  1. comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
  2. programmer la suite de Conway pour retrouver la classification des "atomes"
  3. écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
  4. écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

• Liens pour commencer
  • [suite de Conway]
  • [suite de Robinson]

Initiation à la démonstration sur ordinateur et certification de logiciel

• Tuteur: Tom Hirschowitz
• Résumé: [Coq] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
• Objectifs:
  1. prendre en main le logiciel [Coq] de démonstration sur ordinateur,
  2. programmer certaines démonstrations basiques en Coq,
  3. suivre le début du cours [Software Foundations],
• Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
• Liens pour démarrer
  • [Software Foundations]
  • [Coq]

Calculabilité et modèles de calcul

• Tuteur: Rodolphe Lepigre
• Résumé: Une fonction f sur l'ensemble des entiers naturels est dite calculable s'il existe une procedure effective (ou un algorithme) qui permet, étant donné un entier n, de calculer f(n) en temps fini. Il existe divers modèles de calcul qui permettent de représenter toutes les fonctions calculables : machines de Turing, λ-calcul, automates cellulaires, ...
• Objectifs:
  1. comprendre la notion de fonction calculable,
  2. comparer l'ensemble des fonctions à l'ensemble des fonctions calculables,
  3. regarder et comparer quelque modèles de calcul,
  4. programmer un modèle de calcul et comprendre les limitations pratiques.

• Liens pour commencer:
  • https://fr.wikipedia.org/wiki/Calculabilité
  • https://fr.wikipedia.org/wiki/Machine_de_Turing
  • https://fr.wikipedia.org/wiki/Lambda-calcul
  • https://fr.wikipedia.org/wiki/Jeu_de_la_vie

Génération et résolution de labyrinthes

• Tuteur: Jacques-Olivier Lachaud Xavier Provençal
• Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
• Objectifs:
  1. Comprendre comment représenter avec une structure de données un labyrinthe
  2. Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
  3. Comprendre l'algorithme d'arbre couvrant minimum
  4. Comprendre le principe du parcours en profondeur et de la récursivité
• Pour aller plus loin
  1. coder la génération d'un labyrinthe et sa visualisation
• Liens pour démarrer
  • [Wikipedia]
  • [Version anglaise plus complète]

Pavages par polyomino

• Tuteur: Xavier Provençal
• Résumé : On s'intéresse aux pavages du plan par des tuiles formées de petits carrés collés les uns aux autres, appelé "polyominos". Étant donné une tuile, peut-on paver le plan ? Si oui, avec quelles opérations (translation et/ou rotations et/ou réflexions) Une fois un pavage réalisé, on observe ses propriétés. Quelles symétries ? Le pavage est-il identique du point de vue de chacune des tuiles ? Si ce n'est pas le cas, en combien de classes peut-on diviser ces tuiles ?

On s'intéressera aussi à des propriétés connexes. Au lieu de paver tout le plan, on peut essayer de paver une région finie donnée. Plus localement, peut-on encercler complètement une tuile avec des copies d'elle-même, sans former de trous ? Si oui, peut-on faire de même avec la proto-tuile formée par la tuile de départ et toutes ses copies ? Si oui, combien de fois peut-on répéter l'opération ?

• Objectifs :
  1. Comprendre les différentes classes de pavages (isohédral, k-isohédral, anisohédral).
  2. Pour chacun des sept types de pavages "isohédraux", comprendre le lien entre les symétries du pavages et la caractérisation des tuiles qui le réalisent.
  3. Pour un pavage k-isohédral, identifier les "classes d'équivalences" et le "domaine fondamental".
• Pour aller plus loin :
  1. Coder la génération de tuiles capables de paver le plan en fonction pour une classe de pavages donnée.
  2. Étudier et implémenter certains algorithmes pour le pavages d'un domaine fini.
• Liens pour démarrer
  • [Polyomino]
  • [Polyomino (en)]
  • [Pavages]