\documentclass[semlcmss,sem-a4]{seminar}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{../include/mon-seminar}
\input{../include/mon-color}
\input{../include/mon-dvipdf}
\usepackage{eurosym}
\usepackage{superpose}
\usepackage{colortbl}


\usepackage{hyperref}
% \usepackage {pstcol,color,pst-node}
\usepackage{advi}
\usepackage{advi-annot}
\usepackage{advi-graphicx}
\usepackage{superpose}

\newcommand{\urlter}[3]{\advirecord{#1}{%
\adviembed[name=netscape; height=0mm]{%
netscape -remote openFile(#2)}}%
\advianchor[click]{#1}{#3}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\newif\ifFrenchItemizeSpacing \FrenchItemizeSpacingfalse
%hevea \bfseries\blueSky
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\WHILE}{\mbox{\sf\colorKeyword while}\;}
\newcommand{\DO}{\;\mbox{\sf\colorKeyword do}\;}
\newcommand{\AND}{\;\mbox{\sf\colorKeyword and}\;}
\newcommand{\OR}{\;\mbox{\sf\colorKeyword or}\;}
\newcommand{\WAIT}{\;\mbox{\sf\colorKeyword wait}\;}
\newcommand{\IF}{\;\mbox{\sf\colorKeyword if}\;}
\newcommand{\THEN}{\;\mbox{\sf\colorKeyword then}\;}
\newcommand{\ELSE}{\;\mbox{\sf\colorKeyword else}\;}
\newcommand{\BEGIN}{\;\mbox{\sf\colorKeyword begin}\;}
\newcommand{\END}{\;\mbox{\sf\colorKeyword end}\;}
\newcommand{\pair}[2]{\langle #1,\; #2 \rangle}
\newcommand{\SKIP}{\mbox{\sf\colorKeyword skip}\;}
\newcommand{\TRUE}{\mbox{\sf\colorKeyword true}\;}
\newcommand{\FALSE}{\mbox{\sf\colorKeyword false}\;}
\newcommand{\AWAIT}{\mbox{\sf\colorKeyword await}\;}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\turn}{\mbox{\em turn}}
\newcommand{\ass}{:=}
\newcommand{\para}{\mid\mid}
\newcommand{\tab}[3]{\multicolumn{#1}{l}{}&
                     \multicolumn{#2}{l}{{#3}}}
\newcommand{\pic}{$\pi$-calculus}
\newcommand{\acquire}{\mathop{\mathit{acquire}}}
\newcommand{\release}{\mathop{\mathit{release}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\assert}[1]{{\orchidBis \{#1\}}}
\newcommand{\actif}{\mathop{\it actif}}
\newcommand{\tour}{\mathop{\it turn}}
\newcommand{\CO}{\mathit{c}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bfseries
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\begin{center}
{\blueBis \huge \bf Concurrency 1 \\[1ex]
\colorbox{monyellow}{Shared Memory}\\[.3ex]
}
\bigskip
{\red Jean-Jacques Lévy (INRIA - Rocq)}\\[2ex]


% {\small\ahref{http://jeanjacqueslevy.net/dea}{jeanjacqueslevy.net/dea}}\\[2ex]

\small
{\blueBis MPRI concurrency course with:}\\[1ex]
Pierre-Louis Curien (PPS)\\
Eric Goubault (CEA)\\
James Leifer (INRIA - Rocq)\\
Catuscia Palamidessi (INRIA - Futurs)

\end{center}

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\centerslidesfalse
\begin{slide}{}
\heading{ Why concurrency?}

\begin{enumerate}
\item Programs for multi-processors
\item Drivers for slow devices
\item Human users are concurrent
\item Distributed systems with multiple clients
\item Reduce lattency
\item Increase efficiency, but Amdahl's law\\
$$ S= {N \over b*N + (1-b)} $$ 
($S = \mbox{speedup}$, $b = \mbox{sequential part}$, $N$ processors)

\end{enumerate}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{MPRI concurrency course}

\renewcommand{\arraystretch}{.9}

\bigskip
\begin{tabular}{llll}
09-30 &JJL& shared memory  {\quad\tiny atomicity, SOS}\\
10-07 &JJL& shared memory  {\quad\tiny readers/writers, 5 philosophers}\\
{\red 10-12} &PLC& CCS {\quad\tiny choice, strong bisim.}\\
10-21 &PLC& CCS {\quad\tiny weak bisim., examples}\\
10-28 &PLC& CCS {\quad\tiny obs.~equivalence, Hennessy-Milner logic}\\
11-04 &PLC& CCS {\quad\tiny examples of proofs}\\
{\red 11-16} &JL& \pic {\quad\tiny syntax, lts, examples, strong bisim.}\\
11-25 &JL& \pic {\quad\tiny red.~semantics, weak bisim., congruence}\\
12-02 &JL& \pic {\quad\tiny extensions for mobility}\\
12-09 &JL/CP& \pic {\quad\tiny encodings: $\lambda$-calculus, arithm., lists}\\
12-16 &CP& \pic {\quad\tiny expressivity}\\
01-06 &CP& \pic {\quad\tiny stochastic models}\\
01-13 &CP& \pic {\quad\tiny security}\\
01-20 &EG& true concurrency {\quad\tiny concurrency and causality}\\
01-27 &EG& true concurrency {\quad\tiny Petri nets, events struct., async. trans.}\\
02-03 &EG& true concurrency {\quad\tiny other models}\\
02-10 &all& exercices \\
02-17 &  & exam
\end{tabular}

\url{http://pauillac.inria.fr/~leifer/teaching/mpri-concurrency-2004/}


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Concurrency $\Rightarrow$ non-determinism}

Suppose $x$ is a global variable. 
At beginning, $x=0$

Consider\\[1ex]
 $S = [x \ass 1; ]$\\
 $T = [x \ass 2; ]$

After $S\para T$, then $x \in \{1,2\}$ 

\bigskip\bigskip

Conclusion:\\[1ex]

Result is not unique.

Concurrent programs are not described by functions.



\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Implicit Communication}

Suppose $x$ is a global variable. 
At beginning, $x=0$

Consider\\[1ex]
 $S = [x \ass x+1; x \ass x+1  \para x\ass 2*x]$             \\ \\
 $T = [x \ass x+1; x \ass x+1  \para \WAIT (x=1); x\ass 2*x ]$\\

After $S$, then $x \in \{2,3,4\}$ \\
After $T$, then $x \in \{3,4\}$ \\
$T$ may be blocked

\bigskip\bigskip

Conclusion

In $S$ and $T$, interaction via $x$ \\



\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Input-output behaviour}

Suppose $x$ is a global variable. 

Consider\\[1ex]
 $S = [x \ass 1 ]$             \\ 
 $T = [x \ass 0; x \ass x+1 ]$

$S$ and $T$ same functions on memory state.

\bigskip
But
 $S \para S$ and 
 $T \para S$ are
different ``functions'' on memory state.

$\Rightarrow$ Interaction is important.

\bigskip

A process is an ``atomic'' action, followed by a process. Ie.
%
$$\mathcal{P} \simeq \mathop{\mathit{Null}} \;+\;
  2^{\mathop{\mathit{action}} \times \mathcal{P}}$$

\bigskip
Part of the concurrency course gives sense to this equation.

\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Atomicity}

Suppose $x$ is a global variable. 
At beginning, $x=0$

Consider\\[1ex]
 $S = [x \ass x+1 \para x \ass x+1]$           

After $S$, then $x=2$.

\bigskip

However if\\[1ex]
$[x \ass x+1]$ compiled into $[A \ass x+1; x \ass A]$

\bigskip

Then \\
$S = [A \ass x+1; x \ass A] \para [B \ass x+1; x \ass B]$

After $S$, then $x \in \{1,2\}$.

\bigskip\bigskip

Conclusion
\begin{enumerate}
\item $[x \ass x+1]$ was firstly considered atomic
\item Atomicity is important
\end{enumerate}

\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Critical section -- Mutual exclusion}

Let
$P_0 = [\cdots; C_0; \cdots]$ and
$P_1 = [\cdots; C_1; \cdots]$

$C_0$ and $C_1$ are critical sections (ie should not be executed
simultaneously). 

\bigskip

{\bf Solution 1}
At beginning, $\turn = 0$.

\begin{tabular}{l@{\hspace{7em}}l}
\begin{lstlisting}{}
P0 : `$\cdots$`  
  while turn != 0 do
    ;
  `$C_0$`; 
  turn := 1;
  `$\cdots$`  
\end{lstlisting}
&
\begin{lstlisting}{}
P1 : `$\cdots$`  
  while turn != 1 do
    ;
  `$C_1$`; 
  turn := 0;
  `$\cdots$`  
\end{lstlisting}

\end{tabular}

\adviwait
$P_0$ privileged, unfair.

\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Critical section -- Mutual exclusion}


{\bf Solution 2}
At beginning, $a_0 = a_1 = \FALSE$.

\begin{tabular}{l@{\hspace{7em}}l}
\begin{lstlisting}{}
P0 : `$\cdots$`  
  while a1 do
    ;
  a0 := true;
  `$C_0$`; 
  a0 := false;
  `$\cdots$`  
\end{lstlisting}
&
\begin{lstlisting}{}
P1 : `$\cdots$`  
  while a0 do
    ;
  a1 := true;
  `$C_1$`; 
  a1 := false;
  `$\cdots$`  
\end{lstlisting}

\end{tabular}

\adviwait
False.

\adviwait
{\bf Solution 3}
At beginning,  $a_0 = a_1 = \FALSE$.

 
\begin{tabular}{l@{\hspace{7em}}l}
\begin{lstlisting}{}
P0 : `$\cdots$`  
  a0 := true;
  while a1 do
    ;
  `$C_0$`; 
  a0 := false;
  `$\cdots$`  
\end{lstlisting}
&
\begin{lstlisting}{}
P1 : `$\cdots$`  
  a1 := true;
  while a0 do
    ;
  `$C_1$`; 
  a1 := false;
  `$\cdots$`  
\end{lstlisting}
\end{tabular}

\adviwait
Deadlock. Both $P_0$ and $P_1$ blocked.


\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Dekker's Algorithm (CACM 1965)}

At beginning, $a_0 = a_1 = \FALSE$, $\mathtt{turn}\in\{0,1\}$\\[1ex]

\begin{tabular}{l@{\hspace{7em}}l}
\begin{lstlisting}{}
P0 : `$\cdots$`  
  a0 := true;
  while a1 do
    if turn != 0 begin
      a0 := false; 
      while turn != 0 do
        ;
      a0 := true;
    end;
  `$C_0$`; 
  turn := 1; a0 := false;
  `$\cdots$`  
\end{lstlisting}
&
\begin{lstlisting}{}
P1 : `$\cdots$`  
  a1 := true;
  while a0 do
    if turn != 1  begin
      a1 := false; 
      while turn != 1 do
        ;
      a1 := true;
    end;
  `$C_1$`; 
  turn := 0; a1 := false;
  `$\cdots$`  
\end{lstlisting}

\end{tabular}

\bigskip\adviwait
\exercice Trouver Dekker pour $n$ processus {\red [Dijkstra 1968]}.
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Peterson's Algorithm (IPL June 81) {\tiny (1/5)}}

At beginning, $a_0 = a_1 = \FALSE$, $\mathtt{turn}\in\{0,1\}$\\[1ex]

\begin{tabular}{l@{\hspace{7em}}l}
\begin{lstlisting}{}
P0 : `$\cdots$`  
  a0 := true;
  turn := 1;
  while a1 && turn != 0 do
    ;
  `$C_0$`; 
  a0 := false;
  `$\cdots$`  
\end{lstlisting}
&
\begin{lstlisting}{}
P1 : `$\cdots$`  
  a1 := true;
  turn := 0;
  while a0 && turn != 1 do
    ;
  `$C_1$`; 
  a0 := false;
  `$\cdots$`  
\end{lstlisting}

\end{tabular}


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Peterson's Algorithm (IPL June 81) {\tiny (2/5)}}




$\CO_0$, $\CO_1$ program counters for $P_0$ and $P_1$.\\
At beginning $\CO_0 = \CO_1 = 1$

\bigskip

\begin{tabular}{@{\hspace{0ex}}l@{\hspace{7em}}l}
\begin{lstlisting}{}
     `$\cdots$`  
     `$\assert{\neg a_0 \wedge \CO_0\neq 2 }$`
`\scriptsize 1`    a0 := true; c0 := 2;
     `$\assert{a_0 \wedge \CO_0 = 2}$`
`\scriptsize 2`    turn := 1; c0 := 1;
     `$\assert{a_0 \wedge \CO_0 \neq 2}$`
`\scriptsize 3`    while a1 && turn != 0 do
`\scriptsize .`      ;
     `$\assert{a0 \wedge \CO_0\neq 2 \wedge (\neg a_1 \vee \tour = 0 \vee \CO_1 = 2)}$`
`\scriptsize .`    `$C_0$`; 
`\scriptsize 5`    a0 := false;
     `$\assert{\neg a_0\wedge \CO_0\neq 2}$`
     `$\cdots$`  
\end{lstlisting}
&
\begin{lstlisting}{}
`$\cdots$`  
`$\assert{\neg a_1 \wedge \CO_1\neq 2 }$`
a1 := true; c1 := 2;
`$\assert{a_1 \wedge \CO_1 = 2}$`
turn := 0; c1 := 1;
`$\assert{a_1 \wedge \CO_1 \neq 2}$`
while a0 && turn != 1 do
  ;
`$\assert{a1 \wedge \CO_1\neq 2 \wedge (\neg a_1 \vee \tour = 1 \vee \CO_0 = 2)}$`
`$C_1$`; 
a1 := false;
`$\assert{\neg a_1\wedge \CO_1\neq 2}$`
`$\cdots$`  
\end{lstlisting}

\end{tabular}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Peterson's Algorithm (IPL June 81) {\tiny (3/5)}}

\adviwait
$$\begin{array}{ll}
& (\tour = 0 \vee \tour = 1)  \\
\adviwait
\wedge & a_0 \;\wedge\; \CO_0\neq 2 \;\wedge\; (\neg a_1 \vee \tour = 0 \vee \CO_1 = 2) 
\wedge  a_1 \;\wedge\; \CO_1\neq 2 \;\wedge\; (\neg a_0 \vee \tour = 1 \vee \CO_0 = 2) \\
\adviwait
\equiv &
(\tour = 0 \vee \tour = 1)  \wedge tour = 0 \wedge tour = 1
\quad\quad\mbox{Impossible}
\end{array}
$$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Peterson's Algorithm (IPL June 81) {\tiny (4/5)}}



$\CO_0$, $\CO_1$ program counters for $P_0$ and $P_1$.\\
At beginning $\CO_0 = \CO_1 = 1$

\bigskip

\begin{tabular}{@{\hspace{0ex}}l@{\hspace{7em}}l}
\begin{lstlisting}{}
     `$\cdots$`  
     `$\assert{\neg a_0 \wedge \CO_0\neq 2 }$`
`\scriptsize 1`    a0 := true; c0 := 2;
     `$\assert{a_0 \wedge \CO_0 = 2}$`
`\scriptsize 2`    turn := 1; c0 := 1;
     `$\assert{a_0 \wedge \CO_0 \neq 2}$`
`\scriptsize 3`    while a1 && turn != 0 do
`\scriptsize .`      ;
     `$\assert{a0 \wedge \CO_0\neq 2 \wedge (\neg a_1 \vee \tour = 0 \vee \CO_1 = 2)}$`
`\scriptsize .`    `$C_0$`; 
`\scriptsize 5`    a0 := false;
     `$\assert{\neg a_0\wedge \CO_0\neq 2}$`
     `$\cdots$`  
\end{lstlisting}
&
\begin{lstlisting}{}
`$\cdots$`  
`$\assert{\neg a_1 \wedge \CO_1\neq 2 }$`
a1 := true; c1 := 2;
`$\assert{a_1 \wedge \CO_1 = 2}$`
turn := 0; c1 := 1;
`$\assert{a_1 \wedge \CO_1 \neq 2}$`
while a0 && turn != 1 do
  ;
`$\assert{a1 \wedge \CO_1\neq 2 \wedge (\neg a_1 \vee \tour = 1 \vee \CO_0 = 2)}$`
`$C_1$`; 
a1 := false;
`$\assert{\neg a_1\wedge \CO_1\neq 2}$`
`$\cdots$`  
\end{lstlisting}

\end{tabular}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Peterson's Algorithm (IPL June 81) {\tiny (5/5)}}

\adviwait
$$\begin{array}{ll}
& (\tour = 0 \vee \tour = 1)  \\
\adviwait
\wedge & a_0 \;\wedge\; \CO_0\neq 2 \;\wedge\; (\neg a_1 \vee \tour = 0 \vee \CO_1 = 2) 
\wedge  a_1 \;\wedge\; \CO_1\neq 2 \;\wedge\; (\neg a_0 \vee \tour = 1 \vee \CO_0 = 2) \\
\adviwait
\equiv &
(\tour = 0 \vee \tour = 1)  \wedge tour = 0 \wedge tour = 1
\quad\quad\mbox{Impossible}
\end{array}
$$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Synchronization}

Concurrent/Distributed algorithms

\bigskip

\begin{enumerate}
\item Lamport: barber, baker, \ldots
\item Dekker's algorithm for $P_0$, $P_1$, $P_N$ (Dijsktra 1968)
\item Peterson is simpler and can be generalised to $N$ processes
\item Proofs ? By model checking ?
With assertions ? In temporal logic (eg Lamport's TLA)?
\item Dekker's algorithm is too complex
\item Dekker's algorithm uses busy waiting
\item Fairness acheived because of fair scheduling
\end{enumerate}

\bigskip

Need for higher constructs in concurrent programming.

\bigskip
\exercice Try to define fairness.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Semaphores}

A {\DarkOrange generalised semaphore} $s$ is integer variable with 2
operations

$\acquire(s)$: If $s > 0$ then $s \ass s-1$\\
Otherwise be suspended on $s$. 

$\release(s)$: If some process is suspended on $s$, wake it up\\
Otherwise $s \ass s+1$.

\bigskip

\adviwait
Now mutual exclusion is easy:

At beginning, $s = 1$. Then 
$$[\cdots; \acquire(s) ;\; A; \; \release(s); \cdots] \;\para\;
 [\cdots; \acquire(s) ;\; B; \; \release(s); \cdots]$$

\bigskip
\adviwait
\exercice Other definition for semaphore:\\
\begin{tabular}{l}
$\acquire(s)$: If $s > 0$ then $s \ass s-1$. Otherwise restart. \\
$\release(s)$: Do $s \ass s+1$. \\
\end{tabular}

Are these definitions equivalent?
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Operational semantics (seq.~part)}

Language
$$
\begin{array}{rcl}
P,Q &::=& \SKIP \mid x \ass e \mid 
\IF b \THEN P \ELSE Q \mid P;Q \mid 
   \WHILE b \DO P \mid \bullet \\
e &::=& \mbox{expression}
\end{array}
$$

\medskip

\adviwait
Semantics (SOS)
$$
\begin{array}{c@{\hspace{2em}}c}
\pair{\SKIP}{\sigma} \arr \pair{\bullet}{\sigma} &

\pair{x \ass e}{\sigma} \arr \pair{\bullet}{\sigma[\sigma(e)/x]} \\[3ex]

\infrule{\sigma(e) = \TRUE}{
     \pair{\IF e \THEN P \ELSE Q}{\sigma} \arr \pair{P}{\sigma}}
&
\infrule{\sigma(e) = \FALSE}{
     \pair{\IF e \THEN P \ELSE Q}{\sigma} \arr \pair{Q}{\sigma}} \\[3ex]


\infrule{\pair{P}{\sigma} \arr \pair{P'}{\sigma'}}{
   \pair{P;Q}{\sigma} \arr \pair{P';Q}{\sigma'}}\;\;(P' \neq \bullet)
&
\infrule{\pair{P}{\sigma} \arr \pair{\bullet}{\sigma'}}{
   \pair{P;Q}{\sigma} \arr \pair{Q}{\sigma'}} \\[3ex]

\infrule{\sigma(e) = \TRUE}{
     \pair{\WHILE e \DO P}{\sigma} \arr 
     \pair{P;\WHILE e \DO P}{\sigma}}
&
\infrule{\sigma(e) = \FALSE}{
     \pair{\WHILE e \DO P}{\sigma} \arr 
     \pair{\bullet}{\sigma}}
\end{array}
$$
\bigskip

$\sigma \in \mbox{Variables} \mapsto \mbox{Values}$ \hfill
$\sigma[v/x](x) = v$ \hfill
$\sigma[v/x](y) = \sigma(y)$ if $y \neq x$


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Operational semantics (parallel part)}

Language
$$
P,Q ::= \ldots \mid P \para Q \mid \WAIT b \mid \AWAIT b \DO P
$$

\bigskip

\adviwait
Semantics (SOS)


$$
\begin{array}{c@{\hspace{2em}}c}
\infrule{\pair{P}{\sigma} \arr \pair{P'}{\sigma'}}{
   \pair{P \para Q}{\sigma} \arr \pair{P' \para Q}{\sigma'}}
&
\infrule{\pair{Q}{\sigma} \arr \pair{Q'}{\sigma'}}{
   \pair{P \para Q}{\sigma} \arr \pair{P \para Q'}{\sigma'}}\\[3ex]

\pair{\bullet \para \bullet}{\sigma} \arr \pair{\bullet}{\sigma}
& \\[3ex]
\infrule{\sigma(e) = \TRUE}{
     \pair{\WAIT e}{\sigma} \arr \pair{\bullet}{\sigma}}

&
\infrule{\sigma(e) = \TRUE \quad
          \pair{P}{\sigma} \arr \pair{P'}{\sigma'}}{
     \pair{\AWAIT e \DO P}{\sigma} \arr \pair{P'}{\sigma'}}

\end{array}
$$

\bigskip


\adviwait
\exercice Complete SOS for $e$ and $v$\\
\exercice Find SOS for boolean semaphores.\\
\exercice Avoid spurious silent steps in $\IF$, $\WHILE$ and $\para$.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{SOS reductions}

Notations
$$
\pair{P_0}{\sigma_0} \arr
\pair{P_1}{\sigma_1} \arr
\pair{P_2}{\sigma_2} \arr
\cdots
\pair{P_n}{\sigma_n} \arr
$$

We write \\[1ex]
\begin{tabular}{l}
$\pair{P_0}{\sigma_0} \arr^* \pair{P_n}{\sigma_n}$ when $n \geq 0$,\\
$\pair{P_0}{\sigma_0} \arr^+ \pair{P_n}{\sigma_n}$ when $n > 0$.
\end{tabular}

\bigskip\bigskip

Remark that in our system, we have no rule such as


$$\infrule{\sigma(e) = \FALSE}{
     \pair{\WAIT e}{\sigma} \arr \pair{\WAIT b}{\sigma}}$$

Ie no busy waiting. Reductions may block.
(Same remark for $\AWAIT e \DO P$).

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Atomic statements (Exercices)}

\exercice If we make following extension
$$
P,Q ::= \ldots \mid \{ P \}
$$
what is the meaning of following rule?
$$\infrule{\pair{P}{\sigma} \arr^+ \pair{\bullet}{\sigma'}}{
\pair{\{P\}}{\sigma} \arr \pair{\bullet}{\sigma'}}$$


\bigskip
\exercice Show   $\AWAIT e \DO P  \equiv \{\WAIT e; P \}$

\bigskip
\exercice Code generalized semaphores in our language.

\bigskip
\exercice Meaning of $\{\WHILE \TRUE \DO \SKIP\}$  ?
Find simpler equivalent statement.

\bigskip
\exercice Try to add procedure calls to our SOS semantics.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Producer - Consumer}



\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\heading{A typical thread package. Modula-3}

\begin{verbatim}
INTERFACE Thread;

TYPE
  T <: ROOT;
  Mutex = MUTEX;
  Condition <: ROOT;
\end{verbatim}

A Thread.T is a handle on a thread. A Mutex is
locked by some thread, or unlocked. A Condition
is a set of waiting threads. A newly-allocated
Mutex is unlocked; a newly-allocated Condition
is empty. It is a checked runtime error to pass
the NIL Mutex, Condition, or T to any procedure
in this interface.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}\small

\begin{verbatim}
PROCEDURE Acquire(m: Mutex);
\end{verbatim}
       Wait until m is unlocked and then
       lock it.

\begin{verbatim}
PROCEDURE Release(m: Mutex);
\end{verbatim}
       The calling thread must have m
       locked. Unlocks m.

\adviwait
\begin{verbatim}
PROCEDURE Wait(m: Mutex; c: Condition);
\end{verbatim}

       The calling thread must have m
       locked. Atomically unlocks m and
       waits on c. Then relocks m and
       returns.

\begin{verbatim}
PROCEDURE Signal(c: Condition);
\end{verbatim}
       One or more threads waiting on c
       become eligible to run.

\adviwait
\begin{verbatim}
PROCEDURE Broadcast(c: Condition);
\end{verbatim}
       All threads waiting on c become
       eligible to run.


\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}\small
\heading{Locks}

A LOCK statement has the form: 

\begin{verbatim}
    LOCK mu DO S END
\end{verbatim}

where S is a statement and mu is an
expression. It is equivalent to:

\begin{verbatim}
    WITH m = mu DO
      Thread.Acquire(m);
      TRY S FINALLY Thread.Release(m) END
    END
\end{verbatim}

where m stands for a variable that does
not occur in S.

\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Try Finally}

A statement of the form: 
\begin{verbatim}
    TRY S_1 FINALLY S_2 END
\end{verbatim}

executes statement $S_1$ and then
statement $S_2$. If the outcome of $S_1$ is
normal, the TRY statement is equivalent
to $S_1$;$S_2$. If the outcome of $S_1$ is an
exception and the outcome of $S_2$ is
normal, the exception from $S_1$ is
re-raised after $S_2$ is executed. If both
outcomes are exceptions, the outcome of
the TRY is the exception from $S_2$.


\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Concurrent stack}

Popping in a stack:

\begin{verbatim}
VAR nonEmpty := NEW(Thread.Condition);

LOCK m DO
    WHILE p = NIL DO Thread.Wait(m, nonEmpty) END;
    topElement := p.head;
    p := p.next;
END;
return topElement;
\end{verbatim}

Pushing into a stack:

\begin{verbatim}
LOCK m DO
    p = newElement(v, p);
    Thread.Signal (nonEmpty);
END;
\end{verbatim}

\bigskip
Caution: \verb+WHILE+ is safer than \verb+IF+ in Pop.


\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Concurrent table}


\begin{verbatim}
VAR table := ARRAY [0..999] of REFANY {NIL, ...};
VAR i:[0..1000] := 0;

PROCEDURE Insert (r: REFANY) =
  BEGIN
    IF r <> NIL THEN

        table[i] := r;
        i := i+1;

  END;
END Insert;
\end{verbatim}

\bigskip
\exercice Complete previous program to avoid lost values.


\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Deadlocks}

Thread $A$ locks mutex $m_1$\\
Thread $B$ locks mutex $m_2$\\
Thread $A$ trying to lock $m_2$\\
Thread $B$ trying to lock $m_1$

\bigskip
\bigskip

Simple stragegy for semaphore controls
\bigskip

Respect a partial order between semaphores. For example, $A$ and $B$
uses $m_1$ and $m_2$ in same order.


\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Conditions and semaphores}

Semaphores are stateful; conditions are stateless.\\[.2ex]

\begin{center}
\begin{tabular}{l@{\hspace{8em}}l}
\begin{lstlisting}{}
Wait (m, c) :
  `$\release$`(m);
  `$\acquire$`(c-sem);
  `$\acquire$`(m);
\end{lstlisting}
&
\begin{lstlisting}{}
Signal (c) :
  `$\release$`(c-sem);
   ` `
    ` `
\end{lstlisting}
\end{tabular}
\end{center}

\bigskip
\exercice Is this translation correct?

\exercice What happens in {\tt Wait} and {\tt Signal} if
it does not atomically unlock $m$ and wait on $c$.

\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}
\heading{Exercices}

\exercice Readers and writers. A buffer may be read by several processes at
same time. But only one process may write in it. Write procedures
StartRead, EndRead, StartWrite, EndWrite.

\bigskip
\exercice Give SOS for operations on conditions.

\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



 \end{document}












\begin{slide}
\heading{Objectifs de INF 431}
\small

\begin{enumerate}
\item Principes de la Programmation (2ème partie)
\item Structures de données (2ème partie)
\item Modularité -- Programmation par objets
\item Concurrence
\item Initiation à l'informatique scientifique
\end{enumerate}

\bigskip
\heading{Format du cours}

\begin{enumerate}
\item Début encadré (Amphi $+$ Petite Classe $+$ TD)
\item Milieu (Amphi $+$ Petite Classe $+$ Devoir maison)
\item Fin (Amphi $+$ Projet informatique)
\item Notation (CC 4h $+$ Projet; 2 DMs)
\end{enumerate}

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Plan}
\small

\begin{enumerate}
\item Files d'attente
\item Piles
\item Graphes 
\item Représentation des graphes
\item Parcours en profondeur d'abord
\item Parcours en largeur d'abord
\item Arbres de recouvrement
\item Connexité et sortie de labyrinthe
\end{enumerate}



\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Files d'attente}
\small


\begin{center}
\epsfig{file=fig/fifo.eps,scale=.4}
\end{center}

Deux représentations. Dans un tableau (tampon circulaire).
\begin{center}
\epsfig{file=fig/fifo1.eps,scale=.4}

\epsfig{file=fig/fifo2.eps,scale=.4}
\end{center}

ou par une liste.

\begin{center}
\epsfig{file=fig/fifo3.eps,scale=.4}
\end{center}




\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Files d'attente représentée par un tampon circulaire}
\small

Premier arrivé, premier servi ({\em {\red First In, First Out}}). Structure de
données très fréquente dans les programmes: par exemple dans les OS,
le {\em hardware}, le temps-réel, etc.

Une première méthode compacte consiste à gérer un {\orchidBis tampon
circulaire.}

\bigskip

\begin{lstlisting}{}
class FIFO {
  int               debut, fin;
  boolean           pleine, vide;
  int[ ]            contenu;    

  FIFO (int n) {
    debut = 0; fin = 0; pleine = n == 0; vide = true;
    contenu = new int[n];
  } 
\end{lstlisting}

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{File d'attente représentée par un tampon circulaire}
\small

\begin{lstlisting}{}
  static void ajouter (FIFO f, int x) {
    if (f.pleine)
        throw new Error ("File Pleine.");
    f.contenu[f.fin] = x;
    f.fin = (f.fin + 1) % f.contenu.length;
    f.vide = false; f.pleine = f.fin == f.debut;
  }

  static int supprimer (FIFO f) {
    if (f.vide)
        throw new Error ("File Vide.");
    int res = f.contenu[f.debut];
    f.debut =  (f.debut + 1) % f.contenu.length;
    f.vide = f.fin == f.debut; f.pleine = false;
    return res;
  }
\end{lstlisting}

Belle symétrie. Complexité en $O(1)$.

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Rappel de notions de Java}
\small

Un programme de test avec la taille, les éléments à ajouter, ou les
ordres de suppression, comme arguments successifs de la
ligne de commande.
\medskip

\begin{lstlisting}{}
  public static void main (String[ ] args) {
    int n = Integer.parseInt (args[0]);
    FIFO f = new FIFO (n);
    for (int i = 1; i < args.length; ++i) 
      if (args[i].equals ("-") )
        System.out.println (supprimer(f));
      else {
        int x = Integer.parseInt (args[i]);
        ajouter (f, x);
      }
  }
\end{lstlisting}

Exécution: file de taille $10$.

\begin{lstlisting}{}
% javac FIFO.java
% java FIFO 10 3 4 5 - - 7 8 - - 9
3
4
5
7
\end{lstlisting}
\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}[21.5cm,16.5cm]
\heading{File d'attente représentée par une liste}
\small

\begin{lstlisting}{}
class FIFO {
  Liste debut, fin;
  FIFO () { debut = null; fin = null; } 

  static void ajouter (FIFO f, int x) {
    if (f.fin == null) f.debut = f.fin = new Liste (x);
    else {
      f.fin.suivant = new Liste (x);
      f.fin = f.fin.suivant;
    }
  }

  static int supprimer (FIFO f) {
    if (f.debut == null) throw new Error ("File Vide.");
    else {
      int res = f.debut.val;
      if (f.debut == f.fin)  f.debut = f.fin = null;
      else f.debut = f.debut.suivant;
      return res;
    }
  }
\end{lstlisting}

Taille non bornée. Complexité en $O(1)$.

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Piles}
\small


\begin{center}
\epsfig{file=fig/pile.eps,scale=.4}
\end{center}

Deux représentations. Dans un tableau
\begin{center}
\epsfig{file=fig/pile1.eps,scale=.4}
\end{center}

ou par une liste.

\begin{center}
\epsfig{file=fig/pile2.eps,scale=.4}
\end{center}




\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Pile représentée par un tableau}
\small \medskip

Une pile correspond à la stratégie LIFO ({\red Last In, First
Out}). 
\medskip

\begin{lstlisting}{}
class Pile {
  int      hauteur ;
  int[ ]   contenu;
  Pile (int n)  {hauteur = 0; contenu = new int[n]; }

  static void empiler (int x, Pile p) {
    if (p.hauteur >= p.contenu.length)
      throw new Error ("Pile pleine.");
    p.contenu[p.hauteur++] = x;
  }

  static int depiler (Pile p) {
    if (p.hauteur <= 0) 
      throw new Error ("Pile vide.");
    return p.contenu [--p.hauteur];
  }
\end{lstlisting}

Complexité en $O(1)$.

\end{slide}
\blueSky

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Pile représentée par une liste}
\small \medskip

\begin{lstlisting}{}
class Pile {
  Liste sommet;
  Pile () { sommet = null; }

  static void empiler (int x, Pile p) {
    p.sommet = new Liste (x, p.sommet);
  }

  static int depiler (Pile p) {
    if (p.sommet == null) throw new Error ("Pile vide.");
    int res = p.sommet.val;
    p.sommet = p.sommet.suivant;
    return res;
  }
\end{lstlisting}

Taille non bornée. Complexité en $O(1)$.

\bigskip

Une des lois fondamentales de l'informatique:

{\red\large Récursif $=$ Itératif $+$ Pile}

(Randell et Russel, 1960 $\Rightarrow$ premier compilateur).

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Graphe}
\medskip\small

Un graphe $G=(V,E)$ a un ensemble de {\red sommets} $V$ et 
d'{\red arcs} $E\subset V \times V$. Un arc $e=(v_1,v_2)$ a pour
origine $\mathit{org}(e) = v_1$ et pour extrémité $\mathit{ext}(e) =
v_2$.

Exemples: les rues de Paris, le plan du métro.

$G=(V,E)$ est un graphe non {\orchidBis orienté} ssi $(v_1,v_2) \in E$
implique $(v_2,v_1) \in E$. Par exemple, les couloirs de l'X.

Un {\orchidBis chemin} est une suite d'arcs $e_1$, $e_2$, \dots $e_n$,
telle que $\mathit{ext}(e_{i}) = \mathit{org}(e_{i+1})$ pour $1 \leq i
< n$, où $n \geq 0$. Un circuit (ou cycle) est un chemin où
$\mathit{ext}(e_{n}) = \mathit{org}(e_{1})$.

Les {\sl\orchidBis dag} ({\sl directed acyclic graphs}) sont des
graphes orientés sans cycles. Exemple: le graphe des dépendances inter
modules pour la création d'un projet informatique. ({\sl Makefile})

Un arbre est un dag.  Une forêt (ensemble d'arbres) est un
dag.

\end{slide}
\blueSky

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Exemple de graphe}
\small

%%BEGIN IMAGE
%%END IMAGE
\thepicture

Graphe de {\red de Bruijn}

\end{slide}
\blueSky

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Exemple de graphe}
\small

%%BEGIN IMAGE
%%END IMAGE
\thepicture

Graphe des diviseurs

\end{slide}
\blueSky

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Représentations d'un graphe (1)}
\small

{\orchidBis Matrice d'adjacence}

$M = (m_{i,j})$ où $m_{i,j}=1$ ssi $(v_i,v_j)$ est un arc du graphe. Matrice
symétrique pour un graphe non orienté.
\bigskip

\begin{lstlisting}{}
class Graphe {
  boolean[ ][ ] m;
  Graphe (int n) { 
    m = new int[n][n];
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        m[x][y] = false;
  }

  static void ajouterArc (Graphe g, int x, int y) { 
    g.m[x][y] = true; 
  }
}
\end{lstlisting}

Place mémoire \(O(V^2)\)

\bigskip
\tiny
(En fait l'initialisation de $m$ est inutile, car c'est l'option par défaut)

\end{slide}
\blueSky

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Représentations d'un graphe (2)}
\small

{\orchidBis Tableau de listes} de successeurs \\
(Représentation creuse de la matrice d'adjacence)

\bigskip

\begin{lstlisting}{}
class Graphe {
  Liste[ ] succ;
  Graphe (int n) { 
    succ = new Liste[n];  
  }

  static void ajouterArc (Graphe g, int x, int y) {
    g.succ[x] = new Liste (y, g.succ[x]);
  }
}
\end{lstlisting}

Place mémoire en \(O(V+E)\)


\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Représentations d'un graphe (2)}
\small

\begin{tabular}{l@{\hspace{2em}}l}
\begin{tabular}[c]{l}
%%BEGIN IMAGE
%%END IMAGE
\mbox{}\apicture\mbox{}
\end{tabular}
&
\begin{tabular}{l}
\begin{lstlisting}{}
g.succ[0] = null;
g.succ[1] = null;
g.succ[2] = {4,6,8,12,10};
g.succ[3] = {6,9,12};
g.succ[4] = {8,12};
g.succ[5] = {10};
g.succ[6] = {12};
g.succ[7] = null;
g.succ[8] = null;
g.succ[9] = null;
g.succ[10] = null;
g.succ[11] = null;
g.succ[12] = null;
\end{lstlisting}
\end{tabular}
\end{tabular}

\bigskip

%BEGIN LATEX
{\tiny Remarque: \lstinline|{4,6,8,10,12}| n'est malheureusement pas
du Java légal, mais est ici une abréviation pour \lstinline|new Liste(4, new Liste(6, new Liste(8, new Liste(10, new Liste (12, null)))))|}
%END LATEX

\end{slide}
\blueSky

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Exemple d'entrée textuelle d'un graphe}
\small

1ère ligne: $n=\mathit{card}(V)$; 
lignes suivantes: arcs $x_i \leftrightarrow y_i$
\bigskip

\begin{lstlisting}{}
static Graphe lireGraphe () {
  BufferedReader in =     // `\small\red\rm\sl idiosyncratie Java!`
     new BufferedReader(new InputStreamReader(System.in));
  try {
    String s = in.readLine(); int n = Integer.parseInt(s);
    Graphe g = new Graphe (n);
    while ((s = in.readLine()) != null) {
      StringTokenizer st = new StringTokenizer(s);
      int x = Integer.parseInt(st.nextToken());
      int y = Integer.parseInt(st.nextToken());
      if (0 <= x && x < n && 0 <= y && y < n) {
        ajouterArc(g, x, y);
        ajouterArc(g, y, x);
      }
    }
    return g;
  } catch (IOException e) {
    System.err.println(e); System.exit(1); return null;
  }
}
\end{lstlisting}

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Parcours en profondeur d'abord, {\sl Depth-First Search}}
\small
Comment visiter tous les sommets sans boucler?

%%BEGIN IMAGE
%%END IMAGE
\thepicture

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Arbre de recouvrement -- {\sl spanning tree}}
\small

%%BEGIN IMAGE
%%END IMAGE
\thepicture

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Vue de l'arbre de recouvrement}
\small

%%BEGIN IMAGE
%%END IMAGE
\thepicture

\bigskip

Les numéros de parcours correspondent à l'ordre préfixe sur l'arbre
de recouvrement.

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Arbres de recouvrement -- {\sl spanning tree}}
\small

%%BEGIN IMAGE
\expandafter\ifx\csname graph\endcsname\relax \csname newbox\endcsname\graph\fi
\expandafter\ifx\csname graphtemp\endcsname\relax \csname newdimen\endcsname\graphtemp\fi
\setbox\graph=\vtop{\vskip 0pt\hbox{%
    \hbox{\vrule depth0.000in width0pt height 0pt}%
    \kern 4.200in
  }%
}%
%%END IMAGE

\thepicture
\bigskip
Un graphe peut avoir plusieurs arbres de recouvrement.
\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}[21.5cm,17.5cm]
\heading{Parcours en profondeur d'abord, {\sl Depth-First Search}}
\small

\begin{lstlisting}{}
final static int BLANC = 0, GRIS = 1, NOIR = 2;
static int[ ] couleur;

static void visiter (Graphe g) {
  int n = g.succ.length; couleur = new int[n];
  for (int x = 0; x < n; ++x)  couleur[x] = BLANC;
  for (int x = 0; x < n; ++x)
    if (couleur[x] == BLANC)  
      dfs(g, x);
}

static void dfs (Graphe g, int x) {
  couleur[x] = GRIS;
  `\rm Pour tout $y$ successeur de $x$ dans $G$ faire`
    if (couleur[y] == BLANC) 
      dfs(g, y);
  couleur[x] = NOIR;
}
\end{lstlisting}

BLANC $=$ non traité,\\
GRIS $=$ en cours de traitement,\\
NOIR $=$ traité.\\
{\tiny Aussi appelé parcours de Trémaux dans le polycopié.}

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}[21.5cm,16.5cm]
\heading{Parcours en profondeur}
\small
%
\begin{lstlisting}{}
static int numOrdre; 
static int[ ] num;

static void visiter (Graphe g) {
  int n = g.succ.length; 
  num = new int[n]; numOrdre = -1; 
  for (int x = 0; x < n; ++x)  num[x] = -1;
  for (int x = 0; x < n; ++x)
    if (num[x] == -1)  
      dfs(g, x);
}

static void dfs (Graphe g, int x) {
  num[x] = ++numOrdre;
  for (Liste ls = g.succ[x]; ls != null; ls = ls.suivant) {
    int y = ls.val;
    if (num[y] == -1) 
      dfs(g, y);
  }
}
\end{lstlisting}

Son temps est en \(O(V+E)\). \\
{\red Tarjan (1972)} a démontré l'utilité de cette méthode.

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}[21.5cm,16.5cm]
\heading{Parcours en profondeur}
\small
%

\begin{lstlisting}{}
static int numOrdre; 

static void visiter (Graphe g) {
  numOrdre = -1; 
  int n = g.succ.length; int[ ] num = new int[n]; 
  for (int x = 0; x < n; ++x)  num[x] = -1;
  for (int x = 0; x < n; ++x)
    if (num[x] == -1)  
      dfs(g, x, num);
}

static void dfs (Graphe g, int x, int[ ] num) {
  num[x] = ++numOrdre;
  for (Liste ls = g.succ[x]; ls != null; ls = ls.suivant) {
    int y = ls.val;
    if (num[y] == -1) 
      dfs(g, y, num);
  }
}
\end{lstlisting}

Mieux car moins de variables globales.\\
\exercice Supprimer la variable globale {\it numOrdre}.

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Arbres de recouvrement -- {\sl spanning tree}}
\small

L'arbre des appels récursifs à {\tt dfs} est un arbre de
recouvrement. Les arcs d'un graphe sont de 4 sortes par rapport à un
de ses arbres de recouvrement:

\begin{enumerate}
\item d'un n{\oe}ud de l'arbre à un de ses fils dans l'arbre

\item d'un n{\oe}ud de l'arbre à un de ses ancètres dans l'arbre

\item d'un n{\oe}ud de l'arbre à un de ses descendants non direct dans l'arbre

\item d'un n{\oe}ud à un de ses cousins dans l'arbre
\end{enumerate}

[Dans un graphe {\orchidBis non orienté}, seulement des arcs du
type {\red 1-3}.]

\bigskip
\exercice Programmer dfs en itératif $+$ pile. Comparer à bfs.

\exercice Montrer que les n{\oe}uds d'un arbre de recouvrement ont un numéro
inférieur à celui de leurs fils.

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Parcours en largeur d'abord}
\small

%%BEGIN IMAGE
%%END IMAGE
\thepicture

Parcours selon la distance à un sommet de départ.
\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Parcours en largeur d'abord, {\sl Breadth-First Search}}

\begin{lstlisting}{}
static void visiter (Graphe g) {
  int n = g.succ.length;
  numOrdre = -1; FIFO f = new FIFO (n);
  for (int x = 0; x < n; ++x)  num[x] = -1;
  for (int x = 0; x < n; ++x)
    if (num[x] == -1) {
      FIFO.ajouter(f, x); num[x] = -2;
      bfs (g, f);
}   }

static void bfs (Graphe g, FIFO f) {
  while ( !f.vide() ) {
    int x = FIFO.supprimer (f);
    num[x] = ++numOrdre;
    for (Liste ls = g.succ[x]; ls != null; ls = ls.suivant) {
      int y = ls.val;
      if (num[y] == -1) {
        FIFO.ajouter(f, y); num[y] = -2;
} } } }
\end{lstlisting}

\bigskip

Itératif et plus compliqué que récursif (comme pour DFS).

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Quelques problèmes classiques}
\small\medskip

\begin{itemize}
\setlength{\itemsep}{1ex}
\renewcommand{\labelitemi}{{\colorItem $\bullet$}}

\item Sortie de labyrinthe (dans un graphe non-orienté)

\item Test de non-cyclicité dans un graphe orienté

\item Tri topologique dans un graphe orienté ({\em Makefiles})

\item Planarité (Tarjan)

\item Connexité dans un graphe non orienté

\item Plus court chemin

\item Coloriage de graphe

\item Optimisation de flot

\end{itemize}

\bigskip
L'algorithmique des graphes a été très étudiée: algorithmique combinatoire.
[{\tiny {\red Tarjan\  Lovasz\ Edmons\ Erdos\ Rosenstiehl }; livres de {\red Berge\ Cormen}}]

{\tiny Plus d'algorithmes sur les graphes seront vus au cours
Algorithmes en Majeure 2}
\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Sortie de labyrinthe}
\small

On cherche un chemin de $d$ à $s$.
\bigskip

\begin{lstlisting}{}
static Liste chemin (Graphe g, int d, int s) {
  num[d] = ++id;
  if (d == s) 
    return new Liste (d, null);
  for (Liste ls = g.succ[d]; ls != null; ls = ls.suivant) {
    int x = ls.val;
    if (num[x] == -1) {
      Liste r = chemin (g, x, s);
      if (r != null) 
        return new Liste (d, r);
    }
  }
  return null;
}
\end{lstlisting}

Complexité en temps en \(O(V+E)\)

\exercice Calculer le chemin le plus court vers la sortie.

\exercice Imprimer tous les chemins vers la sortie.

\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Connexité}
\small

Une {\red composante connexe} est un ensemble maximal de sommets tel
que pour toute paire de sommets dans cet ensemble, il existe un chemin
entre les deux.

\exercice Calculer les composantes connexes dans le graphe des
diviseurs. 

\exercice Ecrire le programme qui imprime les composantes connexes
dans un graphe non orienté.

\bigskip

Dans un graphe non dirigé, un {\orchidBis point d'articulation} est un
sommet qui sépare une composante connexe en parties non connexes si on
l'enlève.

Un graphe sans point d'articulation est un graphe {\red bi-connexe}.

\exercice Montrer que dans un graphe bi-connexe il existe toujours
deux chemins différents entre toute paire de sommets.

\exercice Le réseau électrique EDF est assimilé à un graphe non
orienté. Quels sont les points névralgiques {\tiny (à protéger contre
le terroriste breton)}?


\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Approfondissement}
\small\medskip

\exercice Calculer les points d'articulation dans le graphe (non
orienté) des diviseurs.

\exercice Un arbre est un graphe non orienté particulier. Quels sont
ses points d'articulation?

\exercice Recherche de la plus longue sortie dans un labyrinthe

\exercice Recherche de toutes les sorties dans un labyrinthe

\exercice Enumérer tous les arbres de recouvrement

\exercice Enumérer tous les chemins (élémentaires) issus d'un
sommet. (Un chemin élémentaire ne passe pas deux fois par un même
sommet).

\exercice Réfléchir au calcul des composantes bi-connexes. 

\exercice Comment définir des composantes tri-connexes?
\end{slide}
\blueSky
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}


\begin{verbatim}
TYPE Closure = OBJECT METHODS apply(): REFANY END;

PROCEDURE Fork(cl: Closure): T;

       Return a handle on a newly-created
       thread executing cl.apply().

PROCEDURE Join(t: T): REFANY;

       Wait until t has terminated and return
      its result. It is a checked runtime error to
      call this more than once for any t.
\end{verbatim}
