You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

147 lines
4.2KB

  1. \section{Chapitre 1: Introduction}
  2. \label{sec:ch1}
  3. \subsection{NP-Complétude}
  4. \label{sec:ch1npc}
  5. \paragraph{Instance SAT}
  6. \begin{itemize}
  7. \item $x_i \in \lbrace 0,1 \rbrace$
  8. \item Un \textbf{litéral}: $x_i$ ou $\neg x_i$
  9. \item Une \textbf{clause} SAT = disjonction de litéraux
  10. \item Une \textbf{solution} satisfait l'ensemble des clauses de l'\textbf{instance}
  11. \item Si au moins une solution existe, l'instance est réalisable ou \textbf{satisfiable}
  12. \end{itemize}
  13. \paragraph{La classe NP}
  14. \begin{itemize}
  15. \item \textbf{Problème de décision}: La réponse est \textit{oui} ou \textit{non}
  16. \item \textbf{Certificat}: Donnée prouvant que la solution au problème de décision est \textit{oui}
  17. \item \textbf{Algorithme de vérification}: vérifie si une donnée est un certificat valide
  18. \item \textbf{Classe NP}: Ensemble des problèmes de décision qui admettent un algorithme de vérification en temps polynomial.
  19. \end{itemize}
  20. \subsection{Problèmes de satisfaction et d'optimisation avec contraintes}
  21. \label{sec:ch1propt}
  22. \paragraph{Satisfaction}
  23. \begin{itemize}
  24. \item Variables: $x_1, \ldots, x_n$
  25. \item Domaine: $\mathtt{dom}(x_1), \ldots, \mathtt{dom}(x_n)$
  26. \item Contraintes: $C_1, \ldots, C_m$
  27. \end{itemize}
  28. \paragraph{Optimisation}
  29. \begin{itemize}
  30. \item Reprend les éléments du problème de satisfaction
  31. \item Ajoute une fonction objectif réelle à minimiser ou maximiser: $f(x_1, \ldots, x_n): \R$
  32. \end{itemize}
  33. \subsection{Contraintes}
  34. \label{sec:ch1cont}
  35. \begin{itemize}
  36. \item \textbf{Contrainte}: condition imposée à un sous-ensemble de variables, appelé \textbf{portée}.
  37. \item \textbf{Arité}: nombre de variables dans la portée
  38. \end{itemize}
  39. \paragraph{Quelques contraintes}
  40. \begin{itemize}
  41. \item $\textsc{Ou}(x_1,x_2) \equiv x_1 \vee x_2$
  42. \item $\textsc{Et}(x_1,x_2) \equiv x_1 \wedge x_2$
  43. \item $\textsc{Addition}(a,b,c) \equiv a+b=c$
  44. \item $\textsc{Soustraction}(a,b,c) \equiv a-b=c$
  45. \item $\textsc{Multiplication}(a,b,c) \equiv ab=c$
  46. \item $\textsc{Division}(a,b,c) \equiv \frac{a}{b}=c$
  47. \item $\textsc{Tableau}(x_1,x_2,x_3,T)$
  48. \item $\textsc{AllDifferent}(x_1, \ldots, x_n) \equiv x_1 \neq \ldots \neq x_n$
  49. \item $\textsc{Croissant}(x_1,x_2) \equiv x_1 \leq x_2$
  50. \item $\textsc{Décroissant}(x_1,x_2) \equiv x_1 \geq x_2$
  51. \end{itemize}
  52. \subsection{Modélisation}
  53. \begin{enumerate}
  54. \item Utiliser les contraintes du solveur
  55. \item Concevoir un modèle:
  56. \begin{itemize}
  57. \item Variables
  58. \item Domaines
  59. \item Fonction objectif
  60. \item Contraintes
  61. \end{itemize}
  62. \item Soumettre un modèle au solveur
  63. \item Recevoir une solution
  64. \end{enumerate}
  65. \paragraph{Exemple}
  66. Problème du commis voyageur: Figure \ref{fig:ch1commis}
  67. \begin{figure}[ht]
  68. \centering
  69. \begin{tikzpicture}
  70. \Vertex[x=0,y=0]{A}
  71. \Vertex[x=4,y=0]{B}
  72. \Vertex[x=0,y=4]{C}
  73. \Vertex[x=4,y=4]{D}
  74. \Edge[label= $1$](A)(B)
  75. \Edge[label= $3$](A)(C)
  76. \Edge[label= $2$](B)(D)
  77. \Edge[label= $6$](C)(D)
  78. \tikzset{EdgeStyle/.append style = {bend left}}
  79. \Edge[label= $1$](A)(D)
  80. \tikzset{EdgeStyle/.append style = {bend right}}
  81. \Edge[label= $5$](B)(C)
  82. \end{tikzpicture}
  83. \caption{Exemple de problème du commis voyageur}
  84. \label{fig:ch1commis}
  85. \end{figure}
  86. \begin{align}
  87. \begin{aligned}
  88. \argmin_{d_0 \ldots d_3} & \left( d_0+ \ldots +d_3 \right) \\
  89. \textrm{s.t.} &\\
  90. &\mathtt{dom}(x_i) = \lbrace A,B,C,D \rbrace & \forall i \in {0,\ldots,3}\\
  91. &\mathtt{dom}(d_i) = \lbrace 1,2,3,5,6 \rbrace & \forall i \in {0,\ldots,3}\\
  92. &\textsc{Tableau}(x_i,x_{i+1 mod 4}, d_i, T) & \forall i \in {0,\ldots,3}\\
  93. &x_i \neq x_j & 0 \leq i \leq j \leq 3
  94. \end{aligned}
  95. \end{align}
  96. \paragraph{Caractéristiques d'un bon modèle}
  97. \begin{itemize}
  98. \item Taille d'un modèle:
  99. \begin{itemize}
  100. \item Nombre de variables
  101. \item Nombre de contraintes (une ligne dans un tableau = une contrainte)
  102. \item Cardinalité des domaines
  103. \end{itemize}
  104. \item Notation asymptotique $\mathcal{O}$ ou $\mathcal{\Theta}$
  105. \item Taille polynomiale
  106. \end{itemize}
  107. \paragraph{Exemple}
  108. Problème du commis voyageur
  109. \begin{itemize}
  110. \item $2n$ variables
  111. \item $n^2+\frac{n^2(n+1)}{2} \in \mathcal{\Theta}(n^3)$ valeurs
  112. \item $n$ contraintes tableau $+\frac{n(n+1)}{2}$ différences $\in \Theta(n^2)$
  113. \end{itemize}
  114. %%% Local Variables:
  115. %%% mode: latex
  116. %%% TeX-master: "notes_de_cours"
  117. %%% End: