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 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

• 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