log1-chapitre-fichier.tex

%===============================
\chapter{Le fichier séquentiel}
%===============================


\marginicon{objectif}

Dans ce chapitre, on voit comment manipuler les fichiers séquentiels.
Ensuite, on généralise la notion de fichier à la notion de «~séquence~»
qui peut englober aussi d'autres structures comme les
listes et les tableaux.

Dans la première partie de ce chapitre, nous utilisons la convention
courante qu'une lecture infructueuse est nécessaire
pour détecter la fin d'un fichier. En fin de chapitre
on voit une autre convention de lecture qu'on
rencontre dans certains langages et qui stipule qu'on
peut détecter la fin de fichier juste après la dernière lecture utile.

%=====================
\section{Présentation}
%=====================

Un \textbf{fichier} informatique est une unité informationnelle
physiquement stockée sur un support de mémoire de masse permanent
(disque dur, CD-ROM, clé USB par exemple). 


Le qualificatif \textbf{séquentiel}\footnote{Il existe également des
fichiers à \textit{accès direct} (cf. votre cours
d'organisation des données)} signifie que
lorsqu'on \textit{lit} un fichier, les éléments sont
accédés dans une \textbf{séquence préétablie et ordonnée} (pour accéder
à un élément de position donnée, il faut d’abord avoir \textit{lu} tous
les éléments précédents). De même, lorsqu'on
\textit{écrit} un fichier séquentiel, les éléments sont ordonnés dans
l'ordre dans lequel ils sont écrits (une prochaine
lecture les donnerait dans ce même ordre).

Nous allons considérer qu'un fichier peut être lu ou
écrit mais pas les deux en même temps\footnote{Certains systèmes et
langages mettent à disposition des fichiers en lecture/écriture
simultanées}. On considère aussi qu'un fichier doit
explicitement être \textbf{ouvert} avant toute lecture/écriture et
qu'il doit être \textbf{fermé} après la dernière
lecture/écriture.

Lors d'une lecture de fichier, on appelle
«~\textbf{élément courant~»}, le prochain élément qui sera lu.
L’ensemble étant fini, il doit être possible d’en détecter la
\textbf{fin}; on peut imaginer la présence d’une marque particulière
caractérisant cette fin (\textbf{marque de fin de fichier}).

On comprend donc qu'il faut une lecture supplémentaire
explicite pour lire la fin de fichier et se rendre ainsi compte
qu'il n'y a plus rien à lire. En fin
de chapitre on présente un autre type d'accès où on
sait qu'on est à la fin du fichier juste après la
lecture du dernier élément.

Le fichier n'est pas la seule structure qui peut être
accédée en séquence. On pourrait faire de même pour un tableau, une
liste ou encore d'autres structures que vous verrez en
deuxième année. Ce point est, lui aussi, abordé en fin de chapitre.


%==========================================
\section{Primitives}
%===========================================

Voyons les notations utilisées pour manipuler des fichiers.

{\sffamily\bfseries\upshape
Déclaration d’un fichier séquentiel}

Les fichiers utilisés dans un algorithme seront déclarés dans la partie
déclarative du code selon le modèle : 

\cadre{
\begin{pseudo}
	\Decl nomFichier : fichier de T
\end{pseudo}
}

où \textstyleCodeInsr{T} est le type des éléments du fichier (types
simples, variables structurées, objets)


Exemples:

\cadre{
\begin{pseudo}
	\Decl fileNumbers : fichier d’entiers
	\Decl fichierTexte : fichier de chaines
	\Decl fichCalendrier : fichier de Date
\end{pseudo}
}

\bigskip

{\sffamily\bfseries\upshape
Ouverture d’un fichier en lecture }

\cadre{
\begin{pseudo}
	\Stmt \K{ouvrir} nomFichier (\K{lecture})
	\RComment ou \K{IN} ou \K{INPUT}
\end{pseudo}
}

Cette primitive met à la disposition de l’exécutant le fichier
\textstyleCodeInsr{nomFichier} en spécifiant que ce fichier sera
utilisé en lecture (IN). De plus, elle positionne la tête de lecture
devant le premier élément du fichier (qui n’est donc pas encore lu).
Attention, si le fichier \textstyleCodeInsr{nomFichier} est inexistant,
cette primitive provoque l’interruption du programme. 

Pour ouvrir plusieurs fichiers en lecture :

\cadre{
\begin{pseudo}
	\Stmt \K{ouvrir} nomFichier1, nomFichier2, nomFichier3 (\K{lecture})
	\RComment ou \K{IN} ou \K{INPUT}
\end{pseudo}
}

{\sffamily\bfseries\upshape
Ouverture d’un fichier en écriture }

\cadre{
\begin{pseudo}
	\Stmt \K{ouvrir} nomFichier (\K{écriture}) 
	\RComment ou \K{OUT} ou \K{OUTPUT}
\end{pseudo}
}

Cette primitive met à la disposition de l’exécutant le fichier
\textstyleCodeInsr{nomFichier} en spécifiant que ce fichier sera
utilisé en écriture (OUT). De plus, elle positionne la tête d’écriture
en début du fichier. Si le fichier \textstyleCodeInsr{nomFichier} est
inexistant, celui-ci sera créé lors de l’exécution de cette primitive.
Par contre, si ce fichier existe déjà, son contenu est «~détruit~» lors
de l'ouverture.

Pour ouvrir plusieurs fichiers en écriture :

\cadre{
\begin{pseudo}
	\Stmt \K{ouvrir} nomFichier1, nomFichier2, nomFichier3 (\K{écriture})
	\RComment ou \K{OUT} ou \K{OUTPUT}
\end{pseudo}
}

{\sffamily\bfseries\upshape
Lecture dans un fichier (ouvert en lecture) }

\cadre{
\begin{pseudo}
	\Read nomFichier ; nomVariable
\end{pseudo}
}

Cette primitive lit dans le fichier \textstyleCodeInsr{nomFichier} une
valeur qui sera affectée à la variable \textstyleCodeInsr{nomVariable}.
La valeur lue est la donnée du fichier se trouvant en face de la tête
de lecture. 

Si \textstyleCodeInsr{nomFichier} est un fichier de T alors
\textstyleCodeInsr{nomVariable} doit être déclaré de type T.

Pour détecter la fin de fichier, on utilise la
\textbf{notation}\footnote{Dans certains langages, il
s'agira d'une variable en lecture
seule; dans d'autres langages, ce sera un appel de
module ou de méthode.} \textstyleCodeInsr{EOF(nomFichier)}.
Après une lecture \textstyleCodeInsr{EOF(nomFichier)} prend la valeur
\textbf{vrai} si la \textbf{fin de fichier} a été détectée et
\textbf{faux} sinon.

Dans le cas où \textstyleCodeInsr{EOF(nomFichier)} est à
\textbf{vrai}, le contenu de 
\textstyleCodeInsr{nomVariable} n’est plus affecté et doit être
considéré comme indéterminé.

Attention à ne pas commettre les erreurs d’utilisation suivantes qui
provoquent toutes l’interruption de l’algorithme :

\begin{liste}
	\item 
		lecture dans un fichier ouvert en écriture, ou non ouvert en lecture;
	\item 
		utilisation de la primitive \textstyleMotCl{lire} alors que la marque de
		fin de fichier a déjà été détectée, c’est-à-dire lorsque
		\textstyleCodeInsr{EOF(nomFichier)} est devenu \textbf{vrai};
	\item 
		utilisation de \textstyleCodeInsr{nomVariable} alors que
		\textstyleCodeInsr{EOF(nomFichier)} est devenu \textbf{vrai};
	\item 
		appel à \textstyleCodeInsr{EOF(nomFichier)} alors
		qu'aucune lecture n'a encore été faite.
\end{liste}

{\sffamily\bfseries
Écriture dans un fichier (ouvert en écriture) }

\cadre{
\begin{pseudo}
	\Writef nomFichier ; nomVariable
\end{pseudo}
}

Cette primitive réalise l’écriture du contenu de la variable
\textstyleCodeInsr{nomVariable} dans le fichier
\textstyleCodeInsr{nomFichier} à l’endroit correspondant à la position
de la tête d’écriture. Après l’écriture, la tête avance d’une position.
Il est bien entendu interdit d’écrire dans un fichier ouvert en
lecture, ou qui n’a pas été ouvert en écriture. 

{\sffamily\bfseries\upshape
Fermeture d’un fichier }

\cadre{
\begin{pseudo}
	\Stmt \K{fermer} nomFichier
\end{pseudo}
}

Cette primitive permet de fermer un fichier après son utilisation, en
lecture ou en écriture. Dans le cas où le fichier a été ouvert en
écriture, cette primitive place la marque spéciale de fin de fichier
dans l’élément courant. Une fois le fichier fermé, il
n'est plus permis de l'utiliser.

Pour fermer plusieurs fichiers :

\cadre{
\begin{pseudo}
	\Stmt \K{fermer} nomFichier1, nomFichier2, nomFichier3
\end{pseudo}
}


%===========================
\section{Algorithme de base}
%===========================

L’algorithme suivant parcourt simplement le fichier
\textstyleCodeInsr{nomFichier}. Il s’agit de l’algorithme type dont la
structure se retrouve dans la majorité des algorithmes exploitant un
fichier.

\cadre{
\begin{pseudo}
\footnotesize
	\Module{parcoursFichier}{}{}
		\Decl nomFichier : fichier de T
		\Decl enregistrement : T
		\Empty

		\Stmt \K{ouvrir} nomFichier (lecture)
		\Read nomFichier ; enregistrement
		\Empty
		
		\While{NON EOF(nomFichier)}
			\LComment traitement de l’information contenue dans enregistrement
			\Read nomFichier ; enregistrement
		\EndWhile
		\Empty
		
		\Stmt \K{fermer} nomFichier
	\EndModule
\end{pseudo}
}

\bigskip

{\sffamily\bfseries\scshape
Exemple : Copie d'un fichier}

Par exemple, voici un programme qui recopie simplement les données
d'un fichier (en lecture) dans un autre (en écriture)

\cadre{
\begin{pseudo}
\footnotesize
	\Module{copieFichier}{}{}
		\Decl fichierIn : fichier de T
		\Decl fichierOut : fichier de T
		\Decl enregistrement : T 
		\Empty
		
		\Stmt \K{ouvrir} fichierIn (lecture), fichierOut (écriture)
		\Read fichierIn ; enregistrement
		\Empty
		
		\While{NON EOF(fichierIn)}
			\Writef fichierOut ; enregistrement
			\Read fichierIn ; enregistrement
		\EndWhile
		\Empty
		
		\Stmt \K{fermer} fichierIn, fichierOut
	\EndModule
\end{pseudo}
}


%%============================================
%\section{Primitives – notation orienté objet}
%%============================================

%On peut aussi définir une notation orienté objet pour la manipulation
%d'un fichier. On utilise une classe pour les fichiers
%séquentiels en entrée et une autre pour les fichiers séquentiels en
%sortie.

%\cadre{
%\begin{pseudo}
	%\Class{FichierEntrée de T}
		%\Public 
			%\ConstrSign{FichierEntrée de T}{localisation : chaine}
			%\MethodSign{ouvrir}{}{}
			%\MethodSign{lire}{}{T}
			%\MethodSign{EOF}{}{booléen}
			%\MethodSign{fermer}{}{}
	%\EndClass
%\end{pseudo}
%}

%\bigskip


%\cadre{
%\begin{pseudo}
	%\Class{FichierSortie de T}
		%\Public 
			%\ConstrSign{FichierSortie de T}{localisation : chaine}
			%\MethodSign{ouvrir}{}{}
			%\MethodSign{écrire}{enregistrement : T}{}
			%\MethodSign{fermer}{}{}
	%\EndClass
%\end{pseudo}
%}

%Quelques remarques s'imposent :

%\begin{liste}
	%\item 
		%Dans la version non orienté objet, rien n'est dit sur
		%la localisation du fichier; on suppose que cela est déterminé par
		%ailleurs. Ici, nous supposerons que le lien est fait à la
		%construction.
	%\item 
		%En Java, l'appel au constructeur «~ouvre~» le fichier;
		%la tête de lecture/écriture est positionnée au début. Toutefois, pour
		%rester proche de la version non OO, nous supposerons en logique
		%qu'un appel à la méthode \textstyleCodeInsr{ouvrir()}
		%est nécessaire.
%\end{liste}

%{\sffamily\bfseries\scshape
%Exemple : parcours d'un fichier}

%Récrivons l'algorithme de base en notation orienté
%objet.

%\cadre{
%\begin{pseudo}
	%\Module{parcoursFichier}{}{}
		%\Decl fichier : FichierEntrée de T
		%\Decl enregistrement : T
		
		%\Let fichier \Gets \K{nouveau} FichierEntrée de T(data.txt)
		
		%\Stmt fichier.ouvrir()
		%\Let enregistrement \Gets fichier.lire()
		
		%\While{NON fichier.EOF()}
			%\LComment traitement de l’information contenue dans enregistrement
			%\Let enregistrement \Gets fichier.lire()
		%\EndWhile
		
		%\Stmt fichier.fermer()
	%\EndModule
%\end{pseudo}
%}

%Bien souvent, le fichier sera un paramètre du module. Dans ce cas, il
%aura déjà été créé. Illustrons ce point pour
%l'algorithme de copie de fichier.


%\cadre{
%\begin{pseudo}
	%\Module{copieFichier}{fichierIn : FichierEntrée de T, fichierOut : FichierSortie de T}{}
		%\Decl enregistrement : T
		
		%\Stmt fichierIn.ouvrir()
		%\Stmt fichierOut.ouvrir()
		
		%\Let enregistrement \Gets fichierIn.lire()
		
		%\While{NON fichierIn.EOF()}
			%\Stmt fichierOut.écrire(enregistrement)
			%\Let enregistrement \Gets fichierIn.lire()
		%\EndWhile
		
		%\Stmt fichierIn.fermer()
		%\Stmt fichierOut.fermer()
	%\EndModule
%\end{pseudo}
%}


%==================================
\section{Le cas des fichiers vides}
%==================================

Dans tout algorithme de manipulation de fichiers, il faut se demander ce
qu'il advient du cas d'un fichier
vide (rappelons que c'est la première lecture qui
permet d'identifier ce cas). Il y a 3 cas de figure :

\begin{enumerate}
	\item 
		Le fichier vide est un cas particulier tout à fait acceptable et qui est
		traité correctement par l'algorithme général.
	\item 
		Le fichier vide demande un traitement spécial qui n'est
		pas couvert par le cas général.
	\item 
		Le fichier vide dénote un problème mal posé qui ne peut être résolu.
\end{enumerate}

{\sffamily\bfseries\scshape
Exemple 1 – Des informations à traiter}

Le module \textstyleCodeInsr{copierFichier} ci-dessus est un exemple du
premier cas. En cas de fichier vide, l'algorithme
fonctionne parfaitement puisqu'il créera bien un
nouveau fichier vide. De façon générale, le fichier vide peut
simplement indiquer qu'il n'y a rien
à traiter pour le moment. Par exemple, on pourrait imaginer un fichier
contenant des informations sur les étudiants qui se sont mis en ordre
d'inscription aujourd'hui et qui
serait utilisé toutes les nuits par un programme créant les comptes
informatiques pour ces étudiants. 

{\sffamily\bfseries\scshape
Exemple 2 – Calcul de la moyenne}

Si le problème de départ est de calculer la somme, la moyenne ou encore
le maximum des nombres contenus dans un fichier, alors la solution ne
peut être donnée dans le cas d'un fichier vide (cas 3)
à moins que l'analyse n'ait
clairement indiqué la réponse à donner dans ce cas (cas 2).
Concentrons-nous sur le calcul de la moyenne d’une série de nombres
contenus dans un fichier. Voici un premier exemple
:


\cadre{
\begin{pseudo}
\footnotesize
	\Module{calculMoyenne}{fileNb : fichier de réels}{réel}
		\Decl somme, nombre : réels
		\Decl cpt : entier
		\Empty
		
		\Open fileNb (lecture)
		\Empty
		
		\Let cpt \Gets 0
		\Let somme \Gets 0
		\Readf fileNb; nombre
		\Empty
		
		\While{NON EOF(fileNb)}
			\Let cpt \Gets cpt + 1
			\Let somme \Gets somme + nombre
			\Readf fileNb; nombre
		\EndWhile
		\Empty
		
		\Close fileNb
		\Empty
		
		\Return somme / cpt
	\EndModule
\end{pseudo}
}

Il est facile de deviner ce qui se passerait si le fichier était vide !
Le nombre de nombres du fichier étant nul, le calcul de la moyenne
provoquerait une interruption (division par zéro).


Une possibilité consiste à discriminer ce cas en fin de traitement :

\cadre{
\begin{pseudo}
\footnotesize
	\Module{calculMoyenne}{fileNb : fichier de réels}{réel}
		\Decl somme, nombre : réels
		\Decl cpt : entier
		\Empty
		
		\Open fileNb (lecture)
		\Empty
		
		\Let cpt \Gets 0
		\Let somme \Gets 0
		\Readf fileNb; nombre
		\Empty
		
		\While{NON EOF(fileNb)}
			\Let cpt \Gets cpt + 1
			\Let somme \Gets somme + nombre
			\Readf fileNb; nombre
		\EndWhile
		\Empty
		
		\Close fileNb
		\Empty
		
		\If{cpt>0}
			\Return somme / cpt
		\Else
			\Error "Fichier vide"
		\EndIf
	\EndModule
\end{pseudo}
}

Mais ce n'est pas toujours possible. Par exemple, si le
problème est simplement de calculer la somme des nombres, la variable
\textstyleCodeInsr{cpt} disparait et la somme seule ne permet pas de
juger si le fichier est vide. En effet, la somme pourrait être nulle
parce que les différents éléments additionnés amènent précisément à ce
résultat. Il est alors plus sûr de traiter ce cas juste après la
première lecture.

\cadre{
\begin{pseudo}
\footnotesize
	\Module{calculMoyenne}{fileNb : fichier de réels}{réel}
		\Decl somme, nombre : réels
		\Decl cpt : entier
		\Empty
		
		\Open fileNb (lecture)
		\Empty
		
		\Let cpt \Gets 0
		\Let somme \Gets 0
		\Readf fileNb; nombre
		\Empty
		
		\If{EOF(fileNb)}
			\Close fileNb
			\Error "Fichier vide"
		\EndIf
		\Empty
		
		\While{NON EOF(fileNb)}
			\Let cpt \Gets cpt + 1
			\Let somme \Gets somme + nombre
			\Readf fileNb; nombre
		\EndWhile
		\Empty
		
		\Close fileNb
		\Empty
		
		\Return somme / cpt
	\EndModule
\end{pseudo}
}

Écrivons l'algorithme général de traitement
d'un fichier séquentiel :

\cadre{
\begin{pseudo}
\footnotesize
	\Module{algorithmeDeTraitementSurFichier}{}{}
		\Empty
	
		\LComment déclaration des variables, fichiers,... éventuellement en paramètres
		\Empty
		
		\Stmt \K{ouvrir} fichier (lecture)
		\Read fichier ; élément
		\Empty
		
		\If {EOF(fichier)}
			\LComment traitement spécial fichier vide
		\Else 
			\LComment initialisation du traitement de l’ensemble
			\While {NON EOF(fichier)}
				\LComment traitement d’un élément
				\Read fichier ; élément
			\EndWhile
			\LComment clôture du traitement de l’ensemble
		\EndIf
		\Empty
		
		\Stmt \K{fermer} fichier
	\EndModule
\end{pseudo}
}

Lorsque le «~traitement spécial du fichier vide~» consiste à générer une
«~ERREUR~» alors le \textstyleMotCl{si-sinon-fin si} peut être changé
en un simple \textstyleMotCl{si-fin si} suivi du traitement normal.

%====================
\section{La séquence}
%====================

Un fichier séquentiel impose un accès séquentiel à ses éléments.
D'autres structures de données peuvent être accédées
séquentiellement : par exemple le tableau et la liste mais aussi la
liste chainée (cf. votre cours de logique de 2ème année), la
communication sur un port série ou via le réseau, ... Les algorithmes
développés pour les fichiers peuvent être réutilisés pour
n'importe quelle séquence.

{\sffamily\bfseries\upshape
Le tableau vu comme une séquence}

Un tableau permet un accès direct à ses éléments mais on peut tout aussi
bien y accéder en séquence. Comment traduire les notations introduites
pour les fichiers ? Il suffit d'utiliser un indice
courant et de le faire évoluer :

\cadre{
\begin{pseudo}
	\LComment Supposons tab : tableau [1 à n] de T et utilisons un indiceCourant
	\bigskip
	\LComment ouvrir devient
	\Let indiceCourant \Gets 0
	\bigskip
	\LComment lire devient
	\Let indiceCourant \Gets indiceCourant + 1
	\If{indiceCourant ${\leq}$ n}
		\Let sauve \Gets tab[indiceCourant]
	\EndIf
	\bigskip
	\LComment EOF devient
	\Stmt indiceCourant > n
\end{pseudo}
}

{\sffamily\bfseries\upshape
La liste vue comme une séquence}

Une liste aussi peut aussi être vue comme une séquence. Nous vous
laissons en exercice le soin de déterminer ce que deviennent les
primitives ouvrir/lire/\textsf{EOF} dans ce cas

%==================================================
\section{Un accès différent aux fichiers/séquences}
%===================================================

Dans les fichiers comme nous les avons vus actuellement, une «~lecture~»
infructueuse est nécessaire pour se rendre compte
qu'il n'y a plus
d'informations à lire. 

On peut envisager des fichiers (ou plus généralement des séquences) où
on doit d'abord demander s'il reste
un élément à traiter avant de l'obtenir effectivement.
Ce schéma est celui qu'on trouve notamment dans 

\begin{liste}
	\item 
		les curseurs en SQL
	\item 
		les itérateurs en Java
	\item 
		la lecture via la classe Scanner en Java
	\item 
		la lecture dans certains langages de programmation comme Visual Basic
\end{liste}

On pourrait définir une telle séquence ainsi

\cadre{
\begin{pseudo}
	\Class{Séquence de T}
		\MethodSign{débuter}{}{}
		\MethodSign{aEncore}{}{booléen}
		\MethodSign{suivant}{}{T}
	\EndClass
\end{pseudo}
}

Pour illustrer ceci, écrivons l'algorithme qui parcourt
la séquence.

\cadre{
\begin{pseudo}
	\Module{parcourir}{données : Séquence de T}{}
		\Decl élément : T
		\Stmt données.débuter()
		\While{données.aEncore()}
			\Let élément \Gets données.suivant()
			\LComment Traiter l'élément
		\EndWhile
	\EndModule
\end{pseudo}
}

\bigskip

\begin{Emphase}{Exercice – Adaptation aux tableaux et aux listes}

Que deviennent les méthodes de la classe Séquence de T pour un
tableau/une liste ?
\end{Emphase}

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

\begin{Exercice}{Algorithmes de base}
	
	Soit un fichier dont chacun des enregistrements est de type
	\code{Elément}. Cette structure contient les champs
	\code{numéro} (entier), \code{clé} (chaine)
	et \code{info} (chaine). Écrire des modules réalisant
	les requêtes suivantes :

	\begin{enumerate}[label=\alph*)]
		\item 
			détermination de la \textbf{longueur} du fichier (c’est-à-dire le nombre
			d’enregistrements du fichier)
		\item 
			affichage de la valeur minimale du champ \code{numéro}
			parmi les enregistrements du fichier
		\item
			recherche du \textit{n}{}-ème enregistrement du fichier. L’entier
			\textit{n} sera entré en paramètre et un paramètre booléen traduira
			l’existence ou non de l’enregistrement recherché ; dans l’affirmative,
			un troisième paramètre renverra cet enregistrement.
		\item 
			recherche d’un élément connaissant sa «~clé~», c’est-à-dire renvoi en
			paramètre du premier enregistrement du fichier dont le champ
			\code{clé} est égal à la valeur \code{val}
			entrée en paramètre. On retournera également un booléen
			traduisant l’existence ou non de l’élément cherché. 
	\end{enumerate}
\end{Exercice}

\begin{Exercice}{Copies et modifications de fichiers}
	
	On considère un fichier d'\code{Elément} comme à l'exercice 1. 
	Pensez à prévoir les différents scénarios possibles.
	
	\begin{enumerate}[label=\alph*)]
		\item 
			Écrire un algorithme qui supprime le $n$-ème élément d’un
			fichier
		\item 
			Écrire un algorithme qui supprime d’un fichier les éléments dont la
			valeur du champs \code{info} est égale à une valeur entrée en paramètre 
		\item 
			Écrire un algorithme qui insère dans un fichier une valeur entrée en
			paramètre (type \code{Elément}) en $n$-ème position
		\item 
			Écrire un algorithme qui «~éclate~» un fichier en deux fichiers ; le
			premier contiendra les éléments dont la valeur du champs \code{numéro} est
			inférieure à une valeur entrée en paramètre, et le deuxième contiendra
			les autres éléments.
	\end{enumerate}
\end{Exercice}

\begin{Exercice}{Fichiers ordonnés}

	Soit \code{fileNum} un fichier d’entiers. Écrire un algorithme :

	\begin{enumerate}[label=\alph*)]
		\item 
			qui vérifie si les éléments du fichier sont ordonnés par ordre
			croissant
		\item 
			qui recherche le mode d’ordonnancement du fichier (croissant,
			strictement croissant, décroissant, strictement décroissant ou aucune
			de ces possibilités)
	\end{enumerate}
	
	En supposant à présent \code{fileNum} ordonné en mode croissant, écrire un
	algorithme :

	\begin{enumerate}[label=\alph*)]
		\item 
			qui insère la valeur \code{val} dans une copie de ce fichier
		\item 
			qui crée une copie du fichier débarrassé de ses redondances
	\end{enumerate}
\end{Exercice}

\begin{Exercice}{Statistiques sur les profs}
	Soit le fichier \code{fileProfs} des professeurs de la
	HEB. La structure des enregistrements de ce fichier est {\code{Prof}}
	
	\cadre{
	\begin{pseudo}
	\Struct{Prof}
	\Decl nom : chaine
	\Decl âge : entier
	\Decl sexe : énumération \{ HOMME, FEMME \} 
	\Decl dateIn : Date \RComment date d’entrée en fonction 
	\EndStruct
	\end{pseudo}
	}
	
	Écrire l’algorithme qui :
	
	\begin{enumerate}[label=\alph*)]
		\item 
			affiche les noms des professeurs qui auront 20 ans d’ancienneté ou plus
			au 31 décembre prochain
		\item 
			affiche l’âge moyen du corps professoral
		\item 
			affiche en \% la proportion de femmes dans le corps professoral
	\end{enumerate}
\end{Exercice}

\begin{Exercice}{La sélection des mannequins}
	Une agence de mannequins a organisé un concours ouvert aux débutantes
	non professionnelles. Les postulantes inscrites ont toutes participé à
	un examen de culture générale au cours duquel les questions étaient
	rédigées indifféremment en français ou en néerlandais. Les
	organisateurs du concours ont encodé tous les renseignements
	nécessaires sur les candidates dans le fichier \code{fileCandidat} dont la structure
	des enregistrements est de type \code{Candidat} 
	
	\cadre{
	\begin{pseudo}
	\Struct{Candidat}
	\Decl nom : chaine
	\Decl adresse : chaine
	\Decl téléphone : chaine
	\Decl date : Date \RComment date de naissance 
	\Decl taille : réel \RComment taille en mètre
	\Decl poids : réel \RComment poids en kilo
	\Decl pts : entier \RComment points obtenus à l’examen coté sur 150
	\EndStruct
	\end{pseudo}
	}
	
	En vue de réaliser une sélection, le jury a décidé d’éliminer les
	candidates :

	\begin{liste}
		\item 
			n’ayant pas atteint 18 ans au 1\up{er} novembre de l’année
			en cours ;
		\item 
			ayant 30 ans ou plus au 1\up{er} décembre de l’année en
			cours ;
		\item 
			de moins de 1m70 ou de plus de 1m90 ;
		\item 
			ayant un IMC inférieur à 18 ou supérieur à 20, l’IMC (\textit{Indice de
			Masse Corporelle}) étant le rapport entre le poids et le carré de la
			taille ;
		\item 
			ayant obtenu moins de 70\% à l’examen de culture générale.
	\end{liste}
	
	Écrire l’algorithme qui réalise, en une seule lecture du fichier \code{fileCandidat},
	cette sélection et qui écrit, sur le fichier \code{fileSélection}, les
	enregistrements des candidates sélectionnées qui pourront continuer le
	concours.
\end{Exercice}

\begin{Exercice}{Le top 10}
	Soit le fichier \code{coureurs} dont les enregistrements
	sont des structures contenant un \code{nom} et un \code{timing} 
	(objet de la classe Moment). 
	Écrire l’algorithme qui affiche le palmarès des dix 
	coureurs les plus rapides.
\end{Exercice}

\begin{Exercice}{Le méli-mélo de cartes}
	Soit le fichier \code{fileCartes} dont chaque
	enregistrement est une structure \code{Carte}

	\cadre{
	\begin{pseudo}
	\Struct{Carte}
	\Decl couleur : entier 
		\RComment 0 pour PIQUE, 1 pour TREFLE, 2 pour CARREAU et 3 pour CŒUR
	\Decl figure : entier 
		\RComment 1 pour l’AS, 2 pour le DEUX,\dots, 
		\Empty \RComment 10 pour le DIX, 11 pour le VALET, 12 pour la DAME et 13 pour le ROI
	\EndStruct
	\end{pseudo}
	}

	Le fichier décrit un nombre indéterminé de
	cartes provenant de paquets différents ; comme le nombre de cartes est
	élevé, chaque carte apparait certainement plusieurs fois dans le
	fichier. Écrire l’algorithme qui dénombre et affiche le nombre de jeux
	complets de 52 cartes contenu dans ce fichier.
\end{Exercice}

\begin{Exercice}{La partie d’échec}
	Lorsqu’une partie d’échec est interrompue, on enregistre la position de
	toutes les pièces sur l’échiquier de manière à pouvoir les replacer le
	jour où la partie va reprendre. Le fichier de sauvegarde est \code{jeu} et
	contient des enregistrements de type \code{Case}
	
	\cadre{
	\begin{pseudo}
	\Struct{Case}
	\Decl nl : entier 
		\RComment numéro de ligne où se trouve la pièce (entre 1 et 8)
	\Decl nc : entier 
		\RComment numéro de colonne où se trouve la pièce (entre 1 et 8)
	\Decl val : Pièce 
		\RComment valeur de la pièce
	\EndStruct
	\Empty
	\Struct{Pièce}
	\Decl type : énumération \{ ROI, REINE, CAVALIER, FOU, TOUR, PION \}
	\Decl couleur : énumération \{ BLANC, NOIR \} 
	\EndStruct	
	\end{pseudo}
	}

	Écrire l’algorithme parcourant le fichier \code{jeu} et permettant :

	\begin{liste}
		\item 
			de replacer les pièces dans le tableau \code{échiquier}
			(tableau à deux dimensions 8 x 8 de \code{Pièce})
		\item 
			de compter combien de cavaliers sont encore présents sur l’échiquier
		\item 
			d’afficher la couleur du joueur possédant encore le plus de pièces sur
			l’échiquier.
	\end{liste}
\end{Exercice}	

\begin{Exercice}{Les stages}
	Soit le tableau \code{stages} de \textit{n} éléments de
	structure \code{Stage}

	\cadre{
	\begin{pseudo}
	\Struct{Stage}
	\Decl réfStage : chaine \RComment référence du stage
	\Decl âgeMin : entier \RComment {âge minimum requis pour pouvoir participer}
	\Decl âgeMax : entier \RComment {âge maximum permis pour pouvoir participer}
	\Decl nbMin : entier \RComment nombre minimum de participants pour que ce stage puisse avoir lieu
	\Decl nbMax : entier \RComment nombre maximum de participants admis
	\Decl nbDemande : entier \RComment nombre de demandes valables 
		\Empty \RComment (au point de vue des limites d’âges)  déjà enregistrées avant aujourd’hui
	\EndStruct
	\end{pseudo}
	}

	Soit le fichier \code{demandes} des nouvelles demandes de
	participation à un stage. La structure \code{Demande} d’un
	enregistrement de ce fichier est la suivante :

	\cadre{
	\begin{pseudo}
	\Struct{Demande}
	\Decl nom : chaine \RComment nom et prénom du candidat
	\Decl âge : entier
	\Decl adresse : chaine
	\Decl réfStage : chaine \RComment référence du stage pour lequel la demande est formulée
	\EndStruct
	\end{pseudo}
	}

	Écrire un module qui reçoit en paramètres le tableau
	\code{stages}, le tableau \code{messages} de
	6 éléments de type chaine (décrit ci-dessous) et le fichier
	\code{demandes}. Ce module va traiter les nouvelles
	demandes en mettant à jour le tableau \code{stages} et en
	créant un fichier \code{réponses} de structure
	d’enregistrement \code{InfoOut}. 

	\bigskip

	\cadre{
	\begin{pseudo}
	\Struct{InfoOut}
	\Decl requête : Demande \RComment reprenant toutes les informations fournies par un candidat
	\Decl msg : chaine \RComment le message à envoyer au demandeur, issu du tableau \code{messages}
	\Decl adresse : chaine
	\Decl réfStage : chaine \RComment référence du stage pour lequel la demande est formulée
	\EndStruct
	\end{pseudo}
	}

	Le contenu du tableau \code{messages} est le suivant
	(ce sont les seuls messages possibles)~:

	\begin{tabular}{|>{\centering\arraybackslash}m{0.36cm}|m{13cm}|}
		\hline
		 1 &
		 Le stage que vous avez demandé \textbf{n’existe
		pas} ! La référence est incorrecte\\\hline
		 2 &
		 Votre êtes \textbf{trop jeune} pour participer
		au stage que vous avez demandé !\\\hline
		 3 &
		 Vous être \textbf{trop âgé} pour participer au
		stage que vous avez demandé !\\\hline
		 4 &
		 Désolé ! Le stage demandé \textbf{est complet}\\\hline
		 5 &
		 Votre inscription pour le stage est \textbf{mise
		en attente} ; pas encore assez d’inscrits\\\hline
		 6 &
		 Votre inscription pour le stage demandé
		\textbf{est acceptée}\\\hline
	\end{tabular}
	
	\textit{Notez qu’un seul message doit être
	fourni en réponse à une demande. L’ordre de priorité des messages
	correspond à l’ordre de leur apparition dans le tableau.}
\end{Exercice}

\begin{Exercice}{Séquence}
	Écrivez un module qui reçoit une séquence d'entiers et
	qui
	\begin{enumerate}
		\item 
			en affiche tous les éléments
		\item 
			détermine la valeur la plus grande (erreur si la séquence est vide)
		\item 
			détermine si la séquence est (strictement) croissante (erreur si la
			séquence est vide)
		\item 
			détermine si la valeur \code{val} (passée en paramètre) est
			présente ou non.
	\end{enumerate}
\end{Exercice}