Réductions de problèmes - Historique des versions

Solene bellissard : /* Classes de complexité */

2023-05-25T16:10:25Z

Classes de complexité

← Version précédente		Version du 25 mai 2023 à 16:10
Ligne 155 :		Ligne 155 :
	= Classes de complexité =		= Classes de complexité =
	[[File:P np.jpg\|right\|250px]]		[[File:P np.jpg\|right\|250px]]
	Le modèle des machines de Turing ~~permettent~~ de définir les classes de complexité algorithmique. Le temps mis par une machine M sur une entrée x est le nombre d’étapes du calcul de M(x) pour arriver un état final.		Le modèle des machines de Turing permet de définir les classes de complexité algorithmique. Le temps mis par une machine M sur une entrée x est le nombre d’étapes du calcul de M(x) pour arriver un état final.

	== Classe P ==		== Classe P ==

Solene bellissard : /* Machine déterministe à un ruban */

2023-05-25T16:09:47Z

Machine déterministe à un ruban

← Version précédente		Version du 25 mai 2023 à 16:09
Ligne 136 :		Ligne 136 :
	Chaque machine est définie par :		Chaque machine est définie par :
	* Un alphabet fini Σ : ensemble des symboles utilisés par la machine ;		* Un alphabet fini Σ : ensemble des symboles utilisés par la machine ;
	* Un ensemble fini des états des têtes : état initial, d’acceptation, de rejet, etc.;		* Un ensemble fini des états des têtes : état initial, d’acceptation, de rejet, etc. ;
	* Une table de transition : décrit – en fonction de l’état de la tête de lecture et du symbole lu par celle-ci – ce qui doit être doit écrit, dans quel état elle doit passer et son sens de déplacement.		* Une table de transition : décrit – en fonction de l’état de la tête de lecture et du symbole lu par celle-ci – ce qui doit être doit écrit, dans quel état elle doit passer et son sens de déplacement.

Solene bellissard : /* Machine déterministe à un ruban */

2023-05-25T16:09:25Z

Machine déterministe à un ruban

← Version précédente		Version du 25 mai 2023 à 16:09
Ligne 130 :		Ligne 130 :
	== Machine déterministe à un ruban ==		== Machine déterministe à un ruban ==
	[[File:Schema machine Turing.jpg\|thumb\|right\|320px\|Schéma machine de Turing]]		[[File:Schema machine Turing.jpg\|thumb\|right\|320px\|Schéma machine de Turing]]
	Une machine de Turing est un modèle abstrait qui reflète ce qu’un appareil de calcul, comme un ordinateur, est capable de faire. Elle est ~~composé~~ d’un ruban, souvent infini à gauche et à droite, qui représente une mémoire infinie.		Une machine de Turing est un modèle abstrait qui reflète ce qu’un appareil de calcul, comme un ordinateur, est capable de faire. Elle est composée d’un ruban, souvent infini à gauche et à droite, qui représente une mémoire infinie.
	<br />		<br />
	Sur le ruban d’une machine de Turing, nous allons trouver une tête, pointant une des ~~case~~, qui va lire et/ou écrire sur le ruban et se déplacer.		Sur le ruban d’une machine de Turing, nous allons trouver une tête, pointant une des cases, qui va lire et/ou écrire sur le ruban et se déplacer.
	<br />		<br />
	Chaque machine est définie par :		Chaque machine est définie par :

Solene bellissard : /* Solutions */

2023-05-25T16:08:15Z

Solutions

← Version précédente		Version du 25 mai 2023 à 16:08
Ligne 80 :		Ligne 80 :
	Les solutions sont récupérées sous forme d'une longue chaîne de caractères, elles doivent donc être formatées pour les obtenir sous forme de suite de Langford.		Les solutions sont récupérées sous forme d'une longue chaîne de caractères, elles doivent donc être formatées pour les obtenir sous forme de suite de Langford.
	<br />		<br />
	Le problème des suites de Langford n’est pas forcément ~~simples~~ à résoudre, en particulier pour des grand nombre. Mais pour trouver ses solutions, on a écrit un programme python qui, algorithmiquement, n’est pas compliqué parce qu’il est réduit par couverture exacte, à l’aide de Dancing Links.		Le problème des suites de Langford n’est pas forcément simple à résoudre, en particulier pour des grand nombre. Mais pour trouver ses solutions, on a écrit un programme python qui, algorithmiquement, n’est pas compliqué parce qu’il est réduit par couverture exacte, à l’aide de Dancing Links.

	== Problème de pavage avec les polyominos ==		== Problème de pavage avec les polyominos ==

Solene bellissard : /* Problème */

2023-05-25T16:07:54Z

Problème

← Version précédente		Version du 25 mai 2023 à 16:07
Ligne 51 :		Ligne 51 :
	=== Problème ===		=== Problème ===
	Une suite de Langford pour un entier k est une suite de 2k entiers constitué des entiers de 1 à k.		Une suite de Langford pour un entier k est une suite de 2k entiers constitué des entiers de 1 à k.
	Ces entiers sont placés les uns à la suite des ~~autre~~ de sorte qu’un entier i soit placé à i+1 place de l’autre entier i.<br />		Ces entiers sont placés les uns à la suite des autres de sorte qu’un entier i soit placé à i+1 place de l’autre entier i.<br />

	=== Passage par une matrice ===		=== Passage par une matrice ===

Solene bellissard : /* Exemples */

2023-05-25T16:07:36Z

Exemples

← Version précédente		Version du 25 mai 2023 à 16:07
Ligne 18 :		Ligne 18 :
	'''<u>Exemple dans les matrices :</u>'''<br />		'''<u>Exemple dans les matrices :</u>'''<br />
	Le problème de couverture exacte peut également être représenté sous forme matricielle. Les colonnes correspondent aux contraintes à respecter et les lignes aux choix possibles pour former la couverture exacte. Chaque case de la matrice contient un 1, si la contrainte est respectée, ou un 0, sinon.<br />		Le problème de couverture exacte peut également être représenté sous forme matricielle. Les colonnes correspondent aux contraintes à respecter et les lignes aux choix possibles pour former la couverture exacte. Chaque case de la matrice contient un 1, si la contrainte est respectée, ou un 0, sinon.<br />
	Soit E = {1, 2, 3, 4} et S = {F, G, H, I, J, K}. Le problème de couverture exacte est ~~représentée~~ par la matrice suivante :		Soit E = {1, 2, 3, 4} et S = {F, G, H, I, J, K}. Le problème de couverture exacte est représenté par la matrice suivante :

	{\| class="wikitable"		{\| class="wikitable"

Solene bellissard : /* Classes de complexité */

2023-05-25T16:04:54Z

Classes de complexité

← Version précédente		Version du 25 mai 2023 à 16:04
Ligne 154 :		Ligne 154 :

	= Classes de complexité =		= Classes de complexité =
⚫	Le modèle des machines de Turing permettent de définir les classes de complexité algorithmique. Le temps mis par une machine M sur une entrée x est le nombre d’étapes du calcul de M(x) pour arriver un état final.
	[[File:P np.jpg\|right\|250px]]		[[File:P np.jpg\|right\|250px]]
		⚫	Le modèle des machines de Turing permettent de définir les classes de complexité algorithmique. Le temps mis par une machine M sur une entrée x est le nombre d’étapes du calcul de M(x) pour arriver un état final.

	== Classe P ==		== Classe P ==

Solene bellissard : /* Classes de complexité */

2023-05-25T16:04:40Z

Classes de complexité

← Version précédente		Version du 25 mai 2023 à 16:04
Ligne 155 :		Ligne 155 :
	= Classes de complexité =		= Classes de complexité =
	Le modèle des machines de Turing permettent de définir les classes de complexité algorithmique. Le temps mis par une machine M sur une entrée x est le nombre d’étapes du calcul de M(x) pour arriver un état final.		Le modèle des machines de Turing permettent de définir les classes de complexité algorithmique. Le temps mis par une machine M sur une entrée x est le nombre d’étapes du calcul de M(x) pour arriver un état final.
			[[File:P np.jpg\|right\|250px]]

	== Classe P ==		== Classe P ==

Solene bellissard : /* Exemples */

2023-05-25T16:02:37Z

Exemples

← Version précédente		Version du 25 mai 2023 à 16:02
Ligne 9 :		Ligne 9 :

	== Exemples==		== Exemples==
			[[File:Couverture exacte exemple.jpg\|thumb\|right\|300px\|Exemple de couverture exacte]]

	'''<u>Exemple dans les ensembles :</u>'''<br />		'''<u>Exemple dans les ensembles :</u>'''<br />
	Prenons un ensemble E = {a, b, c} et un ensemble S = {{a, b}, {a, b, c}, {c, b}, {c}} de parties de E.<br />		Prenons un ensemble E = {a, b, c} et un ensemble S = {{a, b}, {a, b, c}, {c, b}, {c}} de parties de E.<br />
Ligne 43 :		Ligne 45 :
	\|'''K'''\|\|style="color:red"\|1\|\|0\|\|0\|\|0		\|'''K'''\|\|style="color:red"\|1\|\|0\|\|0\|\|0
	\|}		\|}


	= Problèmes réduits par couverture exacte =		= Problèmes réduits par couverture exacte =

Solene bellissard : /* Passage par une matrice */

2023-05-25T16:01:55Z

Passage par une matrice

← Version précédente		Version du 25 mai 2023 à 16:01
Ligne 68 :		Ligne 68 :

	[[File:Dlx.png\|thumb\|right\|300px\|Fonctions d’appel de DLX et de traitement de sa sortie]]		[[File:Dlx.png\|thumb\|right\|300px\|Fonctions d’appel de DLX et de traitement de sa sortie]]

	=== Utilisation DLX ===		=== Utilisation DLX ===
	Afin de trouver une couverture exacte de cette matrice, nous allons utiliser le programme Dancing Links (DLX) qui prend en entrée l’ensemble des éléments d’une matrice qui sont à 1 et en sort les couvertures exactes.		Afin de trouver une couverture exacte de cette matrice, nous allons utiliser le programme Dancing Links (DLX) qui prend en entrée l’ensemble des éléments d’une matrice qui sont à 1 et en sort les couvertures exactes.

Réductions de problèmes - Historique des versions

Solene bellissard : /* Classes de complexité */

Solene bellissard : /* Machine déterministe à un ruban */

Solene bellissard : /* Machine déterministe à un ruban */

Solene bellissard : /* Solutions */

Solene bellissard : /* Problème */

Solene bellissard : /* Exemples */

Solene bellissard : /* Classes de complexité */

Solene bellissard : /* Classes de complexité */

Solene bellissard : /* Exemples */

Solene bellissard : /* Passage par une matrice */

Solene bellissard : /* Classes de complexité */

Solene bellissard : /* Machine déterministe à un ruban */

Solene bellissard : /* Machine déterministe à un ruban */

Solene bellissard : /* Solutions */

Solene bellissard : /* Problème */

Solene bellissard : /* Exemples */

Solene bellissard : /* Classes de complexité */

Solene bellissard : /* Classes de complexité */

Solene bellissard : /* Exemples */

Solene bellissard : /* Passage par une matrice */