\font\normal=cmr10 scaled \magstep1
\font\italic=cmsl10 scaled \magstep1
\font\bold=cmb10 scaled \magstep1
\font\type=cmtt10 scaled \magstep1
\tolerance=10000

\normal

{	\obeylines
	\normal
	\parindent=0cm
	Universit\'e Bordeaux 1, Sciences et Technologies
	UFR Math\'ematiques et Informatique

}

\vskip 0.5cm

{	\obeylines
	\normal
	\parindent=0cm
	Ma\^{\i}trise d'Informatique
	Session de janvier 2000
}

\vskip 2cm

\centerline{\bold Techniques et Fondements de la Programmation (TFP)}
\centerline{\bold partie ``techniques''}
\centerline{\bold le 28 janvier 2000}

\vskip 2cm

\noindent
Dur\'ee~: trois heures (les deux parties)
\vskip 0.5cm

\noindent
Tous documents autoris\'es sauf photocopies de
livres.  Votre voisin n'est pas un document.

\vskip 0.5cm

\noindent
Rappel~: Soyez bref et clair~!  Personne n'est impressionn\'e par la
quantit\'e~! 

\vskip 0.5cm

\noindent
Bon courage~!
\vfill\eject


\noindent {\bold Exercice 1. (7p)}
\vskip 0.25cm
\noindent
Une file de priorit\'es est un conteneur dans lequel chaque
\'el\'ement est associ\'e \`a une {\italic priorit\'e} (un entier
positif).  \`A l'insertion (op\'eration {\type insert}) d'un
\'el\'ement dans la file, cette priorit\'e est donn\'ee explicitement.
L'op\'eration {\type dequeue\_max} de suppression d'un
\'el\'ement renvoie et supprime l'un des \'el\'ements de la file
ayant la plus grande priorit\'e.  Finalement l'op\'eration {\type
empty} renvoie une valeur indiquant si la file est vide.
\vskip 0.25cm
Souvent, on peut supposer que la priorit\'e maximale est relativement
petite.  Avec cette supposition, on peut repr\'esenter la file sous la
forme d'un tableau dont la taille est \'egale \`a la priorit\'e
maximale.  Si de plus, on se permet de donner la priorit\'e maximale
\`a la cr\'eation de la file, ce tableau peut \^etre de taille fixe
pendant toute la dur\'ee de vie de la file.
\vskip 0.25cm
Avec ces suppositions, \'ecrire (en langage C) l'interface et
l'impl\'ementation d'une file de priorit\'es.  Vous pouvez supposer
l'existence d'un type {\italic liste} dont les
op\'erations sont {\type cons(head, tail)}, {\type car(list)}, et
{\type cdr(list)}.

\vskip 0.5cm
\noindent {\bold Exercice 2. (7p)}
\vskip 0.25cm
\noindent
\'Ecrire une macro Common Lisp permettant la simulation d'une boucle
{\type for} du langage C, y compris la possibilit\'e d'interrompre la
boucle avec la forme {\type (break)} et de passer imm\'ediatement \`a
l'it\'eration suivante avec la forme {\type (continue)}.
\vskip 0.25cm
Indication: cr\'eer un {\type block} \`a l'ext\'erieur de la boucle
\`a utiliser avec {\type (break)}, et un {\type block} \`a
l'int\'erieur \`a utiliser avec {\type (continue)}, puis
d\'efinir (avec {\type flet}) deux fonctions {\type break} et {\type
continue} dont la fonction est d'effectuer un {\type goto} non local
au {\type block} correspondant.

\vskip 0.5cm
\noindent {\bold Exercice 3. (6p)}
\vskip 0.25cm
\noindent
Dans un jeu de Pacman, un labyrinthe contient un ensemble de
cellules.  Une cellule peut \^etre vide ou occup\'ee par un ensemble d'objets de
types diff\'erents.  Les types d'objets sont~:
\vskip 0.25cm
{\parindent=2cm
\item {\type pastille}~: les objets de ce type sont immobiles, et
certaines sont des super pastilles.  
\item {\type fant\^ome}~: les objets de ce type sont mobiles.  
\item {\type pacman}~: les objets de ce type sont aussi mobiles.  
}
\vskip 0.25cm
Quand un objet {\italic A} ce d\'eplace d'une cellule \`a une autre
cellule d\'ej\`a occup\'ee par un ou plusieurs autres objets, il y a
une {\type collision} entre l'objet {\italic A} et chaque autre objet
de la cellule.  Il n'y a jamais collision entre deux pastilles.  La
collision entre un fant\^ome et une pastille ou entre un fant\^ome et
un autre fant\^ome ne fait rien.  Une collision entre un pacman et une
pastille a pour cons\'equence de supprimer la pastille du labyrinthe
et d'augmenter la force du pacman.  Si de plus, la pastille est une
super pastille, alors, le pacman devient invincible.  Une collision
entre un pacman invincible et un fant\^ome a pour cons\'equence la
suppression du fant\^ome.  Si le pacman n'est pas invincible, alors
c'est le pacman qui est supprim\'e.
\vskip 0.25cm
Mod\'eliser les types d'objets et les collision avec des classes, des
fonctions g\'en\'eriques et des m\'ethodes CLOS.  Vous avez \`a votre
disposition une fonction {\type delete-object} permettant de supprimer
n'importe quel objet du labyrinthe.  On suppose que d'autres fonctions
du programme s'occupent de d\'eplacer les objets, de d\'etecter les
collision, et d'appeler la fonction g\'en\'erique {\type collision}
pour chaque collision d\'etect\'ee. 

\bye
