VISI401 CMI : bibliographie scientifique - Historique des versions

Hyvernat : /* diviser en multipliant, et autres astuces */

2026-01-27T15:11:21Z

diviser en multipliant, et autres astuces

← Version précédente		Version du 27 janvier 2026 à 15:11
Ligne 103 :		Ligne 103 :
	* le livre "Hacker's Delight", contenant notamment un chapitre sur les divisions entières		* le livre "Hacker's Delight", contenant notamment un chapitre sur les divisions entières
	* le site https://godbolt.org/ permettant d'explorer le code généré par les compilateurs standards		* le site https://godbolt.org/ permettant d'explorer le code généré par les compilateurs standards
			* la bibliothèque C / C++ <tt>libdivide</tt> qui permet de remplacer des divisions par des multiplications : https://libdivide.com/

	=== [[Peut-on calculer(efficacement) une transformation de Fourier Rapide sur GPU ]] ===		=== [[Peut-on calculer(efficacement) une transformation de Fourier Rapide sur GPU ]] ===

Hyvernat : diviser en multipliant

2026-01-18T21:01:00Z

diviser en multipliant

← Version précédente		Version du 18 janvier 2026 à 21:01
Ligne 86 :		Ligne 86 :
	[[Fichier:imagequilting.gif\|400px]][[Fichier:Quiltingtransfer.png\|400px]]		[[Fichier:imagequilting.gif\|400px]][[Fichier:Quiltingtransfer.png\|400px]]

	=== [[le ~~bytecode~~ ~~Python~~]] ===		=== [[diviser en multipliant, et autres astuces]] ===

	''' Tuteur :''' Pierre Hyvernat		''' Tuteur :''' Pierre Hyvernat

			''' Résumé :''' lors de la compilation d'un programme (par exemple dans le langage C), de nombreuses optimisations sont faites pour améliorer l'efficacité du code obtenu. On peut par exemple remplacer une multiplication entière par 2 par un décalage des bits vers la gauche, ou une division entière par 2 par un décalage de bits vers la gauche. Une optimisation plus surprenant consiste à remplacer les divisions entières (par des constantes) par ... des multiplications ! (Les multiplications entières sont effectivement plus rapide que les divisions ou les modulo...)
	''' Résumé :''' Python est un langage "interprété". Un programme Python n'est jamais directement transformé en suite d'instructions pour le processeur sur lequel il doit s'exécuter. C'est l'interpréteur qui va, lors de l'exécution, regarder les instructions Python pour les exécuter. Pour éviter que le passage par cet intermédiaire prenne trop de temps, le programme Python est d'abord transformé en un "langage intermédiaire" appelé "bytecode". Ce langage est une espèce de langage d'assemblage propre à Python. Les instructions sont beaucoup plus simples à exécuter que les instructions "haut niveau" et sont identiques pour tous les processeurs.
			L'objectif est de se familiariser avec les techniques simples (décalages, masques et autres manipulations des entiers machines) et d'explorer certaines techniques plus avancées comme la recherches des nombres magiques permettant de remplacer les divisions par des multiplications.

	L'outils principal pour étudier le bytecode python est le module <tt>dis</tt> (comme <tt>dis</tt>assembler) de la version usuelle de Python (CPython).

	'''Objectifs :'''		'''Objectifs :'''
			* se familiariser avec les techniques simples (décalages, masques et autres manipulations des entiers machines),
	* comprendre la différence entre les langages compilé et interprétés
			* comprendre certaines techniques plus avancées comme la recherches des nombres magiques permettant de remplacer les divisions par des multiplications,
	* comprendre globalement le mécanisme de transformation d'un programme Python en bytecode
			* mettre en évidence l'impact de ces techniques, soit en écrivant des benchmark directement en assembleur, soit en désactivant (lorsque c'est possible) les optimisations du compilateur,
	* étudier le bytecode produit sur des exemples particuliers et pertinents (<tt>if</tt>, <tt>for</tt>, comprehension sur les listes, etc.)
			* explorer le code produit, notamment un utilisant https://godbolt.org/
	* comprendre la différence entre les fonctions "builtin" et les définitions Python.

			'''Ressources :'''
			* le livre "Hacker's Delight", contenant notamment un chapitre sur les divisions entières
			* le site https://godbolt.org/ permettant d'explorer le code généré par les compilateurs standards

	=== [[Peut-on calculer(efficacement) une transformation de Fourier Rapide sur GPU ]] ===		=== [[Peut-on calculer(efficacement) une transformation de Fourier Rapide sur GPU ]] ===

Hirschowitz : /* Une petite machine abstraite pour le lambda-calcul */

2026-01-15T09:41:29Z

Une petite machine abstraite pour le lambda-calcul

← Version précédente		Version du 15 janvier 2026 à 09:41
Ligne 20 :		Ligne 20 :
	== sujets 2025-2026 ==		== sujets 2025-2026 ==

	=== [[Une petite machine abstraite pour le ~~lambda~~-calcul]] ===		=== [[Une petite machine abstraite pour le λ-calcul]] ===

	'''Tuteur :''' Tom Hirschowitz		'''Tuteur :''' Tom Hirschowitz

			'''Résumé :''' Le λ-calcul est un modèle mathématique assez simple d'un langage de programmation fonctionnelle minimal : on dispose seulement de variables, de fonctions de première classe, et de l'application de fonction. Pourtant, ce langage suffit à programmer les entiers naturels et toutes les fonctions récursives. Pourtant, la définition mathématique (pas si simple!) du λ-calcul pose des problèmes d'implémentation. Le but du projet est de programmer un interpréteur pour le λ-calcul et d'expérimenter les techniques classiques de programmation permettant par exemple d'exprimer les fonctions récursives.
	'''Résumé :'''

	'''Objectifs :'''		'''Objectifs :'''

			- Découverte du λ-calcul sur le plan mathématique.

			- Bibliographie rapide sur les stratégies de réduction et les techniques d'implémentation.

			- Programation d'un interpréteur naïf de type CAM ou KAM.

			- Expérience des techniques de programmation standard.

			- Programmation d'un interpréteur optimisé de type ZAM.

	'''Références :'''		'''Références :'''

			Sur le λ-calcul:

			- un [https://lsv.ens-paris-saclay.fr/~goubault/Lambda/lambda-agreg-1_compressed.pdf cours] de Jean Goubault-Larrecq,

			- une [https://repository.ubn.ru.nl/bitstream/handle/2066/17289/17289.pdf introduction] de Henk Barendregt.

			Sur les machines abstraites:

			- un [https://xavierleroy.org/talks/zam-kazam05.pdf exposé] de Xavier Leroy.

	=== [[Formalisation du jeu de Nim en Rocq]] ===		=== [[Formalisation du jeu de Nim en Rocq]] ===

Hyvernat : /* Formalisation du jeu de Nim en Rocq */

2026-01-13T10:38:39Z

Formalisation du jeu de Nim en Rocq

← Version précédente		Version du 13 janvier 2026 à 10:38
Ligne 34 :		Ligne 34 :
	'''Tuteur :''' Robin Jourde		'''Tuteur :''' Robin Jourde

			'''Résumé :''' on considère le jeu à deux joueurs suivant. On dispose de N jetons, tour à tour chaque joueur peut retirer 1, 2 ou 3 jetons et l'objectif est de retirer le dernier jeton. Il est possible de jouer à ce jeu de manière optimale, c'est-à-dire de s'assurer la victoire (quand elle est possible) en appliquant une stratégie simple. L'objectif est de déterminer cette stratégie, de l'implémenter et de démontrer formellement que l'implémentation est correcte. Pour ce faire, on utilisera l'assistant de preuves Rocq au sein duquel il faudra formaliser le problème. On implémentera la stratégie dans le langage Gallina, le langage de spécification de Rocq, fonctionnel et fortement typé.
	'''Résumé :'''

	'''Objectifs :'''		'''Objectifs :'''

			# découverte de l'assistant de preuves Rocq
			# formalisation d'un jeu simple
			# établissement de la stratégie optimale
			# implémentation dans un langage fonctionnel
			# démonstration d'optimalité en Rocq

	'''Références :'''		'''Références :'''

			# Jeux de Nim : https://fr.wikipedia.org/wiki/Jeux_de_Nim
			# Rocq : https://rocq-prover.org/

	=== [[Synthèse de texture et transfert de texture par matelassage d'images]] ===		=== [[Synthèse de texture et transfert de texture par matelassage d'images]] ===

Hyvernat : /* sujets 2025-2026 */

2026-01-13T10:35:55Z

sujets 2025-2026

← Version précédente		Version du 13 janvier 2026 à 10:35
Ligne 19 :		Ligne 19 :

	== sujets 2025-2026 ==		== sujets 2025-2026 ==

			=== [[Une petite machine abstraite pour le lambda-calcul]] ===

			'''Tuteur :''' Tom Hirschowitz

			'''Résumé :'''

			'''Objectifs :'''

			'''Références :'''

			=== [[Formalisation du jeu de Nim en Rocq]] ===

			'''Tuteur :''' Robin Jourde

			'''Résumé :'''

			'''Objectifs :'''

			'''Références :'''


	=== [[Synthèse de texture et transfert de texture par matelassage d'images]] ===		=== [[Synthèse de texture et transfert de texture par matelassage d'images]] ===

Gledelv : /* sujets 2025-2026 */

2026-01-12T12:29:06Z

sujets 2025-2026

@@ Ligne 70 : / Ligne 70 : @@
 * La page wikipedia des FFT https://fr.wikipedia.org/wiki/Transformation_de_Fourier_rapide
 * les supports de cours de l'IDRIS  http://www.idris.fr/formations/supports_de_cours.html
 == sujets 2024-2025 ==

Hyvernat : /* le bytecode Python */

2026-01-09T08:20:59Z

le bytecode Python

← Version précédente		Version du 9 janvier 2026 à 08:20
Ligne 49 :		Ligne 49 :
	* comprendre globalement le mécanisme de transformation d'un programme Python en bytecode		* comprendre globalement le mécanisme de transformation d'un programme Python en bytecode
	* étudier le bytecode produit sur des exemples particuliers et pertinents (<tt>if</tt>, <tt>for</tt>, comprehension sur les listes, etc.)		* étudier le bytecode produit sur des exemples particuliers et pertinents (<tt>if</tt>, <tt>for</tt>, comprehension sur les listes, etc.)
			* comprendre la différence entre les fonctions "builtin" et les définitions Python.

	=== [[Peut-on calculer(efficacement) une transformation de Fourier Rapide sur GPU ]] ===		=== [[Peut-on calculer(efficacement) une transformation de Fourier Rapide sur GPU ]] ===

Hyvernat : /* le bytecode Python */

2026-01-09T08:18:37Z

le bytecode Python

← Version précédente		Version du 9 janvier 2026 à 08:18
Ligne 48 :		Ligne 48 :
	* comprendre la différence entre les langages compilé et interprétés		* comprendre la différence entre les langages compilé et interprétés
	* comprendre globalement le mécanisme de transformation d'un programme Python en bytecode		* comprendre globalement le mécanisme de transformation d'un programme Python en bytecode
	* étudier le bytecode produit sur des exemples particuliers et pertinents (<tt>if</tt>, <tt>for</tt>, ~~concaténation~~, ~~<tt>append</tt>~~)		* étudier le bytecode produit sur des exemples particuliers et pertinents (<tt>if</tt>, <tt>for</tt>, comprehension sur les listes, etc.)

	=== [[Peut-on calculer(efficacement) une transformation de Fourier Rapide sur GPU ]] ===		=== [[Peut-on calculer(efficacement) une transformation de Fourier Rapide sur GPU ]] ===

Wiki-lama : /* Synthèse de texture et transfert de texture par matelassage d'images */

2026-01-07T16:06:16Z

Synthèse de texture et transfert de texture par matelassage d'images

← Version précédente		Version du 7 janvier 2026 à 16:06
Ligne 35 :		Ligne 35 :
	* [[http://graphics.cs.cmu.edu/people/efros/research/quilting.html Efros et Freeman, Siggraph'2001]]		* [[http://graphics.cs.cmu.edu/people/efros/research/quilting.html Efros et Freeman, Siggraph'2001]]

	[[Fichier:imagequilting.gif\|400px]]		[[Fichier:imagequilting.gif\|400px]][[Fichier:Quiltingtransfer.png\|400px]]

	=== [[le bytecode Python]] ===		=== [[le bytecode Python]] ===

Wiki-lama : /* Synthèse de texture et transfert de texture par matelassage d'images */

2026-01-07T16:03:50Z

Synthèse de texture et transfert de texture par matelassage d'images

← Version précédente		Version du 7 janvier 2026 à 16:03
Ligne 35 :		Ligne 35 :
	* [[http://graphics.cs.cmu.edu/people/efros/research/quilting.html Efros et Freeman, Siggraph'2001]]		* [[http://graphics.cs.cmu.edu/people/efros/research/quilting.html Efros et Freeman, Siggraph'2001]]

	[[Fichier:imagequilting.gif\|~~200px~~]]		[[Fichier:imagequilting.gif\|400px]]

	=== [[le bytecode Python]] ===		=== [[le bytecode Python]] ===

VISI401 CMI : bibliographie scientifique - Historique des versions

Hyvernat : /* diviser en multipliant, et autres astuces */

Hyvernat : diviser en multipliant

Hirschowitz : /* Une petite machine abstraite pour le lambda-calcul */

Hyvernat : /* Formalisation du jeu de Nim en Rocq */

Hyvernat : /* sujets 2025-2026 */

Gledelv : /* sujets 2025-2026 */

Hyvernat : /* le bytecode Python */

Hyvernat : /* le bytecode Python */

Wiki-lama : /* Synthèse de texture et transfert de texture par matelassage d'images */

Wiki-lama : /* Synthèse de texture et transfert de texture par matelassage d'images */

Hyvernat : /* diviser en multipliant, et autres astuces */

Hyvernat : diviser en multipliant

Hirschowitz : /* Une petite machine abstraite pour le lambda-calcul */

Hyvernat : /* Formalisation du jeu de Nim en Rocq */

Hyvernat : /* sujets 2025-2026 */

Gledelv : /* sujets 2025-2026 */

Hyvernat : /* le bytecode Python */

Hyvernat : /* le bytecode Python */

Wiki-lama : /* Synthèse de texture et transfert de texture par matelassage d'images */

Wiki-lama : /* Synthèse de texture et transfert de texture par matelassage d'images */