Problème de séparation par automate : Différence entre versions
De AgregmathKL
m (unification de PSA et Problème de séparation par automates) |
|||
(6 révisions intermédiaires par 3 utilisateurs non affichées) | |||
Ligne 1 : | Ligne 1 : | ||
− | On montre que le problème de séparatation de langages par | + | On montre que le problème de séparatation de langages par automate (PSA) est NP-Complet. |
+ | |||
+ | == PSA est NP-complet == | ||
+ | *[[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:PSA est NPcomplet.pdf|PSA est NP-complet]] | ||
+ | *[[Fichier:tex.png|alt=Pdf|link=|24px]] [[Média:PSA est NPcomplet.tex|PSA est NP-complet]] | ||
== Version de Kévin 2012 == | == Version de Kévin 2012 == | ||
Séparons les langages | Séparons les langages | ||
− | *[[Fichier:Tex.png|alt=Tex|link=|24px]] [[Média:dvt_psa.tex | Problème de séparation par | + | *[[Fichier:Tex.png|alt=Tex|link=|24px]] [[Média:dvt_psa.tex | Problème de séparation par automate]] |
− | *[[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Média:dvt_psa.pdf | Problème de séparation par | + | *[[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Média:dvt_psa.pdf | Problème de séparation par automate]] |
+ | |||
+ | Recasements : | ||
+ | * [[908 -- Automates Finis, exemples et applications]] | ||
+ | * [[909 -- Langages rationnels. Exemples et applications.]] | ||
+ | * [[915 -- Classes de complexité : exemples.]] | ||
+ | |||
+ | [[Category: Développement de la leçon 908]] | ||
+ | [[Category: Développement de la leçon 909]] | ||
+ | [[Category: Développement de la leçon 915]] | ||
+ | [[Category: Développement de la leçon 928]] |
Version actuelle en date du 27 mars 2015 à 12:52
On montre que le problème de séparatation de langages par automate (PSA) est NP-Complet.
PSA est NP-complet
Version de Kévin 2012
Séparons les langages
Recasements :