\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[frenchb]{babel}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{listings}
\usepackage{amssymb}
\usepackage{pdfpages}
\usetikzlibrary{chains,positioning,matrix,arrows,decorations,calc,fit}
%\usepackage{hyperref}
\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{}

\lstset{
  language=C,    %% Preload
  language=Lisp, %% Preload + default
  showspaces=false,
  showstringspaces=false,
  showtabs=false,
  tabsize=4,
  columns=flexible% if this is not enough, use columns=fullflexible.
}

\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}
\includepdf{couverture.pdf}
\setcounter{page}{0}
\pagestyle{empty}
\thispagestyle{empty}
\tableofcontents
\pagestyle{empty}
\thispagestyle{empty}
\newpage
\pagestyle{plain}


\section{Descriptif des tâches}
Vos résultats seront présentés en procédant à la rédaction d'un mémoire dont la qualité influencera la note finale. Ce manuscrit sera rendu le jour de la soutenance. La soutenance consiste à présenter résultats pratiques (choix du langage, choix des structures de données, résultats obtenus, tests sur un grand jeu de données, analyse de ceux-ci ...). Vous aurez 15 minutes au maximum, questions comprises. Vous avez la possibilité d'utiliser des transparents.


\section{Partie théorique}
\subsection{Partie algorithmique}

\subsubsection*{Exercice \stepcounter{exocount}\bf\small \arabic{exocount} -- Modélisation et résolution d'un problème d'ordonnancement par un problème de flot maximum : ordonnancement avec coûts dépendants des dates de début}
\addcontentsline{toc}{subsubsection}{Exercice \arabic{exocount} -- Modélisation et résolution d'un problème d'ordonnancement par un problème de flot maximum : ordonnancement avec coûts dépendants des dates de début}



\begin{figure}[h!]
  \centering
  \begin{tikzpicture}[node distance=3cm]
    \node (J1) {$J_{1}$};
    \node (J2) [above of=J1] {$J_{2}$};
    \node (J3) [right of=J1] {$J_{3}$};
    \draw[->] (J1) -- (J2);
    \draw[->] (J1) -- (J3);
    \draw[->] (J3) -- (J2);
  \end{tikzpicture}
  \caption{Graphe G}
  \label{fig:graphe-g}
\end{figure}

\begin{enonce}
Construire le graphe $G^*$ pour $n = 3$, $T = 5$, $p_1 = 1$, $p_2 = 2$, $p_3 = 1$, 
$E = \{(1,2), (1,3), (3,2)\}$ et les coûts suivants :
\end{enonce}

\begin{figure}[ht!]
  \centering
	\begin{tabular}{cccccc}
	\hline	
	$i,t$ & 0 & 1 & 2 & 3 & 4\\
	\hline
	1 & 0 & 2 & 5 & 0 & 1\\
	2 & 1 & 1 & 2 & 4 & -\\
	3 & 1 & 10 & 2 & 3 & 3\\
	\hline
\end{tabular}
\end{figure}

\begin{figure}[ht!]
  \centering
  \colorlet{affectation}{green!75!black}
  \colorlet{auxiliaire}{black}
  \colorlet{précédence}{blue}
  \begin{tikzpicture}[
      affectation/.style = {
        draw=affectation,
        ->
      },
      auxiliaire/.style = {
        draw=auxiliaire,
        ->
      },
      précédence/.style = {
        draw=précédence,
        ->
      },
      capacité/.style = {
        fill=white,
        font=\footnotesize
      },
      capacité affectation/.style = {
        text=affectation,
        capacité
      },
      capacité auxiliaire/.style = {
        text=auxiliaire,
        capacité
      },
      capacité précédence/.style = {
        text=précédence,
        capacité
      }
    ]
    
    \matrix[matrix of math nodes, nodes in empty cells, row sep=1cm, column sep=0.9cm] (m) {
      & v_{1,0} & v_{1,1} & v_{1,2} & v_{1,3} & v_{1,4} & v_{1,5} & \\
      s & v_{3,0} & v_{3,1} & v_{3,2} & v_{3,3} & v_{3,4} & v_{3,5} & t \\
      & v_{2,0} & v_{2,1} & v_{2,2} & v_{2,3} & v_{2,4} & & \\
    };
    
    %% Penser a rajouter les J1, J2 et J3 a gauche du graphe.
    
  	\draw[affectation] (m-1-2)-- node[capacité affectation]{0} (m-1-3);
	\draw[affectation] (m-1-3)-- node[capacité affectation]{2} (m-1-4);
	\draw[affectation] (m-1-4)-- node[capacité affectation]{5} (m-1-5);
	\draw[affectation] (m-1-5)-- node[capacité affectation]{0} (m-1-6);
	\draw[affectation] (m-1-6)-- node[capacité affectation]{1} (m-1-7);

	\draw[affectation] (m-2-2)-- node[capacité affectation]{1} (m-2-3);
	\draw[affectation] (m-2-3)-- node[capacité affectation]{10} (m-2-4);
	\draw[affectation] (m-2-4)-- node[capacité affectation]{2} (m-2-5);
	\draw[affectation] (m-2-5)-- node[capacité affectation]{3} (m-2-6);
	\draw[affectation] (m-2-6)-- node[capacité affectation]{3} (m-2-7);

	\draw[affectation] (m-3-2)-- node[capacité affectation]{1} (m-3-3);
	\draw[affectation] (m-3-3)-- node[capacité affectation]{1} (m-3-4);
	\draw[affectation] (m-3-4)-- node[capacité affectation]{2} (m-3-5);
	\draw[affectation] (m-3-5)-- node[capacité affectation]{4} (m-3-6);
	
  	\draw[auxiliaire] (m-2-1)-- node[capacité auxiliaire]{$\infty$} (m-1-2);
  	\draw[auxiliaire] (m-2-1)-- node[capacité auxiliaire]{$\infty$} (m-2-2);
  	\draw[auxiliaire] (m-2-1)-- node[capacité auxiliaire]{$\infty$} (m-3-2);
  	\draw[auxiliaire] (m-1-7)-- node[capacité auxiliaire]{$\infty$} (m-2-8);
  	\draw[auxiliaire] (m-2-7)-- node[capacité auxiliaire]{$\infty$} (m-2-8);
  	\draw[auxiliaire] (m-3-6)--(m-3-7.center)-- node[capacité auxiliaire]{$\infty$} (m-2-8);
	
	\draw[précédence] (m-1-2)-- node[capacité précédence]{$\infty$} (m-2-3);
	\draw[précédence] (m-1-3)-- node[capacité précédence]{$\infty$} (m-2-4);
	\draw[précédence] (m-1-4)-- node[capacité précédence]{$\infty$} (m-2-5);
	\draw[précédence] (m-1-5)-- node[capacité précédence]{$\infty$} (m-2-6);
	\draw[précédence] (m-1-6)-- node[capacité précédence]{$\infty$} (m-2-7);
    
	\draw[précédence] (m-2-2)-- node[capacité précédence]{$\infty$} (m-3-3);
	\draw[précédence] (m-2-3)-- node[capacité précédence]{$\infty$} (m-3-4);
	\draw[précédence] (m-2-4)-- node[capacité précédence]{$\infty$} (m-3-5);
	\draw[précédence] (m-2-5)-- node[capacité précédence]{$\infty$} (m-3-6);

	\draw[précédence] (m-1-2)-- node[capacité précédence,pos=0.3]{$\infty$} (m-3-3);
	\draw[précédence] (m-1-3)-- node[capacité précédence,pos=0.3]{$\infty$} (m-3-4);
	\draw[précédence] (m-1-4)-- node[capacité précédence,pos=0.3]{$\infty$} (m-3-5);
	\draw[précédence] (m-1-5)-- node[capacité précédence,pos=0.3]{$\infty$} (m-3-6);
  \end{tikzpicture}
  \caption{Graphe $G^*(X^*, E^*)$}
  \label{fig:graphe-g*}
\end{figure}



\begin{enonce}
Montrer qu'il existe une coupe dans $G^*$ de capacité minimale de laquelle sort un et un seul arc d'affectation par job.
\end{enonce}

Démonstration par construction~: 
On effectue un tri topologique sur le graphe des contraintes de précédence $G(\{J_1, \dots, J_n\}, E)$. Ce tri topologique nous donne un
ensemble ordonné de n\oe uds $(J_{a1}, \dots, J_{an})$. On a donc~:
$$\forall j < i \quad (J_{aj}, J_{ai}) \not\in E$$
On transforme ensuite $G$ en un graphe de flots $G^*(X^*,E^*)$ à l'aide de l'algorithme fourni dans le sujet. 
Considérons les arcs entre les $v_{ai,t}$~: 
\begin{itemize}
	\item Arcs d'affectation~: ces arcs sont entre des sommets $v_{ai,t}$ et $v_{aj,t'}$ avec $ai = aj$
	\item Arcs de précédences~: ces arcs sont entre des sommets $v_{ai,t}$ et $v_{aj,t'}$ avec $ai < aj$, car grâce au tri topologique, il
      n'existe pas d'arcs entre des sommets $J_{ai}$ et $J_{aj}$ avec $aj < ai$, et de plus il n'y a pas de boucle (donc pas d'arc
      $(J_{ai},J_{ai})$ dans $E$, donc pas d'arc $(v_{ai,t}, v_{ai,t'})$ dans $E^*$).
	\item Arcs auxiliaires~: ces arcs ne sont pas entre des sommets $v_{ai,t}$.
\end{itemize}

Soit un $(s-t)-\mathrm{coupe}$ minimale, entre les ensembles de noeuds $S$ et $T$. Etant donné que cette coupe est minimale, aucun arc de
capacité infinie n'a son origine dans $S$ et son extremité dans $\overline{S}$. Autrement dit, en fonction des noeuds présents dans S, on
est donc \og obligé\fg{} d'inclure dans $S$ toutes les extrémités des arcs de capacité infinie et dont l'origine est dans $S$. On va donc
construire $S$ itérativement en suivant cette règle.

\begin{itemize}
\item $s \in S$ et tous les arcs sortants de $s$ sont les arcs auxiliaires de capacité infinie qui pointent sur tous les $v_{ai,0}$. On
  les inclut donc dans $S$.
\item Pour chaque $v_{ai,t}$ dans $S$ on n'a pas besoin de suivre les arcs d'affectation car ils sont de capacité finie. Comme ces arcs
  d'affectation \og restent sur la même ligne\fg, à partir du moment où un $v_{ai,t}$ est présent dans $S$, les arcs d'affectation ne nous
  obligent pas à inclure les $v_{ai,t'}$ avec $t' > t$.
\item Par contre les arcs de précédence nous obligent, lorsqu'on inclut un $v_{ai,t}$, d'inclure tous les $v_{aj,t'}$ qui sont à l'extrêmité
  d'un arc de précédence partant de ce $v_{ai,t}$.
\end{itemize}

Puisque la coupe est minimale et que tous les $v_{ai,0}$ font partie de $S$, lorsqu'un $v_{ai,t}$ fait partie de S, alors tous les
$v_{ai,t'}$ avec $0 \leq t' \leq t$ font aussi partie de $S$ (car sinon on ajoute le coût des arcs d'affectation intermédiaires).

On a donc $s \in S$ et
\begin{equation}
\forall ai \quad \exists t \quad (0 <= t' <= t) \Leftrightarrow (v_{ai,t} \in S)
\label{eq:tous-t-debut-ligne}
\end{equation}

Il ne sort donc qu'un et un seul arc d'affectation par job dans toute coupe minimale.

Évidemment, cette coupe minimale ne peut exister que s'il y a «suffisemment de temps pour tout faire», autrement dit, si la somme des durées
d'exécution des tâches est supérieure au temps disponible, on ne pourra pas effectuer toutes les tâches.

\begin{enonce}
Montrer que l'on peut associer un ordonnancement réalisable (qui respecte toutes les contraintes) à toute 
coupe de capacité finie minimale dans le graphe. Quel est le coût de cet ordonnancement ? 
\end{enonce}

Dans l'exercice précédent, on a montré que de toute coupe minimale sort un et un seul arc d'affectation par job.

On cherche à associer un ordonancement réalisable à toute coupe minimale.

On va construire cet ordonancement de la manière suivante~: à chaque
fois qu'un arc d'affectation $v_{ai,t}, v_{ai,t+1}$ traverse la coupe,
on exécute le job $ai$ à l'instant $t$ dans l'ordonancement. 

\textbf{Cherchons un ordonancement}, un ensemble de paires $(\text{tâche},\text{date de début})$ respectant les dépendances.
Autrement dit, chaque tâche apparaît après ses dépendances dans la suite.

Soit $te(ai) = t$ la fonction qui à un job $ai$ associe son temps de début d'exécution $t$.
Nous allons montrer que~:
$$(\exists ai,t,aj,t' \quad (v_{ai,t},v_{aj,t'}) \in E^*) \qquad \Rightarrow \qquad (te(ai) > te(aj) \quad \Leftrightarrow \quad ai > aj)$$
Cela signifie que s'il existe un arc de précédence entre deux noeuds, alors le job qui
correspond au noeud «le plus haut» s'exécute avant le job qui correspond au
noeud «le plus bas».

En effet, si $t = te(ai)$ est le temps de début d'exécution du job $ai$, alors c'est que $v_{ai,t}, v_{ai,t+1}$
traverse la coupe, et donc :
\begin{equation}
  \forall tt \quad v_{ai,tt} \in S \Leftrightarrow tt <= t
  \label{eq:tous-t-avant-exec}
\end{equation}

Il en va de même pour $\forall tt' <= t' \quad v_{aj,tt'} \in S$.

Comme il y a un arc d'affectation du job $ai$ vers le job $aj$,
$$\exists\ {} tdest > t \quad (v_{ai,t},v_{aj,tdest}) \in E^*$$
et vu que la capacité de cet arc de précédence est infinie, $tdest \in S$. En utilisant les équations \ref{eq:tous-t-debut-ligne} et
\ref{eq:tous-t-avant-exec}, on peut affirmer que $tdest <= t$. Nous avons donc bien montré que l'arc d'affectation entre la tâche $ai$ et la
tâche $aj$ «forçait» $aj$ à s'exécuter après $ai$.

Grâce au tri topoligique, nous pouvons affirmer que tous les arcs de précédence entrants dans le noeud $v_{ai,te(ai)}$ viennent d'une ligne
«plus haute», autrement dit d'un noeud $v_{aj,t'}$ avec $aj < ai$. Et grâce à ce que nous avons prouvé précédemment,
on sait que $te(aj) < te(ai)$.

\textbf{On cherche un ordonancement réalisable}, c'est-à-dire pour lequel
toutes les tâches peuvent être menées à bout durant le temps
imparti.


La propriété énoncée dans la question 2 de l'exercice 1 nous indique que de toute coupe minimale sort un et un seul arc d'affectation par
job. Cela signifie que chaque job a commencé à être exécuté. Comme il exite un noeud pour le job $aj$ à l'instant $t$ si et seulement s'il y
a le temps de l'exécuter (\ogà chaque date de début possible\fg), cela signifie que tous les jobs commencés ont eu le temps d'être terminés
et, comme nous venons de voir, que tous les jobs ont pu être commencés -- ils ont tous pu être terminés -- et, par conséquent,
l'ordonancement est réalisable.

\begin{enonce}
Montrer qu'à tout ordonnancement réalisable correspond une coupe dont la capacité est égale au coût de l'ordonnancement.
\end{enonce}

On construit la coupe à partir de l'ordonancement de la même manière
qu'on a construit l'ordonancement à partir de la coupe dans l'exercice
précédent, mais en suivant l'algorithme dans l'autre sens.

Si on exécute le job $ai$ à l'instant $t$ dans l'ordonancement, alors
tous les noeuds $v_{ai,t'}$ avec $t' \leq t$ sont dans la partie \og
gauche\fg{} de la coupe. De plus, $s$ appartient lui aussi à la partie
gauche de la coupe et aucun arc de précédence ne sort de la coupe.

La capacité de cette coupe est la somme de la capacité de tous les
arcs qui sortent de la coupe, c'est-à-dire la somme des capacités des
arcs $v_{ai,t}, v_{ai,t+1}$. Comme la capacité de ces arcs est égale au
coût d'exécution de la tâche $ai$ à l'instant $t$, on a bien égalité entre
la somme des capacités et la somme des coûts de démarrage des jobs,
donc la capacité de la coupe est égale au coût de l'ordonancement.


\subsubsection*{Exercice \stepcounter{exocount}\bf\small \arabic{exocount} -- Coupes et chemins arc-disjoints}
\addcontentsline{toc}{subsubsection}{Exercice \arabic{exocount} -- Coupes et chemins arc-disjoints}
\setcounter{enoncecount}{0}

\begin{enonce}
Calculer le nombre maximum des chemins d'arcs disjoints à partir de la source jusqu'au puits dans le réseau donné par la figure 1. 
\end{enonce}

Il existe un ensemble de chemins d'arcs disjoints de cardinal 3~:

$$
\begin{array}{ccccccc}
  1 & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 6 \\
  1 & \rightarrow & 3 & \rightarrow & 4 & \rightarrow & 6 \\
  1 & \rightarrow & 4 & \rightarrow & 5 & \rightarrow & 6 \\
\end{array}
$$

Cherchons s'il en existe un de cardinal 4. Voici la liste des chemins
obtenue par un parcours en profondeur (en prennant toujours en premier
les sommets voisins avec le numéro le plus petit possible)~:

%% TODO~: numéroter les "équations" «proprement». Mais il semble que LaTeX ne permette pas de numéroter les lignes d'une matrice sans se casser la tête :-(
%% Ou sinon, il faut utilise \begin{align}/\end{align}, mais On ne peut pas choisir l'espacement des colonnes (et il est beaucoup trop gros à ce moment-là.
$$
\begin{array}{cccccccccccr}
  1 & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 4 & \rightarrow & 5 & \rightarrow & 6 & \quad (A) \\
  1 & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 4 & \rightarrow & 6 &             &   & \quad (B) \\
  1 & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 6 &             &   &             &   & \quad (C) \\
  1 & \rightarrow & 3 & \rightarrow & 4 & \rightarrow & 5 & \rightarrow & 6 &             &   & \quad (D) \\
  1 & \rightarrow & 3 & \rightarrow & 4 & \rightarrow & 6 &             &   &             &   & \quad (E) \\
  1 & \rightarrow & 3 & \rightarrow & 6 &             &   &             &   &             &   & \quad (F) \\
  1 & \rightarrow & 4 & \rightarrow & 5 & \rightarrow & 6 &             &   &             &   & \quad (G) \\
  1 & \rightarrow & 4 & \rightarrow & 6 &             &   &             &   &             &   & \quad (H) \\
\end{array}
$$

Voyons les ensembles qui contiennent le chemin $A$~: On ne peut pas
prendre les chemins $B$ et $C$ car ils ont l'arc $(1,2)$ en commun
avec $A$. On ne peut pas prendre non plus les chemin $D$ et $G$ car
ils ont l'arc $(5,6)$ en commun avec $A$ ni le chemin $E$ à cause de
l'arc $(3,4)$. Il ne reste plus que les chemins $F$ et $H$ qu'on
pourrait peut-être prendre si on prend $A$, mais le cardinal de
l'ensemble serait alors 3, donc on n'améliorerait pas le résultat
existant. En conséquence, ce n'est pas la peine de chercher si ces chemins
sont \og compatibles\fg{} avec $A$.

Procédons de la même manière pour $B$ (sachant que $A$ ne peut pas
faire partie de l'ensemble). Si on a le chemin $B$, alors on ne peut
pas avoir~:
\begin{itemize}
  \item $C$ (arc $(2,3)$),
  \item $D$ (arc $(3,4)$),
  \item $E$ (arc $(3,4)$),
  \item $H$ (arc $(4,6)$).
\end{itemize}
À partir de ce moment, il ne reste plus que $F$ et $G$, l'ensemble
serait de cardinal 3, donc $B$ ne peut pas être dans un ensemble de
cardinal 4.

Passons à $D$ avec $A$ et $B$ exclus. On ne peut pas avoir~:
\begin{itemize}
\item $E$ (arc $(3,4)$),
\item $F$ (arc $(1,3)$),
\item $G$ (arc $(4,5)$).
\end{itemize}
Donc $D$ n'est pas dans l'ensemble.

Passons à $F$ avec $A,B,D$ exclus. On ne peut pas avoir~:
\begin{itemize}
\item $C$ (arc $(3,6)$),
\item $E$ (arc $(1,3)$).
\end{itemize}
Donc $F$ n'est pas dans l'ensemble.

Comme $A,B,D,F$ ne sont pas dans l'ensemble et que nous avons
seulement 8 candidats, la seule possibilité qui reste pour un ensemble
de cardinal 4 est $C,E,G,H$. Or, dans cet ensemble, l'arête $(1,4)$
est commune à $G$ et $H$, donc on ne peut pas construire un ensemble
de chemins d'arcs disjoints de taille 4 ni de taille supérieure
à 4.

Conclusion~: Le nombre maximum de chemins d'arcs disjoints est 3.

\begin{enonce}
Enumérer tous les s-t-coupes dans le réseau donnés par la figure 1. Pour chaque s-t-coupe $[S,\overline{S}]$, énumérer les sommets, les arcs avants et les arcs arrières.
\end{enonce}

% Code LISP pour générer le tableau ci-après :

% (defun S (n p)
%   (if p
%       (format t "         ~a  " n)
%       (format t "\\phantom{~a} " n)))

% (defun Sbar (n p)
%   (S-n-p n (not p)))

% (defun print-arcs (arcs)
%   (when arcs
%     (when (car arcs)
%       (format t "(~a,~a)" (caar arcs) (cdar arcs))
%       (unless (endp (cdr arcs))
%         (format t ", ")))
%     (print-arcs (cdr arcs))))

% (defun print-arcs-if-not-nil (arcs)
%   (print-arcs (remove-if-not #'identity arcs)))

% (defun print-line (l nodes edges)
%   (let ((num-and-pred (pairlis nodes (mapcar #'list l))))
%     ;; (cdr (butlast)) pour ne pas imprimer les 1ers et derniers qui sont fixes.
%     (format t "~a " (car nodes))
%     (mapcar #'S (cdr (butlast nodes)) (cdr (butlast l)))
%     (format t "& ")
%     (mapcar #'Sbar (cdr (butlast nodes)) (cdr (butlast l)))
%     (format t "~a " (car (last nodes)))
%     (format t "& ${")
%     (print-arcs-if-not-nil
%      (mapcar (lambda (arc)
%                (and (cadr (assoc (car arc) num-and-pred))
%                     (not (cadr (assoc (cdr arc) num-and-pred)))
%                     arc))
%              edges))
%     (format t "}$ & ${")
%     (print-arcs-if-not-nil
%      (mapcar (lambda (arc)
%                (and (cadr (assoc (cdr arc) num-and-pred))
%                     (not (cadr (assoc (car arc) num-and-pred)))
%                     arc))
%              edges))
%     (format t "}$ \\\\~%")))

% (defun range (n)
%   (loop for i from 0 below n collect i))

% (defun print-s-t-cuts (nodes edges)
%   (loop
%      for i from 0 below (expt 2 (- (length nodes) 2))
%      do (print-line (append
%                      '(t) ;; Source : toujours t
%                      (mapcar (lambda (n)
%                                (/= 0 (logand i (expt 2 n))))
%                              (range (- (length nodes) 2)))
%                      '(nil)) ;; Target : toujours nil
%                     nodes
%                     edges)))

% (print-s-t-cuts
%  '(1 2 3 4 5 6)
% '((1 . 2)
%   (1 . 3)
%   (1 . 4)
%   (2 . 3)
%   (3 . 4)
%   (3 . 6)
%   (4 . 5)
%   (4 . 6)
%   (5 . 6)))

\begin{tabular}{|l|l|l|l|}
  \hline
  $S$ & $\overline{S}$ & Arcs avants & Arcs arrières \\
  \hline
  \hline
  1 \phantom{2} \phantom{3} \phantom{4} \phantom{5} &          2           3           4           5  6 & ${(1,2), (1,3), (1,4)}$               & ${}$             \\
  1          2  \phantom{3} \phantom{4} \phantom{5} & \phantom{2}          3           4           5  6 & ${(1,3), (1,4), (2,3)}$               & ${}$             \\
  1 \phantom{2}          3  \phantom{4} \phantom{5} &          2  \phantom{3}          4           5  6 & ${(1,2), (1,4), (3,4), (3,6)}$        & ${(2,3)}$        \\
  1          2           3  \phantom{4} \phantom{5} & \phantom{2} \phantom{3}          4           5  6 & ${(1,4), (3,4), (3,6)}$               & ${}$             \\
  1 \phantom{2} \phantom{3}          4  \phantom{5} &          2           3  \phantom{4}          5  6 & ${(1,2), (1,3), (4,5), (4,6)}$        & ${(3,4)}$        \\
  1          2  \phantom{3}          4  \phantom{5} & \phantom{2}          3  \phantom{4}          5  6 & ${(1,3), (2,3), (4,5), (4,6)}$        & ${(3,4)}$        \\
  1 \phantom{2}          3           4  \phantom{5} &          2  \phantom{3} \phantom{4}          5  6 & ${(1,2), (3,6), (4,5), (4,6)}$        & ${(2,3)}$        \\
  1          2           3           4  \phantom{5} & \phantom{2} \phantom{3} \phantom{4}          5  6 & ${(3,6), (4,5), (4,6)}$               & ${}$             \\
  1 \phantom{2} \phantom{3} \phantom{4}          5  &          2           3           4  \phantom{5} 6 & ${(1,2), (1,3), (1,4), (5,6)}$        & ${(4,5)}$        \\
  1          2  \phantom{3} \phantom{4}          5  & \phantom{2}          3           4  \phantom{5} 6 & ${(1,3), (1,4), (2,3), (5,6)}$        & ${(4,5)}$        \\
  1 \phantom{2}          3  \phantom{4}          5  &          2  \phantom{3}          4  \phantom{5} 6 & ${(1,2), (1,4), (3,4), (3,6), (5,6)}$ & ${(2,3), (4,5)}$ \\
  1          2           3  \phantom{4}          5  & \phantom{2} \phantom{3}          4  \phantom{5} 6 & ${(1,4), (3,4), (3,6), (5,6)}$        & ${(4,5)}$        \\
  1 \phantom{2} \phantom{3}          4           5  &          2           3  \phantom{4} \phantom{5} 6 & ${(1,2), (1,3), (4,6), (5,6)}$        & ${(3,4)}$        \\
  1          2  \phantom{3}          4           5  & \phantom{2}          3  \phantom{4} \phantom{5} 6 & ${(1,3), (2,3), (4,6), (5,6)}$        & ${(3,4)}$        \\
  1 \phantom{2}          3           4           5  &          2  \phantom{3} \phantom{4} \phantom{5} 6 & ${(1,2), (3,6), (4,6), (5,6)}$        & ${(2,3)}$        \\
  1          2           3           4           5  & \phantom{2} \phantom{3} \phantom{4} \phantom{5} 6 & ${(3,6), (4,6), (5,6)}$               & ${}$             \\
  \hline
\end{tabular}

\begin{enonce}
Vérifier que le nombre maximum de chemins d'arcs disjoints à partir du sommet source jusqu'au puits est égal au nombre minimum d'arcs avant dans une s-t-coupe.
\end{enonce}

D'après notre conclusion de la question 1, on  a uniquement trois chemins d'arcs disjoints et d'après le tableau de la question 2, on constate que le nombre minimum d'arcs avant est de 3. On peut donc vérifier que le nombre maximum d'arcs disjoints est égal au nombre minimum d'arcs avants. 

\subsection{Partie complexité}

\subsubsection*{Exercice \stepcounter{exocount}\bf\small \arabic{exocount} -- Sur quelques réductions}
\addcontentsline{toc}{subsubsection}{Exercice \arabic{exocount} -- Sur quelques réductions}
\setcounter{enoncecount}{0}

\begin{enonce}
On vous demande de rappeler la réduction de SAT à 3-SAT.
\end{enonce}

\begin{sousenonce}
Enoncer SAT et 3-SAT.
\end{sousenonce}

SAT est une abbrévation pour 'problème de satisfiabilité'. En logique propositionnelle, résoudre un problème SAT consiste à déterminer s'il existe une assignation des variables booléennes telle qu'une formule logique sous forme normale conjonctive s'évalue à vrai. Si tel est le cas, la formule est dite 'satisfiable', sinon elle est 'insatisfiable'. Etant donné le résultat booléen ('satisfiable' ou 'insatisfiable') de ce genre de problème, il s'agit bien d'un problème de décision.  

On appelle 2-sat un problème dont chaque clause de la formule logique en question contient au plus 2 littéraux, 3-sat un problème SAT dans lequel chaque clause de la formule logique en question contient au plus 3 littéraux. Un problème 2-sat est polynomial et NL-complet alors qu'un problème 3-sat est NP-complet.

Un exemple d'un problème 3-SAT est le suivant :

$(v_{1} \vee v_{2} \vee v_{3}) \wedge (v_{4} \vee v_{5} \vee v_{6}) \wedge (v_{7} \vee v_{8} \vee v_{9}) \wedge$ ...	

où chaque v est une variable ou la négation d'une variable, chaque variable pouvant figurer plusieurs fois dans l'expression. 

\begin{sousenonce}
Définir la réduction.
\end{sousenonce}

En théorie de complexité, une 'réduction' est la transformation d'un problème en un autre problème. Selon la transformation utilisée, la réduction peut être utilisée afin de définir une classe de complexité à un ensemble de problèmes. Problème A est réductible à Problème B si les solutions au Problème B existent et donnent des solutions au Problème A à chaque fois que A a des solutions. Par conséquent, la solution de A ne peut pas être plus difficile que la solution de B. 

Il peut être utile de résoudre un problème qui est similaire à un problème que l'on a déjà résolu. Dans ce cas, une méthode efficace de résoudre le nouveau problème est de transformer chaque instance du nouveau problème en une instance d'un problème que l'on sait résoudre et puis de résoudre chaque instance à l'aide de solutions existantes afin d'obtenir une solution finale. Une autre stratégie est de subdiviser un problème en plusieurs sous-problèmes que l'on sait résoudre, d'où le terme 'réduction'.

Une autre application des 'réductions' est son application aux problèmes qui sont difficiles à résoudre. Lorsque l'on a un problème qui a été prouvé difficile à résoudre et que nous avons un nouveau problème similaire, nous pouvons faire l'hypothèse que le nouveau problème, lui aussi, est difficile à résoudre. Le raisonnement est l'inverse de celui des problèmes qui peuvent être résolu aisément. 

Un exemple simple est de passer de la multiplication à la quadrature. Supposons que nous ne sommes capable que d'effectuer l'addition, la soustraction la quadrature et la division. Avec ces quatre opérations, nous pouvons trouver le produit de deux nombres quelconques :


$$(a \times b) = \dfrac{(a + b)^2 - a^2 - b^2}{2}$$


Lorsqu'il est possible de réduire un problème difficile en un problème que l'on sait résoudre, la difficulté demeure souvent dans la réduction elle-même.

Pour la réduction de SAT à 3-SAT, on prend chaque clause de littéraux du problème SAT et on la transforme en une ou plusieurs clauses de la manière suivante~:

\begin{itemize}
\item Si la clause possède 3 littéraux ou moins, on la laisse telle quelle. Elle est déjà sous forme 3-SAT.
\item Sinon, soient $l_1, \dots, l_n$ les littéraux de la clause, on construit plusieurs clauses ainsi~:
$$
(l_1, l_2, z_1), (\lnot z_1, l_3, z_2), (\lnot z_2, l_4, z_3), \dots, (\lnot z_{i-2}, l_{i}, z_{i-1}), \dots, (\lnot z_{n-3}, l_{n-1}, l_{n})
$$
\end{itemize}

Les littéraux $z_i$, qui n'était pas présents dans la clause d'origine, sont ajoutés afin de pouvoir subdiviser une clause en deux ou
plusieurs clauses et afin de les relier. Par exemple, la clause $(a \vee \lnot b \vee c \vee d)$ sera transformée en deux clauses~: $(a
\vee \lnot b \vee z_1) \wedge (\lnot z_1 \vee c \vee d)$ ; la clause ${\lnot a \vee b \vee \lnot c \vee d \vee e}$ sera transformée en trois
clauses, à savoir $(\lnot a \vee b \vee z_1) \wedge (\lnot z_1 \vee \lnot c \vee z_2) \wedge (\lnot z_2 \vee d \vee e)$.

L'ensemble des clauses ainsi créées sont équivalentes à l'ensemble des clauses d'origines correspondant car, à chaque fois, soit un des littéraux d'origine vérifie la clause et $z_i$ peut être faux, ce qui permet à $\lnot z_i$ de valider la clause suivante, de proche en proche, soit aucun des littéraux d'origine ne vérifie la clause, auquel cas, si on prend un $z_i$ faux, la clause est fausse, et si on prend un $z_i$ vrai, la clause suivante 
contiendra $\lnot z_i$ qui sera faux, et le résultat dépendra des littéraux de la ou des clause(s) suivante(s).

Si l'on souhaite que le résultat soit strictement 3-SAT (toutes les clauses contenant exactement 3 littéraux, on applique les transformations suivantes~:
\begin{itemize}
\item Les clauses qui contiennent un seul littéral, ${l_1}$, sont transformées en ${l_1, l_1, l_1}$.
\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.

\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ésider 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.
\end{sousenonce}

Le système obtenu par la réduction contient :
\begin{itemize}
\item Une variable supplémentaire pour chaque clause à 4 littéraux.
\item Deux variables supplémentaires pour chaque clause à 5 littéraux.
\item Soit au total $n_v + n_4 + 2n_5$ variables.
\end{itemize}

De plus, les expansions sont les suivantes :
\begin{itemize}
\item Un littéral : 1 clause
\item Deux littéraux : 1 clause
\item Trois littéraux : 1 clause
\item Quatre littéraux : 2 clauses
\item Cinq littéraux : 3 clause
\item Soit au total $n_1 + n_2 + n_3 + 2n_4 + 3n_5$ clauses.
\end{itemize}



\begin{enonce}
Pourquoi le principe de la réduction ne permet-il pas de réduire 3-SAT à 2-SAT et de prouver que 2-SAT est NP-complet ? (Il ne s'agit pas
d'expliquer pourquoi 2-SAT n'est pas NP-complet, mais pourquoi cette réduction ne marche pas).
\end{enonce}

Tentons de réduire la clause $(a \vee b \vee c)$ de manière similaire à l'algorithme donné pour la réduction de SAT à 3-SAT~. 

On a $(a \vee z_1) \wedge (\lnot z_1 \vee b)$. A partir de là, on ne peut insérer de variable permettant de faire la liaison entre la clause
qui contient $b$ et celle qui contient $c$, donc on ne peut pas appliquer cette réduction.

\begin{enonce}
Il s'agit de prouver que 2-SAT est un problème polynomial. Vous avez un article en français expliquant cette preuve à \\ http://philippe.gambette.free.fr/SCOL/Graphes
\end{enonce}
\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.
\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.

\begin{enumerate}
\item L'algorithme de construction de graphe : 
\begin{enumerate}
\item On crée un graphe avec $2n$ sommets ($n$ étant ici le nombre littéraux distincts de la formule) contenant tous les littéraux de la
  formule ainsi que les négations de ces littéraux.
\item On prend chaque clause de la formule que l'on traduit en implications dans les deux sens : $(a \vee b)$ 
se transforme en deux clauses : $(\neg a \Rightarrow b)$ et ($\neg b \Rightarrow a)$.
\item On crée des arcs correspondant aux implications créées à l'étape précédente (arc ($\neg a 
\rightarrow b$) et ($\neg b \rightarrow a$))
\end{enumerate}
\item On effectue un tri topologique en numérotant les sommets de $1$ à $n$.
\item En ordre inverse, du sommet $n$ au sommet $1$ du graphe, on affecte à tout noeud $x$ la valeur VRAI et au noeud $\neg x$ la valeur
  FAUX, c'est-à-dire dans l'ordre inverse du tri topologique.
\end{enumerate}  	

S'il existe une composante fortement connexe contenant un littéral et sa négation, la formule est insatisfiable étant donné qu'on a $x_{i}
\Leftrightarrow \neg x_{i}$ sinon, la formule est satisfiable, c'est-à-dire soit contingente soit valide. L'algorithme ne nous donne aucune
information pour distinguer une formule contingente et une formule valide, il nous donne une ou deux informations : (1) il nous dit si la
formule admet un modèle, et (2) si oui, il nous donne un modèle~: le modèle est assuré car le graphe en question ne contient aucun arc $VRAI
\rightarrow FAUX$.

Prenons trois exemples~: une formule insatisfiable, une formule contingente et une formule valide.

\begin{figure}[ht!]
  \centering
  \begin{tikzpicture}[
      node distance=2.5cm,
      lettre/.style={
        draw,
        circle,
        minimum size=1cm
      }
    ]
    \node[lettre] (nx1) {$\lnot x_1$} ;
    \node[lettre, below of=nx1] (x1) {$x_1$} ;
    \node[coordinate,xshift=0.1cm] (x1r) at (x1.north) {};
    \node[coordinate,xshift=-0.1cm] (x1l) at (x1.north) {};
    \node[coordinate,xshift=0.1cm] (nx1r) at (nx1.south) {};
    \node[coordinate,xshift=-0.1cm] (nx1l) at (nx1.south) {};
    \draw[->] (x1r) -- (nx1r);
    \draw[->] (nx1l) -- (x1l);

  \end{tikzpicture}
  \caption{Clause insatisfiable : $(x_{1} \vee x_{1}) \wedge (\neg x_{1} \vee \neg x_{1})$}
  \label{fig:clause-insat}
\end{figure}

\paragraph*{Clause insatisfiable $(x_{1} \vee x_{1}) \wedge (\neg x_{1} \vee \neg x_{1})$~:}

Le résultat de l'application de l'algorithme décrit ci-dessus est un graphe orienté cyclique. Il est impossible d'effectuer un tri
topologique étant donné qu'un tri topologique ne peut être effectué que sur un graphe acyclique orienté. Ce graphe contient un composant
fortement connexe contenant un littéral et sa négation, et la formule associée est, par conséquent, insatisfiable. Il est impossible
d'attribuer un ordre aux sommets pour ensuite affecter des valeurs aux littéraux correspondant aux sommets car la formule admet aucun
modèle. Pour cette raison, les arcs de ce graphe n'ont pas été numérotés ni affectés des valeurs $VRAI$ ou $FAUX$. En somme, l'algorithme
nous dit simplement que ce graphe n'admet aucun modèle.

\begin{figure}[ht!]
  \centering
  \begin{tikzpicture}[
      start chain=circle placed {at=(\tikzchaincount*-45+22.5+90:2.5)},
      lettre/.style={
        on chain,
        draw,
        circle,
        minimum size=1cm
      },
      chiffre/.style={
        node distance = 0.75cm
      },
      arr/.style={
        ->,
        >=triangle 90
      }
    ]
    \node[lettre] (1) {$\lnot x1$} ;
    \node[lettre] (5) {$x2$} ;
    \node[lettre] (3) {$\lnot x2$} ;
    \node[lettre] (6) {$x3$} ;
    \node[lettre] (4) {$\lnot x3$} ;
    \node[lettre] (7) {$x4$} ;
    \node[lettre] (2) {$\lnot x4$} ;
    \node[lettre] (8) {$x1$} ;
    
    \node[right of=1] {\textcolor{red}{faux}} ;
    \node[right of=5] {\textcolor{green!75!black}{vrai}} ;
    \node[right of=3] {\textcolor{red}{faux}} ;
    \node[right of=6] {\textcolor{green!75!black}{vrai}} ;
    \node[left  of=4] {\textcolor{red}{faux}} ;
    \node[left  of=7] {\textcolor{green!75!black}{vrai}} ;
    \node[left  of=2] {\textcolor{red}{faux}} ;
    \node[left  of=8] {\textcolor{green!75!black}{vrai}} ;
    
    \node[chiffre, above right of=1] {1} ;
    \node[chiffre, above right of=5] {5} ;
    \node[chiffre, below right of=3] {3} ;
    \node[chiffre, below right of=6] {6} ;
    \node[chiffre, below left of=4]  {4} ;
    \node[chiffre, below left of=7]  {7} ;
    \node[chiffre, above left of=2]  {2} ;
    \node[chiffre, above left of=8]  {8} ;

    \draw[arr] (1) -- (5) ;
    \draw[arr] (3) -- (8) ;
    \draw[arr] (2) -- (6) ;
    \draw[arr] (4) -- (7) ;
  \end{tikzpicture}
  \caption{Clause contingente : $(x_{1} \vee x_{2}) \wedge (x_{3} \vee x_{4})$}
  \label{fig:clause-conting}
\end{figure}

% \includegraphics[height=2in, width = 3in]{img/contingente.png

\paragraph*{Clause contingente $(x_{1} \vee x_{2}) \wedge (x_{3} \vee x_{4})$~:}
Le graphe de la figure \ref{fig:clause-conting} ne contient aucune composante fortement connexe contenant un littéral et sa négation, donc
la formule associée admet bien un modèle. Ce modèle est le résultat du tri topologique effectué et les valeurs $VRAI$ et $FAUX$ affectées à
des sommets par notre algorithme. Il existe aucun arc qui part d'un sommet étiqueté $VRAI$ vers un sommet étiqueté $FAUX$ et, en effet, les
valeurs attribuées aux arcs donnent bien un modèle.



\begin{figure}[ht!]
  \centering
  \begin{tikzpicture}[
      start chain=circle placed {at=(\tikzchaincount*-90+180:1.6)},
      lettre/.style={
        on chain,
        draw,
        circle,
        minimum size=1cm
      },
      chiffre/.style={
        node distance = 0.75cm
      },
      arr/.style={
        ->,
        >=triangle 90
      }
    ]
    \node[lettre] (1) {$\lnot x1$} ;
    \node[lettre] (2) {$x1$}  ;
    \node[lettre] (3) {$\lnot x2$} ;
    \node[lettre] (4) {$x2$}  ;
    
    \node[right of=1] {\textcolor{green!75!black}{vrai}} ;
    \node[right of=2] {\textcolor{red}{faux}} ;
    \node[right of=3] {\textcolor{green!75!black}{vrai}} ;
    \node[left  of=4] {\textcolor{red}{faux}} ;
    
    \node[chiffre, above right of=1] {1} ;
    \node[chiffre, below right of=2] {2} ;
    \node[chiffre, below right of=3]  {3} ;
    \node[chiffre, below left of=4]  {4} ;

	\path
       (1) edge[loop above] (1)
       (2) edge[loop above]  (2)
       (3) edge[loop below] (3)
       (4) edge[loop above] (4) ;
  \end{tikzpicture}
  \caption{Clause valide :  $(x_{1} \vee \neg x_{1}) \wedge (x_{2} \vee \neg x_{2})$}
  \label{fig:clause-valide}
\end{figure}

% \includegraphics[height=2in, width = 3in]{img/valide.png}

\paragraph*{Clause valide $(x_{1} \vee \neg x_{1}) \wedge (x_{2} \vee \neg x_{2})$~:}
L'application de l'algorithme de transformation en graphe d'une formule valide nous donne un graphe ne contenant que des boucles à chaque
sommet. Nous pouvons donc numéroter les arcs de n'importe quel façon. Ce étant, nous pouvous aussi affecter n'importe quelles valeurs aux
sommets (hormis la même valeur à un littéral et sa négation, bien entendu) et la formule sera toujours vraie.

L'objectif de cet algorithme n'est pas de dire si une formule satisfiable est contingente ou valide. Toutefois, si le résultat de
l'algorithme est un graphe ne comportant que des boucles à chaque sommet, la formule associée est satisfiable et valide. Autrement, et si le
graphe ne contient aucune composante fortement connexe contenant un littéral et sa négation, la formule est contingente.


\begin{sousenonce}
Vous expliciterez ensuite l'algorithme de transformation et vous évaluerez sa complexité.
\end{sousenonce}

L'algorithme de transformation est expliqué plus haut, sous le nom \og L'algorithme de construction de graphe\fg{}

On pose~:

c = nb clauses \\
l = nb littéraux

En triant la liste des sommets du graphe (coût $n \log n$ pour le tri), on peut effectuer les opérations de recherche d'un littéral (ou de sa négation) par dichotomie (coût $\log n$), donc les $c \times l$ et $O(l \times l)$ (1.a, 1.c, 3.) ci-dessous deviennent respectivement $O(c \log l)$ et $O(l \log l)$


\begin{itemize}
\item 1.a : $O(c \times l)$ car pour chaque littéral qu'on insère, il faut chercher s'il existe déjà.
\item 1.b : $O(c)$ une opération pour chaque clause
\item 1.c : $O(c \times l)$ pour chaque clause, on cherche ses 2 littéraux et leur négation dans le graphe
\item 2. : $O(card(V) + card(E))$, comme $card(V) = 2l$ et $card(E) <= 2c$ (inférieur ou égal à cause des doublons potentiels qui n'ajoutent rien au graphe)., on a $O(l+c)$
\item 3. : $O(l \times l)$ car pour chaque littéral qu'on rencontre on devra chercher sa négation dans tout le graphe.
\end{itemize}

Comme $l <= 2c$, tous les l ci-dessus peuvent être transformés en c.

Donc, on prend le coût le plus élevé~:
$$
O(c^2 + c + c^2 + 2c + c^2) = O(c^2)
$$

On a donc bien un coût polynomial.

De plus, si on trie le graphe, on a (le premier $c \log c$ est la création du graphe en maintenant sa liste de sommets triés (tri par insertion)):
$$
O(c \log c + c + c \log c + 2c + c \log c) = O(c \log c)
$$


\begin{sousenonce}
Vous expliciterez ensuite l'algorithme d'exploration du graphe et vous évaluerez sa complexité
en fonction de la taille de l'ensemble de clauses initial.
\end{sousenonce}

L'algorithme a déjà été expliqué plus haut à la question 3(a).

Pour la partie «trouver un modèle» de l'algorithme, le tri topologique se fait en $O(V + E)$ en faisant un parcours en profondeur. Ensuite, on parcourt chaque littéral auquel on n'a pas encore affecté de valeur~; on lui affecte VRAI et on affecte FAUX à sa négation. Cela coûte
$O(V^2)$ car pour chaque littéral, il faudra chercher sa négation dans $V$ et le coût total est donc $O(V + E + V^2) = O(V^2 + E)$.

On peut toutefois trier les noeuds de $V$ et faire une recherche par dichotomie, ce qui coûte alors $O(V \log V)$ pour le tri et la
recherche coûte alors $O(\log V)$, soit $O(V \log V)$ pour toute la phase d'affectation des valeurs. Le coût total de cette partie est donc
$O(V + E + V \log V + V \log V)$, soit $O(E + V \log V)$.

Pour la partie «déterminer si la formule est invalide», il faut parcourir le graphe pour voir si une composante fortement connexe contient
un littéral et sa négation. On fera encore un parcours en profondeur $O(V + E)$ et pour chaque noeud (littéral) rencontré lors du parcours,
il faudra voir si on a déjà rencontré la négation de ce littéral dans la même composante, ce qui coûte $O(\text{taille composante})$. Dans
le pire des cas, la composante fortement connexe fait tout le graphe et le coût de la recherche sera alors $O(V)$. Comme cette recherche
est effectuée pour chaque noeud, le coût total sera $O(V+E)$ pour le parcours en profondeur et $O(V^2)$ pour l'ensemble des recherches,
soit $O(V+E+V^2) = O(V^2+E)$ au total.

On peut améliorer le coût de la recherche en maintenant une structure de données permettant un accès rapide aux littéraux déjà rencontrés, par exemple, un arbre binaire de recherche balancé (AVL). Le coût de la recherche descend alors à $O(\log V)$ dans le pire des cas, pour un coût total de $O(E + V \log V)$.

L'algorithme d'exploration du graphe (y compris la partie qui trouve un modèle) coûte donc $O(E + V^2)$ sans les tris supplémentaires et $O(E + V \log V)$ avec.

\begin{sousenonce}
Enfin, vous justifierez l'équivalence de la réponse au problème 2-SAT et au problème qui est posé dans le graphe.
\end{sousenonce}

Un problème 2-SAT est une conjonction de disjonctions de deux littéraux (ou de leur négation). Pour que la formule soit satisfiable, il faut
qu'il existe une affectation des littéraux telle que chaque clause soit vraie (car les clauses sont reliées par des $\wedge$ et il suffit
donc qu'une seule d'entre elles soit fausse pour que toute la formule devienne fausse).

Pour qu'une clause soit valide, il faut qu'au moins un de ses deux membres soit vrai. Cela signifie que si le premier membre est forcément
faux, alors le deuxième doit être vrai pour que la formule entière soit vraie.

On peut donc ré-écrire la formule
$$(a_1 \vee a_2) \wedge (a_3 \vee a_4) \wedge \dots \wedge (a_{n-1} \vee a_n)$$
(les $a_i$ étant des littéraux ou leur négation) de la manière suivante :
$$(\lnot a_1 \rightarrow a_2) \wedge (\lnot a_3 \rightarrow a_4) \wedge \dots \wedge (\lnot a_{n-1} \rightarrow a_n)$$

Le graphe que l'on constuit explicite ces implications en faisant un arc entre le littéral à gauche et le littéral à droite.

Pour chercher une contradiction dans la formule, qui la rend insatisfiable, il faut trouver un ensemble d'implications présentes dans la
formules telles que~:
$$
\begin{array}{rrcl}
       & (a_{i1} & \Rightarrow & a_{i2}) \\
  \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
est bien évidemment insatisfiable.

Cet ensemble d'implication se traduit dans le graphe par un chemin de $a_{i1}$ jusqu'à $\lnot a_{i1}$, et un chemin de $\lnot a_{i1}$
jusqu'à $\lnot a_{i1}$, autrement dit, $a_{i1}$ et $\lnot a_{i1}$ sont dans la même composante connexe.

L'algorithme utilise cette même transformation en implications pour déterminer un modèle~: le graphe étant trié topologiquement, on part du
terme «le plus à droite» d'une chaîne d'implications et on lui affecte vrai si c'est un littéral sans négation en affectant faux à sa
négation et vice versa si c'est un littéral avec négation. Lorsque l'on remonte ainsi de droite à gauche, on s'assure qu'il n'y aura jamais un
$\text{VRAI} \Rightarrow \text{FAUX}$ (puisqu'on vient de la droite et qu'on n'affecte que des valeurs qui rendent le membre vrai), à moins
qu'il y ait une boucle (qui aurait été détectée à l'étape précédente). Cette combinaison de valeurs nous donne donc un modèle.

\subsection{Partie Calculabilité}

\subsubsection*{Exercice \stepcounter{exocount}\bf\small \arabic{exocount} -- Sur le problème de codage}
\addcontentsline{toc}{subsubsection}{Exercice \arabic{exocount} -- Sur le problème de codage}
\setcounter{enoncecount}{0}

\begin{enonce}
Comment énumérer les couples d'entiers ?
\end{enonce}


L'énumération des couples de manière relativement homogène nous donnerait un codage qui nous permettrait d'identifier chaque couple par un nombre unique. 

Il ne serait pas du tout utile de commencer par tous les couples $(0,y_{i})$  tel que $i \in \mathbb{Z}$ car il s'agirait, là, d'un ensemble infini de couples et on ne passerait jamais aux couples $(1, y_{i})$. 

Une solution, pour tous les nombres naturels, serait de parcourir un graphe comme suit:

\begin{figure}[ht!]
  %% «Paramètres»
  \xdef\maxdots{23}
  \xdef\maxdotsX{5}
  \xdef\maxdotsY{5}
  \xdef\maxnums{20}
  \xdef\maxcoordsX{3}
  \xdef\maxcoordsY{3}
  
  %% ===== Code is below =====
  
  %% Macros crades
  \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
  \centering
  \begin{tikzpicture}[
    scale=1.4,
    dot/.style={
      circle,
      inner sep=0.7pt,
      fill=black
    },
    dotphantom/.style={
      circle,
      inner sep=3pt,
      fill=none,
      draw=none
    },
    numero/.style={rectangle, fill=white, inner sep=2pt, text=red!50!black},
    coord/.style={darkgray, scale=.8},
    %
    bigarrow/.style={
      ->,
      thick,
      draw=green!50!black
    },
    constatation1/.style={
      circle,
      inner sep=1.5pt,
      outer sep=0.8pt,
      fill=white,
      text=red,
      anchor=south,
      rotate around={45:(0,0)}
    },
    constatation2/.style={
      text=green!50!black,
      node distance=0.6cm
    }
    ]
    
    % %% Digonale
    % \draw[bigarrow,red] (0,0) -- (.5*7.5,-.5*7.5);
    
    % Définitions pour le code ci-dessous.
    \xdef\i{0}
    \xdef\x{0}
    \xdef\y{0}
    \xdef\corner{3}
    \xdef\sidelen{0}
    \xdef\nextsidelen{1}
    \xdef\direction{3}
    \incr\maxnums
    \incr\maxcoordsX
    \incr\maxcoordsY
    
    \foreach \x in {0,...,\maxcoordsX} {
      \foreach \y in {1,...,\maxcoordsY} {
        \expandafter\xdef\csname dotxypresent-\x-\y\endcsname{0}
      }
    }
    
    \def\reallysmallcheat#1{%
      \ensuremath{\hphantom{\vphantom{X}}_{\hphantom{\vphantom{X}}_{#1}}}
    }
    \def\drawnode{%
      \node[dot] (dot-\x-\y) at (\x,-\y) {};
      \node[dotphantom] (phantom-\x-\y) at (\x,-\y) {};
      \ifnum\maxnums>\i
        % \ifnum\corner=0    \node[numero,anchor=south]      at (dot-\x-\y.north)      {\i}; \else
        % \ifnum\corner=1    \node[numero,anchor=east]       at (dot-\x-\y.west)       {\i}; \else
        % \ifnum\corner=2    \node[numero,anchor=east]       at (dot-\x-\y.west)       {\i}; \else
        % \ifnum\corner=3    \node[numero,anchor=south]      at (dot-\x-\y.north)      {\i}; \else
        % \ifnum\direction=0 \node[numero,anchor=north west] at (dot-\x-\y.south east) {\i}; \else
        % \ifnum\direction=2 \node[numero,anchor=north west] at (dot-\x-\y.south east) {\i}; \fi\fi\fi\fi\fi\fi
        \node[numero,anchor=north west] at (dot-\x-\y.south east) {\i};
      \fi
      \ifnum\maxcoordsX>\x
      \ifnum\maxcoordsY>\y
        % \ifnum\corner=0    \node[coord,anchor=south east] at (dot-\x-\y.north west) {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\corner=1    \node[coord,anchor=north east] at (dot-\x-\y.south west) {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\corner=2    \node[coord,anchor=north west] at (dot-\x-\y.south east) {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\corner=3    \node[coord,anchor=south west] at (dot-\x-\y.north east) {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\direction=0 \node[coord,anchor=east]       at (dot-\x-\y.west)       {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\direction=1 \node[coord,anchor=north]      at (dot-\x-\y.south)      {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\direction=2 \node[coord,anchor=west]       at (dot-\x-\y.east)       {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\direction=3 \node[coord,anchor=south]      at (dot-\x-\y.north)      {\reallysmallcheat{(\x, \y)}}; \fi\fi\fi\fi\fi\fi\fi\fi
        \expandafter\xdef\csname dotxypresent-\x-\y\endcsname{1}
        \ifnum\y=0
          \node[coord,anchor=south west] at (dot-\x-\y.north east) {\reallysmallcheat{(\x, \y)}};
        \else
          \node[coord,anchor=west,xshift=0.2] at (dot-\x-\y.east) {\reallysmallcheat{(\x, \y)}};
        \fi
      \fi
      \fi
    }
    \def\drawlinknode{%
      \drawnode%
      \draw[->] (phantom-\oldx-\oldy) -- (phantom-\x-\y);%
    }
    \def\mystep{%
      \incr\i%
      \xdef\oldx{\x}%
      \xdef\oldy{\y}%
    }
    \def\changedir#1{%
      \xdef\direction{#1}%
      \xdef\corner{#1}%
    }
    
    \drawnode
    \mystep \incr\x
    \xdef\cornerc{0}

    \foreach \pos in {1,...,\maxdots} {
      % Detect when we are at the end of this edge.
      \ifnum\sidelen=0
        \ifnum\direction=0 \changedir{1} \incr\nextsidelen \xdef\sidelen{1}            \else
        \ifnum\direction=1 \changedir{2}                   \xdef\sidelen{\nextsidelen} \else
        \ifnum\direction=2 \changedir{3} \incr\nextsidelen \xdef\sidelen{1}            \else
        \ifnum\direction=3 \changedir{0}                   \xdef\sidelen{\nextsidelen} \fi\fi\fi\fi% Brin d'acier
        
      \fi
      % Draw node and link to previous, step counters
      \drawlinknode \mystep
      %% Se déplacer vers ↙↓↗→
      \ifnum\direction=0 \incr\y \decr\x \fi
      \ifnum\direction=1 \incr\y         \fi
      \ifnum\direction=2 \decr\y \incr\x \fi
      \ifnum\direction=3         \incr\x \fi
      \decr\sidelen
      \xdef\corner{4}%% 4 == pas de coin-coin.
    }
    
    \foreach \x in {0,...,\maxdotsX} {
      \foreach \y in {1,...,\maxdotsY} {
        \node[dot] (dot-\x-\y) at (\x,-\y) {};
      }
    }
    \decr\maxcoordsX
    \decr\maxcoordsY
    \foreach \x in {0,...,\maxcoordsX} {
      \foreach \y in {0,...,\maxcoordsY} {
        \node[dot,fill=none] (fakedot-\x-\y) at (\x,-\y) {};
        \expandafter\ifnum\csname dotxypresent-\x-\y\endcsname=0
          \ifnum\y=0
            \node[coord,anchor=south west] at (fakedot-\x-\y.north east) {\reallysmallcheat{(\x, \y)}};
          \else
            \node[coord,anchor=west,xshift=0.2] at (fakedot-\x-\y.east) {\reallysmallcheat{(\x, \y)}};
          \fi
        \fi
      }
    }
    
    % \foreach \i in {1, ...,6}{
    %   \node[constatation1] at (.5*\i,-.5*\i) {\i};
    % }
    % \node[constatation1] at (.5*7,-.5*7) {\vdots};
    
    % \node[coordinate] (fake0-0) at (0,0) {};
    % \node[coordinate] (fake1-0) at (1,0) {};
    % \node[coordinate] (fake3-0) at (3,0) {};
    % \node[coordinate] (fake5-0) at (5,0) {};
    % \node[coordinate] (fake0-2) at (0,-2) {};
    % \node[coordinate] (fake0-4) at (0,-4) {};
    % \node[coordinate] (fake0-6) at (0,-6) {};
    % \node[constatation2, above left of=fake0-0] {0};
    % \node[constatation2, above of=fake1-0]  {1};
    % \node[constatation2, above of=fake3-0]  {6};
    % \node[constatation2, above of=fake5-0] {15};
    % \node[constatation2, left of=fake0-2] {3};
    % \node[constatation2, left of=fake0-4] {10};
    % \node[constatation2, left of=fake0-6] {21};
  \end{tikzpicture}
  \caption{Codage d'un couple d'entiers relatifs}%% TODO : caption
  \label{fig:codage-zigzag}
\end{figure}

%% TODO: Il faudrait ajouter les coordonnées (0,0), (1,0), (0,1), et les codes correspondants au graphe ci-dessus, etc. VOIR LES DIAGRAMMES QUE J'AI DONNE A BERTRAND
%% TODO : Réponse georges : c'est fait.

Dans la figure \ref{fig:codage-zigzag}, on commence par le couple $(0,0)$, puis on procède aux couples $(1,0)$, $(0,1)$, $(0,2)$, $(1,1)$, $(2,0)$, $(3,0)$, $(2,1)$, $(1,2)$, $(0,3)$, $(0,4)$\ldots L'algorithme pour simplement parcourir les couples de cette façon consisterait tout d'abord de déclarer et d'intialiser trois variables globales~: le point de départ, \lstinline!*current*!, et les valeurs maximales courantes de $x$ et de $y$, c'est-à-dire \lstinline!*max-x*! et \lstinline!*max-y*!. En LISP, ceci pourrait être codé comme suit~:

\begin{lstlisting}[language=Lisp]
(defvar *current* (list 0 0 0)) ;; liste courante (code x y)
(setf *current* (list 0 0 0)) 
(defvar *max-x* 0) ;; valeur maximal courante de x
(setf *max-x* 0)
(defvar *max-y* 0) ;; valeur maximal courante de y
(setf *max-y* 0)
\end{lstlisting}

On pourrait stocker toutes les valeurs de \lstinline!*current*! dans un tableau \lstinline!*db*! (base de données) comme suit~:

\begin{lstlisting}[language=Lisp]
(defvar *db* nil) 
(setf *db* nil)
(push *current* *db*)
\end{lstlisting}

Puis, les conditions pour déterminer la direction à prendre afin de parcourir le graphe pourrait être implémentées comme suit (toujours en LISP)~:

\begin{lstlisting}[language=Lisp]
(defun move (L)
  (cond
    ((and (zerop (third L)) (= *max-x* *max-y*)) 
		;; RIGHT takes precedence over LEFT becuase it occurs first
      (print "in RIGHT") ;; 
         (right L))
    ((and (zerop (second L)) (= *max-x* *max-y*)) ;; DOWN
      (print "in DOWN") 
         (down L))
    ((> *max-x* *max-y*) ;; DOWN-LEFT
      (print "in DOWN-LEFT")  
         (down-left L))
    ((< *max-x* *max-y*) ;; UP-RIGHT
      (print "in UP-RIGHT") 
         (up-right L))))
\end{lstlisting}
 
La liste \lstinline!*current*! est passée en paramètre lorsque l'on appelle ces fonctions~: L correspond toujours à *current*. Les fonctions 'right', 'down', 'down-left' et 'up-right', qui correspondent au parcours dans la figure \ref{fig:codage-zigzag}, incrémente la première valeur de L (le codage), qui est une liste de la forme \lstinline!(code x y)!. Par ailleurs, la fonction 'right' incrémente la valeur courante de $x$ (le deuxième élément de la liste), la fonction 'down' incrémente la valeur courante de $y$ (la troisième élément de la liste), la fonction 'down-left' décrémente la valeur de $x$ et incrémente la valeur $y$ et la fonction 'up-right', elle, fait le contraire, elle incrémente la valeur de $x$ et décrémente la valeur de $y$. 

On peut parcourir le graphe à l'aide de la fonction 'zig-zag' qui, elle, se sert de la fonction move-and-update afin de mettre à jour les variables globales *max-x* et *max-y*. 'move-and-update' se sert de 'move' qui choisit la bonne direction à prendre pour parcourir le graphe, c'est-à-dire 'right', 'down', 'down-left' ou 'up-right'~:

\begin{lstlisting}[language=Lisp]
(defun move-and-update (L)
  (progn
    (setf L (move L))
    (update-max-x-y L)
    *db*))
 
(defun zig-zag (L n)
    (if (zerop n) 
      (move-and-update *current*)
      (progn
        (move-and-update *current*)
        (zig-zag L (- n 1)))))
\end{lstlisting}


%% TODO : JOHN :
%% Pour définir un label pour une section / sous-section / …, il faut mettre ceci juste après le \section{…}
%% \label{foobar}
%%
%% Pour avoir le numéro de page correspondant :
%% \pageref{foobar}
%%
%% Pour le numéro de section / sous-section / … :
%% \ref{foobar}
%%
%% Tu changes foobar par un nom de ton choix.

%% TODO TODO TODO !!!!!!!!
L'intégralité du programme est en annexe à la page \pageref{coupleslisp}.

Voici une trace de cette fonction en passant \lstinline!*current*! égal à \lstinline!(0 0 0)! et $n = 100$ en paramètres~:

\begin{lstlisting}[language=Lisp]
> (zig-zag *current* 100)
"in RIGHT" 
"in DOWN-LEFT" 
"in DOWN" 
"in UP-RIGHT" 
"in UP-RIGHT" 
"in RIGHT" 
(etc.)
"in DOWN-LEFT" 
"in DOWN-LEFT" 
((101 3 10) (100 4 9) (99 5 8) (98 6 7) (97 7 6) (96 8 5) 
(95 9 4) (94 10 3) (93 11 2) (92 12 1) (91 13 0) (90 12 0) 
(89 11 1) (88 10 2) (87 9 3) (86 8 4) (85 7 5) (84 6 6) 
(83 5 7) (82 4 8) (81 3 9) (80 2 10) (79 1 11) (78 0 12) 
(77 0 11) (76 1 10) (75 2 9) (74 3 8) (73 4 7) (72 5 6) 
(71 6 5) (70 7 4) (69 8 3) (68 9 2) (67 10 1) (66 11 0) 
(65 10 0) (64 9 1) (63 8 2) (62 7 3) (61 6 4) (60 5 5) 
(59 4 6) (58 3 7) (57 2 8) (56 1 9) (55 0 10) (54 0 9) 
(53 1 8) (52 2 7) (51 3 6) (50 4 5) (49 5 4) (48 6 3) 
(47 7 2) (46 8 1) (45 9 0) (44 8 0) (43 7 1) (42 6 2) 
(41 5 3) (40 4 4) (39 3 5) (38 2 6) (37 1 7) (36 0 8) 
(35 0 7) (34 1 6) (33 2 5) (32 3 4) (31 4 3) (30 5 2) 
(29 6 1) (28 7 0) (27 6 0) (26 5 1) (25 4 2) (24 3 3) 
(23 2 4) (22 1 5) (21 0 6) (20 0 5) (19 1 4) (18 2 3) 
(17 3 2) (16 4 1) (15 5 0) (14 4 0) (13 3 1) (12 2 2) 
(11 1 3) (10 0 4) (9 0 3) (8 1 2) (7 2 1) (6 3 0) (5 2 0) 
(4 1 1) (3 0 2) (2 0 1) (1 1 0) (0 0 0))
\end{lstlisting}


\begin{enonce}
Donner les fonctions de codage et de décodage $f_1(z)\rightarrow x$ et $f_2(z)\rightarrow y$.
\end{enonce}

\begin{figure}[ht!]
  %% «Paramètres»
  \xdef\maxdots{23}
  \xdef\maxdotsX{5}
  \xdef\maxdotsY{5}
  \xdef\maxnums{20}
  \xdef\maxcoordsX{3}
  \xdef\maxcoordsY{3}
  
  %% ===== Code is below =====
  
  %% Macros crades
  \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
  \centering
  \begin{tikzpicture}[
    scale=1.4,
    dot/.style={
      circle,
      inner sep=0.7pt,
      fill=black
    },
    dotphantom/.style={
      circle,
      inner sep=3pt,
      fill=none,
      draw=none
    },
    numero/.style={rectangle, fill=white, inner sep=2pt, text=red!50!black},
    coord/.style={darkgray, scale=.8},
    %
    bigarrow/.style={
      ->,
      thick,
      draw=green!50!black
    },
    constatation1/.style={
      circle,
      inner sep=1.5pt,
      outer sep=0.8pt,
      fill=white,
      text=red,
      anchor=south,
      rotate around={45:(0,0)}
    },
    constatation2/.style={
      text=green!50!black,
      node distance=0.6cm
    }
    ]
    
    %% Digonale
    \draw[bigarrow,red] (0,0) -- (.5*7.5,-.5*7.5);
    
    % Définitions pour le code ci-dessous.
    \xdef\i{0}
    \xdef\x{0}
    \xdef\y{0}
    \xdef\corner{3}
    \xdef\sidelen{0}
    \xdef\nextsidelen{1}
    \xdef\direction{3}
    \incr\maxnums
    \incr\maxcoordsX
    \incr\maxcoordsY
    
    \foreach \x in {0,...,\maxcoordsX} {
      \foreach \y in {1,...,\maxcoordsY} {
        \expandafter\xdef\csname dotxypresent-\x-\y\endcsname{0}
      }
    }
    
    \def\reallysmallcheat#1{%
      \ensuremath{\hphantom{\vphantom{X}}_{\hphantom{\vphantom{X}}_{#1}}}
    }
    \def\drawnode{%
      \node[dot] (dot-\x-\y) at (\x,-\y) {};
      \node[dotphantom] (phantom-\x-\y) at (\x,-\y) {};
      \ifnum\maxnums>\i
        % \ifnum\corner=0    \node[numero,anchor=south]      at (dot-\x-\y.north)      {\i}; \else
        % \ifnum\corner=1    \node[numero,anchor=east]       at (dot-\x-\y.west)       {\i}; \else
        % \ifnum\corner=2    \node[numero,anchor=east]       at (dot-\x-\y.west)       {\i}; \else
        % \ifnum\corner=3    \node[numero,anchor=south]      at (dot-\x-\y.north)      {\i}; \else
        % \ifnum\direction=0 \node[numero,anchor=north west] at (dot-\x-\y.south east) {\i}; \else
        % \ifnum\direction=2 \node[numero,anchor=north west] at (dot-\x-\y.south east) {\i}; \fi\fi\fi\fi\fi\fi
        \node[numero,anchor=north west] at (dot-\x-\y.south east) {\i};
      \fi
      \ifnum\maxcoordsX>\x
      \ifnum\maxcoordsY>\y
        % \ifnum\corner=0    \node[coord,anchor=south east] at (dot-\x-\y.north west) {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\corner=1    \node[coord,anchor=north east] at (dot-\x-\y.south west) {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\corner=2    \node[coord,anchor=north west] at (dot-\x-\y.south east) {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\corner=3    \node[coord,anchor=south west] at (dot-\x-\y.north east) {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\direction=0 \node[coord,anchor=east]       at (dot-\x-\y.west)       {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\direction=1 \node[coord,anchor=north]      at (dot-\x-\y.south)      {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\direction=2 \node[coord,anchor=west]       at (dot-\x-\y.east)       {\reallysmallcheat{(\x, \y)}}; \else
        % \ifnum\direction=3 \node[coord,anchor=south]      at (dot-\x-\y.north)      {\reallysmallcheat{(\x, \y)}}; \fi\fi\fi\fi\fi\fi\fi\fi
        \expandafter\xdef\csname dotxypresent-\x-\y\endcsname{1}
        \ifnum\y=0
          \node[coord,anchor=south west] at (dot-\x-\y.north east) {\reallysmallcheat{(\x, \y)}};
        \else
          \node[coord,anchor=west,xshift=0.2] at (dot-\x-\y.east) {\reallysmallcheat{(\x, \y)}};
        \fi
      \fi
      \fi
    }
    \def\drawlinknode{%
      \drawnode%
      \draw[->] (phantom-\oldx-\oldy) -- (phantom-\x-\y);%
    }
    \def\mystep{%
      \incr\i%
      \xdef\oldx{\x}%
      \xdef\oldy{\y}%
    }
    \def\changedir#1{%
      \xdef\direction{#1}%
      \xdef\corner{#1}%
    }
    
    \drawnode
    \mystep \incr\x
    \xdef\cornerc{0}

    \foreach \pos in {1,...,\maxdots} {
      % Detect when we are at the end of this edge.
      \ifnum\sidelen=0
        \ifnum\direction=0 \changedir{1} \incr\nextsidelen \xdef\sidelen{1}            \else
        \ifnum\direction=1 \changedir{2}                   \xdef\sidelen{\nextsidelen} \else
        \ifnum\direction=2 \changedir{3} \incr\nextsidelen \xdef\sidelen{1}            \else
        \ifnum\direction=3 \changedir{0}                   \xdef\sidelen{\nextsidelen} \fi\fi\fi\fi% Brin d'acier
        
      \fi
      % Draw node and link to previous, step counters
      \drawlinknode \mystep
      %% Se déplacer vers ↙↓↗→
      \ifnum\direction=0 \incr\y \decr\x \fi
      \ifnum\direction=1 \incr\y         \fi
      \ifnum\direction=2 \decr\y \incr\x \fi
      \ifnum\direction=3         \incr\x \fi
      \decr\sidelen
      \xdef\corner{4}%% 4 == pas de coin-coin.
    }
    
    \foreach \x in {0,...,\maxdotsX} {
      \foreach \y in {1,...,\maxdotsY} {
        \node[dot] (dot-\x-\y) at (\x,-\y) {};
      }
    }
    \decr\maxcoordsX
    \decr\maxcoordsY
    \foreach \x in {0,...,\maxcoordsX} {
      \foreach \y in {0,...,\maxcoordsY} {
        \node[dot,fill=none] (fakedot-\x-\y) at (\x,-\y) {};
        \expandafter\ifnum\csname dotxypresent-\x-\y\endcsname=0
          \ifnum\y=0
            \node[coord,anchor=south west] at (fakedot-\x-\y.north east) {\reallysmallcheat{(\x, \y)}};
          \else
            \node[coord,anchor=west,xshift=0.2] at (fakedot-\x-\y.east) {\reallysmallcheat{(\x, \y)}};
          \fi
        \fi
      }
    }
    
    \foreach \i in {1, ...,6}{
      \node[constatation1] at (.5*\i,-.5*\i) {\i};
    }
    \node[constatation1] at (.5*7,-.5*7) {\vdots};
    
    \node[coordinate] (fake0-0) at (0,0) {};
    \node[constatation2, coordinate, above of=fake0-0] (fake0-0-bis) {};
    \node[coordinate] (fake1-0) at (1,0) {};
    \node[coordinate] (fake3-0) at (3,0) {};
    \node[coordinate] (fake5-0) at (5,0) {};
    \node[coordinate] (fake0-2) at (0,-2) {};
    \node[coordinate] (fake0-4) at (0,-4) {};
    \node[coordinate] (fake0-6) at (0,-6) {};
    \node[constatation2, left of=fake0-0-bis] {0};
    \node[constatation2, above of=fake1-0]  {1};
    \node[constatation2, above of=fake3-0]  {6};
    \node[constatation2, above of=fake5-0] {15};
    \node[constatation2, left of=fake0-2] {3};
    \node[constatation2, left of=fake0-4] {10};
    \node[constatation2, left of=fake0-6] {21};
  \end{tikzpicture}
  \caption{Codage d'un couple d'entiers relatifs}%% TODO : caption
  \label{fig:codage-nat-avec-constatation}
\end{figure}


En reprenant la figure \ref{fig:codage-nat-avec-constatation} ci-dessus, on peut faire plusieurs constatations~:

\begin{itemize}
\item La somme de $x$ et $y$ de chaque sommet du graphe d'une diagonale dans le sens du parcours est toujours la même.
\item La longueur de chaque diagonale successive s'incrémente à chaque fois et nous donne par conséquent toujours une longueur impaire suivie d'une longueur paire.
\item Le point à partir duquel on commence à incrémenter le code au long d'une diagonale correspond aux codes $1$, $3$, $6$, $10$, $15$, $21$\ldots (voir la figure \ref{fig:codage-nat-avec-constatation}), ce qui correspond à la formule de Gauss, à savoir~:

$$\dfrac{(n \times (n + 1))}{2}$$
\end{itemize}

Ces trois informations nous permettront de coder un couple de nombres naturels sans parcourir le graphe. En voici l'algorithme en C~:

\begin{lstlisting}[language=C]
long int orderedPairToCodeNat(int x, int y){
	long code;
	int sumxy; 
	sumxy = x + y;
	code = ((sumxy)*(sumxy + 1))/2;

	if(even(sumxy)){
		code = code + x;
	}
	else{
		code = code + y; 
	}
	return code;
}
\end{lstlisting}


En reprenant les trois informations constatées à partir du figure \ref{fig:codage-nat-avec-constatation} et les algorithmes décrits ci-dessus, il est également relativement facile de calculer n'importe quel couple d'entiers naturels à partir d'un code. En voici l'algorithme en C~:

\begin{lstlisting}[language=C]
int* codeToOrderedPairNat(long int code){
	int *couple = malloc(2*sizeof(int));
	int n = sqrt(code * 2);
	long int axis = (n * (n + 1))/2;
	int diff = 0;
	if(axis > code){
			n = n - 1;
			axis = (n * (n + 1))/2;
	}
	diff = code - axis;
	if(even(n)){
		couple[0] = diff;
		couple[1] = n - diff;
	}
	else{
		couple[0] = n - diff;
		couple[1] = diff;
	}
	return couple;
}
\end{lstlisting}

On trouve d'abord une valeur approximative du code correspondant aux valeurs de la formule de Gauss (la variable \lstinline!axis! dans la fonction ci-dessus), puis on modifie cette valeur afin qu'elle soit une valeur plus petite que le vrai code passé en paramètre. La valeur \lstinline!n! est égale soit à la valeur de \lstinline!x! soit à la valeur de \lstinline!y! d'un point extrêmal de la ligne diagonale en question (selon le point en question). On modifie les valeurs de \lstinline!x! et de \lstinline!y! en calculant la différence entre le code et le code approximatif (la variable $axis$), ce qui nous donne les valeurs de \lstinline!x! et de \lstinline!y! correspondant au code passé en paramètre.

Prenons un simple example. Mettons qu'on voulait connaitre le couple correspondant au code $19$. La valeur entière  correspondant au point extrêmal de la diagonale est $15$ ($axis = 15$, $n = 5$). La différence entre ces deux points est $19 - 15 = 4$ ($diff = code - axis$). On soustrait $4$ à $5$ ($couple[0] = n - diff$) pour avoir la valeur de $x$ (ce qui nous donne $1$) et $4$ ($diff$) est la valeur de $y$. On retourne $x$ et $y$ (à savoir ($(1,4)$).

On peut étendre ce codage pour comprendre tous les nombres entiers en réutilisant la fonction ci-dessus. Voici l'algorithme implémenté en C de la fonction du codage des entiers~:

\begin{lstlisting}[language=C]
long int orderedPairToCodeInt(int x, int y){
	long int code = 0;	

	if (x < 0){
		x = (2 * (abs (x))) - 1;
	}
	else{
		x = 2 * x;
	}

	if (y < 0){
		y = (2 * (abs(y))) - 1;
	}
	else{
		y = 2 * y;
	}

	code = orderedPairToCodeNat(x, y);
	return code;
}
\end{lstlisting}


On n'utilise que des valeurs positive pour ce codage. Si x est négative, on l'attribut une valeur impaire. Si \lstinline!x! est positif, on
l'attribut une valeur paire, et il en va de même des valeurs de y. Ensuite, on passe le nouveau couple ainsi créé en paramètre en se servant
de la fonction initialement créée pour coder les nombres naturels.


Pour trouver un couple à partir d'un code, on fait l'inverse~:

\begin{lstlisting}[language=C]
int* codeToOrderedPairInt(long int code){
	int *pair = codeToOrderedPairNat(code);

	if (even(pair[0])){
		pair[0] = pair[0] / 2;
	}
	else{
		pair[0] = (pair[0] / 2)*(-1) - 1;
	} 
	
	if (even (pair[1])){
		pair[1] = pair[1] / 2;
	}
	else{
		pair[1] = (pair[1] / 2)*(-1) - 1;
	}

	return pair;
}
\end{lstlisting}  


Un autre système de codage pourrait être utilisé en parcourant un graphe comme montré dans la figure \ref{fig:codage-rel}.

\begin{figure}[ht!]
  %% «Paramètres»
  \xdef\maxdots{81}
  \xdef\maxnums{56}
  \xdef\maxcoords{20}
  
  %% ===== Code is below =====
  
  %% Macros crades
  \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
  % \centering
  \hskip -21mm%% Hack-o-matic to get the picture more or less centered…
  \begin{tikzpicture}[
    dot/.style={
      circle,
      inner sep=0.7pt,
      fill=black
    },
    dotphantom/.style={
      circle,
      inner sep=3pt,
      fill=none,
      draw=none
    },
    numero/.style={circle, fill=white, inner sep=0.2pt, text=red, scale=.75},
    coord/.style={darkgray, scale=.6},
    %
    bigarrow/.style={
      ->,
      thick,
      draw=green!50!black
    }
    ]
    
    % Diagonales
    \node[dotphantom] (pre-phantom-0-0) at (0,0) {};
    \node[dotphantom] (pre-phantom-1-0) at (1,0) {};
    
    % Top right
    \node[inner sep=0.1pt] (tr-start) at (4,4) {};
    \xdef\previous{tr-start}
    \foreach \pos/\content in {0/$1\times 2=2$,1/$3\times 4=12$,2/$5\times 6=30$,3/$7\times 8=56$,4/$\vphantom{X}\dots$}{
      \node[anchor=south] (tr-temp-\pos) at (intersection cs: first line={(\previous.north west)--(\previous.north east)}, second line={(0,0)--(6,6)}) {\phantom{\content}};
      \node[anchor=north west] (tr-\pos) at (intersection cs: first line={(tr-temp-\pos.north west)--(tr-temp-\pos.north east)}, second line={(0,0)--(6,6)}) {\content};
      \xdef\previous{tr-\pos}
    }
    \draw[bigarrow] (pre-phantom-0-0) -- (intersection cs: first line={(\previous.north west)--(\previous.south west)}, second line={(0,0)--(6,6)});
    
    % Top left
    \node[inner sep=0.1pt] (tl-start) at (-4,4) {};
    \xdef\previous{tl-start}
    \foreach \pos/\content in {0/$0^2=0$,1/$2^2=4$,2/$6^2=36$,3/$8^2=64$,4/$\vphantom{X}\dots$}{
      \node[anchor=south] (tl-temp-\pos) at (intersection cs: first line={(\previous.north west)--(\previous.north east)}, second line={(0,0)--(-6,6)}) {\phantom{\content}};
      \node[anchor=north east] (tl-\pos) at (intersection cs: first line={(tl-temp-\pos.north west)--(tl-temp-\pos.north east)}, second line={(0,0)--(-6,6)}) {\content};
      \xdef\previous{tl-\pos}
    }
    \draw[bigarrow] (pre-phantom-0-0) -- (intersection cs: first line={(\previous.north east)--(\previous.south east)}, second line={(0,0)--(-6,6)});
    
    % Bottom left
    \node[inner sep=0.1pt] (bl-start) at (-4,-4) {};
    \xdef\previous{bl-start}
    \foreach \pos/\content in {0/$0\times 1=0$,1/$2\times 3=6$,2/$4\times 5=20$,3/$6\times 7=42$,4/$\vphantom{X}\dots$}{
      \node[anchor=north] (bl-temp-\pos) at (intersection cs: first line={(\previous.south west)--(\previous.south east)}, second line={(0,0)--(-6,-6)}) {\phantom{\content}};
      \node[anchor=south east] (bl-\pos) at (intersection cs: first line={(bl-temp-\pos.south west)--(bl-temp-\pos.south east)}, second line={(0,0)--(-6,-6)}) {\content};
      \xdef\previous{bl-\pos}
    }
    \draw[bigarrow] (pre-phantom-0-0) -- (intersection cs: first line={(\previous.north east)--(\previous.south east)}, second line={(0,0)--(-6,-6)});
    
    % Bottom right
    \node[inner sep=0.1pt] (br-start) at (5,-4) {};
    \xdef\previous{br-start}
    \foreach \pos/\content in {0/$1^2=1$,1/$3^2=9$,2/$5^2=25$,3/$7^2=49$,4/$\vphantom{X}\dots$}{
      \node[anchor=north] (br-temp-\pos) at (intersection cs: first line={(\previous.south west)--(\previous.south east)}, second line={(1,0)--(6,-5)}) {\phantom{\content}};
      \node[anchor=south west] (br-\pos) at (intersection cs: first line={(br-temp-\pos.south west)--(br-temp-\pos.south east)}, second line={(1,0)--(6,-5)}) {\content};
      \xdef\previous{br-\pos}
    }
    \draw[bigarrow] (pre-phantom-1-0) -- (intersection cs: first line={(\previous.north west)--(\previous.south west)}, second line={(1,0)--(6,-5)});
    % Fin diagonales

    % Définitions pour le code ci-dessous.
    \xdef\i{0}
    \xdef\x{0}
    \xdef\y{0}
    \xdef\corner{4}
    \xdef\sidelen{0}
    \xdef\nextsidelen{1}
    \xdef\direction{3}
    \incr\maxnums
    \incr\maxcoords
    
    \def\reallysmallcheat#1{%
      \ensuremath{\hphantom{\vphantom{X}}_{\hphantom{\vphantom{X}}_{#1}}}
    }
    \def\drawnode{%
      \node[dot] (dot-\x-\y) at (\x,\y) {};
      \node[dotphantom] (phantom-\x-\y) at (\x,\y) {};
      \ifnum\maxnums>\i
        \ifnum\corner=0    \node[numero,anchor=north west] at (dot-\x-\y.south east) {\i}; \else
        \ifnum\corner=1    \node[numero,anchor=south west] at (dot-\x-\y.north east) {\i}; \else
        \ifnum\corner=2    \node[numero,anchor=south east] at (dot-\x-\y.north west) {\i}; \else
        \ifnum\corner=3    \node[numero,anchor=north east] at (dot-\x-\y.south west) {\i}; \else
        \ifnum\direction=0 \node[numero,anchor=west]       at (dot-\x-\y.east)       {\i}; \else
        \ifnum\direction=1 \node[numero,anchor=south]      at (dot-\x-\y.north)      {\i}; \else
        \ifnum\direction=2 \node[numero,anchor=east]       at (dot-\x-\y.west)       {\i}; \else
        \ifnum\direction=3 \node[numero,anchor=north]      at (dot-\x-\y.south)      {\i}; \fi\fi\fi\fi\fi\fi\fi\fi
      \fi
      \ifnum\maxcoords>\i
        \ifnum\corner=0    \node[coord,anchor=south east] at (dot-\x-\y.north west) {\reallysmallcheat{(\x, \y)}}; \else
        \ifnum\corner=1    \node[coord,anchor=north east] at (dot-\x-\y.south west) {\reallysmallcheat{(\x, \y)}}; \else
        \ifnum\corner=2    \node[coord,anchor=north west] at (dot-\x-\y.south east) {\reallysmallcheat{(\x, \y)}}; \else
        \ifnum\corner=3    \node[coord,anchor=south west] at (dot-\x-\y.north east) {\reallysmallcheat{(\x, \y)}}; \else
        \ifnum\direction=0 \node[coord,anchor=east]       at (dot-\x-\y.west)       {\reallysmallcheat{(\x, \y)}}; \else
        \ifnum\direction=1 \node[coord,anchor=north]      at (dot-\x-\y.south)      {\reallysmallcheat{(\x, \y)}}; \else
        \ifnum\direction=2 \node[coord,anchor=west]       at (dot-\x-\y.east)       {\reallysmallcheat{(\x, \y)}}; \else
        \ifnum\direction=3 \node[coord,anchor=south]      at (dot-\x-\y.north)      {\reallysmallcheat{(\x, \y)}}; \fi\fi\fi\fi\fi\fi\fi\fi
      \fi
    }
    \def\drawlinknode{%
      \drawnode%
      \draw[->] (phantom-\oldx-\oldy) -- (phantom-\x-\y);%
    }
    \def\mystep{%
      \incr\i%
      \xdef\oldx{\x}%
      \xdef\oldy{\y}%
    }
    \def\changedir#1{%
      \xdef\direction{#1}%
      \xdef\corner{#1}%
    }
    
    \drawnode
    \mystep \incr\x
    \xdef\cornerc{0}

    \foreach \pos in {1,...,\maxdots} {
      % Detect when we are at the end of this edge.
      \ifnum\sidelen=0
        \ifnum\direction=0 \changedir{1} \incr\nextsidelen \else
        \ifnum\direction=1 \changedir{2}                   \else
        \ifnum\direction=2 \changedir{3} \incr\nextsidelen \else
        \ifnum\direction=3 \changedir{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.
    }
  \end{tikzpicture}
  \caption{Codage d'un couple d'entiers relatifs}
  \label{fig:codage-rel}
\end{figure}

Bien que les algorithmes d'encodage et de décodage ne soient pas les mêmes, le principe reste identique. 

On peut faire plusieurs constations~:

\begin{itemize}
\item Le code correspondant aux couples (1,1), (2,2), (3,3), (4,4)\ldots sont respectivement 1, 2, 12, 30\ldots, ce qui correspond à $(1 \times 2)$, $(3 \times 4)$, $(5 \times 6)$, $(7 \times 8)$\ldots
\item Le code correspondant aux couples (0,0), (-1,-1), (-2,-2), (-3,-3)\ldots sont respectivement 0, 6, 20, 42\ldots, ce qui correspond à $(0 \times 1)$, $(2 \times 3)$, $(4 \times 5)$, $(6 \times 7)$\ldots
\item Le code des couples $(1,0)$, $(2,-1)$, $(3,-2)$, $(4,-3)$ sont respectivement $1$, $9$, $25$, $49$\ldots ce qui correspond à la valeur de $(x + |y|))^{2}$, ce sont les carrés des entiers impairs.
\item Le code des couples $(-1,-1)$, $(-2,-2)$, $(-3,-3)$, $(-4,-4)$ sont respectivement $4$, $16$, $36$, $64$\ldots,  ce qui correspond à la valeur de $(|x| + |y|))^{2}$, ce sont les carrés des entiers pairs.
\end{itemize}


A l'aide de ces constations, on peut coder n'importe quel couple d'entiers. En voici un exemple en C~:


\begin{lstlisting}[language=C]
long int orderedPairToCodeIntAlgo2(int x, int y){
	long int code = 0;
	int _x, _y, diff;
	_x = _y = diff = 0;
	int temp;
	int absmax;	
	absmax = max(abs(x), abs(y));	
	
	if(absmax == abs(x)){ // _x == x 
		_x = _y = x;
		temp = abs(x) * 2;
		if(x < 0){ // x negative
			code = temp * (temp + 1);
			if(y < 0){ // x negative, y negative
				diff = abs(_y) - abs(y);
			}
			else{ // x negative, y positive
				diff = abs(_y) + abs(y);
			}
		}
		else{ // x positive
			code = (temp - 1) * temp; 
			if(y > 0){ // x positive, y positive
				diff = abs(_y) - abs(y);
			}
			else{ // x positive, y negative
				diff = abs(_y) + abs(y);
			}
		}
		code = code - diff;
	}
	else{ // _y = y
		_x = _y = y;
		temp = abs(y) * 2;
		if(y < 0){ // y negative
			code = temp * (temp + 1);		
			if(x < 0){ // y negative, x negative
				diff = abs(_x) - abs(x);
			}
			else{ // y negative, x positive
				diff = abs(_x) + abs (x);
			}
		}
		else{ // y positive
			code = (temp - 1) * temp;
			if(x > 0){ // y positive, x positive
				diff = abs(_x) - abs(x);
			}
			else{ // y positive, x negative
				diff = abs(_x) + abs(x);
			}	
		}	
		code = code + diff;	
	}
	return code;
}
\end{lstlisting}


On commence par trouver le max de $|x|$ et $|y|$~: $(-3,1)$ nous donnerait comme $absmax$ la valeur $3$. Ensuite on détermine si cette valeur correspond à la valeur de $x$ ou la valeur de $y$. Si cette valeur correspond à la valeur de $x$ (resp. $y$), on affecte la valeur de $x$ (resp. $y$) aux variables temporaires $\_x$ et $\_y$. Ensuite, on se sert de la propriété des multiplications décrite précédemment selon les quatre cas de figures possibles, à savoir, le cas où $x$ et $y$ sont positives, le cas où $x$ et $y$ sont négatives, celui où $x$ est positive et $y$ est négative, et inversement. On affecte une valeur provisoire à la variable $code$, qui est soit $temp$ (la valeur absolue de la max des deux coordonnées) multiplié par $temp + 1$ ou bien $temp$ multiplié par $temp - 1$ selon que la valeur de la coordonnée $absmax$ est négative ou positive respectivement. Nous avons à ce point un code approximatif. On peut facilement trouver la coordonnée correspondant à $absmax$, et pour trouver l'autre coordonnée on calcule la différence entre la valeur absolue de la coordonnée qu'on connaît et l'autre coordonnée afin d'ajuster le code. Puis, enfin, on retourne le code exact.

Le décodage utilise le même principe mais dans le sens inverse~:

\begin{lstlisting}[language=C]
int* codeToOrderedPairIntAlgo2(long int code){
	int* pair = malloc(2*sizeof(int));
	int isqrtcode = (int) sqrt(code);
	long int pivotcode = isqrtcode * (isqrtcode + 1);
	int x, y;
	x = y = 0;	

	if(even(isqrtcode)){
		x = y = -(isqrtcode / 2);
		if(code > pivotcode){
			x = x + (code - pivotcode);
		}
		else{
			y = y + (pivotcode - code);
		}
	}
	else{
		x = y = (isqrtcode / 2) + 1;
		if(code > pivotcode){
			x = x - (code - pivotcode);
		}
		else{
			y = y - (pivotcode - code); 
		}
	}
	pair[0] = x;
	pair[1] = y; 
	return pair;
}
\end{lstlisting}

Plusieurs programmes complets pour le codage des entiers naturels et le codage des entiers se trouve annexe~: couples-2.lisp (page \pageref{couples2lisp}), couples-3.lisp (page \pageref{couples3lisp}), couples.c (page \pageref{couplesc}) et couple\_entiers.c (page \pageref{coupleentiersc}).



\begin{enonce}
Montrer que l'on peut coder les triplets. Généraliser aux k-uplets, puis aux listes de longueurs quelconques.
\end{enonce}

Pour coder un triplet $(x_1, x_2, x_3)$, on code d'abord le couple $(x_1, x_2)$, puis, soit $x^*$ le résultat intermédiaire, on code le couple $(x^*, x_3)$.

\begin{figure}[ht!]
  \centering
  \begin{tikzpicture}
    \node (x11) {$x_1$};
    \node[right of=x11] (x21) {$x_2$};
    \node[right of=x21] (x31) {$x_3$};
    \node[coordinate] (xmark) at ($ .5*(x11) + .5*(x21) $) {};
    \node[below of=xmark] (x*2) {$x^*$};
    \node[coordinate] (xmark2) at ($ .5*(xmark) + .5*(x*2) $) {};
    
    \node[anchor=base] (x32) at (x*2.base -| x31) {$x_3$};
    
    \node[coordinate] (xmark4) at ($ .5*(x*2) + .5*(x32) $) {};
    \node[below of=xmark4] (x*3) {résultat};
    \node[coordinate] (xmark5) at ($ .5*(xmark4) + .5*(x*3) $) {};
    
    \draw (x11) -- (xmark2);
    \draw[->] (x21) -- (xmark2) -- (x*2);
    \draw[->] (x31) -- (x32 |- x*2.north);
    \draw (x*2) -- (xmark5);
    \draw[->] (x32) -- (xmark5) -- (x*3);
  \end{tikzpicture}
  \caption{Codage d'un triplet d'entiers naturels}
  \label{fig:codage-couple}
\end{figure}

Le décodage suit tout simplement le chemin inverse (on décode ne nombre en $(x^*, x_3)$, puis on décode $x^*$ en $(x_1, x_2)$ et on recompose en $(x_1, x_2, x_3)$.

La généralisation aux k-uplets suit le même principe : On code les deux premiers nombres de la paire en nommant le résultat $x^*$, puis, on
code successivement chaque paire $(x^*, x_i)$, avec $x_i$ qui vaut successivement chaque élément du k-uplet, et $x^*$ qui vaut à chaque fois
le résultat précédent.

Le décodage d'un k-uplet de longueur k décodera le nombre en une paire $(x^*, x_i)$ $k-1$ fois, et la dernière paire ainsi générée sera
$(x_1, x_2)$. Il suffira alors de recomposer le k-uplet à partir de $x_1$, $x_2$ et tous les $x_i$.

Le codage et le décodage d'un singleton sont triviaux : $(x_1) \leftrightarrow x_1$.

Pour les listes de longueur quelconque, le problème est de savoir combien de fois faudra-t-il décoder le résultat. En effet, $(0)$, $(0,0)$
et $(0,0,0)$ ont le même code, $0$, donc il n'y a plus de bijection entre la liste et les entiers naturels, donc ambiguïté lors du décodage.

Étant donné que pour un k donné, il y a une bijection entre les k-uplets et les entiers naturels, il nous suffit d'ajouter une information
permettant de déterminer de manière unique la valeur de k. On code donc d'abbord le k-uplet correspondant à la liste, en nommant le résultat
$x^*$, puis on code le couple $(x^*, k)$. Au décodage, on décodera le nombre pour obtenir $x^*$ et $k$, et on décodera $x^*$ avec la méthode
de décodage des k-uplets donnés ci-dessus.

Reste un dernier problème, celui de pouvoir encoder des listes d'entiers relatifs (et non pas juste des entiers naturels). Pour cela, on
fera une transformation préalable sur chaque élément des k-uplets :

Soit $n$ le $i$-ième élément du k-uplet, si $n$ est positif, on le transforme en le $n$-ième nombre pair, sinon, il est strictement négatif et on le transforme en le $|n|-1$ ième nombre impair. Ainsi, $0 \mapsto 0$, $1 \mapsto 2$, $2 \mapsto 4$, $-1 \mapsto 1$, $-2 \mapsto 3$, \dots

\begin{equation}
  \begin{array}{r l}
    \mathrm{transformation} : Z & \longrightarrow N \\
    n & \mapsto
    \left \{
      \begin{array}{r l}
        2n       & \text{si $n$ est pair} \\
        2(|n|-1) & \text{si $n$ est impair}
      \end{array}
    \right .
  \end{array}
\end{equation}

Le codage d'une liste d'entiers relatifs peut donc être résumé par la figure \ref{fig:codage-all}

\begin{figure}[ht!]
  \centering
  \begin{tikzpicture}[
    level distance=0.7cm,
    circle,
    inner sep=0.1pt,
    ]
    \node[rectangle, inner sep=1pt] (res) {$\text{résultat}$} [grow=up]
    child[draw=red] {
      node[coordinate] (catch-k) {} edge from parent[<-]
    }
    child {
      node {x*}
      child {
        child {
          child {
            child {
              child {
                child {
                  node (xk) {$x_{\phantom{k}}$}
                  % node[anchor=base] at (xk.base) {$\vphantom{x}_{k}$}
                  % node[anchor=east] at (xk.east) {$\hphantom{x}_{k}$}
                  node[anchor=base] (get-k-v) at (xk.base) {$\vphantom{x}_{\phantom{k}}$}
                  node[anchor=east] (get-k-h) at (xk.east) {$\hphantom{x}_{\phantom{k}}$}
                  node[coordinate] (get-k-se) at (get-k-v.south -| get-k-h.east) {}
                  node[coordinate] (get-k-nw) at (get-k-v.north -| get-k-h.west) {}
                  node[anchor=base east, draw=red, inner sep=0.15pt] (the-k)
                  at (get-k-v.base -| get-k-h.east) {$\vphantom{.}_{k}$}
                }
              }
            }
          }
        } edge from parent[<-]
      }
      child {
        node {x*}
        child {
          child {
            child {
              child {
                child {node {...} edge from parent[dashed]}
                edge from parent[dashed]
              }
              edge from parent[dashed]
            }
            edge from parent[dashed]
          }
          edge from parent[dashed,<-]
        }
        child {
          node{x*}
          child {
            child {
              child {
                child {node {$x_5$}}
              }
            } edge from parent[<-]
          }
          child {
            node{x*}
            child {
              child {
                child {node {$x_4$}}
              } edge from parent[<-]
            }
            child {
              node{x*}
              child {
                child {node {$x_3$}} edge from parent[<-]
              }
              child {
                node{x*} [sibling distance=7.5mm] edge from parent[<-]
                child {node {$x_2$} edge from parent[<-]}
                child {node {$x_1$} edge from parent[<-]}
                child[missing] {}
              } edge from parent[<-]
            } edge from parent[<-]
          } edge from parent[<-]
        } edge from parent[<-]
      } edge from parent[<-]
    };
    
    \draw[red] (the-k) -| (catch-k);
    
    \node[xshift=0cm, anchor=base west] at (res.base east) {$\vphantom{\text{résultat}} = \operatorname{code}(x^*,k)$};
    
    % \node (e11) {$x_1$}; 
    % \node[right of=e11] (e21) {$x_2$};
    % \node[right of=e21] (e31) {$x_3$};
    % \node[right of=e31] (e41) {$x_4$};
    % \node[right of=e41] (e51) {$x_5$};
    % \node[right of=e51] (ed1) {\dots};
    % \node[right of=ed1] (ek1) {$x_k$};


    % \matrix[column sep=2mm, row sep=7mm]{
    %   \node (e11) {$x_1$}; & \node[coordinate] (o11) {}; &
    %   \node (e21) {$x_2$}; & \node[coordinate] (o21) {}; &
    %   \node (e31) {$x_3$}; & \node[coordinate] (o31) {}; &
    %   \node (e41) {$x_4$}; & \node[coordinate] (o41) {}; &
    %   \node (e51) {$x_5$}; & \node[coordinate] (o51) {}; &
    %   \node (ed1) {\dots}; & \node[coordinate] (o61) {}; &
    %   \node (ek1) {$x_k$}; & \node[coordinate] (o71) {}; \\
      
    %   \node[coordinate] (e12) {}; & \node (o11) {$x^*$}; &
    %   \node (e22) {$x_2$}; & \node[coordinate] (o22) {}; &
    %   \node (e32) {$x_3$}; & \node[coordinate] (o32) {}; &
    %   \node (e42) {$x_4$}; & \node[coordinate] (o42) {}; &
    %   \node (e52) {$x_5$}; & \node[coordinate] (o52) {}; &
    %   \node (ed2) {\dots}; & \node[coordinate] (o62) {}; &
    %   \node (ek2) {$x_k$}; & \node[coordinate] (o72) {}; \\
      
    %   \node[coordinate] (e12) {}; & \node[coordinate] (o12) {}; &
    %   \node[coordinate] (e22) {}; & \node (o22) {$x^*$}; & 
    %   \node (e32) {$x_3$}; & \node[coordinate] (o32) {}; &
    %   \node (e42) {$x_4$}; & \node[coordinate] (o42) {}; &
    %   \node (e52) {$x_5$}; & \node[coordinate] (o52) {}; &
    %   \node (ed2) {\dots}; & \node[coordinate] (o62) {}; &
    %   \node (ek2) {$x_k$}; & \node[coordinate] (o72) {}; \\
      
    %   \node[coordinate] (e12) {}; & \node[coordinate] (o12) {}; &
    %   \node[coordinate] (e22) {}; & \node[coordinate] (o22) {}; & 
    %   \node[coordinate] (e32) {}; & \node (o32) {$x^*$}; &
    %   \node (e42) {$x_4$}; & \node[coordinate] (o42) {}; &
    %   \node (e52) {$x_5$}; & \node[coordinate] (o52) {}; &
    %   \node (ed2) {\dots}; & \node[coordinate] (o62) {}; &
    %   \node (ek2) {$x_k$}; & \node[coordinate] (o72) {}; \\
      
    %   \node[coordinate] (e12) {}; & \node[coordinate] (o12) {}; &
    %   \node[coordinate] (e22) {}; & \node[coordinate] (o22) {}; & 
    %   \node[coordinate] (e32) {}; & \node[coordinate] (o32) {}; &
    %   \node[coordinate] (e42) {}; & \node (o42) {$x^*$}; &
    %   \node (e52) {$x_5$}; & \node[coordinate] (o52) {}; &
    %   \node (ed2) {\dots}; & \node[coordinate] (o62) {}; &
    %   \node (ek2) {$x_k$}; & \node[coordinate] (o72) {}; \\
    % };
    
    % \node[coordinate] (x11-21) at ($ .5*(x11) + .5*(x21) $) {};
    % \node[coordinate] (x21-31) at ($ .5*(x11) + .5*(x21) $) {};
    % \node[coordinate] (x31-41) at ($ .5*(x11) + .5*(x21) $) {};
    % \node[coordinate] (x41-51) at ($ .5*(x11) + .5*(x21) $) {};
    % \node[coordinate] (x51-d1) at ($ .5*(x11) + .5*(x21) $) {};
    % \node[coordinate] (xd1-k1) at ($ .5*(x11) + .5*(x21) $) {};
    
    % \node[below of=xmark] (x*2) {$x^*$};
    % \node[coordinate] (xmark2) at ($ .5*(xmark) + .5*(x*2) $) {};
    
    % \node[anchor=base] (x32) at (x*2.base -| x31) {$x_3$};
    
    % \node[coordinate] (xmark4) at ($ .5*(x*2) + .5*(x32) $) {};
    % \node[below of=xmark4] (x*3) {résultat};
    % \node[coordinate] (xmark5) at ($ .5*(xmark4) + .5*(x*3) $) {};
    
    % \draw (x11) -- (xmark2);
    % \draw[->] (x21) -- (xmark2) -- (x*2);
    % \draw[->] (x31) -- (x32 |- x*2.north);
    % \draw (x*2) -- (xmark5);
    % \draw[->] (x32) -- (xmark5) -- (x*3);
  \end{tikzpicture}
  \caption{Codage d'un $n$-uplet d'entiers}
  \label{fig:codage-all}
\end{figure}

%% TODO : ce qui suit est un doublon du début de l'exercice !?!

Pour coder les triplets, on considère un triplet, (3,1,2) par exemple, comme un couple (3,(1,2)). On calcule le code du couple imbriqué,
c'est-à-dire du couple (1,2), ce qui nous donne 8. On refait le même codage en substituant 8 à (1,2), ce qui nous donne (3,8). On code
ensuite (3,8) et notre résultat est 74. L'algorithme est récursif, tant qu'on n'a pas un couple à deux éléments atomiques, on continue à
coder les \og{}sous-couples\fg{}, ce qui nous permet non seulement de coder les triplets, mais de coder n'importe quel k-uplet. Donc, pour
ce faire, il nous faut deux informations, le code et la taille du k-uplet, qui est implicite lorsque l'on code, mais qui doit être
explicitée lorsque l'on doit trouver le k-uplet à partir d'un code.

Voici le code en C pour coder et décoder respectivement n'importe quel k-uplet de nombres entiers en reprenant les fonctions déjà décrites
dans la réponse de la question précédente~:

\begin{lstlisting}[language=C]

long int orderedMultipleToCodeInt(int *arr, int size){
	long int code;	
	if(size > 1){
		code = orderedPairToCodeInt(arr[size - 2], arr[size - 1]);
		arr[size - 2] = code;
		arr = realloc(arr, (size - 1));
		if(size > 2){		
			code = orderedMultipleToCodeInt(&arr[0], (size - 1));
		}
	}
	return code;
}

int* codeToOrderedMultipleInt(long int code, int size){
	int *multiple = malloc(size*sizeof(int));
	int *pair;
	int i = 0;
	for(i = 0; i < (size - 1); i++){
		pair = codeToOrderedPairInt(code);
		code = pair[1];
		multiple[i] = pair[0];
		multiple[i + 1] = pair[1];
	}
	return multiple;
}

\end{lstlisting}


Plusieurs programmes permettant de coder et de décoder des couples et des k-uplets en LISP et en C sont fournis en annexe de ce document, y
compris les fonctions 'int* codeToOrderedMultipleIntAlgo2(long int code, int size)' et 'long int orderedMultipleToCodeIntAlgo2(int *arr, int
size)' qui se servent du deuxième algorithme pour coder et pour décoder les k-uplets de nombres entiers.


\begin{enonce}
  Peut-on énumérer les fonctions C syntaxiquements correctes ? Et les fonctions C qui ne bouclent jamais ? Justifier vos réponses le plus
  clairement et le plus synthétiquement possible.
\end{enonce}

On sait énumérer récursivement toutes les séquences d'octets~:

Pour passer d'une séquence à la suivante, on commence par le dernier octet. S'il est inférieur à 255, on incrémente sa valeur de 1, sinon on passe à l'octet d'avant, et continue la même démarche. Si on arrive au premier octet de la séquence sans avoir pu en incrémenter de 1, on crée une séquence d'octets de longueur $n + 1$ (où $n$ est la longueur de la séquence courante) dans laquelle chaque octet vaut zéro.

Pour énumérer les fonctions C syntaxiquement correctes, on passe successivement chaque séquence d'octets et on vérifie si elle correspond à une fonction C syntaxiquement correcte (La reconaissance de la syntaxe C peut être faite grâce à un automate, qui se termine toujours dans un temps fini). S'il s'agit d'une fonction C syntaxiquement correcte, on l'affiche, et dans tous les cas on passe à la suivante et on recommence.

Énumérer les fonctions consiste à fournir un algorithme (donc un programme) permettant de donner l'élément suivant à partir de l'élément courant (ou de les donner un à un, ce qui revient à la même chose).

Dans ce cas-ci, il faudrait donc faire un programme (algorithme) qui énumère toutes les fonctions C (ce qu'on sait faire), et soit capable de ne pas lister celles qui bouclent indéfiniment.

Or, cela signifierait que ce programme (algorithme) serait capable de résoudre le problème de l'arrêt, ce qui n'est pas possible.

% TODO : faire un titre de la ligne suivante
\textbf{Démonstration de l'impossibilité de résoudre algorithmiquement le problème de l'arrêt.}

Supposons qu'il existe un programme $h(p, x)$ prennant en paramètre un programme et une donnée tel que :
\[
h(p, x) = \left\{
\begin{array}{ll}
  1 & \qquad \text{si $p(x)$ se termine} \\
  0 & \qquad \text{sinon $p(x)$ boucle indéfiniment} \\
\end{array}
\right.
\]

\ldots on pourrait alors construire le programme $gamma(n)$ suivant~:
\begin{lstlisting}[language=C]
  int gamma(int n) {
    if (h(gamma, n))
     while (1);
    else
     return (0);
  }
\end{lstlisting}
Si $gamma(n)$ se termine, alors $gamma(n)$ boucle et donc ne se termine pas. Si $gamma(n)$ ne se termine pas, alors $gamma(n)$ retourne 0,
donc $gamma(n)$ se termine.

Dans les deux cas, il y a contradiction. Par conséquent, il n'est pas possible de déterminer algorithmiquement si un programme s'arrête ou
boucle indéfiniment, et donc il est impossible d'énumerer toutes les fonctions C qui ne bouclent jamais (puisqu'on ne peut pas savoir si la
fonction en question boucle ou non, on ne peut pas savoir si elle fait partie de l'énumération ou non).

\section{Partie pratique sur les algorithmes de flots}


\subsubsection*{Exercice \stepcounter{exocount}\bf\small \arabic{exocount} -- La méthode de Edmonds-Karp et celle de Dinic}
\addcontentsline{toc}{subsubsection}{Exercice \arabic{exocount} -- La méthode de Edmonds-Karp et celle de Dinic}
\setcounter{enoncecount}{0}

\begin{enonce}
Programmer une procédure qui construit à partir d'un graphe orienté valué (les valuations représentent les capacités) et deux sommets $s$ et $p$ du graphe, le graphe d'écart associé (correspondant à un flot nul sur chaque arc).
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
Programmer un procédure qui à partir d'un graphe orienté et deux sommets $s$ et $p$ donne un plus court chemin en nombre d'arcs de $s$ à $p$ ou qui signale s'il n'y en a pas.
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
Etant donnés un graphe G orienté et valué et un chemin de G, écrire une fonction uqi calcule l'arc de plus petite valuation sur le chemin.
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
Etant donnés un graphe d'écard, un chemin et un entier $k$, donner une procédure qui met à jour le graphe d'écard si on augmente le flot de $k$ le long de la chaîne augmentante correspondant au chemin. 
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
Ecrire une procédure qui à partir du graphe initial et du graphe d'écard final (plus de chemins entre $s$ et $p$ donne la valeur du flot maximum ainsi que la valeur deu flot sur chaque arc lorsque le flot maximum est atteint. 
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
En utilisant les procédures et les fonctions précédentes, programmer l'algorithme de Edmond-Karp. 
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
Ecrire une procédure qui prend en compte l'ensemble des plus cours chemins en nombres d'arcs.
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
Ecrire une procédure qui calcule la plus petite valeur du flot dans le graphe de couche.
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
Ecrire une procédure qui met à jour le flot dans le graphe G. 
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
En déduire l'algorithme de Dinic.
\end{enonce}

(Voir Annexe B, page \pageref{annexeexo5})

\begin{enonce}
Comparer les résultats (temps d'exécution, taux d'occupation mémoire) entre les deux méthodes. Vous apporterez un soin tout particulier à la génération de vos résultats et à leur présentation.
\end{enonce}

Les graphiques ci-dessous représentent le temps d'exécution et l'espace mémoire utilisé par nos implémentations de l'algorithme de Dinic et d'Elmonds-Karp. Notre implémentation de l'algorithme de Dinic fonctionne, mais les résultats montrés dans les graphiques ne reflète pas la réalité car nous avons mal implémenté la gestion de la structure de couche dans cet algorithme, ce qui rend notre implémentation très gourmand en mémoire. 

\newpage
\input{temps}
\newpage
\input{espace}
\newpage
\input{espace2}
\newpage

\appendix
\section{Annexe~: Exercice 4}
\label{annexe-deb}
\newpage
\subsection{couples.lisp}
\label{coupleslisp}
\begin{lstlisting}[language=Lisp, basicstyle=\footnotesize]

;;COUPLES.LISP

;; definition des variables globales (toujours entre asterisques)
(defvar *current* (list 0 0 0)) ;; liste courante "(code x y)"
(setf *current* (list 0 0 0)) 
(defvar *db* nil) ;; base de donnees qui stocke tous les "(code x y)"
(setf *db* nil)
(push *current* *db*)

(defvar *max-x* 0) ;; valeur maximal courante de x
(setf *max-x* 0)
(defvar *max-y* 0) ;; valeur maximal courante de y
(setf *max-y* 0)

#| pour remettre toutes les variables globales a leur valeurs par defaut 
afin de tester, de refaire un 'zig-zag', etc.
|#
(defun reset ()
  (progn
    (defvar *current* (list 0 0 0)) ;; liste courante (cle x y)
    (setf *current* (list 0 0 0))  
    (defvar *db* nil) ;; base de donnees qui stocke tous les "(cle x y)"
    (setf *db* nil)
    (push *current* *db*)
    (defvar *max-x* 0) ;; valeur maximal de x jusque "la"
    (setf *max-x* 0)
    (defvar *max-y* 0) ;; valeur maximal de y jusque "la"
    (setf *max-y* 0)
    *current*))
  
#| Les fonctions "right" "down-left", "down", "up-right" imitent le movement des 
coordonnees sur un graphe mais au les coordonnees "y" positifs sont en DESSOUS du graphe
|#
(defun right (L)
  (progn
    (push
      (setf *current*
        (cons (+ 1 (first L)) (cons (+ 1 (second L)) (last L)))) *db*)
    *current*))
  
(defun down (L)
  (progn
    (push
      (setf *current*
        (cons (+ 1 (first L)) (cons (second L) (cons (+ 1 (third L)) ())))) *db*)
     *current*))

(defun up-right (L)
  (progn
    (push
      (setf *current*
        (cons (+ 1 (first L)) (cons (+ 1 (second L)) (cons (- (third L) 1) ())))) *db*)
    *current*))
    
(defun down-left (L)
  (progn
	(push
	  (setf *current*
	    (cons (+ 1 (first L)) (cons (- (second L) 1) (cons (+ 1 (third L)) ())))) *db*)
    *current*))

(defun update-max-x (L)
  (if (> (second L) *max-x*)
    (setf *max-x* (second L))
    nil))

(defun update-max-y (L)
  (if (> (third L) *max-y*)
    (setf *max-y* (third L))
    nil))

(defun update-max-x-y (L)
  (cond
    ((> (second L) *max-x*)
      (setf *max-x* (second L)))
    ((> (third L) *max-y*)
      (setf *max-y* (third L)))
    (t ())))

;; "move" s'occupe de choisir "right", "down-left" etc. selon les valeurs dans *current*
(defun move (L)
  (cond
    ((and (zerop (third L)) (= *max-x* *max-y*)) ;; RIGHT takes precedence over LEFT becuase it occurs first
      (print "in RIGHT") ;; 
         (right L))
    ((and (zerop (second L)) (= *max-x* *max-y*)) ;; DOWN
      (print "in DOWN") 
         (down L))
    ((> *max-x* *max-y*) ;; DOWN-LEFT
      (print "in DOWN-LEFT")  
         (down-left L))
    ((< *max-x* *max-y*) ;; UP-RIGHT
      (print "in UP-RIGHT") 
         (up-right L))))

#|
On fait un "move" et puis un "update-max-x-y"
Attention : il faut bien faire un setf L, sinon, le parametre L de "update-max-x-y utilise la valeur
de L inchange !
|#
(defun move-and-update (L)
  (progn
    (setf L (move L))
    (update-max-x-y L)
    *db*))

;; "zig-zag" fait n "move-and-update" en un seul coup et affiche le contenu de *db* (toutes les couples) 
(defun zig-zag (L n)
    (if (zerop n) 
      (move-and-update *current*)
      (progn
        (move-and-update *current*)
        (zig-zag L (- n 1)))))

;;END COUPLES.LISP

\end{lstlisting}

\subsection{couples-2.lisp}
\label{couples2lisp}
\begin{lstlisting}[language=Lisp, basicstyle=\footnotesize]

;;COUPLES-2.LISP

(defun gauss-formula (n)
  (/ (* n (+ n 1)) 2))

(defun get-n (code)
  (isqrt (* code 2)))

(defun get-axis (code)
  (gauss-formula (isqrt (* code 2))))

(defun get-axis-from-n (n)
  (gauss-formula n))

(defun axis-code-compare (code)
  (format t "~d    ~d~%" code (get-axis code))) 

(defun axis-code-compare-n (startcode n)
  (let ((i 0))
    (loop
      (when (> i n) (return))
      (axis-code-compare (+ startcode i))
      (incf i))))
  
(defun ord-pr-to-code (x y)
  (let ((sumxy (+ x y)))
    (if (evenp sumxy)
      (+ (gauss-formula sumxy) x)
      (+ (gauss-formula sumxy) y))))

(defun code-to-ord-pr (code)
  (let ((n (get-n code))
        (axis (get-axis code))
        (diff 0))
  (progn
    (when (> (get-axis code) code)
      (progn
        (setf n (- n 1))
        (setf axis (get-axis-from-n n))))
    (setf diff (- code axis))
    (if (evenp n)
      (cons diff (cons (- n diff) ()))
      (cons (- n diff) (cons diff ()))))))

(defun ord-mult-to-code (L)
  (if (= (list-length L) 1)
    (car L)
    (ord-mult-to-code (append (butlast (butlast L)) 
                        (cons (ord-pr-to-code (car (last (butlast L))) (car (last L))) ())))))

(defun code-to-ord-mult (L-or-code size)
  (if (atom L-or-code)
       (code-to-ord-mult (code-to-ord-pr L-or-code) (- size 1))
    (if (not (= size 1))
        (code-to-ord-mult (append (butlast L-or-code) (code-to-ord-pr (car (last L-or-code))))
          (- size 1))
      L-or-code)))

#| Les codes generes par cette fonction ne correspondent pas au code genere par le
diagramme du rapport ni des fonctions ord-mult-to-code et code-to-ord-mult. 
Toutefois, la fonction ci-dessous a ete creees ici car son ecriture et beaucoup plus idiomatique
en LISP (d'ou le nom 'ord-mult-to-code-lisp'). En effet, si on avait a coder les nombres naturels en LISP, on ajouterait 
(resp. supprimerait) des elements de la liste en partant du debut de la liste afin de creer
une paire ou un n-uplet (resp. pour trouver le code correspondant a une paire ou un n-uplet
|#
(defun ord-mult-to-code-lisp (L)
  (if (= (list-length L) 1)
    (car L)
    (ord-mult-to-code-lisp (cons (ord-pr-to-code (first L) (second L)) (cddr L)))))

#| voir le commentaire precedent concernant la fonction ord-mult-to-code-lisp |#
(defun code-to-ord-mult-lisp (L-or-code size)
  (if (atom L-or-code)
    (code-to-ord-mult-lisp (code-to-ord-pr L-or-code) (- size 1))
    (if (not (= size 1))
      (code-to-ord-mult-lisp (append (code-to-ord-pr (car L-or-code)) (cdr L-or-code)) (- size 1))
      L-or-code)))

#|
(defun code-to-ord-pr (code)
  (;let* ((code*2 (* code 2))
         (n (isqrt code*2))
         (axis (gauss-formula n))
         (diff 0))
    (cond 
      ((> axis code)
         (loop while (> axis code)
           ((setf n (- n 1)) 
           (setf axis (gauss-formula n))))
       (< axis code)
          ((loop while (< axis code)
             ((setf n (- n 1)) 
             (setf axis (gauss-formula n))))
           (when (> axis code)
             ((setf n (- n 1))
             (setf axis (gauss-formula n))))))
        (t 5))))
  |#           
  

(defun loop-test (n)
  (let ((n 0))
    (loop
      (when (> n 10) (return))
      (format t "~d ~d ~d~%" n (isqrt n) (gauss-formula n))
      ;(print n) (write (* n n)) (write n)
      (incf n))))

;;END COUPLES-2.LISP

\end{lstlisting}

\subsection{couples-3.lisp}
\label{couples3lisp}
\begin{lstlisting}[language=Lisp, basicstyle=\footnotesize]

;;COUPLES-3.LISP

(defun gauss-formula (n)
  (/ (* n (+ n 1)) 2))

(defun get-n (code)
  (isqrt (* code 2)))

(defun get-axis (code)
  (gauss-formula (isqrt (* code 2))))

(defun get-axis-from-n (n)
  (gauss-formula n))

(defun axis-code-compare (code)
  (format t "~d    ~d~%" code (get-axis code))) 

(defun axis-code-compare-n (startcode n)
  (let ((i 0))
    (loop
      (when (> i n) (return))
      (axis-code-compare (+ startcode i))
      (incf i))))
  
(defun ord-pr-to-code-nat (x y)
  (let ((sumxy (+ x y)))
    (if (evenp sumxy)
      (+ (gauss-formula sumxy) x)
      (+ (gauss-formula sumxy) y))))

(defun code-to-ord-pr-nat (code)
  (let ((n (get-n code))
        (axis (get-axis code))
        (diff 0))
  (progn
    (when (> (get-axis code) code)
      (progn
        (setf n (- n 1))
        (setf axis (get-axis-from-n n))))
    (setf diff (- code axis))
    (if (evenp n)
      (cons diff (cons (- n diff) ()))
      (cons (- n diff) (cons diff ()))))))

(defun nat-to-int (nat)
  (if (< nat 0)
    (- (* 2 (abs nat)) 1)
    (* 2 (abs nat))))

(defun int-to-nat (int)
  (if (evenp int)
    (/ int 2) 
    (ceiling (- (- (/ int 2)) 1))))
    

(defun ord-pr-to-code-int (x y)
  (setf x (nat-to-int x))
  (setf y (nat-to-int y))
  (ord-pr-to-code-nat x y))

(defun code-to-ord-pr-int (code)
  (let ((L (code-to-ord-pr-nat code)))
    (progn
        (setf L (cons (int-to-nat (first L)) (cdr L)))
        (setf L (cons (car L) (cons (int-to-nat (second L)) ())))
      L)))  

(defun ord-mult-to-code-nat (L)
  (if (= (list-length L) 1)
    (car L)
    (ord-mult-to-code-nat (append (butlast (butlast L)) 
                        (cons (ord-pr-to-code-nat (car (last (butlast L))) (car (last L))) ())))))

(defun code-to-ord-mult-nat (L-or-code size)
  (if (atom L-or-code)
       (code-to-ord-mult-nat (code-to-ord-pr L-or-code) (- size 1))
    (if (not (= size 1))
        (code-to-ord-mult-nat (append (butlast L-or-code) (code-to-ord-pr (car (last L-or-code))))
          (- size 1))
      L-or-code)))

#| Les codes generes par cette fonction ne correspondent pas au code genere par le
diagramme du rapport ni des fonctions ord-mult-to-code et code-to-ord-mult. 
Toutefois, la fonction ci-dessous a ete creees ici car son ecriture et beaucoup plus idiomatique
en LISP (d'ou le nom 'ord-mult-to-code-lisp'). En effet, si on avait a coder les nombres naturels en LISP, on ajouterait 
(resp. supprimerait) des elements de la liste en partant du debut de la liste afin de creer
une paire ou un n-uplet (resp. pour trouver le code correspondant a une paire ou un n-uplet.
On aurait pu faire pareil pour les fonctions concernant tous les entiers
|#
(defun ord-mult-to-code-nat-lisp (L)
  (if (= (list-length L) 1)
    (car L)
    (ord-mult-to-code-lisp (cons (ord-pr-to-code (first L) (second L)) (cddr L)))))

#| voir le commentaire precedent concernant la fonction ord-mult-to-code-lisp |#
(defun code-to-ord-mult-nat-lisp (L-or-code size)
  (if (atom L-or-code)
    (code-to-ord-mult-lisp (code-to-ord-pr L-or-code) (- size 1))
    (if (not (= size 1))
      (code-to-ord-mult-lisp (append (code-to-ord-pr (car L-or-code)) (cdr L-or-code)) (- size 1))
      L-or-code)))

(defun loop-test (n)
  (let ((n 0))
    (loop
      (when (> n 10) (return))
      (format t "~d ~d ~d~%" n (isqrt n) (gauss-formula n))
      ;(print n) (write (* n n)) (write n)
      (incf n))))

;;END COUPLES-3.LISP

\end{lstlisting}

\subsection{couples.c}
\label{couplesc}
\begin{lstlisting}[language=C, basicstyle=\footnotesize]

//COUPLES.C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int even(int x){
	return (!(x % 2));
}

int max(int a, int b){
	if(a > b) 
		return a;
	return b;
}

long int orderedPairToCodeNat(int x, int y){
	long code;
	int sumxy; 
	sumxy = x + y;
	code = ((sumxy)*(sumxy + 1))/2;

	if(even(sumxy)){
		code = code + x;
	}
	else{
		code = code + y; 
	}
	return code;
}

int* codeToOrderedPairNat(long int code){
	int *couple = malloc(2*sizeof(int));
	int n = sqrt(code * 2);
	long int axis = (n * (n + 1))/2;
	int diff = 0;
	if(axis > code){
			n = n - 1;
			axis = (n * (n + 1))/2;
	}
	diff = code - axis;
	if(even(n)){
		couple[0] = diff;
		couple[1] = n - diff;
	}
	else{
		couple[0] = n - diff;
		couple[1] = diff;
	}
	return couple;
}

long int orderedPairToCodeInt(int x, int y){
	long int code = 0;	

	if (x < 0){
		x = (2 * (abs (x))) - 1;
	}
	else{
		x = 2 * x;
	}

	if (y < 0){
		y = (2 * (abs(y))) - 1;
	}
	else{
		y = 2 * y;
	}

	code = orderedPairToCodeNat(x, y);
	return code;
}

int* codeToOrderedPairInt(long int code){
	int *pair = codeToOrderedPairNat(code);

	if (even(pair[0])){
		pair[0] = pair[0] / 2;
	}
	else{
		pair[0] = (pair[0] / 2)*(-1) - 1;
	} 
	
	if (even (pair[1])){
		pair[1] = pair[1] / 2;
	}
	else{
		pair[1] = (pair[1] / 2)*(-1) - 1;
	}

	return pair;
}

long int orderedPairToCodeIntAlgo2(int x, int y){
	long int code = 0;
	int _x, _y, diff;
	_x = _y = diff = 0;
	int temp;
	int absmax;	
	absmax = max(abs(x), abs(y));	
	
	if(absmax == abs(x)){ // _x == x 
		_x = _y = x;
		temp = abs(x) * 2;
		if(x < 0){ // x negative
			code = temp * (temp + 1);
			if(y < 0){ // x negative, y negative
				diff = abs(_y) - abs(y);
			}
			else{ // x negative, y positive
				diff = abs(_y) + abs(y);
			}
		}
		else{ // x positive
			code = (temp - 1) * temp; 
			if(y > 0){ // x positive, y positive
				diff = abs(_y) - abs(y);
			}
			else{ // x positive, y negative
				diff = abs(_y) + abs(y);
			}
		}
		code = code - diff;
	}
	else{ // _y = y
		_x = _y = y;
		temp = abs(y) * 2;
		if(y < 0){ // y negative
			code = temp * (temp + 1);		
			if(x < 0){ // y negative, x negative
				diff = abs(_x) - abs(x);
			}
			else{ // y negative, x positive
				diff = abs(_x) + abs (x);
			}
		}
		else{ // y positive
			code = (temp - 1) * temp;
			if(x > 0){ // y positive, x positive
				diff = abs(_x) - abs(x);
			}
			else{ // y positive, x negative
				diff = abs(_x) + abs(x);
			}	
		}	
		code = code + diff;	
	}
	return code;
}

int* codeToOrderedPairIntAlgo2(long int code){
	int* pair = malloc(2*sizeof(int));
	int isqrtcode = (int) sqrt(code);
	long int pivotcode = isqrtcode * (isqrtcode + 1);
	int x, y;
	x = y = 0;	

	if(even(isqrtcode)){
		x = y = -(isqrtcode / 2);
		if(code > pivotcode){
			x = x + (code - pivotcode);
		}
		else{
			y = y + (pivotcode - code);
		}
	}
	else{
		x = y = (isqrtcode / 2) + 1;
		if(code > pivotcode){
			x = x - (code - pivotcode);
		}
		else{
			y = y - (pivotcode - code); 
		}
	}
	pair[0] = x;
	pair[1] = y; 
	return pair;
}

long int orderedMultipleToCodeNat(int *arr, int size){
	long int code;	
	if(size > 1){
		code = orderedPairToCodeNat(arr[size - 2], arr[size - 1]);
		arr[size - 2] = code;
		arr = realloc(arr, (size - 1));
		if(size > 2){		
			code = orderedMultipleToCodeNat(&arr[0], (size - 1));
		}
	}
	return code;
}

int* codeToOrderedMultipleNat(long int code, int size){
	int *multiple = malloc(size*sizeof(int));
	int *pair;
	int i = 0;
	for(i = 0; i < (size - 1); i++){
		pair = codeToOrderedPairNat(code);
		code = pair[1];
		multiple[i] = pair[0];
		multiple[i + 1] = pair[1];
	}
	return multiple;
}


long int orderedMultipleToCodeInt(int *arr, int size){
	long int code;	
	if(size > 1){
		code = orderedPairToCodeInt(arr[size - 2], arr[size - 1]);
		arr[size - 2] = code;
		arr = realloc(arr, (size - 1));
		if(size > 2){		
			code = orderedMultipleToCodeInt(&arr[0], (size - 1));
		}
	}
	return code;
}

int* codeToOrderedMultipleInt(long int code, int size){
	int *multiple = malloc(size*sizeof(int));
	int *pair;
	int i = 0;
	for(i = 0; i < (size - 1); i++){
		pair = codeToOrderedPairInt(code);
		code = pair[1];
		multiple[i] = pair[0];
		multiple[i + 1] = pair[1];
	}
	return multiple;
}


long int orderedMultipleToCodeIntAlgo2(int *arr, int size){
	long int code = 0;	
	if(size > 1){
		code = orderedPairToCodeIntAlgo2(arr[size - 2], arr[size - 1]);
		arr[size - 2] = code;
		arr = realloc(arr, (size - 1));
		if(size > 2){		
			code = orderedMultipleToCodeIntAlgo2(&arr[0], (size - 1));
		}
	}
	return code;
}

int* codeToOrderedMultipleIntAlgo2(long int code, int size){
	int *multiple = malloc(size*sizeof(int));
	int *pair;
	int i = 0;
	for(i = 0; i < (size - 1); i++){
		pair = codeToOrderedPairIntAlgo2(code);
		code = pair[1];
		multiple[i] = pair[0];
		multiple[i + 1] = pair[1];
	}
	return multiple;
}


void testMultiNat(){
	
	int x = 0;
	int y = 0;
	long int code = 0;
	int *p;
	int size = 0;

	do{		
		printf("\n(NATURAL NUMBERS) testPairInt();Enter a size of a multidimensional array representing a 'ordered multiple': ");
		scanf("%d",&size);
		p = malloc(size * sizeof(int));
		int i;
		for(i = 0; i < size; i++){
			printf("Enter value number %d: ", i);
			scanf("%d", &p[i]);
		}

		code = orderedMultipleToCodeNat(p, size);
		printf("\n... The code is %ld", code);
		printf ("\ncode = ");
		scanf("%ld",&code);
		printf ("\nnumber of ordered elements = ");
		scanf("%d",&size);
		p = codeToOrderedMultipleNat(code, size);
		printf("The ordered multiple identified by code %ld contains the following elements: ", code);
		printf("(");
	
		for(i = 0; i < (size - 1); i++){
			printf("%d, ", p[i]);
		}
		printf("%d)", p[size-1]);
	}
	while(1);
}

void testPairInt(){
	
	int x = 0;
	int y = 0;
	long int code = 0;
	int *p;

	do{		
		p = malloc(2 * sizeof(int));
		int i;
		for(i = 0; i < 2; i++){
			printf("(ORDERED PAIRS INT) Enter value number %d: ", i);
			scanf("%d", &p[i]);
		}

		code = orderedPairToCodeInt(p[0], p[1]);
		printf("\n... The code is %ld", code);
		printf ("\ncode = ");
		scanf("%ld",&code);
		p = codeToOrderedPairInt(code);
		printf("The ordered pair identified by code %ld contains the following elements: ", code);
		printf("(");
	
		for(i = 0; i < 1; i++){
			printf("%d, ", p[i]);
		}
		printf("%d)\n", p[1]);
	}
	while(1);
}

void testMultiInt(){
	
	int x = 0;
	int y = 0;
	long int code = 0;
	int *p;
	int size = 0;

	do{		
		printf("\n(INTEGERS) Enter a size of a multidimensional array representing a 'ordered multiple': ");
		scanf("%d",&size);
		p = malloc(size * sizeof(int));
		int i;
		for(i = 0; i < size; i++){
			printf("Enter value number %d: ", i);
			scanf("%d", &p[i]);
		}

		code = orderedMultipleToCodeInt(p, size);
		printf("\n... The code is %ld", code);
		printf ("\ncode = ");
		scanf("%ld",&code);
		printf ("\nnumber of ordered elements = ");
		scanf("%d",&size);
		p = codeToOrderedMultipleInt(code, size);
		printf("The ordered multiple identified by code %ld contains the following elements: ", code);
		printf("(");
	
		for(i = 0; i < (size - 1); i++){
			printf("%d, ", p[i]);
		}
		printf("%d)", p[size-1]);
	}
	while(1);
}

void testPairIntAlgo2(){
	
	int x = 0;
	int y = 0;
	long int code = 0;
	int *p;

	do{		
		p = malloc(2 * sizeof(int));
		int i;
		
		for(i = 0; i < 2; i++){
			printf("(ORDERED PAIRS INT) Enter value number %d: ", i);
			scanf("%d", &p[i]);
		}

		code = orderedPairToCodeIntAlgo2(p[0], p[1]);
		printf("\n... The code is %ld", code);	

		printf ("\ncode = ");
		scanf("%ld",&code);
		p = codeToOrderedPairIntAlgo2(code);
		printf("The ordered pair identified by code %ld contains the following elements: ", code);
		printf("(");
	
		for(i = 0; i < 1; i++){
			printf("%d, ", p[i]);
		}
		printf("%d)\n", p[1]);
	}
	while(1);
}


void testMultiIntAlgo2(){
	
	int x = 0;
	int y = 0;
	long int code = 0;
	int *p;
	int size = 0;

	do{		
		printf("\n(INTEGERS) Enter a size of a multidimensional array representing a 'ordered multiple': ");
		scanf("%d",&size);
		p = malloc(size * sizeof(int));
		int i;
		for(i = 0; i < size; i++){
			printf("Enter value number %d: ", i);
			scanf("%d", &p[i]);
		}

		code = orderedMultipleToCodeIntAlgo2(p, size);
		printf("\n... The code is %ld", code);
		printf ("\ncode = ");
		scanf("%ld",&code);
		printf ("\nnumber of ordered elements = ");
		scanf("%d",&size);
		p = codeToOrderedMultipleIntAlgo2(code, size);
		printf("The ordered multiple identified by code %ld contains the following elements: ", code);
		printf("(");
	
		for(i = 0; i < (size - 1); i++){
			printf("%d, ", p[i]);
		}
		printf("%d)", p[size-1]);
	}
	while(1);
}




int main(int argc, char **argv, char **envp){
	// testMultiNat();
	// testPairInt();
	// testMultiInt();
	// testPairIntAlgo2();
	 testMultiIntAlgo2();
}


//END COUPLES.C

\end{lstlisting}

\subsection{couple\_entiers.c}
\label{coupleentiersc}
\begin{lstlisting}[language=C, basicstyle=\footnotesize]


//COUPLES_ENTIERS.C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int pair(int x){
	return (!(x % 2));
}

int orderedPairToCode(int x, int y){
	int sumxy, code;
	sumxy = x + y;
	code = ((sumxy)*(sumxy + 1))/2;

	if(pair(sumxy)){
		code = code + x;
	}
	else{
		code = code + y; 
	}
	return code;
}


int* codeToOrderedPair(int code){
	int *couple = malloc(2*sizeof(int));
	int n = sqrt(code * 2);
	int axis = (n * (n + 1))/2;
	int diff = 0;
	if(axis > code){
		while(axis > code){
			n = n - 1;
			axis = (n * (n + 1))/2;
		}
	}
	else if(axis < code){
		while(axis < code){
			n = n + 1;
			axis = (n * (n + 1))/2;
		}
		if(axis > code){
			n = n - 1;
			axis = (n * (n + 1))/2;
		}
	}

	if(axis == code){ // je pense que je peux me dispenser de cet "if", ca revient au meme car diff serait = 0
		if(pair(n)){
			couple[0] = 0;
			couple[1] = n;
		}
		else{
			couple[0] = n;
			couple[1] = 0;
		}
	}
	if(axis != code){ // idem
		diff = code - axis;
		if(pair(n)){
			couple[0] = diff;
			couple[1] = n - diff;
		}
		else{
			couple[0] = n - diff;
			couple[1] = diff;
		}
	}
	return couple;
}

int	orderedMultipleToCode(int *arr, int size){
	int code;	
	if(size > 1){
		code = orderedPairToCode(arr[size - 2], arr[size - 1]);
		arr[size - 2] = code;
		arr = realloc(arr, (size - 1));
		if(size > 2){		
			code = orderedMultipleToCode(&arr[0], (size - 1));
		}
	}
	return code;
}

int* codeToOrderedMultiple(int code, int size){
	int *multiple = malloc(size*sizeof(int));
	int *pair;
	int i = 0;
	for(i = 0; i < (size - 1); i++){
		pair = codeToOrderedPair(code);
		code = pair[1];
		multiple[i] = pair[0];
		multiple[i + 1] = pair[1];
	}
	return multiple;
}


int main(int argc, char **argv, char **envp){

	int x = 0;
	int y = 0;
	int code = 0;
	int *p;
	int size = 0;

	do{
	/*
		printf ("\nx = ");
		scanf("%d",&x);
		printf ("y = ");
		scanf("%d",&y);
		code = orderedPairToCode(x, y);
		printf("Le code du couple (%d, %d) est %d\n", x, y, code);

		printf ("\ncode = ");
		scanf("%d",&code);
		p = codeToOrderedPair(code);
		printf("The ordered pair identified by code %d is (%d, %d)", code, p[0], p[1]);
	
*/			
		printf("\nEnter a size of a multidimensional array representing a 'ordered multiple': ");
		scanf("%d",&size);
		p = malloc(size * sizeof(int));
		int i;
		for(i = 0; i < size; i++){
			printf("Enter value number %d: ", i);
			scanf("%d", &p[i]);
		}

		code = orderedMultipleToCode(p, size);
		printf("\n... The code is %d", code);
	


		printf ("\ncode = ");
		scanf("%d",&code);
		printf ("\nnumber of ordered elements = ");
		scanf("%d",&size);
		p = codeToOrderedMultiple(code, size);
		printf("The ordered multiple identified by code %d contains the following elements: ", code);
		printf("(");
		for(i = 0; i < (size - 1); i++){
			printf("%d, ", p[i]);
		}
		printf("%d)", p[size-1]);


	}
	while(code != -1);
}

//END COUPLES_ENTIERS.C
\end{lstlisting}
\newpage
\section{Annexe~: Exercice 5}
\label{annexeexo5}
\includepdf[pages=-]{exo5}

\end{document}