\documentclass[12pt,addpoints]{exam}
\usepackage[utf8]{inputenc}
\usepackage{lastpage}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{mdframed}
\usepackage{array}
\usepackage{url}
\usepackage{multicol}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{shapes.misc}
\usepackage{pgfplots}
\usepackage{algpseudocode}

% Paramètres globaux
\bonuspointpoints{point \emph{bonus}}{points \emph{boni}}
\parindent 0cm
\hqword{Question}
\hpword{Sur}
\hsword{Note}
\htword{Total}
\setcounter{MaxMatrixCols}{15}

% Solutions
\printanswers

% En-tête et pieds de page
\headrule
\cfoot{\thepage /\pageref{LastPage}}
\lhead{MAT1060 --- Mathématiques algorithmiques}
\rhead{Hiver 2017}
\newcommand{\headrulewidth}{0.4pt}
\newcommand{\footrulewidth}{0.4pt}

% Algorithmes
\algrenewcommand\algorithmicwhile{\textbf{tant que}}
\algrenewcommand\algorithmicfunction{\textbf{fonction}}
\algrenewcommand\algorithmicend{\textbf{fin}}
\algrenewcommand\algorithmicdo{\textbf{faire}}
\algrenewcommand\algorithmicfor{\textbf{pour}}
\algrenewcommand\algorithmicif{\textbf{si}}
\algrenewcommand\algorithmicelse{\textbf{sinon}}
\algrenewcommand\algorithmicthen{\textbf{alors}}
\algrenewcommand\algorithmicreturn{\textbf{retourner}}
\algrenewcommand\algorithmicrepeat{\textbf{faire}}
\algrenewcommand\algorithmicuntil{\textbf{tant que}}
\newcommand{\enteteproc}[2]{\vskip\baselineskip \hspace*{\fill} \algorithmicprocedure~\Call{#1}{#2} \hspace*{\fill} \vskip\baselineskip}
\newcommand{\entetefunc}[3]{\vskip\baselineskip \hspace*{\fill} \algorithmicfunction~\Call{#1}{#2} : #3 \hspace*{\fill} \vskip\baselineskip}

% Code
\lstset{
  literate={é}{{\'e}}1
           {è}{{\`e}}1
           {ê}{{\^e}}1
           {î}{{\^i}}1
           {à}{{\`a}}1
           {ç}{{\c{c}}}1
           {É}{{\'E}}1,
  basicstyle=\footnotesize\ttfamily,
  keywordstyle=\bfseries\color{green!70!black},
  identifierstyle=\color{blue},
  commentstyle=\ttfamily\color{red!70!black}\emph,
  stringstyle=\bfseries\color{orange},
  showstringspaces=false,
  language=python,
  breaklines=true
}

% Raccourcis
\newcommand{\bigo}{\mathcal{O}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\pgcd}{\mathrm{pgcd}}
\newcommand{\trunc}{\mathrm{trunc}}
\newcommand{\sign}{\mathrm{sign}}

\begin{document}
	
\ifprintanswers
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Solution du devoir 3}}}
  \vskip 0.5cm
  \begin{mdframed} \begin{center}
  \textbf{Auteur : Inscrire votre nom ici} \\
  \end{center} \end{mdframed}
  \vskip 0.5cm
\else
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Devoir 3}}}
  \centerline{\small (à remettre au plus tard le 24 avril, à 16h00)}
  \centerline{\small (dans la chute du département d'informatique, située au PK-4150)}
  \vskip 1.2cm
Le devoir doit être rédigé \textbf{individuellement}. Vous devez \textbf{justifier} chacune de vos réponses. \textbf{Aucun retard} ne sera accepté puisque la solution sera publiée dans la soirée. 

\emph{Notes~:} Préférez une impression recto-verso et agrafez votre devoir. Ne le mettez pas dans une enveloppe, pour éviter de consommer du papier inutilement. Aussi, si vous avez terminé le devoir en avance, vous pouvez me le remettre en mains propres au début ou à la fin du cours.
\fi

\ifprintanswers
\else
\begin{center} \gradetable[h] \end{center}
\fi

\begin{questions}

% Argument combinatoire et générateur
\question
Supposez que vous avez $n$ billes identiques devant vous. Vous souhaitez diviser ces $n$ billes en $k$ paquets. Par exemple, si $n = 5$ et $k = 3$, vous pourriez diviser les $n = 5$ billes comme suit~: $2$ paquets de $2$ billes et $1$ paquet de $1$ bille, pour un total de $k = 3$ paquets, qu'on représente par le triplet $(2, 2, 1)$, appelé \emph{partage}. Plus précisément, un \emph{partage} de $n$ billes en $k$ paquets est un $k$-tuplet $(n_1,n_2,\ldots,n_k)$ tel que $n_1 + n_2 + \ldots + n_k = n$ et $n_1 \geq n_2 \geq \ldots \geq n_k \geq 1$.

Dénotons par $P(n,k)$ l'ensemble de tous les partages de $n$ billes en $k$ paquets, où chaque paquet contient au moins $1$ bille et soit $p(n,k) = |P(n,k)|$.
\begin{parts}
  \part[2] Montrez que $p(8,3) = 5$ en calculant $P(8,3)$.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[3] Calculez les valeurs de $p(n,k)$ pour $1 \leq k \leq n \leq 5$. Présentez votre solution sous forme de tableau.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[5]\label{P:equations} Les nombres $p(n,k)$ vérifient les égalités suivantes~:
  \begin{enumerate}[(i)]
    \item $p(n,k) = 0$ si $n < k$;
    \item $p(n,n) = p(n,1) = 1$;
    \item $p(n,k) = p(n - 1, k - 1) + p(n - k, k)$.
  \end{enumerate}
  Donnez un argument combinatoire qui justifie les égalités (i), (ii) et (iii). \emph{Indice~:} Étant donné un partage, il y a deux possibilités : (1) il existe au moins un paquet ayant exactement une bille ou (2) tous les paquets ont au moins deux billes.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}

  \part[10] Écrivez un générateur dans SageMath (ou Python) qui, étant donnés deux entiers positifs $n$ et $k$ tels que $1 \leq k \leq n$, génère les éléments de l'ensemble $P(n,k)$. Par exemple, si votre fonction est de la forme
  \begin{lstlisting}[language=python]
  def paquets(n, k):
      #
      # A compléter
      #
      # Vous devez utilisez le mot réservé
      #
      #   yield
      #
      # au moins une fois dans votre code
      # pour obtenir un générateur
      #
  \end{lstlisting}
  alors on s'attend à ce que le bout de code suivant
  \begin{lstlisting}[language=python]
  for paquet in paquets(9, 4):
      print paquet
  \end{lstlisting}
  affiche
  \begin{lstlisting}[language=python]
  (6, 1, 1, 1)
  (5, 2, 1, 1)
  (4, 3, 1, 1)
  (4, 2, 2, 1)
  (3, 3, 2, 1)
  (3, 2, 2, 2)
  \end{lstlisting}
  \emph{Note~:} Les équations données à la sous-question~\eqref{P:equations} cachent un algorithme récursif.
  \emph{Suggestion~:} Comme votre générateur retourne des $k$-tuplets, certaines fonctions sur les $k$-tuplets pourraient vous être utiles~:
  \begin{itemize}
    \item Il est possible de construire un $k$-tuplet en compréhension, comme pour les listes et les ensembles. Par exemple \lstinline|tuple(1 for _ in range(n))| construit le $n$-tuplet $(1,1,\ldots,1)$. De la même façon, \lstinline|tuple(i + 1 for i in paquet)| construit un nouveau $k$-tuplet à partir de \lstinline|paquet| en ajoutant $1$ à chaque élément du $k$-tuplet \lstinline|paquet|.
    \item Il est possible de concaténer des $k$-tuplets à l'aide de l'opérateur \lstinline|+|. Par exemple, \lstinline|(1, 2, 3)  + (4, 5, 6)| retourne \lstinline|(1, 2, 3, 4, 5, 6)|
    \item Pour construire un $1$-tuplet, une particularité syntaxique de Python est qu'il faut ajouter une virgule à la fin (sinon, l'interpréteur croit qu'il s'agit d'une expression parenthésée et non d'un $k$-tuplet). Par exemple, le $1$-tuplet $(6)$ est représenté par \lstinline|(6,)| en Python.
  \end{itemize}
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

% Relation
\question
Dans cette question, nous nous intéressons à construire deux relations sur les éléments de $\N^2$ à partir de deux fonctions mathématiques très importantes. La première est la fonction signe $\sign : \R \rightarrow \{-1,0,1\}$ définie par
$$\sign(z) = \begin{cases}
  -1, & \mbox{si $z < 0$;} \\
  0,  & \mbox{si $z = 0$;} \\
  1,  & \mbox{si $z > 0$.} \\
\end{cases}$$
La seconde est la troncature $\trunc : \R \rightarrow \Z$, définie par
$$\trunc(z) = \sign(z)\lfloor|z|\rfloor,$$
qui est semblable à la fonction plancher $\lfloor \cdot \rfloor$, mais qui a un comportement différent sur les valeurs négatives.

De plus, considérons les trois relations suivantes définies sur $\N^2$.
\begin{enumerate}
  \item La relation $\leftrightarrow$, définie par
    \begin{equation}
    (x,y) \leftrightarrow (x',y') \quad \text{si et seulement si} \quad (x - x')^2 + (y - y')^2 = 1.
    \end{equation}
    On dit alors que $(x,y)$ et $(x',y')$ sont \emph{voisins}.
  \item La relation $\rightarrow$, définie par
    \begin{equation}
    (x,y) \rightarrow (x',y') \quad \text{si et seulement si} \quad (x,y) = \left( \lfloor x'/2 \rfloor, \lfloor y'/2 \rfloor \right)
    \end{equation}
    On dit alors que $(x,y)$ est le \emph{parent} de $(x',y')$.
  \item La relation $\Leftrightarrow$ définie par
    \begin{equation}
    p \Leftrightarrow p' \quad \text{si et seulement si} \quad \text{il existe $p'' \in \N^2$ tel que $p'' \rightarrow p$ et $p'' \rightarrow p'$},
    \end{equation}
    On dit alors que $p$ et $p'$ sont \emph{frères}, puisqu'ils ont le même parent.
\end{enumerate}
\begin{parts}
  \part[2] Montrez que $\sign(-z) = -\sign(z)$ pour tout $z \in \R$.
  \part[2] Montrez que $\trunc(-z) = -\trunc(z)$ pour tout $z \in \R$.
  \part[6] Pour chaque propriété parmi la réflexivité, l'irréflexivité, la transitivité, la symétrie, l'antisymétrie et l'asymétrie, indiquez si la relation $\leftrightarrow$ satisfait ou non la propriété. Dans chaque cas, justifiez.
  \part[6] Pour chaque propriété parmi la réflexivité, l'irréflexivité, la transitivité, la symétrie, l'antisymétrie et l'asymétrie, indiquez si la relation $\rightarrow$ satisfait ou non la propriété. Dans chaque cas, justifiez.
  \part[4] Montrez que la relation $\Leftrightarrow$ est une relation d'équivalence.
  \part[5]\label{SQ:graphe} Dessinez le graphe des relations $\rightarrow$ et $\leftrightarrow$ si on se restreint à l'ensemble de sommets $V = \{(x,y) \mid 0 \leq x,y \leq 7\}$.
  \part[5] Calculez les classes d'équivalence de la relation $\Leftrightarrow$ lorsqu'on se restreint à l'ensemble de sommets $V$ mentionné à la sous-question \eqref{SQ:graphe}. Ajoutez au dessin fait en \eqref{SQ:graphe} ces classes d'équivalence.
\end{parts}
\begin{solution}
Ajouter votre solution ici
\end{solution}

% Automorphismes
\question
Un \emph{automorphisme} de graphes est un isomorphisme d'un graphe $G$ avec lui-même. Intuitivement, un automorphisme correspond à une symétrie d'un graphe. Par exemple, prenons le graphe non orienté ci-bas~:
\vskip \baselineskip
\begin{center} \begin{tikzpicture}[sommet/.style={fill=black, circle, minimum size=2mm, inner sep=0pt}]
  \node[sommet, label=225:$v_1$] (v1) at (0,0) {};
  \node[sommet, label=135:$v_2$] (v2) at (0,2) {};
  \node[sommet, label=270:$v_3$] (v3) at (2,0) {};
  \node[sommet, label=90:$v_4$] (v4) at (2,2) {};
  \node[sommet, label=-45:$v_5$] (v5) at (4,0) {};
  \node[sommet, label=45:$v_6$] (v6) at (4,2) {};
  \path (v1) edge (v2);
  \path (v1) edge (v3);
  \path (v2) edge (v4);
  \path (v3) edge (v4);
  \path (v3) edge (v5);
  \path (v4) edge (v6);
  \path (v5) edge (v6);
\end{tikzpicture} \end{center}
Ce graphe possède quatre axes de symétrie décrits par les quatre automorphismes suivants~:
\begin{center} \begin{tabular}{*{7}{|>{$}c<{$}}|}
  \hline
  $Fonction$ & v_1 & v_2 & v_3 & v_4 & v_5 & v_6 \\
  \hline
  \hline
  f_1        & v_1 & v_2 & v_3 & v_4 & v_5 & v_6 \\
  \hline
  f_2        & v_2 & v_1 & v_4 & v_3 & v_6 & v_5 \\
  \hline
  f_3        & v_5 & v_6 & v_3 & v_4 & v_1 & v_2 \\
  \hline
  f_4        & v_6 & v_5 & v_4 & v_3 & v_2 & v_1 \\
  \hline
\end{tabular} \end{center}
Pour chacun des graphes suivants, donnez son nombre d'automorphismes. Justifiez.
\begin{parts}
  \part[4] Le graphe complet $K_n$, pour $n \geq 1$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[4] Le graphe biparti complet $K_{m,n}$, pour $m,n \geq 1$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[4] Le cycle $C_n$, pour $n \geq 3$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[4] L'hypercube $Q_n$, pour $n \geq 1$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[4] La roue $W_n$, pour $n \geq 3$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

% Sous-graphes induits
\question[15]
Soit $G = (V,E)$ un graphe simple et $U \subseteq V$. On appelle \emph{sous-graphe induit par $U$} le graphe
$$G[U] = (U, E \cap \mathcal{P}_2(U)),$$
où $\mathcal{P}_2(V)$ est l'ensemble des paires d'éléments de $V$. Autrement dit, c'est l'unique sous-graphe de $G$ obtenu en prenant les sommets qui sont dans $U$ et toutes les arêtes dont les deux extrémités sont elles aussi dans $U$.

Aussi, étant donné un graphe $G = (V,E)$, on dit que $G$ est \emph{acyclique} si les seuls cycles qu'il contient sont triviaux. Un \emph{transversal de cycles} de $G$ est un sous-ensemble de sommets $U \subseteq V$ tel que pour tout cycle $(v_1,v_2,\ldots,v_k)$ de $G$, il existe au moins un indice $i \in \{1,2,\ldots,k\}$ tel que $v_i \in U$.

Montrez que $U$ est un transversal de cycle de $G$ si et seulement si $G[V - U]$ est un graphe acyclique.
\begin{solution}
Ajouter votre solution ici
\end{solution}

% Arbres
\question
Étant donné un arbre non orienté quelconque $T = (V,E)$, on dénote par $E(T)$ l'arbre obtenu de $T$ en supprimant toutes ses feuilles (une feuille est simplement un sommet de degré exactement $1$, en particulier, un sommet de degré $0$ n'est pas une feuille).
\begin{parts}
  \part[5] Vrai ou faux? Pour tout arbre $T$, il existe un unique arbre $T'$ tel que $T = E(T')$. Si c'est vrai, démontrez-le, si c'est faux, donnez un contre-exemple.
  \part[5] Vrai ou faux? Pour tout arbre $T$, il existe un unique arbre $T'$ tel que $T' = E(T)$. Si c'est vrai, démontrez-le, si c'est faux, donnez un contre-exemple.
  \part[5] Je prétends que pour tout arbre $T$, il existe un entier $n \geq 0$ tel que $E^n(T) = E^{n+1}(T) = E^{n+2}(T) = \cdots$, de sorte que l'expression
    $$\lim_{n \rightarrow \infty} E^n(T)$$
    est bien définie. Montrez que mon affirmation est vraie et qu'il n'y a que deux arbres qui peuvent être obtenus comme une telle limite.
\end{parts}
\begin{solution}
Ajouter votre solution ici
\end{solution}

% Algorithmes
\question
Soit $G = (V,E)$ un graphe non orienté de $k$ composantes connexes. On dit que $\{u,v\} \in E$ est un \emph{pont} si le nombre de composantes du graphe $G' = (V,E - \{u,v\})$ est strictement plus petit que $k$. Autrement dit, la suppression de l'arête $\{u,v\}$ fait augmenter le nombre de composantes connexes de $G$.

Aussi, supposez que vous avez à votre disposition seulement les fonctions suivantes pour manipuler un graphe simple $G$~:
\begin{itemize}
  \item $G.\Call{sommets}$ retourne l'ensemble des sommets de $G$;
  \item $G.\Call{arêtes}$ retourne l'ensemble des arêtes de $G$;
  \item $G.\Call{supprimer}{u,v}$ retourne une copie du graphe $G$ après avoir supprimé l'arête $\{u,v\}$
  \item $G.\Call{voisins}{u}$ retourne l'ensemble des sommets adjacents à $u$ dans $G$;
\end{itemize}

\begin{parts}
  \part[10] Donnez le pseudocode d'une fonction
      \entetefunc{NbComposantes}{$G$ : graphe simple}{naturel}
    qui retourne le nombre de composantes connexes de $G$. \emph{Indice~:} Une stratégie possible consiste à utiliser une procédure auxiliaire
      \enteteproc{Visiter}{$G$ : graphe simple, $u$ : sommet, $\emph{visité}$ : marquage}
      qui explore tous les sommets dans la même composante connexe que $u$ en les marquants comme visités (via le marquage $\emph{visité}$).
    \begin{solution}
Ajouter votre solution ici
    \end{solution}
  \part[10] Donnez le pseudocode d'une fonction
      \entetefunc{PossèdePont}{$G$ : graphe simple}{booléen}
    qui retourne vrai si et seulement si $G$ possède un pont.
    \begin{solution}
Ajouter votre solution ici
    \end{solution}
\end{parts}

\end{questions}

\end{document}
