\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}}

\begin{document}
	
\ifprintanswers
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Solution du devoir 2}}}
  \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 2}}}
  \centerline{\small (à remettre au plus tard le 27 mars, à 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}

  % Démonstration pgcd
  \question
  Soient $a, b, m$ sont des nombres naturels quelconques, où $m \neq 0$ et $(a,b) \neq (0,0)$. Démontrez les deux identités suivantes à propos de la fonction $\pgcd$.
  \begin{parts}
    \part[5] $\pgcd(ma, mb) = m\cdot\pgcd(a, b)$ \emph{Suggestion~:} Posez $a = p_1^{x_1}p_2^{x_2}\cdots p_k^{x_k}$, $b = p_1^{y_1}p_2^{y_2}\cdots p_k^{y_k}$ et $m = p_1^{z_1}p_2^{z_2}\cdots p_k^{z_k}$, où $k$ est un nombre positif, les exposants $x_k$, $y_k$ et $z_k$ sont des nombres entiers positifs ou nuls et $p_i$ est un nombre premier pour $i = 1, 2, \ldots k$, puis calculez les $\pgcd$ en fonction des exposants.
    \begin{solution}
Ajouter votre solution ici
    \end{solution}
    \part[5] $\pgcd(a, b) = \pgcd(a + b, b)$ \emph{Suggestion~:} Montrez que les diviseurs communs de $a$ et $b$ sont exactement les diviseurs communs de $a + b$ et $b$ et donc les $\pgcd$ doivent être les mêmes.
    \begin{solution}
Ajouter votre solution ici
    \end{solution}
  \end{parts}

  % Mot de Fibonacci
  \question (\totalpoints{} points)
  Les \emph{mots de Fibonacci} sont définis récursivement comme suit~:
  $$f_1 = 1, \quad f_2 = 0 \quad \text{et} \quad f_n = f_{n-1}\cdot f_{n-2}, \quad \text{pour tout $n \geq 3$,}$$
  où $\cdot$ est la concaténation de deux mots. Par exemple, $f_3 = f_2\cdot f_1 = 0\cdot 1 = 01$, $f_4 = f_3\cdot f_2 = 01\cdot 0 = 010$, et ainsi de suite.
  \begin{parts}
    \part[5] Calculez les mots $f_n$ pour $1 \leq n \leq 8$. Pour chacun, indiquez leur longueur ainsi que le nombre de $0$ et le nombre de $1$ qu'on y trouve. Présentez vos résultats sous la forme d'un tableau.
    \begin{solution}
Ajouter votre solution ici
    \end{solution}
    \part[5] Montrez par induction que $|f_n|$ est le $n$-ième nombre de Fibonacci, pour tout entier $n \geq 1$.
    \begin{solution}
Ajouter votre solution ici
    \end{solution}
    \part[5] Montrez par induction que pour tout $n \geq 3$, le mot $f_n$ termine par $01$ si $n$ est impair et par $10$ si $n$ est pair.
    \begin{solution}
Ajouter votre solution ici
    \end{solution}
    \part[5] Montrez par induction que pour tout entier $n \geq 3$, il existe un palindrome $p$ et deux lettres $a$ et $b$ telles que $f_n = pab$. \emph{Indice~:} Utilisez (c) et le fait que $f_n = f_{n-2}f_{n-3}f_{n-2}$ pour $n \geq 4$.
    \begin{solution}
Ajouter votre solution ici
    \end{solution}
  \end{parts}

  % Arbres parfaits
\question
On dit d'un arbre binaire qu'il est \emph{parfait} si chacun de ses noeuds possède zéro ou deux enfants (autrement dit, il n'y a aucun noeud qui possède exactement un enfant).
\begin{parts}
  \part[8] Soit $T$ un arbre binaire parfait non vide de $n$ noeuds, dont $i$ noeuds sont internes et $f$ sont des feuilles. Montrez par induction sur $n$ que $f = i + 1$.

\begin{solution}
Ajouter votre solution ici
\end{solution}

  \part[7] Donnez le pseudocode d'un algorithme qui vérifie si un arbre binaire $T$ est parfait ou non. Utilisez l'en-tête de fonction
  \entetefunc{EstParfait}{$T$ : arbre binaire}{booléen}
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

% Dénombrement
\question
Soit $\Sigma = \{0,1\}$ l'alphabet binaire. Pour tout mot $u$ sur $\Sigma$ et pour tout entier positif $n$, on définit $W(u,n)$ comme l'ensemble des mots de longueur $n$ sur $\Sigma$ qui évitent le facteur $u$ et $P(u,n)$ comme l'ensemble des mots de $W(u,n)$ qui sont des palindromes.

Par exemple,
$$W(00,4) = \{0101, 0110, 0111, 1010, 1011, 1101, 1110, 1111\}.$$
et
$$P(00,4) = \{0110, 1111\}.$$
\begin{parts}
  \part[3] Calculez $|W(00,n)|$ pour $0 \leq n \leq 6$. 
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] Calculez $|P(00,n)|$ pour $0 \leq n \leq 6$. 
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[5] Proposez une formule générale donnant la valeur de $|W(00,n)|$, pour $n \geq 0$ et démontrez-la par induction.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[5] Proposez une formule générale donnant la valeur de $|P(00,n)|$, pour $n \geq 0$ et démontrez-la par induction.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

% Numéro de téléphones
\question[10]
Dans une région mystérieuse de notre planète, un numéro de téléphone est valide si et seulement s'il vérifie les conditions suivantes~:
\begin{itemize}
  \item Il est formé de $10$ chiffres consécutifs entre $0$ et $9$;
  \item Chaque chiffre impair ($1$, $3$, $5$, $7$ et $9$) doit apparaître au moins une fois.
\end{itemize}
Par exemple, le numéro $4189375351$ est valide, puisqu'il contient les chiffres $1$, $3$, $5$, $7$ et $9$, mais pas le numéro $012345678$, car il ne contient pas le chiffre $9$.

Combien existe-t-il de numéros de téléphone valides dans cette région? \emph{Indice~:} Principe d'inclusion-exclusion. \emph{Suggestion~:} Vous pouvez écrire un programme qui énumère les numéros, mais il prendra sans doute beaucoup de temps pour terminer. Si vous êtes patient, vous pourrez donc l'utiliser pour confirmer votre solution.
\begin{solution}
Ajouter votre solution ici
\end{solution}

% Principe des tiroirs
\question[10]
Soit $n$ un entier strictement positif et $A = \{1,2,3,\ldots,2n\}$. Montrez à l'aide du principe des tiroirs que si on choisit un sous-ensemble $B$ de $A$ constitué de $n + 1$ éléments, alors il en existe au moins $2$ qui sont premiers entre eux.
\begin{solution}
Ajouter votre solution ici
\end{solution}

% Argument combinatoire
\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$.

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.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

\end{questions}

\end{document}
