commit fdc26a36a4b386cd5145e06753682460c6a131f4
parent 9ad26fc8f150257ba519f73982f05ba22348ab6f
Author: John Charron <rm_rf_windows@yahoo.fr>
Date: Tue, 14 Dec 2010 19:21:07 +0100
Merge branch 'master' of github:jsmaniac/2010-m1s1-complexite
Diffstat:
| M | rapport.tex | | | 31 | +++++++++++++++++++------------ |
| A | test.tex | | | 154 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 173 insertions(+), 12 deletions(-)
diff --git a/rapport.tex b/rapport.tex
@@ -574,18 +574,22 @@ transformations suivantes~:
\item Les clauses qui contiennent exactement deux littéraux, ${l_1, l_2}$ sont transformées en ${l_1, l_2, l_1}$.
\end{itemize}
-Cette transformation est linéaire en complexité. En effet, on ne considère chaque littéral qu'une fois et on ajoute $n-3$ littéraux pour chaque clause. Il s'agit de complexité polynomiale.
+Cette transformation est linéaire en complexité. En effet, on ne considère chaque littéral qu'une fois et on ajoute $n-3$ littéraux pour
+chaque clause. Il s'agit de complexité polynomiale.
\begin{sousenonce}
Justifier alors que 3-SAT est NP-complet (sachant que SAT est NP-complet).
\end{sousenonce}
-Vu que SAT est np-complet et que 3-SAT sait faire ce que sait faire SAT, avec une transformation polynomiale, 3-SAT (y compris la transformation) est au moins aussi dur que SAT. La difficulté peut résiter(??) dans la transformation, 3-SAT ou les deux.(??)
+Vu que SAT est np-complet et que 3-SAT sait faire ce que sait faire SAT, avec une transformation polynomiale, 3-SAT (y compris la
+transformation) est au moins aussi dur que SAT. La difficulté peut résiter(??) dans la transformation, 3-SAT ou les deux.(??)
Vu que la difficulté ne s'est pas cachée dans la transformation, qui est polynomiale alors que SAT est np-complet, 3-SAT est np-complet lui aussi.
\begin{sousenonce}
-Application : si un ensemble de clauses contient $n_v$ variables, $n_1$ clauses à un littéral, $n_2$ clauses à 2 littéraux, $n_3$ clauses à 3 littéraux, $n_4$ clauses à 4 littéraux, $n_5$ clauses à 5 littéraux (et pas d'autres clauses), combien le système obtenu par votre réduction contient-il de variables et de clauses ? Vous devrez bien sûr justifier votre réponse.
+ Application : si un ensemble de clauses contient $n_v$ variables, $n_1$ clauses à un littéral, $n_2$ clauses à 2 littéraux, $n_3$ clauses
+ à 3 littéraux, $n_4$ clauses à 4 littéraux, $n_5$ clauses à 5 littéraux (et pas d'autres clauses), combien le système obtenu par votre
+ réduction contient-il de variables et de clauses ? Vous devrez bien sûr justifier votre réponse.
\end{sousenonce}
Le système obtenu par la réduction contient :
@@ -622,12 +626,15 @@ Il s'agit de prouver que 2-SAT est un problème polynomial. Vous avez un article
\setcounter{sousenoncecount}{0}
\begin{sousenonce}
-Vous commencerez par fabriquer trois ensembles de deux clauses, le premier valide, le deuxième insatisfiable et le troisième contingent, et pour chacun de ces ensembles de clauses vous construirez le graphe correspondant. Vous expliquerez comment apparaît sur chacun des trois graphes la validité de l'ensemble de clauses corresponsdantes.
+ Vous commencerez par fabriquer trois ensembles de deux clauses, le premier valide, le deuxième insatisfiable et le troisième contingent,
+ et pour chacun de ces ensembles de clauses vous construirez le graphe correspondant. Vous expliquerez comment apparaît sur chacun des
+ trois graphes la validité de l'ensemble de clauses corresponsdantes.
\end{sousenonce}
Philippe Gambette, dans son article intitulé 'Un graphe pour résoudre 2-SAT', donne une explication succincte de l'agorithme d'Aspvall, Plass et Tarjan.
-Une formule logique en forme normale conjonctive contenant des clauses à deux littéraux est transformé en un problème de graphe orienté. On doit tout d'abord établir si la formule admet un modèle, et ensuite, si tel est le cas, donner un modèle quelconque.
+Une formule logique en forme normale conjonctive contenant des clauses à deux littéraux est transformé en un problème de graphe orienté. On
+doit tout d'abord établir si la formule admet un modèle, et ensuite, si tel est le cas, donner un modèle quelconque.
\begin{enumerate}
\item L'algorithme de construction de graphe :
@@ -936,13 +943,13 @@ formules telles que~:
$$
\begin{array}{rrcl}
& (a_{i1} & \Rightarrow & a_{i2}) \\
- \vee & (a_{i3} & \Rightarrow & a_{i4}) \\
- \vee & & \dots & \\
- \vee & (a_{i5} & \Rightarrow & \lnot a_{i1}) \\
- \vee & (\lnot a_{i1} & \Rightarrow & a_{i6}) \\
- \vee & (a_{i7} & \Rightarrow & a_{i8}) \\
- \vee & & \dots & \\
- \vee & (a_{i9} & \Rightarrow & a_{i1}) \\
+ \wedge & (a_{i3} & \Rightarrow & a_{i4}) \\
+ \wedge & & \dots & \\
+ \wedge & (a_{i5} & \Rightarrow & \lnot a_{i1}) \\
+ \wedge & (\lnot a_{i1} & \Rightarrow & a_{i6}) \\
+ \wedge & (a_{i7} & \Rightarrow & a_{i8}) \\
+ \wedge & & \dots & \\
+ \wedge & (a_{i9} & \Rightarrow & a_{i1}) \\
\end{array}
$$
Ce qui peut se réduire à $a_{i1} \Rightarrow \lnot a_{i1} \Rightarrow a_{i1}$ autrement dit $a_{i1} \Leftrightarrow \lnot a_{i1}$, ce qui
diff --git a/test.tex b/test.tex
@@ -0,0 +1,153 @@
+\documentclass{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage[frenchb]{babel}
+\usepackage{tikz}
+\usepackage{amsmath}
+\usepackage{listings}
+\usepackage{amssymb}
+\usetikzlibrary{chains,positioning,matrix,arrows,decorations,calc}
+\title{Rapport de projet : FMIN105\\ Cours algorithmique / complexité / calculabilité}
+\author{\textsc{Bonavero} Yoann \\ \textsc{Brun} Bertrand \\ \textsc{Charron} John \\ \textsc{Dupéron} Georges}
+\date{}
+
+\setlength{\parindent}{0pt}
+\setlength{\parskip}{2ex}
+
+\newcounter{exocount}
+\setcounter{exocount}{0}
+
+\newcounter{enoncecount}
+\setcounter{enoncecount}{0}
+
+\newenvironment{enonce}
+{
+\stepcounter{enoncecount}
+\bf\small \arabic{enoncecount}.
+\begin{bf}
+}
+{
+\end{bf}
+}
+
+
+\newcounter{sousenoncecount}
+\setcounter{sousenoncecount}{0}
+\newenvironment{sousenonce}
+{
+\stepcounter{sousenoncecount}
+\bf\small (\alph{sousenoncecount})
+\begin{bf}
+}
+{
+\end{bf}
+}
+
+\begin{document}
+\setcounter{page}{0}
+\pagestyle{plain}
+
+\makeatletter
+\def\myadv#1#2{%
+ \xdef\incr@backup{\the\@tempcnta}%
+ \@tempcnta=#1{}%
+ \advance\@tempcnta by #2{}%
+ \xdef#1{\the\@tempcnta}%
+ \@tempcnta=\incr@backup{}%
+}
+\def\incr#1{%
+ \myadv#1{1}%
+}
+\def\decr#1{%
+ \myadv#1{-1}%
+}
+\makeatother
+
+\begin{figure}[h!]
+ \xdef\maxdots{81}
+ \xdef\maxnums{56}
+ \xdef\maxcoords{20}
+ \centering
+ \begin{tikzpicture}[
+ dot/.style={
+ circle,
+ inner sep=0.5pt,
+ outer sep=0.5pt,
+ fill=black
+ },
+ numero/.style={red},
+ ]
+ \xdef\i{0}
+ \xdef\x{0}
+ \xdef\y{0}
+ \xdef\corner{0}
+ \xdef\sidelen{1}
+ \xdef\nextsidelen{1}
+ \xdef\direction{0}
+ \incr\maxnums
+ \incr\maxcoords
+
+ \def\reallysmallcheat#1{%
+ \ensuremath{\hphantom{\vphantom{X}}_{\hphantom{\vphantom{X}}_{#1}}}
+ }
+ \def\drawnode{%
+ \node[dot] (\x-\y) at (\x,\y) {};
+ \ifnum\maxnums>\i
+ \ifnum\corner=0 \node[numero,anchor=north west] at (\x-\y.south east) {\i}; \else
+ \ifnum\corner=1 \node[numero,anchor=south west] at (\x-\y.north east) {\i}; \else
+ \ifnum\corner=2 \node[numero,anchor=south east] at (\x-\y.north west) {\i}; \else
+ \ifnum\corner=3 \node[numero,anchor=north east] at (\x-\y.south west) {\i}; \else
+ \ifnum\direction=0 \node[numero,anchor=west] at (\x-\y.east) {\i}; \else
+ \ifnum\direction=1 \node[numero,anchor=south] at (\x-\y.north) {\i}; \else
+ \ifnum\direction=2 \node[numero,anchor=east] at (\x-\y.west) {\i}; \else
+ \ifnum\direction=3 \node[numero,anchor=north] at (\x-\y.south) {\i}; \fi\fi\fi\fi\fi\fi\fi\fi
+ \fi
+ % {\i\reallysmallcheat{(\x, \y)}};
+ }
+ \def\drawlinknode{%
+ \drawnode%
+ \draw[->] (\oldx-\oldy) -- (\x-\y);%
+ }
+ \def\mystep{%
+ \incr\i%
+ \xdef\oldx{\x}%
+ \xdef\oldy{\y}%
+ }
+
+ \drawnode
+ \mystep \incr\x
+
+ \foreach \pos in {1,...,\maxdots} {
+ % Detect when we are at the end of this edge.
+ \ifnum\sidelen=0
+ \ifnum\direction=0 \xdef\direction{1} \xdef\corner{1} \incr\nextsidelen \else
+ \ifnum\direction=1 \xdef\direction{2} \xdef\corner{2} \else
+ \ifnum\direction=2 \xdef\direction{3} \xdef\corner{3} \incr\nextsidelen \else
+ \ifnum\direction=3 \xdef\direction{0} \xdef\corner{0} \fi\fi\fi\fi% Brin d'acier
+ \xdef\sidelen{\nextsidelen}
+ \fi
+ % Draw node and link to previous, step counters
+ \drawlinknode \mystep
+ %% Se déplacer vers ↑←↓→
+ \ifnum\direction=0 \incr\y \fi
+ \ifnum\direction=1 \decr\x \fi
+ \ifnum\direction=2 \decr\y \fi
+ \ifnum\direction=3 \incr\x \fi
+ \decr\sidelen
+ \xdef\corner{4}%% 4 == pas de coin-coin.
+ }
+ % \foreach \sidelen in {2,4, ...,6} {
+ % \foreach \pos in {2, ..., \sidelen} { \drawlinknode \mystep \incr\y }
+ % \foreach \pos in {1, ..., \sidelen} { \drawlinknode \mystep \decr\x }
+ % \foreach \pos in {1, ..., \sidelen} { \drawlinknode \mystep \decr\y }
+ % \foreach \pos in {0, ..., \sidelen} { \drawlinknode \mystep \incr\x }
+ % }
+ % %% Dernier côté :
+ % \foreach \pos in {2, ..., 8} { \drawlinknode \mystep \incr\y }
+ \end{tikzpicture}
+ \caption{TODO : caption}
+ \label{fig:graphe-g}
+\end{figure}
+
+\end{document}
+\ No newline at end of file
