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

% Paramètres globaux
%\qformat{\fbox{\textbf{Question \thequestion}} (\totalpoints \ \points)}
\bonuspointpoints{point \emph{bonus}}{points \emph{boni}}
\parindent 0cm
\hqword{Question}
\hpword{Sur}
\hsword{Note}
\htword{Total}

% Réponses
\printanswers

% En-tête et pieds de page
\headrule
\cfoot{\thepage /\pageref{LastPage}}
\lhead{INF7341 --- Structures de données}
\rhead{Hiver 2017}
\newcommand{\headrulewidth}{0.4pt}
\newcommand{\footrulewidth}{0.4pt}

% Boîtes
\newcommand\boite[1]{\begin{center} \begin{tikzpicture} \draw (0,0) rectangle (.99\linewidth, #1 cm); \end{tikzpicture} \end{center}}

% Colonnes mathématiques
\newcolumntype{L}{>{$}l<{$}}
\newcolumntype{C}{>{$}c<{$}}
\newcolumntype{R}{>{$}r<{$}}

% Raccourcis
\newcommand{\bigo}{\mathcal{O}}
\newcommand{\0}{\mathbf{0}}
\newcommand{\1}{\mathbf{1}}
\newcommand{\2}{\mathbf{2}}
\newcommand{\3}{\mathbf{3}}

% 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
           {É}{{\'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
}

% Types abstraits
\newcommand{\Booleen}{\mathrm{Booleen}}
\newcommand{\Naturel}{\mathrm{Naturel}}
\newcommand{\Entier}{\mathrm{Entier}}
\newcommand{\Pile}{\mathrm{Pile}}
\newcommand{\Sommet}{\mathrm{Sommet}}
\newcommand{\Ensemble}{\mathrm{Ensemble}}
\newcommand{\Graphe}{\mathrm{Graphe}}
\newcommand{\Association}{\mathrm{Association}}
\newcommand{\Arbre}{\mathrm{Arbre}}
\newcommand{\Foret}{\mathrm{Foret}}
\newcommand{\Element}{\mathrm{Element}}

% Opérations
\newcommand{\pileVide}{\textsc{pileVide}}
\newcommand{\estVide}{\textsc{estVide}}
\newcommand{\empiler}{\textsc{empiler}}
\newcommand{\depiler}{\textsc{depiler}}
\newcommand{\tete}{\textsc{tete}}
\newcommand{\sommets}{\textsc{sommets}}
\newcommand{\successeurs}{\textsc{successeurs}}
\newcommand{\associationVide}{\textsc{associationVide}}
\newcommand{\set}{\textsc{set}}
\newcommand{\get}{\textsc{get}}
\newcommand{\racine}{\textsc{racine}}
\newcommand{\arbre}{\textsc{arbre}}
\newcommand{\nombreNoeuds}{\textsc{nbNoeuds}}
\newcommand{\nombreFeuilles}{\textsc{nbFeuilles}}
\newcommand{\estFeuille}{\textsc{estFeuille}}
\newcommand{\ajouterEnfant}{\textsc{ajouterEnfant}}
\newcommand{\enfants}{\textsc{enfants}}
\newcommand{\foretVide}{\textsc{foretVide}}
\newcommand{\ajouterArbre}{\textsc{ajouterArbre}}
\newcommand{\nombreArbres}{\textsc{nbArbres}}


\begin{document}
	
\allowdisplaybreaks

\ifprintanswers
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Solution du devoir 1}}}
  \vskip 1.2cm
\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} et à l'\textbf{ordinateur}. Vous devez \textbf{justifier} chacune de vos réponses. La démarche ainsi que l'utilisation correcte de la notation mathématique seront évaluées. Tout retard entraînera une pénalité de \textbf{20\%} par jour (incluant les jours de la fin de semaine).
\fi

\ifprintanswers
  \begin{mdframed} \begin{center}
  \textbf{Auteur : (Indiquer votre nom ici)}
  \end{center} \end{mdframed}
\fi

\begin{center} \gradetable[h] \end{center}

\begin{questions}

% Complexité
\question (\totalpoints{} points)
Pour chacune des expressions suivantes, indiquez si elle est vraie ou fausse. Dans tous les cas, justifiez votre réponse.
\begin{parts}
  \part[5] $\log(n!) \in \Omega(n\log n)$;
  \part[5] $n3^{2n} \in \omega(9^{n-4})$;
  \part[5] $\sum_{i=1}^n i^2 \in \Theta(n^3)$;
  \part[5] $\log^* n \in \bigo(1)$, où $\log^*$ est le logarithme itéré.
\end{parts}
\begin{solution}
Ajouter votre solution ici
\end{solution}

% Pile
\question[20]
Donnez un algorithme qui affiche les sommets d'un graphe orienté $G$ rencontrés lors d'un parcours en profondeur, en respectant les contraintes suivantes~:
\begin{itemize}
  \item Vous n'avez pas le droit d'utiliser la récursivité.
  \item Vous devez utiliser la structure de données Pile, qui respecte la spécification suivante vue en classe~:
\begin{center} \begin{tabular}{|l|L|}
  \hline
  Type       & \Pile                                               \\
  \hline
  Utilise    & \Element, \Booleen                                  \\
  \hline
             & \pileVide : \emptyset \rightarrow \Pile             \\
             & \estVide  : \Pile \rightarrow \Booleen              \\
  Opérations & \empiler  : \Pile \times \Element \rightarrow \Pile \\
             & \depiler  : \Pile \rightarrow \Pile                 \\
             & \tete     : \Pile \rightarrow \Element              \\
  \hline
\end{tabular} \end{center}
  \item Vous devez utiliser la structure de données Graphe, qui respecte la spécification suivante~:
\begin{center} \begin{tabular}{|l|L|}
  \hline
  Type       & \Graphe                                                     \\
  \hline
  Utilise    & \Sommet, \Ensemble                                          \\
  \hline
  Opérations & \sommets     : \Graphe \rightarrow \Ensemble                \\
             & \successeurs : \Graphe \times \Sommet \rightarrow \Ensemble \\
  \hline
\end{tabular} \end{center}
  \item Vous devez utiliser la structure de données $\Association$, qui respecte la spécification suivante~:
\begin{center} \begin{tabular}{|l|L|}
  \hline
  Type       & \Association                                                            \\
  \hline
  Utilise    & \Sommet, \Element                                                       \\
  \hline
             & \associationVide : \emptyset \rightarrow \Association \\
  Opérations & \set             : \Association \times \Sommet \times \Element
                                                              \rightarrow \Association \\
             & \get             : \Association \times \Sommet \rightarrow \Element     \\
  \hline
\end{tabular} \end{center}
  et qui permet de marquer des sommets avec des valeurs quelconques (booléens, entiers, chaînes de caractères, etc.). Vous pouvez supposer que chacune des opérations s'effectuent en temps constant.
  \item Vous pouvez supposer que l'instruction $u.\Call{afficher}$ affiche le contenu d'un sommet $u \in \Sommet$.
  \item Votre algorithme doit être linéaire au pire cas en temps et en espace.
  \item Le graphe $G$ n'est pas nécessairement connexe.
\end{itemize}

Indiquez les complexités temporelle et spatiale de votre algorithme en utilisant la notation asymptotique.
\begin{solution}
Ajouter votre solution ici
\end{solution}

% Arbres et forêts
\question[30]
Dans cette question, nous nous intéressons à deux structures de données, nommées $\Arbre$ et $\Foret$, qui implémentent respectivement une structure d'\emph{arborescence} (arbre enraciné) et de \emph{forêt enracinée}. Elles sont définies de récursivement, l'une par rapport à l'autre, de la façon suivante~:

\begin{center} \begin{tabular}{|l|L|}
  \hline
  Type       & \Arbre                                                         \\
  \hline
  Utilise    & \Naturel, \Booleen, \Element, \Foret                           \\
  \hline
             & \arbre          : \Element \times \Foret \rightarrow \Arbre    \\
             & \racine         : \Arbre \rightarrow \Element                  \\
  Opérations & \enfants        : \Arbre \rightarrow \Foret                    \\
             & \nombreNoeuds   : \Arbre \rightarrow \Naturel                  \\
             & \nombreFeuilles : \Arbre \rightarrow \Naturel                  \\
  \hline
  \hline
  Type       & \Foret                                                         \\
  \hline
  Utilise    & \Naturel, \Booleen, \Element, \Arbre                           \\
  \hline
             & \foretVide      : \emptyset \rightarrow \Foret              \\
             & \estVide        : \Foret \rightarrow \Booleen               \\
             & \ajouterArbre   : \Foret \times \Arbre \rightarrow \Foret   \\
  Opérations & \nombreArbres   : \Foret \rightarrow \Naturel               \\
             & \arbre          : \Foret \times \Naturel \rightarrow \Arbre \\
             & \nombreNoeuds   : \Foret \rightarrow \Naturel               \\
             & \nombreFeuilles : \Foret \rightarrow \Naturel               \\
  \hline
\end{tabular} \end{center}
Donnez les préconditions et les axiomes qui sont cohérents avec la sémantique suivante~:
\begin{enumerate}[(1)]
  \item Les enfants d'un arbre forment une forêt.
  \item Une feuille est un arbre dont les enfants sont une forêt vide.
  \item Une forêt est une liste ordonnée d'arbres enracinés, indicée de $0$ à $k - 1$, où $k$ est le nombre d'arbres dans la forêt.
  \item Lorsqu'on ajoute un arbre à une forêt, il est inséré en dernière position.
\end{enumerate}
Votre ensemble d'axiomes doit être complet et non redondant.
\begin{solution}
Ajouter votre solution ici
\end{solution}

% Hachage
\question
Pour chacun des ensembles suivants $E$, calculez sa cardinalité $n$, donnez une fonction de hachage $h : E \rightarrow \{0,1,2,\ldots,n-1\}$ qui est parfaite et implémentez la fonction de hachage $h$ à l'aide de votre langage préféré parmi Python, Java, C et C++. En particulier, montrez que votre implémentation est correcte en l'illustrant sur plusieurs exemples.
\begin{parts}
  \part[15] $E$ est l'ensemble des points à coordonnées entières dans le rectangle induit par les points $(0,0)$ et $(a,b)$, où $a,b \geq 1$ sont des entiers donnés, c'est-à-dire
$$E = \{(x,y) \mid 0 \leq x \leq a \wedge 0 \leq y \leq b\}.$$
  \part[15] $E$ est l'ensemble des palindromes de longueur $n$ sur l'alphabet $\{0,1\}$, où $n \geq 0$ est un nombre entier donné.
\end{parts}
\begin{solution}
Ajouter votre solution ici
\end{solution}

\end{questions}

\end{document}
