Jeu de la vie - Historique des versions

Antoine le 20 mai 2025 à 21:48

2025-05-20T21:48:58Z

← Version précédente		Version du 20 mai 2025 à 21:48
Ligne 309 :		Ligne 309 :
	</ul>		</ul>

	<p>Cette approche est souvent combinée avec l'algorithme <b>Hashlife</b>, qui exploite la ~~redondance~~ des configurations en mémorisant et réutilisant les sous-structures déjà calculées, permettant ainsi d'accélérer les simulations sur des périodes très longues.</p>		<p>Cette approche est souvent combinée avec l'algorithme <b>Hashlife</b>, qui exploite la répétition des configurations en mémorisant et réutilisant les sous-structures déjà calculées, permettant ainsi d'accélérer les simulations sur des périodes très longues.</p>

	<h1>Conclusion</h1>		<h1>Conclusion</h1>

Antoine le 20 mai 2025 à 21:48

2025-05-20T21:48:27Z

← Version précédente		Version du 20 mai 2025 à 21:48
Ligne 289 :		Ligne 289 :
	<h1>Approche en arbre (quadtrees)</h1>		<h1>Approche en arbre (quadtrees)</h1>

	Un <b>quadtree</b> est une structure d’arbre qui divise récursivement la grille en 4 sous-régions. Cette approche est ~~particulièrement~~ adaptée pour simuler le Jeu de la Vie sur de très grandes grilles, voire infinies, lorsqu'une grande partie des cellules reste inactive.		Un <b>quadtree</b> est une structure d’arbre qui divise récursivement la grille en 4 sous-régions. Cette approche est plus adaptée pour simuler le Jeu de la Vie sur de très grandes grilles, voire infinies, lorsqu'une grande partie des cellules reste inactive.

	<h2>Principe</h2>		<h2>Principe</h2>
Ligne 295 :		Ligne 295 :
	<ul>		<ul>
	<li><b>Subdivision de la grille</b> : La grille est divisée en 4 quadrants, chacun pouvant être à son tour subdivisé en 4 sous-quadrants. Cette récursivité permet de représenter efficacement les zones homogènes, par exemple les régions totalement mortes.</li>		<li><b>Subdivision de la grille</b> : La grille est divisée en 4 quadrants, chacun pouvant être à son tour subdivisé en 4 sous-quadrants. Cette récursivité permet de représenter efficacement les zones homogènes, par exemple les régions totalement mortes.</li>
	<li><b>Compression </b> : Les régions ayant un ~~état~~ ~~homogène~~ (~~par exemple,~~ totalement mortes) n'ont pas besoin d'être représentées en détail. Le quadtree regroupe ces zones en un seul noeud, réduisant ainsi la mémoire utilisée.</li>		<li><b>Compression </b> : Les régions ayant un le même état(ex: totalement mortes) n'ont pas besoin d'être représentées en détail. Le quadtree regroupe ces zones en un seul noeud, réduisant ainsi la mémoire utilisée.</li>
	<li><b>Optimisation de l’évolution</b> : Seules les zones actives, donc celles avec des cellules vivantes ou susceptibles de changer, sont simulées en détail. Ceci permet de gagner en performances en ignorant rapidement les grandes portions inactives.</li>		<li><b>Optimisation de l’évolution</b> : Seules les zones actives, donc celles avec des cellules vivantes ou susceptibles de changer, sont simulées en détail. Ceci permet de gagner en performances en ignorant rapidement les grandes portions inactives.</li>
	</ul>		</ul>

Antoine le 20 mai 2025 à 21:46

2025-05-20T21:46:12Z

← Version précédente		Version du 20 mai 2025 à 21:46
Ligne 7 :		Ligne 7 :
	<h1>Théorie et règles</h1>		<h1>Théorie et règles</h1>

	<h2>Règles de base du ~~jeu~~ de la ~~vie~~</h2>		<h2>Règles de base du Jeu de la Vie</h2>

	À chaque génération, l'état de chaque cellule dépend de ses 8 voisins immédiats (représentés en vert):		À chaque génération, l'état de chaque cellule dépend de ses 8 voisins immédiats (représentés en vert):
Ligne 86 :		Ligne 86 :
	</div>		</div>

	* <b>Gosper Glider Gun</b> : C'est l'une des structures les plus importantes du ~~jeu~~ de la ~~vie~~, elle est la base pour la logique. En effet, comme nous le verrons après, le Gosper Glider Gun va pouvoir devenir une source d'information dans une simulation logique servant ensuite à prouver que le ~~jeu~~ de la ~~vie~~ est Turing-complet.		* <b>Gosper Glider Gun</b> : C'est l'une des structures les plus importantes du Jeu de la Vie, elle est la base pour la logique. En effet, comme nous le verrons après, le Gosper Glider Gun va pouvoir devenir une source d'information dans une simulation logique servant ensuite à prouver que le Jeu de la Vie est Turing-complet.

	<div>		<div>
Ligne 161 :		Ligne 161 :


	Pour réaliser la porte AND dans le ~~jeu~~ de la ~~vie~~, nous avons positionné trois Gosper Glider Guns qui servent de flux de données, ainsi que des <b>Eaters</b> pour forcer les sorties à 0 ou à 1. Pour les entrées A et B, il est maintenant possible de retirer un des deux Eaters afin de mettre l’entrée à 0 ou à 1.		Pour réaliser la porte AND dans le Jeu de la Vie, nous avons positionné trois Gosper Glider Guns qui servent de flux de données, ainsi que des <b>Eaters</b> pour forcer les sorties à 0 ou à 1. Pour les entrées A et B, il est maintenant possible de retirer un des deux Eaters afin de mettre l’entrée à 0 ou à 1.


Ligne 182 :		Ligne 182 :
	<h1>Implémentation sur une grille finie</h1>		<h1>Implémentation sur une grille finie</h1>

	Cette première version permet d'expérimenter les règles du ~~jeu~~ de la ~~vie~~ sur une grille simple. Elle est idéale pour bien comprendre le fonctionnement de base, même si elle montre vite ses limites sur des grandes tailles.		Cette première version permet d'expérimenter les règles du Jeu de la Vie sur une grille simple. Elle est idéale pour bien comprendre le fonctionnement de base, même si elle montre vite ses limites sur des grandes tailles.

	<h2>Structure de données utilisée</h2>		<h2>Structure de données utilisée</h2>
Ligne 204 :		Ligne 204 :
	<h2>Calcul des voisins et évolution des cellules</h2>		<h2>Calcul des voisins et évolution des cellules</h2>

	L'évolution d'une cellule s'effectue en comptant le nombre de voisins vivants autour d'elle et en appliquant les règles du ~~jeu~~ de la ~~vie~~.		L'évolution d'une cellule s'effectue en comptant le nombre de voisins vivants autour d'elle et en appliquant les règles du Jeu de la Vie.

	<pre>		<pre>
Ligne 289 :		Ligne 289 :
	<h1>Approche en arbre (quadtrees)</h1>		<h1>Approche en arbre (quadtrees)</h1>

	Un <b>quadtree</b> est une structure d’arbre qui divise récursivement la grille en 4 sous-régions. Cette approche est particulièrement adaptée pour simuler le ~~jeu~~ de la ~~vie~~ sur de très grandes grilles, voire infinies, lorsqu'une grande partie des cellules reste inactive.		Un <b>quadtree</b> est une structure d’arbre qui divise récursivement la grille en 4 sous-régions. Cette approche est particulièrement adaptée pour simuler le Jeu de la Vie sur de très grandes grilles, voire infinies, lorsqu'une grande partie des cellules reste inactive.

	<h2>Principe</h2>		<h2>Principe</h2>
Ligne 314 :		Ligne 314 :
	Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.		Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.

	Nous avons vu qu'il est possible d'implémenter le ~~jeu~~ de la ~~vie~~ avec une première version naïve dans une grille finie, simple à comprendre, mais limitée pour les grandes tailles de grille ; une version sur une grille infinie pour les grilles de grandes tailles et enfin pour finir, une approche en arbre permettant d'accélérer et d'optimiser la simulation.		Nous avons vu qu'il est possible d'implémenter le Jeu de la Vie avec une première version naïve dans une grille finie, simple à comprendre, mais limitée pour les grandes tailles de grille ; une version sur une grille infinie pour les grilles de grandes tailles et enfin pour finir, une approche en arbre permettant d'accélérer et d'optimiser la simulation.

	<h2>Sources</h2>		<h2>Sources</h2>

Antoine le 20 mai 2025 à 21:44

2025-05-20T21:44:57Z

← Version précédente		Version du 20 mai 2025 à 21:44
Ligne 9 :		Ligne 9 :
	<h2>Règles de base du jeu de la vie</h2>		<h2>Règles de base du jeu de la vie</h2>

	A chaque génération, l'état de chaque cellule dépend de ses 8 voisins immédiats (~~représenté~~ en vert):		À chaque génération, l'état de chaque cellule dépend de ses 8 voisins immédiats (représentés en vert):

	<div>		<div>
Ligne 99 :		Ligne 99 :
	<h1>Turing-complet</h1>		<h1>Turing-complet</h1>

	Le concept de <b>Turing ~~complétude~~</b> désigne la capacité d’un système à simuler <b>tout algorithme calculable</b>. Autrement dit, un dispositif Turing-complet peut, en principe, exécuter n’importe quel programme qu’un ordinateur classique permettrait de lancer.		Le concept de <b>Turing-complet</b> désigne la capacité d’un système à simuler <b>tout algorithme calculable</b>. Autrement dit, un dispositif Turing-complet peut, en principe, exécuter n’importe quel programme qu’un ordinateur classique permettrait de lancer.

	<h2>Critères de Turing complétude dans le Jeu de la Vie</h2>		<h2>Critères de Turing complétude dans le Jeu de la Vie</h2>

Antoine le 20 mai 2025 à 21:41

2025-05-20T21:41:18Z

← Version précédente		Version du 20 mai 2025 à 21:41
Ligne 22 :		Ligne 22 :
	* Une cellule morte naît si elle a exactement 3 voisins vivants.		* Une cellule morte naît si elle a exactement 3 voisins vivants.

	* Une ~~cellules~~ vivante meurt si elle a moins de 2 ou plus de 3 voisins vivants (sous-population ou surpopulation).		* Une cellule vivante meurt si elle a moins de 2 ou plus de 3 voisins vivants (sous-population ou surpopulation).

	* Une cellule vivante survit si elle a exactement 2 ou 3 voisins.		* Une cellule vivante survit si elle a exactement 2 ou 3 voisins.
Ligne 54 :		Ligne 54 :


	* <b>Les vaisseaux</b> : Ce sont des structures capables de se déplacer à travers la grille tout en conservant leur forme. Elles permettront de transporter de l'information. La plus ~~connu~~ est le <i>Spaceship</i>, un petit vaisseau qui se déplace horizontalement. Ces motifs montrent comment un mouvement global peut émerger sans avoir été programmé.		* <b>Les vaisseaux</b> : Ce sont des structures capables de se déplacer à travers la grille tout en conservant leur forme. Elles permettront de transporter de l'information. La plus connue est le <i>Spaceship</i>, un petit vaisseau qui se déplace horizontalement. Ces motifs montrent comment un mouvement global peut émerger sans avoir été programmé.

	<div>		<div>
Ligne 86 :		Ligne 86 :
	</div>		</div>

	* <b>Gosper Glider Gun</b> : C'est l'une des structures les plus importantes du jeu de la vie, elle est la base pour la logique. En effet, comme nous le verrons après, le Gosper Glider Gun va pouvoir devenir une source d'information dans une simulation logique servant ensuite a prouver que le jeu de la vie est Turing ~~Complet~~.		* <b>Gosper Glider Gun</b> : C'est l'une des structures les plus importantes du jeu de la vie, elle est la base pour la logique. En effet, comme nous le verrons après, le Gosper Glider Gun va pouvoir devenir une source d'information dans une simulation logique servant ensuite à prouver que le jeu de la vie est Turing-complet.

	<div>		<div>
Ligne 144 :		Ligne 144 :

	* Une mémoire linéaire où les gliders codent des bits le long d’une barre de cellules.		* Une mémoire linéaire où les gliders codent des bits le long d’une barre de cellules.
	* Un unité arithmétique et logique (ALU) capable d’ajouter ou de comparer deux registres codés en impulsions de gliders.		* Une unité arithmétique et logique (ALU) capable d’ajouter ou de comparer deux registres codés en impulsions de gliders.
	* Un contrôleur d'instructions séquencé par un réseau de Gosper Glider Guns, synchronisant lecture, calcul et écriture.		* Un contrôleur d'instructions séquencé par un réseau de Gosper Glider Guns, synchronisant lecture, calcul et écriture.

	Ces réalisations confirment que, malgré ses règles extrêmement simples, le Jeu de la Vie possède ~~tous~~ le nécessaire pour créer un ordinateur ou en d’autres termes, être Turing complet.		Ces réalisations confirment que, malgré ses règles extrêmement simples, le Jeu de la Vie possède tout le nécessaire pour créer un ordinateur ou en d’autres termes, être Turing complet.

	<h2>Exemple porte logique <b>AND</b></h2>		<h2>Exemple porte logique <b>AND</b></h2>
Ligne 237 :		Ligne 237 :

	if cases[x][y] == 1: # Vérifie si cellule vivante		if cases[x][y] == 1: # Vérifie si cellule vivante
	if vivants == 2 or vivants == 3: # ~~Survi~~ si deux ou trois voisins exactement		if vivants == 2 or vivants == 3: # Survit si deux ou trois voisins exactement
	nouveau[x][y] = 1		nouveau[x][y] = 1
	else: # Meurt (pas assez ou trop de voisins)		else: # Meurt (pas assez ou trop de voisins)
	nouveau[x][y] = 0		nouveau[x][y] = 0
	else: # Si la cellule est morte		else: # Si la cellule est morte
	if vivants == 3: # Nait (3 voisins ~~exactements~~)		if vivants == 3: # Nait (3 voisins exactement)
	nouveau[x][y] = 1		nouveau[x][y] = 1
	else: # Reste morte		else: # Reste morte
Ligne 285 :		Ligne 285 :
	<h2>Comparaison avec la grille finie</h2>		<h2>Comparaison avec la grille finie</h2>

	L'utilisation d'~~une~~ dictionnaire pour stocker uniquement les cellules ~~vivante~~ est bien plus efficace en mémoire lorsque la grille est de grande taille car nous n'avons pas à parcourir l'entièreté de la grille à chaque génération mais uniquement les cellules vivantes.		L'utilisation d'un dictionnaire pour stocker uniquement les cellules vivantes est bien plus efficace en mémoire lorsque la grille est de grande taille car nous n'avons pas à parcourir l'entièreté de la grille à chaque génération mais uniquement les cellules vivantes.

	<h1>Approche en arbre (quadtrees)</h1>		<h1>Approche en arbre (quadtrees)</h1>
Ligne 314 :		Ligne 314 :
	Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.		Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.

	Nous avons vu ~~que~~ il est possible d'implémenter le jeu de la vie avec une première version ~~naive~~ dans une grille finie, simple à comprendre mais limitée ~~sur~~ les ~~grilles de~~ grandes tailles ; une version sur une grille infinie pour les grilles de grandes tailles et enfin pour finir, une approche en arbre permettant d'accélérer et d'optimiser la simulation.		Nous avons vu qu'il est possible d'implémenter le jeu de la vie avec une première version naïve dans une grille finie, simple à comprendre, mais limitée pour les grandes tailles de grille ; une version sur une grille infinie pour les grilles de grandes tailles et enfin pour finir, une approche en arbre permettant d'accélérer et d'optimiser la simulation.

	<h2>Sources</h2>		<h2>Sources</h2>

Antoine le 20 mai 2025 à 21:35

2025-05-20T21:35:50Z

← Version précédente		Version du 20 mai 2025 à 21:35
Ligne 312 :		Ligne 312 :

	<h1>Conclusion</h1>		<h1>Conclusion</h1>
	Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.		Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.

			Nous avons vu que il est possible d'implémenter le jeu de la vie avec une première version naive dans une grille finie, simple à comprendre mais limitée sur les grilles de grandes tailles ; une version sur une grille infinie pour les grilles de grandes tailles et enfin pour finir, une approche en arbre permettant d'accélérer et d'optimiser la simulation.

	<h2>Sources</h2>		<h2>Sources</h2>

Antoine le 20 mai 2025 à 21:32

2025-05-20T21:32:41Z

← Version précédente		Version du 20 mai 2025 à 21:32
Ligne 311 :		Ligne 311 :
	<p>Cette approche est souvent combinée avec l'algorithme <b>Hashlife</b>, qui exploite la redondance des configurations en mémorisant et réutilisant les sous-structures déjà calculées, permettant ainsi d'accélérer les simulations sur des périodes très longues.</p>		<p>Cette approche est souvent combinée avec l'algorithme <b>Hashlife</b>, qui exploite la redondance des configurations en mémorisant et réutilisant les sous-structures déjà calculées, permettant ainsi d'accélérer les simulations sur des périodes très longues.</p>

	<h2>Conclusion</h2>		<h1>Conclusion</h1>
	Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.		Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.

			<h2>Sources</h2>

Antoine le 20 mai 2025 à 21:29

2025-05-20T21:29:51Z

← Version précédente		Version du 20 mai 2025 à 21:29
Ligne 313 :		Ligne 313 :
	<h2>Conclusion</h2>		<h2>Conclusion</h2>
	Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.		Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.

	<syntaxhighlight lang="python">
	def iteration():
	for i in range(10):
	print(i)
	</syntaxhighlight>

Antoine le 20 mai 2025 à 21:29

2025-05-20T21:29:39Z

← Version précédente		Version du 20 mai 2025 à 21:29
Ligne 313 :		Ligne 313 :
	<h2>Conclusion</h2>		<h2>Conclusion</h2>
	Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.		Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.

			<syntaxhighlight lang="python">
			def iteration():
			for i in range(10):
			print(i)
			</syntaxhighlight>

Antoine le 20 mai 2025 à 17:12

2025-05-20T17:12:30Z

← Version précédente		Version du 20 mai 2025 à 17:12
Ligne 310 :		Ligne 310 :

	<p>Cette approche est souvent combinée avec l'algorithme <b>Hashlife</b>, qui exploite la redondance des configurations en mémorisant et réutilisant les sous-structures déjà calculées, permettant ainsi d'accélérer les simulations sur des périodes très longues.</p>		<p>Cette approche est souvent combinée avec l'algorithme <b>Hashlife</b>, qui exploite la redondance des configurations en mémorisant et réutilisant les sous-structures déjà calculées, permettant ainsi d'accélérer les simulations sur des périodes très longues.</p>

			<h2>Conclusion</h2>
			Pour conclure, le Jeu de la vie, malgré ses règles très simples, permet de faire émerger des comportements complexes. Nous avons vu qu'il est possible de créer un ordinateur à l'aide de portes logiques, de la mémoire, et des circuits complets ce qui en fait un système Turing-complet.