\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}
\usepackage{pgfplots}
\usepackage{algpseudocode}

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

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

\begin{document}
	
\ifprintanswers
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Solution du devoir 1}}}
  \vskip 0.5cm
  \begin{mdframed} \begin{center}
  \textbf{Auteur : INDIQUER VOTRE NOM} \\
  \end{center} \end{mdframed}
  \vskip 0.5cm
\else
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Devoir 1}}}
  \centerline{\small (à remettre au plus tard le 10 février, à 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. Tout retard entraînera une pénalité de \textbf{20\%} par jour incluant les jours de fin de semaine. 

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

% Ensembles
\question (\totalpoints~points)
Soient $a$, $b$, $c$ et $d$ quatre nombres entiers tels que $a \leq c$ et $b \leq d$. On définit un \emph{rectangle discret} comme l'ensemble suivant~:
$$R(a,b,c,d) = \{(x,y) \in \Z^2 \mid a \leq x \leq c \wedge b \leq y \leq d\}.$$
\begin{parts}
  \part[2] Donnez une formule pour la cardinalité de l'ensemble $R(a,b,c,d)$ en fonction de $a$, $b$, $c$ et $d$, peu importe leur valeur.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] Considérez huit entiers $a, b, c, d, x, y, z, t$ tels que $a \leq x \leq c \leq z$ et $b \leq y \leq d \leq t$. Exprimez $R(a,b,c,d) \cap R(x,y,z,t)$ comme un rectangle discret. Quelle est sa cardinalité ?
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] Même question, mais supposez cette fois-ci que $x > c$ et $y > d$. Que vaut $R(a,b,c,d) \cap R(x,y,z,t)$ et quelle est sa cardinalité ?
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] Toujours la même question, mais en supposant que $y = b$, $x = c + 1$ et $t = d$. Exprimez $R(a,b,c,d) \oplus R(x,y,z,t)$ comme un rectangle discret et donnez sa cardinalité.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] Exprimez l'ensemble $\bigcap_{i=0}^5 R(i,i,i+10,i+10)$ comme un rectangle discret et donnez sa cardinalité.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

% Fonctions
\question (\totalpoints~points)
Pour tous $(a,b) \in \Z^2$, on définit les fonctions
$$\begin{array}{ccccl}
  T_{a,b} & : & \Z^2 \rightarrow \Z^2 & : & (x,y) \mapsto (x + a, y + b), \\
  R_{a,b} & : & \Z^2 \rightarrow \Z^2 & : & (x,y) \mapsto (-y + a + b, x - a + b).
\end{array}$$
\begin{parts}
  \part[3] Montrez que $T_{a,b}$ est une bijection peu importe $(a,b) \in \Z^2$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[3] Montrez que $R_{a,b}$ est une bijection peu importe $(a,b) \in \Z^2$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] Donnez la règle de correspondance de la fonction $R^2_{0,0}$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] Donnez la règle de correspondance de la fonction $R^{-1}_{a,b}$.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[5] Vrai ou faux? Pour tout couple $(a,b) \in \Z^2$, l'égalité
  $$R_{a,b} = T_{a,b} \circ R_{0,0} \circ T_{-a,-b}$$
  est vérifiée. Si c'est vrai, démontrez-le, sinon, donnez un contre-exemple.
  \part[5] Vrai ou faux? Pour tout couple $(a,b) \in \Z^2$, l'égalité
  $$R_{a,b} = T_{-a,-b} \circ R_{0,0} \circ T_{a,b}$$
  est vérifiée. Si c'est vrai, démontrez-le, sinon, donnez un contre-exemple.
\end{parts}

% Injectivité, surjectivité, bijectivité
\question (\totalpoints~points)
Pour chacune des règles de correspondance suivantes, donnez un domaine et un codomaine maximaux pour que la fonction soit bijective~:
\begin{parts}
  \part[2] $f(z) = z + 3$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[4] $f(z) = \lfloor (2z + 3) / 2 \rfloor$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[4] $f(z) = |z - 5|$.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}
Le domaine et le codomaine doivent être des sous-ensembles de $\Z$. Montrez que la fonction est bien bijective et justifiez pourquoi le domaine et le codomaine sont bien maximaux (c'est-à-dire qu'on ne peut pas les agrandir sans perdre la propriété d'injectivité ou de surjectivité).

% Suites
\question (\totalpoints{} points)
Écrivez les huit premiers termes de la suite $\{a_n\}_{n\in\N}$ dont le terme général est
\begin{parts}
  \part[4] $a_n = 2n(-1)^n + 3$;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[4] $a_0 = 0$, $a_1 = 1$ et $a_n = 2a_{n-1} + a_{n-2}$ pour tout entier $n \geq 2$.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] La suite définie à la sous-question (b) est très connue en combinatoire. Quel nom lui donne-t-on?
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

% Image-miroir
\question (\totalpoints~points)
Étant donné un mot $w = w_1w_2\cdots w_n$ de longueur $n$, l'\emph{image-miroir} de $w$, notée $\widetilde{w}$ est définie par
$$\widetilde{w} = \begin{cases}
  \varepsilon, & \mbox{si $w = \varepsilon$;} \\
  a\widetilde{u}, & \mbox{si $w = ua$, où $a$ est une lettre et $u$ un mot.}
\end{cases}.$$
Par exemple, $\widetilde{01001} = 10010$. Une propriété de l'opérateur image-miroir est qu'il satisfait l'égalité $\widetilde{uv} = \widetilde{v}\,\widetilde{u}$ pour n'importe quels mots $u$ et $v$ (vous n'avez pas à démontrer cette propriété). Un \emph{palindrome} est un mot $w$ qui vérifie l'équation $w = \widetilde{w}$. Dites si les affirmations suivantes sont vraies. Si oui, donnez une démonstration, sinon, donnez un contre-exemple.
\begin{parts}
  \part[5] $pq$ est un palindrome aussitôt que $p$ et $q$ sont des palindromes;
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[5] $pqp$ est un palindrome aussitôt que $p$ et $q$ sont des palindromes.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

% Mots équilibrés
\question (\totalpoints~points)
Soit $A = \{a,b\}$. On dit d'un mot $w$ sur $A$ qu'il est \emph{équilibré} si, pour toute paire de facteur $u$ et $v$ de $w$ de même longueur, on a $\left||u|_a - |v|_a\right| \leq 1$, c'est-à-dire qu'ils contiennent presque autant de $a$ que de $b$. Par exemple, $aaba$ est équilibré, mais pas $aabb$, puisque $\left||aa|_a - |bb|_a\right| = |2 - 0| = 2 > 1$. De plus, soit $E_n$ le nombre de mots équilibrés de longueur $n$ et $F_n$ la suite dont le terme général est
$$F_n = \sum_{i=1}^n (n - i + 1)\varphi(i),$$
où $\varphi$ est la fonction \emph{indicatrice d'Euler}, c'est-à-dire que $\varphi(i)$ est le nombre d'entiers entre $1$ et $i$ qui sont premiers avec $i$.
\begin{parts}
  \part[4] Pour $n = 0,1,2,3,4,5,6$, énumérez tous les mots équilibrés de longueur $n$ et calculez $E_n$. \emph{Note~:} Bien que ce ne soit pas obligatoire, il peut être intéressant d'écrire un petit programme en SageMath qui énumère ces mots, pour vous assurer de ne pas en avoir oublié.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[4] Calculez les valeurs $F_n$ pour $n = 0,1,2,3,4,5,6$.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[2] Quel est le lien entre $E_n$ et $F_n$ (pas de démonstration requise)?
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

% Algorithme 1
\question[10]
Écrivez un algorithme qui prend en entrée deux listes ordonnées de nombres entiers (avec répétitions possibles) $L_1$ et $L_2$ et qui retourne comme résultat la liste ordonnée résultant de la fusion de $L_1$ et $L_2$. Par exemple, si vous avez les listes
$$L_1 = [2,2,5,8,9] \quad \text{et} \quad L_2 = [1,3,3,3,4,4,5],$$
vous devriez retourner comme résultat la liste
$$L = [1,2,2,3,3,3,4,4,5,5,8,9].$$

Votre algorithme ne doit parcourir qu'une seule fois chacune des listes $L_1$ et $L_2$ et il ne peut pas utiliser d'autres listes auxiliaires hormis la liste résultante $L$. De plus, étant donné une liste de nombres entiers $L$, vous devez utiliser la notation $|L|$ pour dénoter la \emph{longueur} de la liste et $L[i]$ pour accéder au $i$-ème terme de la liste $L$.

L'en-tête de votre fonction devrait être
\entetefunc{FusionnerListes}{$L_1$, $L_2$ : listes d'entiers}{liste d'entiers}

Indiquez la complexité de votre algorithme à l'aide de la notation $\mathcal{O}$ si les longueurs de $L_1$ et $L_2$ sont $m$ et $n$ respectivement.

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

% Algorithme 2
\question (\totalpoints{} points)
Étant donné une liste d'entiers $L$, on appelle \emph{plage de longueur $k$} une suite de $k$ valeurs consécutives qui se répètent dans $L$.
\begin{parts}
  \part[10] Écrivez un algorithme qui prend en entrée une liste et qui retourne le couple $(i,j)$ où $i$ est le début d'une plage de longueur maximale dans $L$ et $j$ est l'indice de la fin de la plage. Par exemple, si la liste est donnée par
\begin{center} \begin{tabular}{c|*{10}{c}}
  $i$    & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
  \hline
  $L[i]$ & 1 & 3 & 3 & 2 & 2 & 1 & 1 & 1 & 4 & 1 \\
\end{tabular} \end{center}
alors l'algorithme devrait retourner le couple $(6,8)$, car la plage maximale est $(1,1,1)$, commence en position $6$ et termine en position $8$. Indiquez la complexité de votre algorithme à l'aide de la notation $\bigo$ si la longueur de la liste $L$ est $n$.

\emph{Note~:} S'il y a plusieurs plages maximales, vous pouvez retourner n'importe laquelle. \emph{Contrainte~:} Votre algorithme ne doit parcourir la liste qu'une seule fois et ne doit pas utiliser de liste auxiliaire pour l'aider dans ses calculs. L'en-tête de votre fonction devrait être
  \entetefunc{PlageMaximale}{$L$ : liste d'entiers}{couple de nombres naturels}
  \part[10] Implémentez votre algorithme en SageMath. Donnez le code correspondant ainsi qu'au moins trois exemples d'exécution pour illustrer que votre implémentation est correcte.
\end{parts}
\begin{solution}
Ajouter votre solution ici
\end{solution}

\end{questions}

\end{document}
