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

% 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 4}}}
  \vskip 1.2cm
\else
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Devoir 4}}}
  \centerline{\small (à remettre au plus tard le 1er mai, à 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}

% Poset
\question (\totalpoints{} points)
Soit $P$ un ensemble fini muni d'une relation d'ordre $\leq$.
\begin{parts}
  \part[20] Donnez le pseudocode d'une fonction
      \entetefunc{Hauteur}{$P$ : poset}{naturel}
    qui retourne la hauteur de l'ensemble partiellement ordonné $P$. Indiquez toutes les opérations que vous supposez disponibles pour $P$. \emph{Note~:} L'efficacité de votre solution sera prise en considération.
  \part[20] Analysez la complexité de votre en fonction selon les deux implémentations de base (listes d'adjacence ou représentation matricielle).
\end{parts}

% Énumération
\question (\totalpoints{} points)
Pour chacune des situations suivantes, donnez les meilleures complexités d'initialisation, de délai et spatiale possibles par rapport au nombre d'éléments $n$.
\begin{parts}
  \part[10] Parcourir les éléments d'une liste simplement chaînée dans l'ordre; 
  \part[10] Parcourir les éléments d'une liste simplement chaînée en inversant l'ordre; 
  \part[10] Parcourir les éléments d'un arbre binaire de recherche quelconque;
  \part[10] Parcourir les éléments d'un arbre AVL.
\end{parts}

% Files de Fibonacci
\question
Nous avons vu en classe la structure de données de files de Fibonacci. Le but de cette question est de compléter l'analyse de complexité des quatre opérations de base. Plus précisément, montrez qu'on a les complexités suivantes~:
\begin{parts}
  \part[3] Insertion en $\Theta(1)$ au pire cas et en complexité amortie.
  \part[3] Lecture du minimum en $\Theta(1)$ au pire cas et en complexité amortie.
  \part[4] Fusion de deux files en $\Theta(1)$ au pire cas et en complexité amortie.
  \part[10] Extraction du minimum au pire cas en $\bigo(n)$ et en $\bigo(\log n)$ en complexité amortie.
\end{parts}

\end{questions}

\end{document}
