\documentclass[a4paper,11pt]{article}

\usepackage{graphicx}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{latexsym}
%\usepackage{fullpage}
\usepackage{multicol}
%\usepackage{picinpar}
\setlength{\textheight}{24.1cm}
\setlength{\textwidth}{19 cm}
%\evensidemargin 0cm
%\oddsidemargin  0cm
%\topmargin 0cm
\textheight 23cm
%\leftmargin 1cm
\textwidth 15cm

\flushbottom
\parindent 1em
%\hoffset -0.5in
\oddsidemargin 0pt
\evensidemargin 0pt
\marginparsep 10pt
\usepackage{epsfig}

%\newcommand{\elem}[1]{\bigskip \noindent {\bf #1}}
\newcounter{exercice}
\newcommand{\exo}{\stepcounter{exercice} \bigskip \noindent {\bf 
Exercice \theexercice . } }
%\newcommand{\td}{\stepcounter{exercice} \bigskip \noindent {\bf 
%Exercice \theexercice\,(TD). } }
%\newcommand{\tp}{\stepcounter{exercice} \bigskip \noindent {\bf 
%Exercice \theexercice\,(TP). } }
%\newcommand{\tptd}{\stepcounter{exercice} \bigskip \noindent {\bf 
%Exercice \theexercice\,(TP-TD). } }
%\newcounter{abclist}
%\newenvironment{abc}{\begin{list}{(\alph{abclist})}{\usecounter{abclist}}}
%{\end{list}}
%\newcommand{\Feuille}[1] {\hfill  {\Large Feuille de TD / TP
%n$^o$\,#1} \hfill IF122
%\vskip 1mm}
%\newcommand{\titre}[1] {\vskip 10mm{\Huge\hfill #1\hspace*{\fill}}
%\vskip 10mm}

%\def\R{\mbox{I\hspace{-.15em}R}}



%\def\dangermarge{\noindent\hbox to
%  0pt{\hskip-\parindent\dbend\hfill}\ignorespaces}


%\pagestyle{empty}

%\newtheorem{rmq}{Remarque}
%\newcommand{\bs}{\symbol{92}}

% Titre
\title{Controle Continu IF122}
\date{}
\author{}
\pagestyle{empty}



\begin{document}

\maketitle
\vspace{-2cm}


{\bf Les documents sont interdits.  La dur\'ee de l'\'epreuve est de
1h50. Si vraiment vous etes bloqu\'es appelez moi, j'echangerais
\'eventuellement une indication contre une p\'enalit\'e. Le bar\`eme
est donn\'e \`a titre indicatif. Bonne chance.}\\



%\Feuille{}

%\titre{}

\bigskip

{\bf [Question de cours]}

{\bf (1.5 points)} D\'efinissez les types suivant : {\tt ArbreBinaire,
 ArbreBinaireDeRecherche,\\ ListeDoublementChainee}.\\



\underline{Objet du Probl\`eme :} On s'int\'eresse \`a la construction
d'ensembles d'entiers formant une partition de $\{0..n\}$, par exemple
$E_0=\{0,2,4\}, ~ E_1=\{3,5\},~E_2=\{1\}$ est une partition de
$\{0,1,2,3,4,5\}$ en $3$ ensembles. On peut aussi consid\'erer que
l'on a associ\'e \`a chaque entier le numero de l'ensemble auquel il
appartient, par une application que l'on a qu'\`a appeler {\tt
est\_dans}, telle qu'ici on ait : $est\_dans(0)=0, est\_dans(1)=2,
est\_dans(2)=0, est\_dans(3)=1, est\_dans(4)=0, est\_dans(5)=1$.

\exo 

{\bf (0.5 points)} Ecrire un programme {\tt main} qui demande \`a l'utilisateur une
valeur limite pour l'intervalle $\{0..n\}$.

{\bf (1 point)} D\'efinissez un type {\tt Tableau} de taille variable.

{\bf (1.5 points)} Ecrire une fonction {\tt init} qui prenne en argument un entier $n$ et
retourne un {\tt Tableau} d'entiers index\'es par $\{0..n\}$, de sorte
qu'\`a l'indice $i$ corresponde la valeur $i$.

{\bf (1 point)} Ecrire une procedure qui affiche ce {\tt Tableau}.

{\bf (1 point)} Compl\'eter votre programme principal pour enchainer et tester vos
fonctions.\\


\underline{Int\'er\^et pour le Probl\`eme :} Ces fonctions vous
permettent de cr\'eer la partition la plus fine possible, puisque le
{\tt Tableau} retourn\'e par {\tt init} attribue \`a chaque entier $i$
un ensemble numerot\'e $i$. Cet ensemble est dans un premier temps
r\'eduit \`a un seul element. On peut remarquer que puisque une
partition quelconque sera toujours plus grossi\`ere que celle l\`a, on
pourra toujours attribuer des num\'eros aux ensembles en prenant des
valeur dans $\{0..n\}$.\\

{\bf (1 point)} Ecrire une fonction {\tt TrouverEnsemble} qui ait pour argument un
entier $i$, et un {\tt Tableau}, qui retourne le num\'ero de
l'ensemble auquel $i$ appartient.

{\bf (2 points)} Ecrire une proc\'edure {\tt AfficheEnsemble} qui prend en argument un
entier $i$ et un {\tt Tableau} d'entier $T$, et qui affiche les
entiers qui sont dans l'ensemble $i$. (Dans l'exemple du debut si $i$
vaut $1$, on affichera $3,5$.)

{\bf (0.5 points)} Quelle est la bonne mesure de complexit\'e pour {\tt AfficheEnsemble}
(R\'epondez sous forme d'un commentaire dans votre programme)

{\bf (0.5 points)} Compl\'eter votre programme principal en verifiant que si $T=init(n)$
alors la sequence {\tt AfficheEnsemble(1,T) ; AfficheEnsemble(3,T)}
affiche bien $1$ puis $3$.\\


\underline{Suivit du probl\`eme :} On ne peut pas avoir une meilleurs
complexit\'e pour {\tt AfficheEnsemble} sans mieux structurer les
donn\'ees, c'est ce que nous allons faire \`a pr\'esent : nous allons
repr\'esenter les ensembles par une liste chain\'ee de leurs elements.\\

\exo

{\bf (2 points)}  Cr\'eer un type {\tt Ensemble} qui ait $3$ champs, un qui contienne
une liste chain\'ee de ses elements, l'autre qui indiquera sa taille,
et un troisi\`eme qui soit un pointeur vers la derni\`ere cellule de
la liste de ses \'el\'ements.

{\bf (2 points)} Ecrivez une procedure {\tt AfficheEnsemble} qui prend en argument un
{\tt Ensemble} et qui affiche ses caract\'eristiques.

{\bf (1 point)} Cr\'e\'er un type {\tt TableauEnsemble} de taille variable et qui
repr\'esente un tableau index\'es par $\{0..n\}$ d'{\bf \tt Ensemble}
(vous vous inspirerez du tableau d'entier \`a taille
variable). L'intention \'etant que l'ensemble en index $i$ portera le
num\'ero $i$.

{\bf (1 point)} Ecrivez une procedure {\tt AfficheTableauEnsemble} qui affiche tout
les ensembles d'un {\tt TableauEnsemble}.

{\bf (0.5 points)} Ecrire une procedure {\tt AfficheEnsemble} qui prenne en argument un
entier $i$ et un\\ {\tt TableauEnsemble}, qui affiche les \'el\'ements
de l'ensemble num\'ero $i$.

{\bf (0.5 points)} Discutez sa complexit\'e par rapport \`a la premi\`ere question.

{\bf (2 points)} Cr\'eer une fonction {\tt initEnsemble(int n)} qui retourne un {\tt
TableauEnsemble} o\`u l'ensemble numero $i$ de ce tableau ne soit
constitu\'e que du seul element $i$.

{\bf (0.5 points)} Compl\'eter votre programme principal pour v\'erifier rapidement que
vos fonctions sont correctes.\\

On va \`a pr\'esent articuler et tester tout ca, avec une question
bonus plus difficile :\\

\exo 

{\bf (4 points)} Ecrire une proc\'edure {\tt UnionEnsemble(int i, int j, Tableau \&T,\\
TableauEnsemble \&TE)} qui fasse l'union des ensembles qui contiennent
les entiers $i$ et $j$. J'impose que l'union de deux ensemble de
taille diff\'erentes prenne pour num\'ero celui du plus grand (en
taille) des deux. L'ensemble correspondant \`a l'autre num\'ero se
retrouvera donc vide. Pensez \`a modifier le tableau $T$ pour propager
les changements que vous avez effectuez.

\end{document}
