Exercices corrigés Initiation aux bases de données
3. Tables des matières. I. Chapitre 1 : Algèbre relationnelle . Correction de l'exercice 1. ... III. Chapitre 3 : Langage SQL .
Exercices et problèmes de statistique et probabilités
Corrigés des exercices . Chapitre 3 Estimation ponctuelle. ... Chapitre 5 Estimateur sans biais de variance minimale ..................... 97.
Exercices Complémentaires
Chapitre 3 : Relations d'isomérie entre les molécules organiques. 3.1 Exercice 3.1. Ecrire les formules semi-développées de tous les isomères correspondant
correction exercices Précis de Physique-Chimie chapitre1 à 4
8 ?Eléments de correction des exercices du chapitre 1 : mesures et incertitudes. Analyse dimensionnelle. Exercice 3 : Équation aux dimensions.
Cours et exercices corrigés
Exercices. 53. Corrigés. 61. Chapitre 3. Espaces compacts. 77. I. Définition et premières propriétés. 77. II. Fonctions continues sur un espace compact.
Cours dAlgèbre I et II avec Exercices CorrigésOM DE VOTRE
Chapitre 3. Théorie des ensembles avec Exercices Corrigés. 19. 1. Notion d'ensemble et propriétés. 19. 2. Applications et relations d'équivalences.
Mathématiques financières EXERCICES CORRIGES
TD Chapitre 3 . Correction : Vf = 500 000 × 1055 ? 638 140
CORRIGE DES EXERCICES DU CHAPITRE 3
MODALITE DE DIFFUSION DES EXERCICES DU CHAPITRE 3 3.7 Correction d'un œil myope : écart de correction entre lunettes et lentilles .
Corrigés des exercices du livre et en ligne
CHAPITRE 3. EXERCICE 1. La structure de gestion en plusieurs centres de responsabilité implique une délégation de décision et de gestion au niveau.
Exercices corrigés sur probl`emes NP-complets
12 sept. 2018 Correction. A ECRIRE. 2. Page 38. 34. CHAPITRE 3. CORRECTIONS DES EXERCICES. IV) Différentes Variantes du probl`eme cycle hamiltonien. Nous ...
![Exercices corrigés sur probl`emes NP-complets Exercices corrigés sur probl`emes NP-complets](https://pdfprof.com/Listes/16/36117-16exercices-NP.pdf.pdf.jpg)
Exercices corrig´es sur probl`emes NP-complets
Johanne Cohen
12 septembre 2018
Table des mati`eres
1 Rappel succinct de cours 1
2 Enonc
´es des exercices 5
I) Probl`eme de d´ecisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 a) Graphe eul´erien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 b) Formulation des probl`emes de d´ecisions . . . . . . . . . . . . . . . . . 6 c) Probl`emes dans NP ou dans P . . . . . . . . . . . . . . . . . . . . . . 6 II) R´eduction polynomiale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 b) R´eduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 III) Probl`emes de logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 a) Le probl`eme2-SATest dansP. . . . . . . . . . . . . . . . . . . . . .8 b) Variante du probl`eme 3-SAT : . . . . . . . . . . . . . . . . . . . . . . . 9 c) Le probl`emeMax2SATest NP-complet. . . . . . . . . . . . . . . . .9 d) Le probl`emek-SAT NAEest NP-complet . . . . . . . . . . . . . . . .10 IV) Diff´erentes Variantes du probl`emecycle hamiltonien. . . . . . . . . . . .11 a) Le probl`emeChaine Hamiltonienest NP-complet . . . . . . . . . .11 b) Le probl`emeChaineest NP-complet . . . . . . . . . . . . . . . . . .11 c) Chevaliers de la table ronde . . . . . . . . . . . . . . . . . . . . . . . . 11 d) Le probl`emeVoyageur de Commerceest NP-complet . . . . . . .11 V) Probl`emes de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 a) Les probl`emescoloration de graphe. . . . . . . . . . . . . . . . .13 b) Le probl`eme de la clique maximum. . . . . . . . . . . . . . . . . . . . 14 c) Probl`eme duSet Cover. . . . . . . . . . . . . . . . . . . . . . . . .15 d) Le probl`emeStableest NP-complet . . . . . . . . . . . . . . . . . . .16 VI) Le probl`eme duk-centre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 a) Le probl`emeEnsemble dominantest NP-complet . . . . . . . . . .17 b) Le probl`emek-centreest NP-Complet . . . . . . . . . . . . . . . . .18 c) Le probl`emek-centreest in-approximable . . . . . . . . . . . . . . .18 VII) Probl`emes encodant les entiers . . . . . . . . . . . . . . . . . . . . . . . . . . 19 a) Le probl`emeSOMME DE SOUS-ENSEMBLEest NP-complet . . . .19 b) Le probl`emeSOMME-DES-CARRESest NP-complet . . . . . . . . .19 2TABLE DES MATI
`ERES33 Corrections des exercices 21
I) Probl`eme de d´ecisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22a) Graphe eul´erien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
b) Formulation des probl`emes de d´ecisions . . . . . . . . . . . . . . . . . 22
c) Probl`emes dans NP ou dans P . . . . . . . . . . . . . . . . . . . . . . 23
II) R´eduction polynomiale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
b) R´eduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
III) Probl`emes de logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
a) Le probl`eme2-SATest dansP. . . . . . . . . . . . . . . . . . . . . .27 b) Variante du probl`eme 3-SAT : . . . . . . . . . . . . . . . . . . . . . . . 30
c) Le probl`emeMax2SATest NP-complet. . . . . . . . . . . . . . . . .31 d) Le probl`emek-SAT NAEest NP-complet . . . . . . . . . . . . . . . .33 IV) Diff´erentes Variantes du probl`emecycle hamiltonien. . . . . . . . . . . .34 a) Le probl`emeChaine Hamiltonienest NP-complet . . . . . . . . . .34 b) Le probl`emeChaineest NP-complet . . . . . . . . . . . . . . . . . .35 c) Chevaliers de la table ronde . . . . . . . . . . . . . . . . . . . . . . . . 35
d) Le probl`emeVoyageur de Commerceest NP-complet . . . . . . .36 V) Probl`emes de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
a) Les probl`emescoloration de graphe. . . . . . . . . . . . . . . . .38 b) Le probl`eme de la clique maximum. . . . . . . . . . . . . . . . . . . . 42
c) Probl`eme duSet Cover. . . . . . . . . . . . . . . . . . . . . . . . .43 d) Le probl`emeStableest NP-complet . . . . . . . . . . . . . . . . . . .45 VI) Le probl`eme duk-centre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47 a) Le probl`emeEnsemble dominantest NP-complet . . . . . . . . . .47 b) Le probl`emek-centreest NP-Complet . . . . . . . . . . . . . . . . .48 c) Le probl`emek-centreest in-approximable . . . . . . . . . . . . . . .49 VII) Probl`emes encodant les entiers . . . . . . . . . . . . . . . . . . . . . . . . . . 51
a) Le probl`emeSOMME DE SOUS-ENSEMBLEest NP-complet . . . .51 b) Le probl`emeSOMME-DES-CARRESest NP-complet . . . . . . . . .52
4TABLE DES MATI`ERES
Partie 1: Rappel succinct de cours
Probl`eme de d´ecision.
Unprobl`eme de d´ecisionΠ = (DΠ,OUIΠ) correspond `a un ensemble d"instancesDΠ et `a un sous-ensembleOUIΠ?DΠd"instances positives.Instance du probl`eme Π. OUIΠ.NON
Π.Les classes de complexit´e.
La classePest la classe des probl`emes de d´ecision qui admettent un algorithme de complexit´e polynomiale. La classeNPest form´ee des probl`emes de d´ecision Π qui poss`edent unv´erificateur polynomial.P ard ´efinitionP?NP.
Un v´erificateurVest un algorithme qui prend une information en plus (certificat) pour v´erifier qu"une instance est positive.Exemple :Graphe Hamiltonien
Probl `emede d ´ecision: Donn´ees: un graphe non-orient´eG= (V,E).Question:Ga-il un cycle hamiltonien?
Le certificat corresp ond` aune suite Sde sommets. Le v´erificateurVv´erifie queS est un cycle et qu"il transverse chaque sommet une unique fois.Vfonctionne bien en temps polynomial. -Graphe Hamiltonienest dans NP.Comment comparer les probl`emes
SoientAetBdeux probl`emes de d´ecision.
12CHAPITRE 1. RAPPEL SUCCINCT DE COURS
Uner´eduction deAversBest une fonctionf:IA→IBcalculableen temps polynomial telle quew?Oui(A) si et seulement sif(w)?Oui(B). Pour cela, il suffit de concevoir un algorithme polynomial qui permet de d´ecider si l"ins-tance deAest positive ou non en temps polynomial :Algorithme 1 :D´ecider si l"instanceIde probl`emeAest positive ou nonOutput :un bool´eenb
d ´ebutTransformer l"instanceIen une instanceI?deBen utilisantf: I ?←f(I) ; siI?est une instance positive deIalorsalorsretournez vrai fin retournez fauxfinInstance du probl`emeAfInstance du probl`emeBAlgorithmeoui non 3Probl`eme NP-difficile
Intuitivement : il est plus difficile que tous les probl`emes dans la classe. Un probl`emeAest ditNP-completsi en plus on aA?NP. Autrement dit :AestTh´eor`eme de Cook-Levin
Les probl`emes SAT et 3-SAT sontNP-complet.
Fonctions bool
´eennes
Nous allons consid´erer des fonctionsbool´eennes, c"est-`a-dire de fonctions deφde{1,0}n→
{1,0}. Les v ariablesne p euventprendre que deux v aleurs,vrai (co d´epar 1) ou faux (co d´e par 0). -φest compos´ee de variables et d"op´erateurs comme n´egation (¬) la conjonction (?) la disjonction (?), l"implication→u v¬u(u?v)u?vu→v0 010010 11011
1 00010
1 10111
On dira que la fonctiont:U→ {0,1}satisfaitla fonctionφsi la fonctionφretourne 1 avec les valeurs deten entr´ee. Probl `eme 3- SAT Une clauseest une fonction deφde{1,0}n→ {1,0}compos´ee de variables et d"op´erateurs comme n´egation (¬) et la disjonction (?). Par exempleC(u1,u2,u3) = (u1?u2? ¬u3) est une clause. Le probl`eme3-SATest d´efini de la fa¸con suivante Donn´ees:
un ensembleUde variables{u1,u2,...,un} et une formule logiqueφ=C1? ··· ?C?des clauses de 3 variables Question: Existe-t-il une fonctiont:U→ {0,1}telle quetsatisfaitφ? Exemple d"instance pour le 3-SATSoitIune instance du probl`eme 3-SAT -U={u1,u2,u3,u4}de variables -φ(U) = (u1? ¬u2?u3)?(¬u1? ¬u3?u4)?(u2? ¬u3? ¬u4),4CHAPITRE 1. RAPPEL SUCCINCT DE COURS
Remarque :3-SATest dans NP car
Certificat t:
-t=x1x2···xn? {0,1}ndonne la liste de valeurs de chaque variable.V ´erification:
V ´erifierque trend la formuleFvraie se fait bien en un temps polynomial en la taille deF.Comment prouver qu"un probl`eme est NP-complet
Pour prouver laNP-compl´etude d"un probl`emeA, il suffit de prouver : 1. qu"il admet un v ´erificateurp olynomial; 2.Pourquoi?
Si Aadmet un v´erificateur polynomial, cela permet de garantir queA?NP, tout probl`emeC?NPUne liste de probl`emes NP-complets connusSAT3-SATVC4-SAT NAECycle HamiltonienChaine Hamiltonienne3-SAT NAECliqueDominant2-partitionStableSomme de sous-ensemble
Partie 2: Enonc´es des exercices
56CHAPITRE 2. ENONC´ES DES EXERCICES
I)Probl `emede d ´ecisions
a)Graphe eul ´erien
Le grapheGesteul´eriensi il existe un cycle en empruntant exactement une fois chaque arˆete du grapheG. On rappelle qu"un graphe connexe est eul´erien si et seulement si chacun de ses sommets a un degr´e pair.Question 1.1. Ecrire le probl`eme de d´ecision qui lui est associ´e et donner la taille de l"instance
Question 1.2. Trouver un algorithme polynomial qui d´etermine si le graphe est eul´erien. b)F ormulationdes probl `emesde d ´ecisions
Mettre sous forme de probl`eme de d´ecision et ´evaluer la taille de leurs instances. Question 2.1. Probl`eme de savoir s"il existe un chemin entre deux sommets disjoints dans un graphe; Question 2.2. Probl`eme de connaitre la distance entre deux sommets disjoints dans un graphe; Question 2.3. Probl`eme de connaitre la longueur de la chaˆıne maximum dans un graphe pond´er´e. c)Probl `emesdans NP ou dans P
Les probl`emes suivants sont-ils dans NP, dans P? Justifier votre r´eponse. Probl `emeP1 Donn´ees: Un grapheG= (V,E)
Question: Existe-t-il cycle de longueur ´egale `a?|V|2 Probl `emeP2 Donn´ees: Un grapheG= (V,E)
Question: Existe-t-il cycle de longueur ´egale `a 4? Probl `emeP3 Donn ´ees: Un grapheG= (V,E), deux sommetsuetvdistincts deGet un entierk. Question: Existe-t-il un simple chemin entreuetvde longueur inf´erieure ou ´egale `ak? Probl `emeP4 Donn´ees: Un grapheG= (V,E), et un entierk.
Question: Existe-t-il un arbre couvrant tous les sommets deGayant moins dekfeuilles?II). R
´EDUCTION POLYNOMIALE.7
II)R ´eductionp olynomiale.
a)SoientAetBdeux probl`emes de d´ecision.
Uner´eduction deAversBest une fonctionf:IA→IBcalculableen temps polynomial telle quew?Oui(A) si et seulement sif(w)?Oui(B). Question 4.3. Montrer queP=NPsi et seulement si 3-SAT?P. b)R ´eduction
SoientA, BetQdes probl`emes de d´ecision. Supposons queAest dansP, et queBest NP-dur. Dire si les affirmations suivantes sont vraies ou fausses : 1. Si Ase r´eduit polynˆomialement `aQ, alorsQest dansP. 2. Si Qse r´eduit polynˆomialement `aA, alorsQest dansP. 3.quotesdbs_dbs29.pdfusesText_35[PDF] Physique : 2nde Cours Chapitre 6 : Mouvement et vitesse I Pour
[PDF] DS2 : Ondes sonores et ultrasonores Nom : Durée conseillée : 45
[PDF] Exercices corrigés de Physique Terminale S - Physique-Chimie au
[PDF] Exercices supplémentaires PIB, chômage et inflation Problèmes
[PDF] Pluriel des adjectifs
[PDF] ORTHOGRAPHE : le pluriel des noms Evaluation CE2
[PDF] Résolution de problèmes de plus court chemin : Exercices - AUNEGE
[PDF] FICHE BREVET : LA POESIE
[PDF] TD5-3 Exos Thermique-eleve
[PDF] Thermodynamique n° 30
[PDF] Grammaire La ponctuation Recopie ce texte en plaçant - La pmev
[PDF] Grammaire La ponctuation Recopie ce texte en plaçant - La pmev
[PDF] Calcul des structures hyperstatiques Cours et exercices - USTO
[PDF] 41 Exercice pour mieux se connaître - Addiction Suisse