\documentclass[a4]{exam}

\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{fullpage}
\usepackage[a4paper]{geometry}
\geometry{top=2cm, bottom=2cm, left=2cm, right=2cm}
\usepackage{url}
\usepackage{amsfonts}
\usepackage{amsmath}

\renewcommand\thequestion{\arabic{section}.\arabic{question}}

\title{Devoir surveillé IM41~: Programmation en C}
\date{Jeudi 17 Mars 2011}
\author{Durée 2h}

\begin{document}
\maketitle
Aucun document papier ou électronique n'est autorisé. Le sujet est volontairement long~: lisez bien tout le devoir, ne bloquez pas sur une question et n'hésitez pas à vous servir des résultats non trouvés pour avancer. La difficulté des questions au sein d'un problème est croissante, et les trois problèmes sont de même difficulté.

\section{Files d'attente}\label{sec:files}
\begin{questions}
  \question Donner la définition mathématique des listes, et quelques exemples de listes. Dans tout le problème, on travaillera sur des listes de réels, les réels étant représentés en C par des \verb|float|.
  \question Donner et expliquer la représentation en langage C des listes vue en cours (appelée représentation par listes simplement chaînées).
  \question \'Ecrire le constructeur correspondant, de prototype \verb|list cons(float h, list t)|.
  \question On s'intéresse à l'opération \verb|sum|, qui à une liste associe la somme de ses éléments (rappel~: les éléments sont supposés réels).
  \begin{parts}
    \part Définissez \verb|sum| comme dans un type abstrait.
    \part Proposez une implémentation en style récursif.
    \part Proposez une implémentation en style itératif.
  \end{parts}
  \question Implémentez l'opération \verb|get| qui renvoie le premier élément d'une liste (attention à la précondition).
  \question Implémentez l'opération \verb|pop|, qui supprime le premier élément d'une liste et renvoie sa queue.
  \question On souhaite maintenant disposer d'une opération \verb|push|, qui ajoute un élément à la fin d'une liste. Le prototype attendu est \verb|list push(float e, list l)|.
  \begin{parts}
    \part Proposez une implémentation en style récursif.
    \part Proposez une implémentation en style itératif.
  \end{parts}
  \question On se donne le programme suivant
\begin{verbatim}
list l = push(2,NULL);
l = push(3,l);
printf("%d", get(l));
pop(l);
l = push(1,l);
printf("%d", get(l));
pop(l);
printf("%d", get(l));
pop(l);
\end{verbatim}
  Représentez l'état de la mémoire après l'exécution de chaque ligne, et déterminez ce que le programme affiche.
  \question Le type abstrait constitué des opérations \verb|get|, \verb|push| et \verb|pop| est appelé {\em file d'attente} dans la littérature. Expliquez pourquoi. Si chaque élément dans la liste correspond à une durée, que calcule la fonction \verb|sum|~?
\end{questions}

\section{Représentation mémoire des matrices}

On souhaite représenter des matrices réelles avec le type \verb|matrix| suivant~:
\begin{verbatim}
struct matrix_t {
  int m; // nombre de lignes
  int n; // nombre de colonnes
  float** coef;
};
typedef matrix_t* matrix;
\end{verbatim}
\begin{questions}
  \question Proposez un constructeur \verb|matrix create_matrix(int m, int n)| qui initialise les coefficients à 0. La solution devra produire $m + 2$ allocations mémoire pour une matrice à $m$ lignes.
  \question \label{q:matrice_exemple}Montrer sur un exemple qu'avec cette représentation, les données de la matrice sont éparpillées en mémoire (avec une matrice de dimension $3\times 4$).
  \question Les processeurs actuels savent optimiser très efficacement l'exécution d'un code lorsque les données traîtées successivement sont proches en mémoire. Pour en tenir compte, proposez une modification de votre constructeur telle que les coefficients de la matrice produite se trouvent dans une même région mémoire. Votre solution devra produire 3 allocations mémoire.
  \question Illustrer l'impact de votre modification en donnant la nouvelle représentation mémoire de l'exemple donné en question \ref{q:matrice_exemple}
  \question On rappelle qu'une matrice symétrique est une matrice $(a_{ij})$ telle que $a_{ij} = a_{ji}$. Dans ce cas particulier, on peut optimiser la représentation pour qu'elle prenne moins de place en mémoire. Proposez une amélioration du constructeur dans ce sens. En supposant que les pointeurs, ainsi que les variables de type \verb|int| et \verb|float| occupent 4 octets, déterminer en fonction de $m$ et $n$ (resp. nombre de lignes et de colonnes de la matrice) la taille respective en octets des deux représentations.
  \question \'Ecrire une fonction \verb|float get(int i, int j)| permettant d'accéder à un élément de la matrice, dans le cas du codage des matrices symétriques (attention aux préconditions~!).
\end{questions}

\section{Tri à bulles sur les listes}
On cherche dans cet exercice à adapter aux listes le tri à bulles vu en cours (et au passage, améliorer sa complexité). Pour rappel, le tri à bulles consiste à parcourir la séquence à trier en regardant deux éléments successifs, et en les permutant s'ils ne sont pas dans le bon ordre. On part de la représentation des listes vue en cours et qui est utilisée dans le problème \ref{sec:files}.
\begin{questions}
  \question \'Ecrire une fonction \verb|int has_inversion(list l)| qui détecte si une liste a au moins deux éléments, et telles que ses deux premiers éléments $x$ et $y$ vérifient $x > y$.
  \question \'Ecrire une fonction \verb|list swap_head(list l)| qui permute les deux premiers éléments d'une liste, s'ils existent (et échoue sinon). Exemple~: si on donne en argument une liste représentant $1 :: 2 :: 3 :: \emptyset$ à \verb|swap_head|, elle retourne la liste représentant $2 :: 1 :: 3 :: \emptyset$.
  \question Soit le programme suivant
\begin{verbatim}
list l = cons(3,cons(2,cons(1,NULL)));
l = swap_head(l);
\end{verbatim}
  Représentez l'état de la mémoire avant et après appel de \verb|swap_head|.

  \question On définit formellement l'opération \verb|ascension| par la récurrence suivante~:
$$\left\{ \begin{array}{ll}
    \mbox{ascension}(\emptyset) = \emptyset\\
    \mbox{ascension}(h :: \emptyset) = h :: \emptyset\\
    \mbox{ascension}(h :: h' :: t) = h :: h' :: t & \mbox{ si } h \leq h'\\
    \mbox{ascension}(h :: h' :: t) = h' :: ascension(h :: t) & \mbox{ si } h > h'\\
  \end{array} \right.$$
Intuitivement la tête remonte dans la liste comme une bulle dans un liquide, et stoppe quand elle rencontre un élément plus grand qu'elle. Implémenter cette opération en utilisant (si vous le souhaitez) les fonctions des questions précédentes, et en veillant bien à la gestion de la mémoire.
\question Quelle est la complexité de l'opération \verb|ascension|~?
\question Implémenter le tri à bulles, en vous aidant de la récurrence suivante~:
$$\left\{ \begin{array}{ll}
    \mbox{sort}(\emptyset) = \emptyset\\
    \mbox{sort}(h :: t) = ascension(h :: sort(t))\\
  \end{array} \right.$$
\question Déterminer et justifier la complexité de ce tri.
\end{questions}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
