Wiki du LAMA (UMR 5127) - Modifications récentes [fr]

Algorithmes de multiplications d'entiers et de matrices

Gledelv — Wed, 13 May 2026 07:33:34 GMT

← Version précédente	Version du 13 mai 2026 à 07:33
(Une version intermédiaire par le même utilisateur non affichée)
(Aucune différence)

Le bytecode Python

Marzin — Tue, 12 May 2026 06:29:31 GMT

correction ortho

Algorithmes de multiplications d'entiers et de matrices

Mangala — Tue, 12 May 2026 04:21:33 GMT

A) Fonctionnement

← Version précédente		Version du 12 mai 2026 à 04:21
(11 versions intermédiaires par le même utilisateur non affichées)
Ligne 152 :		Ligne 152 :
	<p>Ils sont tous sur l'axe des abscisses.</p>		<p>Ils sont tous sur l'axe des abscisses.</p>
	<p>La courbe rouge représente la complexité de la multiplication naïve.</p>		<p>La courbe rouge représente la complexité de la multiplication naïve.</p>
	<p>On remarque que la courbe a un visuel très similaire à la fonction <math>f(x) = x^2</math> </p>		<p>On remarque que la courbe a un visuel très similaire à la fonction <math> f(x) = x^2 </math> </p>
	</div>		</div>
	</div>		</div>
Ligne 162 :		Ligne 162 :
	</div>		</div>
	<div style="max-width:800px;">		<div style="max-width:800px;">
	<p>La courbe rouge représente la complexité de la multiplication naïve récursive.</p>		<p>Cette courbe rouge représente la complexité de la multiplication naïve récursive.</p>
	<p>Elle sera utilisé pour comparer les complexités entre algorithmes car, comme tous récursifs, elle a été codé avec les mêmes biais d'implémentation qu'eux.</p>		<p>Elle sera utilisé pour comparer les complexités entre algorithmes car, comme tous récursifs, elle a été codé avec les mêmes biais d'implémentation qu'eux.</p>
	<p>Théoriquement les deux courbes ci-contre ont la même complexité, mais encore une fois, notre implémentation n'est pas parfaitement optimale et donc ne respecte pas de manière minutieuse le Master Theorem.</p>		<p>Théoriquement les deux courbes ci-contre ont la même complexité, mais encore une fois, notre implémentation n'est pas parfaitement optimale et donc ne respecte pas de manière minutieuse le Master Theorem.</p>
Ligne 178 :		Ligne 178 :
	L'algorithme de multiplication naif récursif utilise la segmentation des facteurs en deux de manière successive.		L'algorithme de multiplication naif récursif utilise la segmentation des facteurs en deux de manière successive.

	Soit <math>x</math> et <math>y</math> deux facteurs, nous avons les égalités suivantes :		Soit <math> x </math> et <math>y</math> deux facteurs, nous avons les égalités suivantes :

	<div style="font-size: 15px;">		<div style="font-size: 15px;">
Ligne 233 :		Ligne 233 :
	<math>(a + b)(c + d)</math>		<math>(a + b)(c + d)</math>
	</div>		</div>


	La relation de récurrence devient donc :		La relation de récurrence devient donc :
	<div style="font-size: 15px;">		<div style="font-size: 15px;">
Ligne 267 :		Ligne 267 :
	On les traite alors comme des polynômes de degré 2:		On les traite alors comme des polynômes de degré 2:

	<math>P(z) = X_2 \cdot z^2 + X_1 \cdot z + X_0</math>		<math> P(z) = X_2 \cdot z^2 + X_1 \cdot z + X_0 </math>
	<math>Q(z) = Y_2 \cdot z^2 + Y_1 \cdot z + Y_0</math>		<math> Q(z) = Y_2 \cdot z^2 + Y_1 \cdot z + Y_0 </math>

	On choisit 5 points distincts pour évaluer nos polynômes.		On choisit 5 points distincts pour évaluer nos polynômes.
Ligne 298 :		Ligne 298 :
	</div>		</div>
	<div style="max-width:800px;">		<div style="max-width:800px;">
			<p>Nous avons réutilisé le graphique précédant, cela nous permettra de comparer Toom-Cook avec les autres algorithmes.</p>
	<p>on a reprit multi récursive (rouge)</p>
	<p>on ~~voit~~ que Toom ~~(vert)~~ en ~~dessous~~ de karatsuba ~~(jaune)~~ en ~~dessous~~ de ~~multi~~ classique ~~(rouge)~~</p>		<p>On remarque que Toom-Cook 3 est plus performant que karatsuba et ainsi que la multiplication classique.</p>
	<p>~~meilleur~~ complexité</p>		<p>Toom-cook est par conséquent un algorithme qui repousse encore une fois la complexité minimum du produit d’entiers.</p>
	</div>		</div>
	</div>		</div>
Ligne 361 :		Ligne 361 :
	Il faut préciser que l'on fait le produit de FFT(A) et FFT(B) terme à terme, soit évaluation par évaluation.		Il faut préciser que l'on fait le produit de FFT(A) et FFT(B) terme à terme, soit évaluation par évaluation.

	Une fois en possession de <math>FFT(C)</math>, qui n'est autre que l'évaluation de notre polynôme final en un nombre suffisant de points pour le retrouver, nous pouvons faire l'<math>IFFT(FFT(C))</math>, qui va nous permettre de retrouver les coefficients de notre polynôme en faisant l'exacte inverse de la FFT.		Une fois en possession de <math>FFT(C)</math>, qui n'est autre que l'évaluation de notre polynôme final en un nombre suffisant de points pour le retrouver, nous pouvons faire l'<math> IFFT(FFT(C)) </math>, qui va nous permettre de retrouver les coefficients de notre polynôme en faisant l'exacte inverse de la FFT.

	Une fois les coefficients retrouvés, il nous suffit de gérer les retenues, et nous retrouvons un entier de la forme : <math>a_0 a_1 (...) a_{n-1} a_n</math>		Une fois les coefficients retrouvés, il nous suffit de gérer les retenues, et nous retrouvons un entier de la forme : <math>a_0 a_1 (...) a_{n-1} a_n</math>
Ligne 396 :		Ligne 396 :
	<div style="display:flex; flex-direction: row; align-items: center; justify-content: center">		<div style="display:flex; flex-direction: row; align-items: center; justify-content: center">
	<div style="display:inline-block; margin:30px; text-align:center;">		<div style="display:inline-block; margin:30px; text-align:center;">
	[[Fichier:~~FFT_image~~.~~webp~~\|500px]]		[[Fichier:FFT complexite.png\|500px]]
	<div><b>Graphiques des complexités</b></div>		<div><b>Graphiques des complexités</b></div>
	</div>		</div>
Ligne 402 :		Ligne 402 :
	<p>Ce graphique ci-contre ne provient pas du fruit de nos recherches personnelles mais illustre bien la comparaison entre la complexité de la FFT et des autres algorithmes.</p>		<p>Ce graphique ci-contre ne provient pas du fruit de nos recherches personnelles mais illustre bien la comparaison entre la complexité de la FFT et des autres algorithmes.</p>
	<p>On remarque que la FFT est très efficace et devance de loin les autres algorithmes en terme de complexité. </p>		<p>On remarque que la FFT est très efficace et devance de loin les autres algorithmes en terme de complexité. </p>
			<p>Les algorithmes les plus efficaces pour calculer le produit de grands entiers reposent aujourd'hui sur des variantes de la transformée de Fourier rapide.</p>
	<p>C'est l'un des plus performants.</p>
	</div>		</div>
	</div>		</div>
Ligne 454 :		Ligne 454 :
	L'étude de ces algorithmes de multiplication nous a clairement montré l'évolution de la complexité algorithmique permettant de gagner en efficacité lorsque la taille des données augmente.		L'étude de ces algorithmes de multiplication nous a clairement montré l'évolution de la complexité algorithmique permettant de gagner en efficacité lorsque la taille des données augmente.

	La multiplication classiqe, en <math>\mathcal{O}(n^2)</math>, résulte d'une approche naïve qui devient rapidement inefficace pour les grands entiers ou les grandes matrices. L'algorithme de Karatsuba nous montre qu'organiser de manière intelligente ses calculs algébrique permet parfois de gagner beaucoup de multiplications, et donc de temps. Nous avons ainsi réussi à passer d'une complexité de <math>\mathcal{O}(n^2)</math> à <math>\mathcal{O}(n^{log_2(3)})</math>, soit environ <math>\mathcal{O}(n^{1/585})</math>.		La multiplication classiqe, en <math>\mathcal{O}(n^2)</math>, résulte d'une approche naïve qui devient rapidement inefficace pour les grands entiers ou les grandes matrices. L'algorithme de Karatsuba nous montre qu'organiser de manière intelligente ses calculs algébrique permet parfois de gagner beaucoup de multiplications, et donc de temps. Nous avons ainsi réussi à passer d'une complexité de <math>\mathcal{O}(n^2)</math> à <math> \mathcal{O}(n^{log_2(3)}) </math>, soit environ <math>\mathcal{O}(n^{1/585})</math>.

	Des méthodes encore plus avancées comme utilise l'algorithme de Toom-Cook-3 continue dans cette idées de divisions d'entiers en blocs plus petits, tandis que la transformée de Fourier rapide change complètement de point de vue. En effet la FFT n'utilise pas la représentation classique des entiers mais fait appel à une vision polynomiale, ce qui transforme la convolution classique en multiplication terme à terme, ce qui lui permet d'atteindre une complexité de <math>\mathcal{O}(n \times log n)</math>.		Des méthodes encore plus avancées comme utilise l'algorithme de Toom-Cook-3 continue dans cette idées de divisions d'entiers en blocs plus petits, tandis que la transformée de Fourier rapide change complètement de point de vue. En effet la FFT n'utilise pas la représentation classique des entiers mais fait appel à une vision polynomiale, ce qui transforme la convolution classique en multiplication terme à terme, ce qui lui permet d'atteindre une complexité de <math>\mathcal{O}(n \times log n)</math>.

Fichier:FFT complexite.png

Mangala — Mon, 11 May 2026 21:16:56 GMT

Mangala a téléversé Fichier:FFT complexite.png

Nouvelle page

Algorithmes de multiplications d'entiers et de matrices

Mangala — Mon, 11 May 2026 21:13:54 GMT

3) La multiplication karatsuba

← Version précédente		Version du 11 mai 2026 à 21:13
(6 versions intermédiaires par le même utilisateur non affichées)
Ligne 123 :		Ligne 123 :

	=== A) Fonctionnement ===		=== A) Fonctionnement ===
	Dans le cas de la multiplication d'entiers, nous allons prendre deux nombres qui n'ont pas nécessairement la même longueur. Soit les nombre a et b, de longueur respective <math>n</math> et <math>m</math>.		Dans le cas de la multiplication d'entiers, nous allons prendre deux nombres qui n'ont pas nécessairement la même longueur. Soit les nombre a et b, de longueur respective <math> n </math> et <math> m </math>.
	<div style="display:flex; flex-direction: row; align-items: center; justify-content: center">		<div style="display:flex; flex-direction: row; align-items: center; justify-content: center">
	<div style="display:inline-block; margin:20px; text-align:center;">		<div style="display:inline-block; margin:20px; text-align:center;">
Ligne 180 :		Ligne 180 :
	Soit <math>x</math> et <math>y</math> deux facteurs, nous avons les égalités suivantes :		Soit <math>x</math> et <math>y</math> deux facteurs, nous avons les égalités suivantes :

	<div style="font-size: ~~20px~~;">		<div style="font-size: 15px;">
	<math>x = a \times B^{n/2} + b</math>		<math>x = a \times B^{n/2} + b</math>
	<math>y = c \times B^{n/2} + d</math>		<math>y = c \times B^{n/2} + d</math>
Ligne 190 :		Ligne 190 :
	Cette présentation des deux facteurs de notre multiplication n'est que la résultante d'un découpage.		Cette présentation des deux facteurs de notre multiplication n'est que la résultante d'un découpage.
	Le [[#Master Theorem\|Master Theorem]] nous montre que :		Le [[#Master Theorem\|Master Theorem]] nous montre que :


	<div style="font-size: ~~20px~~;">		<div style="font-size: 15px;">
	<math>T(n) = 4T(n/2) + O(n)</math>		<math>T(n) = 4T(n/2) + O(n)</math>
	</div>		</div>
Ligne 203 :		Ligne 203 :
	Avec l'écriture ci-dessus des nombres <math>x</math> et <math>y</math>, on peut facilement en déduire l'égalité suivante :		Avec l'écriture ci-dessus des nombres <math>x</math> et <math>y</math>, on peut facilement en déduire l'égalité suivante :

	<div style="font-size: ~~20px~~;">		<div style="font-size: 15px;">
	<math>x \times y = (ac) \times B^n + (ad + bc) \times B^{n/2} + bd</math>		<math>x \times y = (ac) \times B^n + (ad + bc) \times B^{n/2} + bd</math>
	</div>		</div>


	On remarque 4 multiplications longues à faire dans cette expression. Les multiplications dont <math>B</math> est l'un des facteurs sont très rapides puisqu'il s'agit de la base dans laquelle nous travaillons. De cela en résulte un décalage plutôt qu'un vrai calcul à faire.		On remarque 4 multiplications longues à faire dans cette expression. Les multiplications dont <math>B</math> est l'un des facteurs sont très rapides puisqu'il s'agit de la base dans laquelle nous travaillons. De cela en résulte un décalage plutôt qu'un vrai calcul à faire.
Ligne 214 :		Ligne 213 :
	En effet, nous savons déjà que :		En effet, nous savons déjà que :

	<div style="font-size: ~~20px~~;">		<div style="font-size: 15px;">
	<math>(a + b)(c + d) = ac + ad + bc + bd</math>		<math>(a + b)(c + d) = ac + ad + bc + bd</math>
	</div>		</div>
Ligne 220 :		Ligne 219 :
	En manipulant l'égalité nous obtenons :		En manipulant l'égalité nous obtenons :

	<div style="font-size: ~~20px~~;">		<div style="font-size: 15px;">
	<math>ad + bc = (a + b)(c + d) - ac - bd</math>		<math>ad + bc = (a + b)(c + d) - ac - bd</math>
	</div>		</div>
Ligne 229 :		Ligne 228 :

	En effet, l'algorithme n'effectuera alors plus que 3 multiplications :		En effet, l'algorithme n'effectuera alors plus que 3 multiplications :
	<div style="font-size: ~~20px~~;">		<div style="font-size: 15px;">
	<math>ac</math>		<math>ac</math>
	<math>bd</math>		<math>bd</math>
Ligne 236 :		Ligne 235 :

	La relation de récurrence devient donc :		La relation de récurrence devient donc :
	<div style="font-size: ~~20px~~;">		<div style="font-size: 15px;">
	<math>T(n)=3T(n/2)+O(n)</math>		<math>T(n)=3T(n/2)+O(n)</math>
	</div>		</div>

	Et le Master Theorem nous dit que :		Et le Master Theorem nous dit que :
	<div style="font-size: ~~20px~~;">		<div style="font-size: 15px;">
	<math>T(n)\in O(n^{\log_2(3)})</math>		<math>T(n)\in O(n^{\log_2(3)})</math>
	</div>		</div>
Ligne 289 :		Ligne 288 :
	On résout un système d'équations linéaires : <math> R(z) = w_4 z^4 + w_3 z^3 + w_2 z^2 + w_1 z + w_0 </math>		On résout un système d'équations linéaires : <math> R(z) = w_4 z^4 + w_3 z^3 + w_2 z^2 + w_1 z + w_0 </math>
	Finalement nous pouvons recomposer notre grand entier en positionnant les coefficients w_i aux bons rangs (en les décalant) et à gérer les retenues lors de l'addition finale:		Finalement nous pouvons recomposer notre grand entier en positionnant les coefficients w_i aux bons rangs (en les décalant) et à gérer les retenues lors de l'addition finale:
	<math>~~Résultat~~ = w_4 B^{4k} + w_3 B^{3k} + w_2 B^{2k} + w_1 B^k + w_0</math>		Résultat <math>= w_4 B^{4k} + w_3 B^{3k} + w_2 B^{2k} + w_1 B^k + w_0</math>

	=== B) Graphique ===		=== B) Graphique ===
Ligne 401 :		Ligne 400 :
	</div>		</div>
	<div style="max-width:800px;">		<div style="max-width:800px;">
	<p>Ce graphique ci-contre ne provient pas du fruit de nos recherches personnelles mais </p>		<p>Ce graphique ci-contre ne provient pas du fruit de nos recherches personnelles mais illustre bien la comparaison entre la complexité de la FFT et des autres algorithmes.</p>
	<p>On ~~comprend ainsi~~ que ~~certaines~~ ~~complexités~~ ne ~~sont~~ ~~pas~~ ~~raisonnable~~ ~~dans~~ la ~~cadre~~ de la ~~multiplication~~ de ~~grands~~ ~~entiers~~.</p>		<p>On remarque que la FFT est très efficace et devance de loin les autres algorithmes en terme de complexité. </p>
	<p>C'est ~~pourquoi~~ l'~~étude~~ de ~~ces algorithmes s'avère~~ ~~nécessaire~~.</p>		<p>C'est l'un des plus performants.</p>
	</div>		</div>
	</div>		</div>
Ligne 468 :		Ligne 467 :

	Le premier gif est le résultat du travail de 'Walké', licence ci-contre : https://fr.wikipedia.org/wiki/Fichier:Addition.gif		Le premier gif est le résultat du travail de 'Walké', licence ci-contre : https://fr.wikipedia.org/wiki/Fichier:Addition.gif

			Utilisation du site de production graphique "Desmos" : https://www.desmos.com/calculator?lang=fr

	= Sources =		= Sources =

Filage d'image et tracé de droites pour un rendu artistique

Goralczyk — Mon, 11 May 2026 19:29:49 GMT

Histogrammes d'erreurs

Algorithme de Viterbi et modèles de Markov cachés

Garcia — Mon, 11 May 2026 19:09:14 GMT

Un exemple :

← Version précédente		Version du 11 mai 2026 à 19:09
(20 versions intermédiaires par le même utilisateur non affichées)
Ligne 21 :		Ligne 21 :
	<br />		<br />
	[[Fichier:Image_probabiliter_meteo.png\|350px]]		[[Fichier:Image_probabiliter_meteo.png\|350px]]
			<br/>''Image illustrant les chaines de Markov dans le cas de la météo.''

	Cependant, dans des conditions réelles, si l’on veut estimer la météo à un endroit où l’on ne se trouve pas, on va plutôt se baser sur des relevés météorologiques comme l’humidité, la pression atmosphérique ou la température.		Cependant, dans des conditions réelles, si l’on veut estimer la météo à un endroit où l’on ne se trouve pas, on va plutôt se baser sur des relevés météorologiques comme l’humidité, la pression atmosphérique ou la température.
Ligne 38 :		Ligne 39 :
	<br />		<br />
	C'est exactement ce que nous avons implémenté en Python. Pour y parvenir nous avons utilisé plusieurs méthodes :		C'est exactement ce que nous avons implémenté en Python. Pour y parvenir nous avons utilisé plusieurs méthodes :
	# Nous avons d'abord créé une fonction qui génère toutes les combinaisons possibles en fonction du nombre de jours observés.		<br/>1. Nous avons d'abord créé une fonction qui génère toutes les combinaisons possibles en fonction du nombre de jours observés.
	[[Fichier:Algorithme_naif_meteo.png\|600px]]		<br/>[[Fichier:Algorithme_naif_meteo.png\|600px]]
			<br/>''Image illustrant le fonctionnement de l'algorithme naïf.''

	# Pour chaque chemin qui a été créé, la fonction calcule la probabilité en tenant compte de la probabilité de transition d'un jour à l'autre et de la probabilité d'observation.		<br/>2. Pour chaque chemin qui a été créé, la fonction calcule la probabilité en tenant compte de la probabilité de transition d'un jour à l'autre et de la probabilité d'observation.
	# La fonction renvoie le chemin ayant obtenu le score maximal.		<br/>3. La fonction renvoie le chemin ayant obtenu le score maximal.
	<br /> Dans la théorie cette méthode marche parfaitement. Pourtant elle a un problème majeur, si n est un nombre de jours, la fonction doit calculer <math>3^n</math> chemins. En effet, pour le jour 1, nous avons 3 climats possibles, pour le jour 2, chaque climat s'ouvre sur 3 nouvelles branches, etc... Au bout d'un mois, l'ordinateur doit calculer <math>3^{30}</math> chemins soit plus de 200 mille milliards de chemins ce qui rend la tache techniquement très compliquée. Le temps de calcul et la mémoire requise croissent de manière exponentielle avec le nombre de jours observés.		<br /> Dans la théorie cette méthode marche parfaitement. Pourtant elle a un problème majeur, si n est un nombre de jours, la fonction doit calculer <math>3^n</math> chemins. En effet, pour le jour 1, nous avons 3 climats possibles, pour le jour 2, chaque climat s'ouvre sur 3 nouvelles branches, etc... Au bout d'un mois, l'ordinateur doit calculer <math>3^{30}</math> chemins soit plus de 200 mille milliards de chemins ce qui rend la tache techniquement très compliquée. Le temps de calcul et la mémoire requise croissent de manière exponentielle avec le nombre de jours observés.

	<br /> [[fichier:graphe_calculs_naif.png\|400px]]		<br /> [[fichier:graphe_calculs_naif.png\|400px]]
			<br/> ''Modélisation de la courbe associée à <math>3^n</math>.''
	<br /> Sur cette image, nous pouvons voir l'explosivité du nombre de chemins à calculer en fonction du nombre de jours (en abscisse).		<br /> Sur cette image, nous pouvons voir l'explosivité du nombre de chemins à calculer en fonction du nombre de jours (en abscisse).

Ligne 61 :		Ligne 64 :
	On répète cela pour chaque jour jusqu'à la fin en ayant gardé que 3 chemins en mémoire à chaque fois.		On répète cela pour chaque jour jusqu'à la fin en ayant gardé que 3 chemins en mémoire à chaque fois.
	<br /> Une fois qu'on arrive au bout des jours, nous avons 3 chemins, nous choisissons le meilleur des 3 et nous remontons pour calculer la séquence complète. Pour illustrer ce qui a été dit précédemment, voici des images qui illustrent un exemple.		<br /> Une fois qu'on arrive au bout des jours, nous avons 3 chemins, nous choisissons le meilleur des 3 et nous remontons pour calculer la séquence complète. Pour illustrer ce qui a été dit précédemment, voici des images qui illustrent un exemple.
	[[Fichier:viterbi_meteo_1.png\|~~400px~~]]		<br/>[[Fichier:viterbi_meteo_1.png\|500px]]
	<br/> Image illustrant l'initialisation de l'algorithme de Viterbi sur la météo.		<br/> ''Image illustrant l'initialisation de l'algorithme de Viterbi sur la météo.''
	[[Fichier:viterbi_meteo_2.png\|~~400px~~]]		<br/>[[Fichier:viterbi_meteo_2.png\|500px]]
	<br/> Image illustrant le début de la récurrence de l'algorithme de Viterbi sur la météo.		<br/> ''Image illustrant le début de la récurrence de l'algorithme de Viterbi sur la météo.''
	[[Fichier:viterbi_meteo_3.png\|~~400px~~]]		<br/>[[Fichier:viterbi_meteo_3.png\|500px]]
	<br/> Image illustrant la fin de la récurrence de l'algorithme de Viterbi sur la météo.		<br/> ''Image illustrant la fin de la récurrence de l'algorithme de Viterbi sur la météo.''
	[[Fichier:viterbi_meteo_4.png\|~~400px~~]]		<br/>[[Fichier:viterbi_meteo_4.png\|500px]]
	<br/> Image illustrant la remontée de l'algorithme de Viterbi sur la météo.		<br/> ''Image illustrant la remontée de l'algorithme de Viterbi sur la météo.''

	== 4 - L'application en communications : Le code de Convolution ==		== 4 - L'application en communications : Le code de Convolution ==
Ligne 81 :		Ligne 84 :

	[[Fichier:Code_de_convolution_V2.png\|400px]]		[[Fichier:Code_de_convolution_V2.png\|400px]]
			<br/>''Image illustrant le fonctionnement du code de convolution.''

	<br /> Nous avons donc couvert le fonctionnement global de cet encodage. Ce qui le rend puissant c'est sa "mémoire". Du fait que ces boites existent, un bit qui rentre va influencer les xor sur trois tours (entre son entrée en boite1 et sa sortie de la boite3) ce qui permet de retrouver le message original en cas de détérioration du message.		<br /> Nous avons donc couvert le fonctionnement global de cet encodage. Ce qui le rend puissant c'est sa "mémoire". Du fait que ces boites existent, un bit qui rentre va influencer les xor sur trois tours (entre son entrée en boite1 et sa sortie de la boite3) ce qui permet de retrouver le message original en cas de détérioration du message.
Ligne 100 :		Ligne 104 :
	{'depart': '11', 'arrivee': '01', 'bits_emis': [0, 1], 'bit_arrivant': 0},		{'depart': '11', 'arrivee': '01', 'bits_emis': [0, 1], 'bit_arrivant': 0},
	{'depart': '11', 'arrivee': '11', 'bits_emis': [1, 0], 'bit_arrivant': 1}]</code>		{'depart': '11', 'arrivee': '11', 'bits_emis': [1, 0], 'bit_arrivant': 1}]</code>
			<br/>''Modélisation de cette liste en Python.''
	Par exemple, si la machine est dans l'état '00' (indiqué par 'depart'), il n'existe que deux possibilités, l'algorithme ne peut émettre que [0, 0] ou [1, 1] (lu dans 'bits_emis'). Ainsi, dans ce cas, si l'on reçoit [1, 0] on sait tout de suite qu'il y a un problème.		<br/>Par exemple, si la machine est dans l'état '00' (indiqué par 'depart'), il n'existe que deux possibilités, l'algorithme ne peut émettre que [0, 0] ou [1, 1] (lu dans 'bits_emis'). Ainsi, dans ce cas, si l'on reçoit [1, 0] on sait tout de suite qu'il y a un problème.

	<br/> Grâce à cette liste, l'algorithme peut parcourir les différentes possibilités en ne sélectionnant que celles qui ont le minimum d'erreurs. Une fois qu'il a trouvé la meilleure "branche", il lui suffit de tout remonter en lisant les "bit_arrivant" (inscrits dans la liste) pour reconstituer le message.		<br/> Grâce à cette liste, l'algorithme peut parcourir les différentes possibilités en ne sélectionnant que celles qui ont le minimum d'erreurs. Une fois qu'il a trouvé la meilleure "branche", il lui suffit de tout remonter en lisant les "bit_arrivant" (inscrits dans la liste) pour reconstituer le message.
Ligne 106 :		Ligne 111 :
	==== Un exemple : ====		==== Un exemple : ====
	[[Fichier:exemple_viterbi.png\|900px]]		[[Fichier:exemple_viterbi.png\|900px]]
			<br/>''Capture d'écran depuis un terminal exécutant le code python de notre projet.''
	<br />Pour illustrer le fonctionnement final du code, on peut observer la capture d'écran du code ci-dessus.		<br />Pour illustrer le fonctionnement final du code, on peut observer la capture d'écran du code ci-dessus.
	On commence par créer un message que l'on souhaite envoyer ('message_original'). Ensuite on lui fait subir l'encodage de convolution et on altère un bit. A la fin on observe bien que le message d'origine a été retrouvé en dépit de cette dégradation.		On commence par créer un message que l'on souhaite envoyer ('message_original'). Ensuite on lui fait subir l'encodage de convolution et on altère un bit. A la fin on observe bien que le message d'origine a été retrouvé en dépit de cette dégradation.


	=== 5.2 - Viterbi via des tableau de probabilité ===		=== 5.2 - Viterbi via des tableau de probabilité ===
Ligne 121 :		Ligne 126 :
	==== Un exemple : ====		==== Un exemple : ====
	<br />[[Fichier:Capture_d'écran_exemple_application_Viterbi.png\|1200px]]		<br />[[Fichier:Capture_d'écran_exemple_application_Viterbi.png\|1200px]]
			<br/>''Capture d'écran depuis un terminal exécutant le code python de notre projet.''
	<br />Comme on peut le voir sur cette capture d’écran, même avec des perturbations(changements de bits) sur les bits encadrés en rouge, on arrive quand même à retrouver le message initial		<br />Comme on peut le voir sur cette capture d’écran, même avec des perturbations(changements de bits) sur les bits encadrés en rouge, on arrive quand même à retrouver le message initial

← Version précédente		Version du 12 mai 2026 à 06:29
Ligne 3 :		Ligne 3 :

	<h1>Introduction </h1>		<h1>Introduction </h1>
	Python est un langage de programmation multiparadigme (à la fois impératif, fonctionnel et orienté objet) créé en 1991. A la ~~difference~~ des langages compilés comme le C, le C++ ou le Rust, le python lui est un langage interprété (nous verrons la différence juste après). Il a la particularité dans son execution, de transformer le code en un code intermédiaire simplifié appelé Bytecode. Ce projet porte sur l'étude du fonctionnement d'un ~~interprèteur~~ python, et plus particulièrement du Bytecode.		Python est un langage de programmation multiparadigme (à la fois impératif, fonctionnel et orienté objet) créé en 1991. A la différence des langages compilés comme le C, le C++ ou le Rust, le python lui est un langage interprété (nous verrons la différence juste après). Il a la particularité dans son execution, de transformer le code en un code intermédiaire simplifié appelé Bytecode. Ce projet porte sur l'étude du fonctionnement d'un interpréteur python, et plus particulièrement du Bytecode.

	<h1 id='compilation'>Langage compilé VS interprété</h1>		<h1 id='compilation'>Langage compilé VS interprété</h1>
	Un langage compilé est un langage qui necessite de passer par un compilateur (un programme qui transforme un code source en un code objet) pour transformer le code de base en instructions de bas niveau proche de l'assembleur ~~éxecutable~~ par la machine. En C par exemple, on doit compiler un programme C pour le transformer en .exe avant de pouvoir le lancer. Le compilateur analyse syntaxiquement tout le code, puis le transforme, ce qui fait que les erreurs sont ~~detectées~~ plus tôt. Les langages compilés ont la particularité d'être très rapides et performants, un programme déjà compilé étant très facilement ~~executable~~. Néanmoins, celà rend le débug ainsi que les test plus complexes. </br>		Un langage compilé est un langage qui necessite de passer par un compilateur (un programme qui transforme un code source en un code objet) pour transformer le code de base en instructions de bas niveau proche de l'assembleur exécutable par la machine. En C par exemple, on doit compiler un programme C pour le transformer en .exe avant de pouvoir le lancer. Le compilateur analyse syntaxiquement tout le code, puis le transforme, ce qui fait que les erreurs sont détectées plus tôt. Les langages compilés ont la particularité d'être très rapides et performants, un programme déjà compilé étant très facilement exécutable. Néanmoins, celà rend le débug ainsi que les test plus complexes. </br>
	Un langage interprété a lui besoin d'un interpréteur (ou interprète) pour fonctionner. Il récupère un code source, le traîte, le transforme et l'execute ~~dirrectement~~ dans une machine virtuelle. Les langages interprétés sont donc par conséquent plus lents que les langages compilés, mais il permettent une plus grande flexibilité. La plupart des ~~interpreteurs~~ traîtent et executent le code instruction par instruction. Or, ce n'est pas totalement le cas de l'~~interprèteur~~ python.		Un langage interprété a lui besoin d'un interpréteur (ou interprète) pour fonctionner. Il récupère un code source, le traîte, le transforme et l'execute directement dans une machine virtuelle. Les langages interprétés sont donc par conséquent plus lents que les langages compilés, mais il permettent une plus grande flexibilité. La plupart des interpréteurs traîtent et executent le code instruction par instruction. Or, ce n'est pas totalement le cas de l'interpréteur python.

	<h1>Spécificité de Python</h1>		<h1>Spécificité de Python</h1>
	L'interpréteur python a un fonctionnement bien particulier. En effet, il est un hybride entre ~~interprète~~ et compilateur. </br>		L'interpréteur python a un fonctionnement bien particulier. En effet, il est un hybride entre interpréteur et compilateur. </br>
	Le code source python est d'abord analysé syntaxiquement et ~~cémantiquement~~ en entiereté par un lexer et un parser (expliqué plus en détails plus bas), puis est compilé en code objet intermédiaire, le bytecode. Ce bytecode est ensuite executé instruction par instruction par la machine virtuelle python. </br>		Le code source python est d'abord analysé syntaxiquement et sémantiquement en entiereté par un lexer et un parser (expliqué plus en détails plus bas), puis est compilé en code objet intermédiaire, le bytecode. Ce bytecode est ensuite executé instruction par instruction par la machine virtuelle python. </br>
	La syntaxe du bytecode est plutôt claire et s'apparente à de l'assembleur siplifié. Chaque ~~instructions~~ du code source python (affectation, calcul, definition de fonction ...) a sa propre représentation bien précise en bytecode. </br>		La syntaxe du bytecode est plutôt claire et s'apparente à de l'assembleur siplifié. Chaque instruction du code source python (affectation, calcul, definition de fonction ...) a sa propre représentation bien précise en bytecode. </br>
	Voici un exemple de bytecode pour l'instruction <strong> a = 10 :</strong> </br>		Voici un exemple de bytecode pour l'instruction <strong> a = 10 :</strong> </br>
	[[Fichier:Bytecode1.png]]		[[Fichier:Bytecode1.png]]

	<h1>Description du projet</h1>		<h1>Description du projet</h1>
	Dans le cadre de nos recherches sur le sujet, nous avons décidé pour comprendre comment fonctionne l'~~interprèteur~~ python d'en recoder une version simplifiée. Le code que nous avons réalisé prend en entrée un code source python basique, le transforme en code intermédiaire inspiré du vrai bytecode de Python3, et l'execute dans une machine virtuelle. Nous avons donc trouvé pertinnent de découper ce projet en deux parties distinctes : la partie <strong>Compilation</strong> et la partie <strong> Machine virtuelle et execution </strong> </br>		Dans le cadre de nos recherches sur le sujet, nous avons décidé pour comprendre comment fonctionne l'interpréteur python d'en recoder une version simplifiée. Le code que nous avons réalisé prend en entrée un code source python basique, le transforme en code intermédiaire inspiré du vrai bytecode de Python3, et l'execute dans une machine virtuelle. Nous avons donc trouvé pertinnent de découper ce projet en deux parties distinctes : la partie <strong>Compilation</strong> et la partie <strong> Machine virtuelle et execution </strong> </br>
	Ce code prend en compte quelques fonctionnalités de base de python telles que :		Ce code prend en compte quelques fonctionnalités de base de python telles que :
	<ul><li>L'affectation de variable</li>		<ul><li>L'affectation de variable</li>
Ligne 78 :		Ligne 78 :
	C’est également à cette étape que l’indentation devient explicite. En Python, l’indentation a une importance syntaxique très forte puisqu’elle permet de délimiter les blocs de code (conditions, boucles, fonctions, etc.).</br>		C’est également à cette étape que l’indentation devient explicite. En Python, l’indentation a une importance syntaxique très forte puisqu’elle permet de délimiter les blocs de code (conditions, boucles, fonctions, etc.).</br>

	Le lexer détecte donc les changements d’indentation et génère des tokens spéciaux représentant l’entrée ou la sortie d’un bloc. ~~Cela~~ permet ensuite au parser de comprendre précisément la structure du programme.		Le lexer détecte donc les changements d’indentation et génère des tokens spéciaux représentant l’entrée ou la sortie d’un bloc. Celà permet ensuite au parser de comprendre précisément la structure du programme.

	<h2>Parser</h2>		<h2>Parser</h2>
Ligne 124 :		Ligne 124 :
	L’AST est une étape extrêmement importante dans la compilation. À ce stade, on ne manipule plus simplement une suite linéaire de tokens, mais une véritable représentation logique et structurée du programme.</br>		L’AST est une étape extrêmement importante dans la compilation. À ce stade, on ne manipule plus simplement une suite linéaire de tokens, mais une véritable représentation logique et structurée du programme.</br>

	~~Cela~~ permet ensuite à la phase de compilation de parcourir facilement l’AST pour générer le bytecode correspondant.		Celà permet ensuite à la phase de compilation de parcourir facilement l’AST pour générer le bytecode correspondant.

	<h2>Compilation</h2>		<h2>Compilation</h2>
Ligne 216 :		Ligne 216 :
	</ul>		</ul>
	<h1>Partie machine virtuelle</h1>		<h1>Partie machine virtuelle</h1>
	Comme énoncé précédemment, la machine virtuelle de l'~~interprèteur~~ python prend en entrée un code objet, et l'execute. </br>		Comme énoncé précédemment, la machine virtuelle de l'interpréteur python prend en entrée un code objet, et l'execute. </br>
	<h2>Fonctionnement global</h2>		<h2>Fonctionnement global</h2>
	La machine virtuelle est basée sur une structure de pile Last In First Out (LIFO) pour les instructions. Elle utilise 2 piles différentes, qui ont chacune un rôle bien défini :		La machine virtuelle est basée sur une structure de pile Last In First Out (LIFO) pour les instructions. Elle utilise 2 piles différentes, qui ont chacune un rôle bien défini :
Ligne 243 :		Ligne 243 :
	<li><strong>STORE_FAST</strong> : Dépile et stock la valeur dans une variable locale </li>		<li><strong>STORE_FAST</strong> : Dépile et stock la valeur dans une variable locale </li>
	<li><strong>BINARY_OP PLUS / MINUS / STAR / SLASH / PERCENT </strong> : Dépile les deux derniers elements de la pile, leur applique l'opération entrée en paramètres, puis empile le résultat : <ul><li>PLUS --> Addition</li><li>MINUS --> Soustraction</li><li>STAR --> Multiplication</li><li>SLASH --> Division</li><li>PERCENT --> Modulo</li></ul>		<li><strong>BINARY_OP PLUS / MINUS / STAR / SLASH / PERCENT </strong> : Dépile les deux derniers elements de la pile, leur applique l'opération entrée en paramètres, puis empile le résultat : <ul><li>PLUS --> Addition</li><li>MINUS --> Soustraction</li><li>STAR --> Multiplication</li><li>SLASH --> Division</li><li>PERCENT --> Modulo</li></ul>
	<li><strong>COMPARE_OP EQEQ / LT / GT / LE / GE / NOTEQ </strong> : Opérateurs de comparaison logiques. Dépile les deux derniers elements et les compare : <ul><li>EQEQ --> égal (==)</li><li>LT (Lower Than) --> Strictement inférieur (<) </li><li>GT (Greater Than) --> Strictement ~~superieur~~ (>) </li><li>LE (Lower Equal) --> Inférieur ou égal (<=) </li><li>GE (Greater Equal) --> ~~Supperieur~~ ou égal (>=) </li><li>NOTEQ (NOT Equal) --> Différent de (!=) </li></ul>		<li><strong>COMPARE_OP EQEQ / LT / GT / LE / GE / NOTEQ </strong> : Opérateurs de comparaison logiques. Dépile les deux derniers elements et les compare : <ul><li>EQEQ --> égal (==)</li><li>LT (Lower Than) --> Strictement inférieur (<) </li><li>GT (Greater Than) --> Strictement supérieur (>) </li><li>LE (Lower Equal) --> Inférieur ou égal (<=) </li><li>GE (Greater Equal) --> Supérieur ou égal (>=) </li><li>NOTEQ (NOT Equal) --> Différent de (!=) </li></ul>
	<li><strong>POP_JUMP_IF_FALSE n / POP_JUMP_IF_TRUE</strong> : Dépile, et effectue un saut (principe de JUMP comme en assembleur) à l'instruction à l'indice n de la liste si la valeur qu'il vient de dépiler est vraie (TRUE) ou fausse (FALSE).</li>		<li><strong>POP_JUMP_IF_FALSE n / POP_JUMP_IF_TRUE</strong> : Dépile, et effectue un saut (principe de JUMP comme en assembleur) à l'instruction à l'indice n de la liste si la valeur qu'il vient de dépiler est vraie (TRUE) ou fausse (FALSE).</li>
	<li><strong>JUMP_ABSOLUTE n </strong> : Effectue un saut à l'instruction d'indice n </li>		<li><strong>JUMP_ABSOLUTE n </strong> : Effectue un saut à l'instruction d'indice n </li>
Ligne 295 :		Ligne 295 :
	<h1>Informations supplémentaires</h1>		<h1>Informations supplémentaires</h1>
	<strong> Lien du dépot github du projet :</strong> https://github.com/Marzzzbeats/Visi201</br></br>		<strong> Lien du dépot github du projet :</strong> https://github.com/Marzzzbeats/Visi201</br></br>
	<strong> Sources : </strong><ul><li>Documentation python</li><li>Wikipédia : (Python, Cpython, Compilateur, ~~Interpreteur~~, Bytecode)</li>		<strong> Sources : </strong><ul><li>Documentation python</li><li>Wikipédia : (Python, Cpython, Compilateur, Interpréteur, Bytecode)</li>

← Version précédente		Version du 11 mai 2026 à 19:29
(5 versions intermédiaires par le même utilisateur non affichées)
Ligne 41 :		Ligne 41 :
	=== Placer des clous aléatoires ===		=== Placer des clous aléatoires ===

	Pour pallier au problème de ne pas pouvoir arrêter une droite ailleurs que sur un bord, nous avons ~~décider~~ de rajouter des clous dont la position a été générée aléatoirement.		Pour pallier au problème de ne pas pouvoir arrêter une droite ailleurs que sur un bord, nous avons décidé de rajouter des clous dont la position a été générée aléatoirement.
	Pour ce faire, nous générons aléatoirement pour chaque clou sa coordonnée x (respectivement : y) un nombre entre 20 et la longueur (respectivement : hauteur) de l'image - 20, pour qu'~~ils~~ ne ~~soient~~ pas trop près du bord.		Pour ce faire, nous générons aléatoirement pour chaque clou sa coordonnée x (respectivement : y) un nombre entre 20 et la longueur (respectivement : hauteur) de l'image - 20, pour qu'il ne soit pas trop près du bord.
	Étant donné qu'un clou au centre de l'image doit pouvoir être relié à tous les autres, nous incrémentons à chaque clou la valeur de son côté, pour que chacun des clous générés aléatoirement ait un côté différent.		Étant donné qu'un clou au centre de l'image doit pouvoir être relié à tous les autres, nous incrémentons à chaque clou la valeur de son côté, pour que chacun des clous générés aléatoirement ait un côté différent.

Ligne 53 :		Ligne 53 :
	=== Utiliser les contours ===		=== Utiliser les contours ===

	Afin d'obtenir des images plus détaillées, nous souhaitons placer les clous autour formes visibles dans nos images.		Afin d'obtenir des images plus détaillées, nous souhaitons placer les clous autour des formes visibles dans nos images.
	Cela permettra de mieux en délimiter les contours, et donc de les faire ressortir et de les dessiner plus fidèlement.		Cela permettra de mieux en délimiter les contours, et donc de les faire ressortir et de les dessiner plus fidèlement.
	Pour y parvenir, nous utilisons un système de probabilités.		Pour y parvenir, nous utilisons un système de probabilités.
Ligne 129 :		Ligne 129 :
	=== La condition d'arrêt ===		=== La condition d'arrêt ===

	Dans ~~note~~ implémentation de cet algorithme, nous avons fait le choix de s'arrêter lorsque la meilleure droite éloigne notre résultat de l'image de départ trois fois d'affilé.		Dans notre implémentation de cet algorithme, nous avons fait le choix de nous arrêter lorsque la meilleure droite éloigne notre résultat de l'image de départ trois fois d'affilé.
	Nous n'arrêtons pas dès que le résultat s'éloigne car il arrive souvent qu'une droite qui éloigne notre résultat de l'image de départ permette ensuite de tracer une meilleure droite, qui va améliorer notre résultat.		Nous n'arrêtons pas dès que le résultat s'éloigne car il arrive souvent qu'une droite qui éloigne notre résultat de l'image de départ permette ensuite de tracer une meilleure droite, qui va améliorer notre résultat.

Ligne 142 :		Ligne 142 :
	Durant ce projet, nous avons travaillé uniquement sur des images en niveaux de gris, nous représentons donc une image par une matrice de dimension identique à cette image, dans laquelle chaque élément de la matrice représente un pixel, comme vu dans la partie précédente.		Durant ce projet, nous avons travaillé uniquement sur des images en niveaux de gris, nous représentons donc une image par une matrice de dimension identique à cette image, dans laquelle chaque élément de la matrice représente un pixel, comme vu dans la partie précédente.
	Pour importer une image, on la convertit donc en niveaux de gris, puis on récupère la valeur de chaque pixel pour en faire une matrice.		Pour importer une image, on la convertit donc en niveaux de gris, puis on récupère la valeur de chaque pixel pour en faire une matrice.
	Pour créer une image blanche, on crée une matrice de la taille souhaitée et on initialise ~~touts~~ les valeurs à 255, la valeur du blanc.		Pour créer une image blanche, on crée une matrice de la taille souhaitée et on initialise toutes les valeurs à 255, la valeur du blanc.

	=== Calculer la liste des pixels traversés ===		=== Calculer la liste des pixels traversés ===
Ligne 169 :		Ligne 169 :
	Dans le cas des droites verticales, a n'est pas défini car il faudrait diviser par 0. On fabrique donc la liste de pixels en laissant la coordonnée x constante, et en ajoutant toutes les coordonnées y entre y1 et y2.		Dans le cas des droites verticales, a n'est pas défini car il faudrait diviser par 0. On fabrique donc la liste de pixels en laissant la coordonnée x constante, et en ajoutant toutes les coordonnées y entre y1 et y2.

	Une fois que nous avons notre liste de ~~pixel~~, on modifie la valeur de chaque pixel dans la liste pour tracer la droite.		Une fois que nous avons notre liste de pixels, on modifie la valeur de chaque pixel dans la liste pour tracer la droite.
	Nous avons fait le choix de modifier de 51 la valeur des pixels, pour obtenir 6 niveaux de gris qui sont du plus foncé au plus clair : 255 -> 204 -> 153 -> 102 -> 51 -> 0.		Nous avons fait le choix de modifier de 51 la valeur des pixels, pour obtenir 6 niveaux de gris qui sont du plus foncé au plus clair : 255 -> 204 -> 153 -> 102 -> 51 -> 0.

Ligne 244 :		Ligne 244 :
	=== Histogrammes d'erreurs ===		=== Histogrammes d'erreurs ===

	Pour chacune des quatre images ci-dessus, nous avons ~~récupérer~~ la liste de la valeur de la réduction de la différence pour chaque droite, puis nous avons tracé un histogramme pour visualiser à quel niveau de réduction il y avait le plus de droites.		Pour chacune des quatre images ci-dessus, nous avons récupéré la liste de la valeur de la réduction de la différence pour chaque droite, puis nous avons tracé un histogramme pour visualiser à quel niveau de réduction il y avait le plus de droites.
	On remarque à chaque fois un pic à -51 (qui est pour rappel la valeur de laquelle on modifie un pixel à chaque fois), puis une baisse jusqu'à -40, et enfin une hausse ~~prohe~~ de 0, particulièrement marquée sur l'image en blanc sur noir.		On remarque à chaque fois un pic à -51 (qui est pour rappel la valeur de laquelle on modifie un pixel à chaque fois), puis une baisse jusqu'à -40, et enfin une hausse proche de 0, particulièrement marquée sur l'image en blanc sur noir.

	Voici les histogrammes, dans l'ordre des images précédentes :		Voici les histogrammes, dans l'ordre des images précédentes :