log1-chapitre-rupture.tex

%===================================
\chapter{Les traitements de rupture}
%===================================

\marginicon{objectif}

Dans ce chapitre, on étudie une classe de problèmes qui peuvent tous se
résoudre avec un même type d'algorithme~:
l'algorithme de rupture. À la fin du chapitre vous
devrez être capable de~:

\begin{liste}
	\item 
		détecter qu'on se trouve bien face à un problème qui
		peut entrer dans le cadre d'un algorithme de rupture.
	\item 
		adapter le squelette général de l'algorithme de rupture
		au problème donné.
\end{liste}


%===============================
\section{Le classement complexe}
%===============================

Dans le chapitre sur les tris, nous avons abordé naturellement la notion
du classement des données. Le plus souvent, les données concernées étaient
des variables dites «~simples~»~: nombres (entiers ou
réels), chaines ou variables pour lesquelles la relation d’ordre est
évidente (ordre numérique ou alphabétique). Les algorithmes mis en
œuvre peuvent facilement s’adapter pour d’autre types, par exemple des
objets Date, où l’opérateur de comparaison est remplacé par la méthode
«~estAntérieure()~».

Noter que dans la plupart des cas, les données composées de plusieurs
champs ou attributs, telles les variables structurées, ne possèdent pas
de relation d’ordre naturelle ; par exemple les points d’un espace à
deux ou trois dimensions, ou une structure reprenant toutes les
informations figurant sur une carte d’identité. Si, dans ce dernier
cas, on veut ordonner une série de telles données, il faudra choisir un
premier critère de classement (par exemple le nom ou la date de
naissance) et en cas d’égalité sur le premier critère (deux personnes
peuvent avoir un même nom ou être nées le même jour), il faudra
départager sur un second critère, et éventuellement sur un troisième,
et ainsi de suite.

Ces critères de classement sont bien entendu arbitraires, et dépendent
de l’information qu’on veut retirer de l’ensemble des données. Notons
aussi que l’ordre de classement peut être pour chaque critère croissant
ou décroissant.

Prenons l’exemple d’une structure \code{Etudiant}, contenant les champs
\code{matricule}, \code{nom}, \code{prénom}, 
\code{dateNais} (date de naissance) et \code{option} (G, I ou
R). Pour l’exemple, considérons une liste de 6 étudiants~:

\begin{center}
\begin{tabular}{*{5}{>{\sffamily\arraybackslash}m{2cm}}}
29845 & Durant & Kevin   & 20/01/94 & R\\
30125 & Dupont & Fabrice & 13/06/94 & G\\
30351 & Simon  & André   & 18/11/94 & G\\
30597 & Dupont & Charles & 9/07/94  & G\\
31857 & Guilmant & Léon  & 17/03/96 & R\\
31886 & Durant & Sam     & 30/05/94 & I
\end{tabular}
\end{center}

Cette liste est classée sur le numéro de matricule. C’est un classement
simple réalisé sur un seul champ des données. Le numéro de matricule
étant dans ce cas-ci un \textbf{\textcolor{black}{identifiant}} des
données, le problème de devoir départager ne se pose pas.

Si nous désirons à présent classer sur l’ordre alphabétique des noms, il
faut décider de départager en cas de noms identiques sur un autre
champ, de façon naturelle sur celui des prénoms. Ceci donnerait le
classement double suivant, en \textbf{majeur} sur le nom et en
\textbf{mineur} sur le prénom~:

\begin{center}
\begin{tabular}{*{5}{>{\sffamily\arraybackslash}m{2cm}}}
30597 & Dupont & Charles & 9/07/94  & G\\
30125 & Dupont & Fabrice & 13/06/94 & G\\
29845 & Durant & Kevin   & 20/01/94 & R\\
31886 & Durant & Sam     & 30/05/94 & I\\
31857 & Guilmant & Léon  & 17/03/96 & R\\
30351 & Simon  & André   & 18/11/94 & G
\end{tabular}
\end{center}

Supposons enfin que nous voulions grouper les étudiants par sections,
nous devons alors classer prioritairement sur l’option, départager sur
les noms et ensuite sur les prénoms. C’est alors un classement triple~:
en \textbf{majeur} sur l’option, en \textbf{médian} sur le nom et en
\textbf{mineur} sur le prénom~: 

\begin{center}
\begin{tabular}{*{5}{>{\sffamily\arraybackslash}m{2cm}}}
30597 & Dupont & Charles & 9/07/94  & G\\
30125 & Dupont & Fabrice & 13/06/94 & G\\
30351 & Simon  & André   & 18/11/94 & G\\
31886 & Durant & Sam     & 30/05/94 & I\\
29845 & Durant & Kevin   & 20/01/94 & R\\
31857 & Guilmant & Léon  & 17/03/96 & R
\end{tabular}
\end{center}

Remarque~: le classement sur l’option n’est pas forcément un classement
alphabétique des trois lettres G, I, R ! Toute autre permutation de ces
trois lettres serait une possibilité~acceptable.

En résumé, les exemples ci-dessus constituent des exemples de
\textbf{classements complexes}. On dira que des données sont classées
sur la \textbf{clé complexe} champ1 – champ 2 – … – champ $n$ (où «~champ
$i$~» est un champ de la structure des données) si le classement se fait
prioritairement depuis le champ 1 jusqu’au champ $n$. Autrement dit, si
deux données ont tous leurs champs 1, 2,…,$i$ égaux ($i < n$), le
classement se fait en départageant sur le champ $i + 1$. L’indice du champ
correspond au \textbf{niveau} du classement complexe.

Par exemple, le dernier classement ci dessus est un classement sur la
clé complexe option – nom – prénom. La terminologie «~majeur~»,
«~médian~» et «~mineur~» sont couramment utilisées lorsqu’au plus trois
champs interviennent dans le classement complexe.


%=============================
\section{La notion de rupture}
%==============================

Nous nous plaçons dans le cadre d’un \textbf{ensemble logique} composé
d’\textbf{éléments} de structure identique (variables simples ou
structurées, enregistrements d’un fichier, éléments d’un tableau, d’une
liste ordonnée ou non) et qui sont l’objet d’un \textbf{traitement
itératif} où chaque élément de l’ensemble est parcouru.

Nous parlons de \textbf{rupture} lorsque dans ce traitement itératif, on
constate que l’information courante que l’on souhaite traiter
n’appartient plus à l’ensemble (ou au sous-ensemble) des informations
déjà traitées précédemment.

Les ruptures sont intimement liées au classement complexe des données,
et elles ne se qualifient que par rapport aux champs des données qui
interviennent dans ce classement. On parle donc de \textit{rupture sur
un champ} des données.

Par exemple, dans le dernier classement des étudiants ci-dessus, il y a
rupture sur l’option au niveau de Durant Sam et de Durant Kevin. En
effet, ces deux étudiants délimitent les sous-ensembles d’étudiants
partageant une même option.

Par contre, cela n’aurait pas de sens de parler de rupture sur l’option
dans les deux classements précédents. Ce champ n’appartenant pas à la
clé complexe pour le classement de ces données, la succession des
lettres G, I, R doit être considérée comme aléatoire dans ces deux cas
et sans signification pour le traitement itératif.

Dans le 2\textsuperscript{ème} classement, nous pouvons parler de
rupture sur les noms~: l’étudiant Durant Kevin met fin au sous-ensemble
des Dupont, et l’étudiant Guilmant met fin au sous-ensemble des Durant.


Dans le 1\textsuperscript{er} classement, qui est un classement simple
sur le numéro de matricule, on peut considérer qu’il n’y a qu’un
ensemble de données d’un seul tenant sans ruptures, ou alors qu’il y a
rupture à chaque étudiant, puisque chaque étudiant forme un
sous-ensemble isolé par son numéro de matricule, vu qu’ils sont
obligatoirement distincts.

Notez que toute rupture à un niveau i de la clé de classement complexe
entraine une rupture aux niveaux supérieurs à i. Ainsi, dans le
classement triple, le passage à Durant Kevin entraine une rupture sur
l’option mais aussi sur le nom. Le fait qu’il y ait dans ce classement
deux Durant qui se succèdent doit être considéré comme une coïncidence.
Bien qu’ayant le même nom, ces deux étudiants appartiennent à deux
sous-ensembles différents lorsqu’on prend l’option en considération.

Notons encore que d’un point de vue théorique, deux éléments ont un rôle
spécial et se singularisent quelque peu des autres~: il s’agit du
\textbf{premier} et du \textbf{dernier} élément qui ont pour rôle de
délimiter l’ensemble logique. Le premier est singulier dans la mesure
où il n’est précédé par aucun autre élément, et de plus sa présence
détermine l’existence de l’ensemble (par opposition à un ensemble
vide). Le dernier est particulier parce qu’il termine l’ensemble des
données. Remarquez que RIEN dans ces deux éléments ne signale ces
particularités! Autrement dit, il n’y a pas, à l’intérieur de ces
éléments une information particulière signifiant \textit{je suis le
premier élément} ou \textit{je suis le dernier}.


%================================================
\section{Traitement des ruptures dans un fichier}
%=================================================

Quel que soit l’ordre de tri des données d’un fichier, celui-ci contient
toujours une information importante signalant la fin des données, il
s’agit de la marque de fin de fichier, sa détection ayant pour effet de
faire passer EOF à vrai. Cette marque de fin de fichier constitue donc
la rupture principale d’un fichier, celle signalant la fin du parcours
itératif.

Sans le savoir, nous avons donc déjà traité la rupture générale d’un
ensemble de données dans un fichier (c’est la rupture de «~niveau 0~»,
car elle n’est pas liée à un champ des données, et est naturellement
prioritaire sur ces champs). Pour illustrer cela, reprenons l’exemple
de la liste d’étudiants, que nous imaginons contenue dans un fichier
nommé Student dont les enregistrements sont de type Etudiant. Le
parcours de base de ce fichier est le suivant~:

\cadre{
\begin{pseudo}
	\Module{RuptureNiveau}{student\In: fichier d’Etudiant}{}
		\Decl enr~: Etudiant
		\Open student (lecture)
		\Readf student; enr
		\While{NON EOF(student)}
			\LComment traitement de l’enregistrement
			\Readf student; enr
		\EndWhile
		\Close student
	\EndModule
\end{pseudo}
}

Si nous voulons faire des statistiques globales sur l’ensemble des
étudiants (par ex. simplement les compter), le traitement de
l’information consiste à incrémenter un compteur, et l’algorithme
ci-dessus peut fonctionner quel que soit l’ordre de classement choisi.

Passons à présent au «~niveau 1~» ; c’est-à-dire un traitement de
rupture correspondant à un classement complexe sur un champ. Imaginons
que nous voulions savoir quel est le nombre d’étudiants dans chaque
option. Une solution consisterait à avoir 3 compteurs, un par option.
On peut imaginer une façon plus judicieuse de faire à partir du dernier
classement~qui contient précisément les étudiants déjà groupés par
option~: à chaque fois qu’il y a rupture sur l’option, on connait alors
le total d’étudiants dans l’option qui vient d’être parcourue. Ceci ne
nécessite qu’un seul compteur remis à 0 à chaque fois qu’une nouvelle
option est rencontrée, c’est-à-dire à chaque rupture. De plus
l’algorithme serait aussi fonctionnel quelle que soit le nombre
d’options. Voici une solution~: 

\cadre{
\begin{pseudo}
	\Module{RuptureNiveau1}{student\In~: fichier d’Etudiant}{}
		\LComment on suppose les données classées en majeur sur l’option
		\Decl enr~: Etudiant
		\Decl saveOption~: caractère
		\Decl cpt~: entier
		\Empty
		
		\Open student (lecture)
		\Readf student; enr
		\Empty		
		
		\While{NON EOF(student)}
			\Let saveOption \Gets enr.option
			\Let cpt \Gets 0
			\While{NON EOF(student) ET saveOption = enr.option}
				\LComment traitement de l’enregistrement
				\Let cpt \Gets cpt + 1
				\Readf student; enr
			\EndWhile
			\Write cpt, «~étudiant dans l’option~», saveOption
		\EndWhile
		\Empty		

		\Close student
	\EndModule
\end{pseudo}
}

\begin{Emphase}[reflexion]{Questions de réflexion}
\begin{enumerate}
	\item 
		Pourquoi la condition \code{NON EOF(student)}
		apparait-elle une 2\up{ème} fois dans la boucle 
		intérieure ?
	\item 
		Pourquoi l’ordre de lecture est-il dans la boucle centrale et pas
		ailleurs ?
	\item 
		Pourquoi dans l’instruction d'affichage, on trouve
		\code{saveOption} plutôt que \code{enr.option} ?
	\item 
		l’ordre des conditions apparaissant dans le 2\up{ème} tant
		que est-il important ?
\end{enumerate}
\end{Emphase}

L’algorithme ci-dessus se généralise facilement si on ajoute davantage
de niveaux de rupture. Pour illustrer le «~niveau 2~», prenons encore
l’exemple suivant. On veut connaitre pour chaque groupe le nombre
d’étudiants nés dans les différentes années de naissance. L’algorithme
correspondant s’écrit facilement et fonctionne lorsque le fichier est
cette fois-ci classé en majeur sur le groupe et en mineur sur la date
de naissance~(ou encore classement double sur la clé complexe option –
dateNais)~:

\cadre{
\begin{pseudo}
	\Module{RuptureNiveau2}{student\In~: fichier d’Etudiant}{}
		\LComment on suppose les données classées en majeur sur l’option
		\LComment et en mineur sur la date de naissance (ordre chronologique)
		\Decl enr~: Etudiant
		\Decl saveOption~: caractère
		\Decl saveAnneNaissance~: entier
		\Decl cpt~: entier
		\Empty

		\Open student (lecture)
		\Readf student; enr
		\Empty
		
		\While{NON EOF(student)}
			\Let saveOption \Gets enr.option
			\While{NON EOF(student) ET saveOption = enr.option}
				\Let saveAnneNaissance \Gets enr.dateNais.getAnnée()
				\Let cpt \Gets 0
				\Custom \algorithmicwhile\ NON EOF(student) ET saveOption = enr.option
					\Suite ET saveAnneNaissance = enr.dateNais.getAnnée() \algorithmicdo
					\LComment traitement de l’enregistrement
					\Let cpt \Gets cpt + 1
					\Readf student; enr
				\EndCustom \algorithmicend\ \algorithmicwhile
				\Write cpt, «~étudiant dans l’option~», saveOption, 
					\Suite «~sont nés en~», saveAnneeNaissance
			\EndWhile 
		\EndWhile
		\Empty

		\Close student
	\EndModule
\end{pseudo}
}

Ces exemples montrent que l’algorithme de rupture et le classement du
fichier sont étroitement liés. La structure de l’algorithme épouse le
schéma de la clé complexe du classement des données. À un classement
déterminé correspondra un algorithme bien précis, et le choix d’un
classement d’un fichier peut être fait précisément en vue qu’un certain
algorithme donne un résultat bien déterminé.


%====================================================
\section{Traitements de clôture et d’initialisation}
%====================================================

Chaque rupture du traitement itératif des éléments d’un ensemble
entraine un \textbf{traitement de clôture} sur cet ensemble. Comme une
rupture à un niveau implique des ruptures en cascade sur tous les
niveaux d’ordre plus grands, un traitement de clôture d’un ensemble ne
pourra se faire que lorsque le dernier sous-ensemble de cet ensemble
sera clôturé.

De la même manière, l’arrivée d’un élément appartenant à un nouvel
ensemble nécessite un \textbf{traitement d’initialisation} de ce nouvel
ensemble.

En fait, il ne s’agit que de généraliser ce qui se fait lors du
traitement d’un fichier (travaux d’initialisation consistant par
exemple à mettre des totalisateurs ou compteurs à zéro et travaux de
clôture consistant par exemple à imprimer des résultats totaux
particuliers) à tous les ensembles et sous-ensembles composant ce
fichier !


%=======================
\section{Généralisation}
%=======================

L’algorithme de rupture vu ci-dessus s’adapte aussi à d’autres
structures que les fichiers. S’il a été présenté avec des fichiers
c’est parce qu’il a été développé à l’origine pour calculer certains
résultats sur des grands ensembles de données sans nécessiter l’usage
de tableaux. 

Montrons simplement comment s’adapterait le modèle de rupture de niveau
1 ci-dessus si les données étaient contenues dans un tableau plutôt
qu’un fichier, ce tableau étant bien entendu ordonné de la même façon
que précédemment.

\cadre{
\begin{pseudo}
	\Module{RuptureNiveau1dansTableau}{Student\In: tableau[1 à n] d’Etudiant}{}
		\LComment on suppose les données classées en majeur sur l’option
		\Decl élément~: Etudiant
		\Decl saveOption~: caractère
		\Decl cpt, i~: entier
		
		\Let i \Gets 1
		\While{i ${\leq}$ n}
			\Let saveOption \Gets tab[i].option
			\Let cpt \Gets 0
			\While{i ${\leq}$ n ET saveOption = tab[i].option}
				\LComment traitement de l’élément
				\Let cpt \Gets cpt + 1
				\Let i \Gets i + 1
			\EndWhile
			\Write cpt, «~étudiant dans l’option~», saveOption
		\EndWhile
	\EndModule
\end{pseudo}
}

Observer comment dans cet exemple se transforme la progression dans
l’ensemble des données, la constatation de rupture à l’issue de chaque
sous-groupe et à la fin de l’ensemble.


%==================
\section{Exercices}
%===================

\begin{Exercice}{La chasse au gaspi.}
	À l’ESI, les quantités de feuilles imprimées et photocopiées par les
	professeurs et les étudiants sont enregistrées dans un fichier
	séquentiel \code{impression}, créé au début de l’année en cours et mis à jour
	tous les soirs. Le service technique désirant facturer les
	«~exagérations~», a demandé à pouvoir utiliser ce fichier de manière à
	établir des statistiques du nombre de feuilles imprimées par
	utilisateur.

	Le fichier \code{impression} présente la structure d’enregistrement
	\code{Enr} suivante~:
	
	\cadre{
	\begin{pseudo}
	\Struct{Enr}
	\Decl login~: chaine \RComment login de l’utilisateur
	\Decl date~: Date \RComment date de la session d’impression
	\Decl moment~: Moment \RComment moment de la session
	\Decl nombre~: entier \RComment nombre de feuilles imprimées ou photocopiées
	\EndStruct
	\end{pseudo}
	}

	De plus, il est ordonné croissant en majeur sur le champ login et en
	mineur sur la date. 

	\begin{enumerate}[label=\alph*)]
		\item 
			Écrire un algorithme permettant d'écrire une ligne par
			utilisateur dont le nombre total de feuilles imprimées dépasse une
			valeur limite entrée en paramètre. Cette ligne contiendra le login et
			le nombre.
		\item 
			Le fichier étant mis à jour tous les soirs, il est plus probable
			qu'il soit trié en majeur sur la date et en mineur sur
			le login. Décrivez l'allure générale de
			l'algorithme dans ce cas~: variables nécessaires et
			grandes étapes de la solution.
	\end{enumerate}
\end{Exercice}
	
\begin{Exercice}{Statistiques de ventes de voitures.}
	Un grand quotidien dispose d’un fichier \code{ventes} regroupant les ventes de
	voitures neuves pendant l’année dernière. Chaque demande
	d’immatriculation a donné naissance à un enregistrement dans ce
	fichier. Ce fichier est ordonné croissant en majeur sur la marque de
	voiture et en mineur sur le type. Chaque enregistrement de ce fichier
	est de type structure \code{Voiture}.

	\cadre{
	\begin{pseudo}
	\Struct{Voiture}
	\Decl plaque~: chaine \RComment numéro d’immatriculation
	\Decl marque~: chaine \RComment marque de la voiture (par ex. «~Citroën~»)
	\Decl type~: chaine \RComment marque de la voiture (par ex. «~Citroën~»)
	\Decl nom~: chaine \RComment nom du propriétaire
	\Decl adresse~: chaine \RComment dresse du propriétaire
	\Decl date~: Date \RComment date de la demande d’immatriculation
	\EndStruct
	\end{pseudo}
	}

	Afin de préparer le travail des journalistes, il a été demandé au
	service informatique de préparer un affichage qui globalise les ventes
	de voiture par marque et pour chaque marque, par type. Cet affichage
	contiendra les renseignements suivants~:

	\begin{liste}
		\item 
			un titre général «~Ventes de voitures neuves en ****~» où les étoiles
			seront remplacées par l’année concernée.
		\item 
			pour chaque marque~:
			\begin{liste}
				\item 
					le nom de la marque
				\item 
					pour chaque type de modèle
				\item 
					le nom de ce type et le nombre de voitures neuves vendues
				\item 
					le nombre total de voitures vendues pour cette marque
			\end{liste}
		\item 
			enfin, le total global du nombre de voitures vendues toutes marques
			confondues
	\end{liste}
	
	À la fin, on souhaite également avoir le palmarès des ventes globales
	par marque donné en ordre décroissant des ventes (en cas d’égalité de
	ventes pour des marques différentes, on respectera l’ordre alphabétique
	pour la parution dans ce palmarès). On devra donc écrire d’abord la
	marque pour laquelle il y a eu le plus de ventes, et ainsi de suite
	jusque la marque pour laquelle il y en a eu le moins. Notez également
	qu’une marque pour laquelle il n’y a pas eu la moindre vente,
	n’apparaitra pas dans ce palmarès !

	Écrivez un algorithme produisant l'affichage décrit.
\end{Exercice}

\begin{Exercice}{Les fanas d'info.}

	Une grande société d’informatique a organisé durant les douze derniers
	mois une multitude de concours ouverts aux membres de clubs
	d’informatique. Elle souhaiterait récompenser le club qui aura été le
	plus «~méritant~» durant cette période au point de vue de la
	participation des mineurs. Chaque résultat individuel des participants
	(y compris des majeurs) a été enregistré dans un fichier \code{résultats} dont
	la structure d’un enregistrement \code{Enr} est~:

	\cadre{
	\begin{pseudo}
	\Struct{Enr}
	\Decl nom~: chaine \RComment nom et prénom du participant
	\Decl âge~: entier \RComment {âge du participant au moment du concours}
	\Decl référence~: chaine \RComment référence du club auquel appartient ce participant
	\Decl numéro~: entier \RComment numéro du concours auquel il a participé
	\Decl résultat~: entier \RComment résultat obtenu lors de ce concours (sur 100)
	\EndStruct
	\end{pseudo}
	}

	Sachant que ce fichier est ordonné en majeur sur le champ la référence
	et en mineur sur le nom, on demande d’écrire l’algorithme qui écrit les
	informations suivantes~:

	pour chaque club~:

	\liststyleListv
	\begin{liste}
		\item 
			sa référence
		\item 
			pour chaque membre mineur de ce club~:
		\item 
			son nom et prénom
		\item 
				la cote moyenne sur 100 des concours auquel ce membre a participé
		\item 
			le nombre total de participations des membres mineurs
	\end{liste}
	
	\textbf{N.B.~: }un membre mineur qui s’est inscrit à un concours = une
	participation. Un club qui n’aura eu aucun membre mineur participant
	figurera quand même dans le résultat avec la mention «~Pas de
	participation de membre mineur~». Par contre, un club dont aucun membre
	n’a participé au moindre concours ne sera pas écrit.

	À la fin, on affichera la référence du meilleur club, à savoir celui qui
	a eu le plus de cotes moyennes des membres mineurs supérieures ou
	égales à 80\%. En cas d’égalité, on départagera sur le club qui a eu le
	plus grand nombre de participations des mineurs (et on suppose qu’il
	n’y a pas d’ex-aequo sur ce point). 
\end{Exercice}

\begin{Exercice}{Degré ou de force.}

	Soit le fichier séquentiel \code{relevés} reprenant par site où un capteur de
	température est installé, les relevés réalisés au cours des douze
	derniers mois. Deux relevés sur un même site sont distanciés au minimum
	de 30 secondes et au maximum de 10 minutes. Chaque enregistrement du
	fichier a la structure \code{Relevé} suivante~:

	\cadre{
	\begin{pseudo}
	\Struct{Relevé}
	\Decl lieu~: chaine \RComment site d’un relevé
	\Decl date~: Date \RComment {âge du participant au moment du concours}
	\Decl moment~: Moment \RComment référence du club auquel appartient ce participant
	\Decl température~: réel \RComment température relevée
	\EndStruct
	\end{pseudo}
	}
	
	Ce fichier est ordonné croissant en majeur sur le lieu, en médian sur la
	date et en mineur sur le moment. On demande d’écrire l’algorithme
	permettant de créer~:

	\begin{liste}
		\item 
			le fichier \code{quotidien} qui reprend les températures maximale et minimale
			pour chaque site et chaque jour ; la structure d’un enregistrement sera
			LIEU – DATE – MAX – MIN
		\item 
			le fichier \code{mensuel} qui reprend par site les températures maximale et
			minimale par mois ainsi que le nombre moyen de relevés quotidiens ; la
			structure d’un enregistrement sera LIEU – MOIS – MAX – MIN – NOMBRE
	\end{liste}
\end{Exercice}

\begin{Exercice}{NBA actions.}
	Soit le fichier \code{résultats} reprenant l’ensemble des points marqués et
	concédés pour chaque équipe inscrite dans le championnat NBA de
	basket-ball. Chaque rencontre jouée du championnat donne naissance à
	deux enregistrements, un pour chacune des deux équipes disputant ce
	match. La structure d’un enregistrement de type \code{Résultat} est
	:
	
	\cadre{
	\begin{pseudo}
	\Struct{Résultat}
	\Decl équipe~: chaine \RComment le nom de l’équipe
	\Decl ptsGagnés~: entier \RComment les points marqués par l’équipe
	\Decl ptsPerdus~: entier \RComment les points encaissés par l’équipe
	\Decl date~: Date \RComment la date de la rencontre
	\EndStruct
	\end{pseudo}
	}

	Le fichier est ordonné croissant en majeur sur l'équipe
	et en mineur sur la date. On demande d’écrire l’algorithme qui
	permet~d’écrire~:

	\begin{liste}
		\item 
			un titre général~: «~STATISTIQUES NBA~»
		\item 
			pour chaque équipe~:
			\begin{liste}
				\item 
					son nom 
				\item 
					le total des points marqués
				\item 
					le total des points encaissés
				\item 
					le plus grand écart de points lors d’une rencontre de cette équipe
			\end{liste}
		\item 
			en fin de traitement~:
			\begin{liste}
				\item 
					le nombre total de points marqués pour l’ensemble des équipes.
				\item 
					le mois pendant lequel le plus de points ont été marqués
				\item 
					le total de points pour le match le plus spectaculaire (plus grand total
					de points pour et contre lors d’un match)
			\end{liste}
	\end{liste}
	
	De plus, cet algorithme enregistrera dans le fichier \code{playoff} le nom des
	équipes dont le pourcentage des victoires est au moins 50\% (une
	victoire se traduit par un enregistrement dans lequel le nombre de
	points marqués est supérieur au nombre de points encaissés, sachant que
	le match nul n’existe pas)
\end{Exercice}

\begin{Exercice}{Le meilleur site.}
	Pendant le mois de novembre dernier, le fournisseur d’accès ESINET a
	proposé aux internautes du monde entier d’élire le plus beau site du
	\textit{World Wide Web}. Pour ce faire, ESINET a enregistré dans un
	fichier séquentiel \code{votes} les votes émis par e-mail durant ce mois. Le
	règlement du concours était simple: on pouvait voter pour plusieurs
	sites, mais pas plusieurs fois pour le même site. Si cela arrivait
	quand même, les votes émis à partir d’une même adresse e-mail pour un
	même site étaient quand même enregistrés dans le fichier \code{votes} mais ne
	pouvaient compter que pour \textbf{un seul} vote valable. Sachant que
	ce fichier a la structure d’enregistrement suivante~:

	\cadre{
	\begin{pseudo}
	\Struct{Vote}
	\Decl url~: chaine \RComment adresse du site choisi (ex.~: «~http://www.heb.be~»)
	\Decl email~: entier \RComment adresse e-mail du votant
	\Decl jour~: entier \RComment jour du vote (de 1 à 31)
	\EndStruct
	\end{pseudo}
	}

	et que le fichier est ordonné croissant en majeur sur
	l'URL et en mineur sur l'email,
	écrire un algorithme qui en une seule lecture du fichier écrit les
	informations suivantes~:

	\begin{liste}
		\item 
			les adresses des sites pour lesquels il y a eu au moins un vote, ainsi
			que le nombre de votes valables recueillis 
		\item 
			le nom du site gagnant, c’est-à-dire celui qui a reçu le plus de votes
			valables, ainsi que le nombre de ces votes (on peut supposer qu’il n’y
			a pas eu d’ex-æquo)
		\item 
			la date du jour qui a connu le plus d’activité, c’est-à-dire le plus
			grand nombre de votes (valables ou non).
	\end{liste}
\end{Exercice}	

\begin{Exercice}{Quoi de neuf, doc ?}
	Vous n’êtes pas sans savoir que les médicaments, dans la plupart des
	cas, doivent faire l’objet d’une prescription médicale pour pouvoir
	être délivrés. Sur la prescription de médicaments, appelée également
	l’ordonnance, on trouve les médicaments prescrits, le cachet du
	prescripteur ou médecin, avec son nom et son numéro d’agrément.

	Chaque ordonnance, lorsqu’elle est présentée au pharmacien, est scannée.
	L’image ainsi obtenue passe dans un programme de traitement
	informatique qui génère autant d’enregistrements dans un fichier qu’il
	y a de médicaments différents prescrits. Les ordinateurs des pharmacies
	sont reliés à un ordinateur central situé à Bruxelles. Ainsi, les
	enregistrements créés au niveau des pharmacies sont directement ajoutés
	à un fichier central annuel appelé \code{prescriptions}. 

	La structure \code{Prescription} des enregistrements de ce fichier est
	la suivante~:

	\cadre{
	\begin{pseudo}
	\Struct{Prescription}
	\Decl date~: Date \RComment  date de la prescription
	\Decl numéro~: entier \RComment numéro d’agrément du médecin
	\Decl nom~: chaine \RComment nom du médicament
	\Decl qté~: entier \RComment quantité de ce médicament prescrite sur cette ordonnance
	\EndStruct
	\end{pseudo}
	}

	On demande d’écrire l’algorithme d’une application qui permettra d’après
	ce fichier de compter le nombre de médecins différents qui ont prescrit
	des médicaments et d’afficher le résultat.

	Pour réaliser cela, expliquez brièvement de quelle façon ce fichier
	devrait être ordonné.
\end{Exercice}

\begin{Exercice}{Vos papiers, SVP !}
	La gendarmerie a enregistré dans un fichier \code{pv} toutes les infractions au
	code de la route commises par des automobilistes ayant une plaque belge
	durant l’année dernière. La structure \code{Infraction} d’un
	enregistrement comprend les champs~:

	\cadre{
	\begin{pseudo}
	\Struct{Infraction}
	\Decl plaque~: chaine
	\Decl date~: Date 
	\Decl moment~: Moment
	\Decl type~: chaine \RComment code associé à une infraction donnée
	\EndStruct
	\end{pseudo}
	}

	Le fichier est ordonné croissant sur la plaque et ne contient aucune
	erreur. Il peut bien entendu y avoir dans le fichier plusieurs
	enregistrements ayant le même numéro de plaque.

	La gendarmerie dispose également d’une table \code{amendes}
	de 60 éléments structurés de type \code{Amende} comprenant les champs~:

	\cadre{
	\begin{pseudo}
	\Struct{Amende}
	\Decl type~: chaine \RComment code associé à une infraction donnée
	\Decl libellé~: chaine \RComment l’infraction (ex. «~excès de vitesse~»)
	\Decl montant~: entier \RComment montant de l’amende en €
	\EndStruct
	\end{pseudo}
	}

	Écrire l’algorithme qui, en une seule lecture du fichier \code{pv}, calcule et
	écrit dans le fichier \code{stats}, pour chaque plaque apparaissant dans le
	fichier \code{pv}, une ligne contenant le numéro de plaque du véhicule et le
	montant total annuel des amendes pour cette plaque. On écrira également
	en fin de traitement le total des montants des amendes pour toutes les
	plaques recensées.

	Enfin, on écrira un tableau récapitulatif du nombre d’amendes par type
	d’amendes. Ce tableau reprendra le libellé et le nombre en commençant
	par les plus fréquentes jusqu’au moins fréquentes. 
\end{Exercice}

\begin{Exercice}{Bruxelles-national}
	Votre société d’informatique a signé un contrat avec l’aéroport national
	pour l’établissement informatique de statistiques sur le trafic aérien.
	Le service informatique de l’aéroport enregistre sans arrêt les
	atterrissages et décollages des avions ainsi que d’autres informations.
	Pour l’année dernière, toutes les informations sont enregistrées dans
	le fichier \code{vols}.

	La structure \code{Vol} des enregistrements de ce fichier est~: 

	\cadre{
	\begin{pseudo}
	\Struct{Vol}
	\Decl numéro~: chaine \RComment le numéro du vol
	\Decl type~: caractère \RComment {‘A’ pour atterrissage ou ‘D’ pour décollage}
	\Decl lieu~: chaine \RComment le lieu d’où provient le vol (type ‘A’) ou sa destination (type ‘D’)
	\Decl cie~: chaine \RComment compagnie aérienne propriétaire de l’avion
	\Decl nb~: entier \RComment le nombre de passagers (pouvant valoir 0)
	\Decl qté~: réel \RComment le tonnage de marchandise transportée (pouvant valoir 0)
	\Decl date~: Date \RComment date du vol
	\Decl moment~: Moment \RComment heure de départ ou d’arrivée
	\EndStruct
	\end{pseudo}
	}

	Sachant que ce fichier est ordonné croissant en majeur sur la compagnie
	et en mineur sur lieu, on vous demande d’établir l’algorithme qui
	permette d’établir les statistiques suivantes~:

	\begin{liste}
		\item 
			pour chaque compagnie apparaissant dans \code{vols}~:
		\begin{liste}
			\item 
				une ligne titre avec le nom de la compagnie,
			\item 
				pour chaque endroit desservi par cette compagnie, une seule ligne avec
				son nom, le nombre d’atterrissages d’avions provenant de ce lieu, le
				nombre de décollages d’avions vers ce lieu
			\item 
				en fin de chaque compagnie, le nom du lieu d’où provient le plus grand
				nombre de passagers transportés par cette compagnie là, ainsi que le
				nom du lieu vers lequel la plus grande quantité totale de marchandises
				a été expédiée par cette compagnie là.
		\end{liste}
		\item 
			à la fin on écrira~: 
		\begin{liste}
			\item 
				la différence entre le nombre \textbf{total} de passagers arrivés et
				partis ;
			\item 
				le nombre de compagnies trouvées dans le fichier ;
			\item 
				le nom de la compagnie ayant eu le moins de vols ;
			\item 
				la tranche horaire où le trafic en nombre de vols est le plus intense
				(\textbf{N.B.:} on peut utiliser un tableau pour résoudre cette
				requête)
		\end{liste}
	\end{liste}
	
	\textbf{N.B.:} Pour toutes les recherches de maxima ou minima, on les
	supposera uniques. La première tranche horaire est 0 et la dernière 23.
\end{Exercice}

\begin{Exercice}{Une suite logique}
	\textstyleMotCl{\textmd{Voici une petite suite logique~:}}

	\begin{enumerate}[label=\alph*)]
		\item 
			\textstyleMotCl{\textmd{Comprenez la logique derrière cette suite et
			écrivez la ligne suivante.}}
			\begin{center}
			\begin{minipage}{4.748cm}
			{\textstyleMotCl{\textmd{1}}}

			{\textstyleMotCl{\textmd{1 1}}}

			{\textstyleMotCl{\textmd{2 1}}}

			{\textstyleMotCl{\textmd{1 2 1 1}}}

			{\textstyleMotCl{\textmd{1 1 1 2 2 1}}}

			{\textstyleMotCl{\textmd{3 1 2 2 1 1}}}

			{\textstyleMotCl{\textmd{1 3 1 1 2 2 2 1}}}

			{\textstyleMotCl{\textmd{1 1 1 3 2 1 3 2 1 1}}}

			{\textstyleMotCl{\textmd{3 1 1 3 1 2 1 1 1 3 1 2 2 1}}}

			{\textstyleMotCl{\textmd{...}}}
			\end{minipage}
			\end{center}
		\item 
			Écrivez un module qui reçoit une ligne (sous forme
			d'une Liste d'entiers) et retourne la
			ligne suivante (sous forme d'une autre liste
			d'entiers). Votre première tâche sera probablement de
			comprendre ce que vient faire cet exercice dans le chapitre des
			ruptures.
		\item 
			Écrivez le module qui reçoit n (un entier) 
			et affiche les n premières lignes de cette suite
			logique.
	\end{enumerate}
\end{Exercice}

\begin{Exercice}{Éliminer les doublons d'une liste.}
	Soit une liste \textbf{ordonnée}
	d'entiers avec des possibles redondances. Écrire un
	module qui enlève les redondances de la liste. On vous demande de créer
	une \textbf{nouvelle liste} (la liste de départ reste inchangée)

	Exemple~: Si la liste est (1, 3, 3, 7, 8, 8, 8) le résultat est (1, 3, 7, 8).
\end{Exercice}