Algorithmique 1 - Ensiwiki
Contents
1. Algorithmique 1 Examen 1 re session Janvier 2009 gt Question 3 1 point Programmer EstVide et Vider en respectant le fait que Senti est une sentinelle de t te la proc dure Vider doit lib rer les ventuelles cellules devenant inutilis es 2 1 Premi re impl mentation Dans la premi re des 2 impl mentations utilisant Senti on ne contraint pas davantage l inva riant sur Senti Question 4 1 point Ecrire la proc dure Inserer de sorte qu elle place la nouvelle occurrence de X en t te de liste dans le suivant de la sentinelle Question 5 1 point Ecrire une fonction interne au paquetage appel e CherchePredMax qui a la sp cification sui vante function CherchePredMax return Liste is requiert la file contient au moins un l ment retourne un pointeur P non nul accessible depuis Senti gt tel que le suivant de P est non nul z et la valeur de la cellule suivant P est le max des l ments de la file Question 6 1 point Utiliser CherchePredMax pour crire DetruireMax La proc dure DetruireMax doit lib rer la cellule qui n est plus utilis e 2 2 Deuxi me impl mentation Dans cette derni re impl mentation on contraint maintenant l invariant sur Senti garantir que la liste dont la t te est Senti Suiv est tri e par ordre d croissant sur les l ments comme sur le dessin de droite page 4 gt Question 7 2 points Reprogrammer Inserer et DetruireMax po2. file end FilePrio FIGURE 2 Interface de FilePrio En supposant Elt First lt 3 et 10 lt Elt Last X Elt on consid re la s quence ci contre begin A l issue de cette s quence la variable X vaut Vider 10 La file de priorit s contient ici les l ments Inserer 3 suivants 3 en deux exemplaires 5 en Inserer 10 quatre exemplaires et 10 en un exemplaire Inserer 5 Inserer 5 Inserer 10 Inserer 5 Inserer 3 Inserer 5 DetruireMax X Si on fait ensuite un nouvel appel DetruireMax X la variable X vaut encore 10 mais la file ne contient plus l l ment 10 Le maximum de la file est donc 5 en quatre exem plaires FIGURE 3 Exemple d utilisation de FilePrio L impl mentation par tableau utilise les deux variables globales NbOcc array Elt of Natural MaxFile Elt L invariant satisfait par ces deux variables du paquetage est la conjonction des deux propri t s 1 si NbOcc others gt 0 alors MaxFile Elt First 2 si NbOcc others gt 0 alors NbOcc MaxFile O et pour tout I Elt tel que NbOcc I 0 ona I lt MaxFile FIGURE 4 Variables globales de FilePrio dans impl m par tableau 2008 2009 page 2 5 Ensimag 1 re ann e Algorithmique 1 Examen 1 re session Janvier 2009 I Files de priorit s 12 points L objectif de cet exercice est d tudier diff rentes impl mentations d une structure d
3. gt 2 5 gt 4 10 gt 1 others gt 0 Pour rendre DetruireMax plus efficace on calcule l avance le maximum courant de la file dans une variable globale appel e MaxFile Typiquement pour le NbOcc de l exemple pr c dent MaxFile 10 Plus pr cis ment ces 2 variables doivent satisfaire l invariant du paquetage donn figure 4 page 2 si la file est vide MaxFile vaut Elt First sinon il vaut l l ment maximum de la file Question 2 4 points Impl menter les sous programmes du paquetage en optimisant les temps de calculs autant que possible 1 crire Vider 0 5 point cette proc dure doit tablir l invariant 2 crire EstVide 0 5 point en utilisant l invariant le co t en temps de cette fonction est constant en fonction de N 3 crire Inserer 1 point cette proc dure doit pr server l invariant 4 crire DetruireMax 1 5 points cette proc dure doit pr server l invariant 2008 2009 page 3 5 Ensimag 1 re ann e Algorithmique 1 Examen l re session Janvier 2009 2 Deux impl mentations par une liste cha n e Maintenant on tudie deux autres impl mentations du paquetage qui peuvent tre int ressantes par rapport l impl mentation pr c dente lorsque N est grand et que le nombre d occurrences de chaque l ments de la file reste faible Dans ces deux impl mentations le paquetage n a qu une seule variable globale interne qui est une liste simple
4. Ensimag 1 re ann e Algorithmique 1 Examen 1 re session Janvier 2009 Algorithmique 1 Dur e 3h Machines lectroniques interdites Tous documents papiers autoris s Les deux parties du sujet sont ind pendantes Veuillez rendre ces deux parties sur des feuilles s par es Veuillez respecter les notations introduites dans l nonc Il est inutile de paraphraser l nonc dans vos r ponses mais des explications avec dessins sur votre code sont les bienvenues Dans l ensemble de cet examen on travaille avec le type Liste des listes simplement cha n es YP P introduit par les d finitions suivantes type Cellule type Liste is access Cellule type Cellule is record Val Integer Suiv Liste end record procedure Liberer is new Ada Unchecked_Deallocation Cellule Liste FIGURE 1 D finition du type Liste 2008 2009 page 1 5 Ensimag 1 re ann e Algorithmique 1 Examen l re session Janvier 2009 package FilePrio is subtype Elt is Integer range function EstVide return Boolean retourne True ssi la file ne contient aucun l ment procedure Vider garantit EstVide True procedure Inserer X in Elt garantit une nouvelle occurrence de X est ins r e dans la file procedure DetruireMax Max out Elt requiert EstVide False garantit une occurrence de Max est retir e de la file x et Max est gt tous les l ments restants dans la
5. e donn es appel e file de priorit s Les impl mentations abord es ici sont relativement na ves Des impl mentations plus efficaces seront trait es au deuxi me semestre On travaille ici avec un paquetage FilePrio dont l interface est donn e figure 2 page 2 L tat interne de ce paquetage repr sente une suite ordonn e d l ments appel e file de priorit s Ces l ments sont du type Elt un sous type intervalle de Integer L ordre sur les l ments est donc l ordre par d faut sur Integer Le mode d emploi du paquetage pr cise que l tat initial au chargement du programme n est pas d fini Il faut donc commencer par appeler Vider avant d utiliser le reste du paquetage La figure 3 page 2 donne un exemple d utilisation du paquetage Dans la suite on note N le cardinal de Elt le nombre d l ments de l intervalle Elt Range Question 1 1 point Utiliser ce paquetage pour d finir une proc dure Tri qui ordonne les l ments d un tableau T suivant l ordre d croissant type Tab is array Integer range lt gt of Elt procedure Tri T in out Tab 1 Impl mentation par un tableau Dans un premier temps on suppose que N est relativement petit On repr sente la file par un tableau NbOcc qui associe chaque l ment son nombre d occurrences ou d exemplaires dans la suite Voir figure 4 page 2 Par exemple l issue de la suite d instructions donn e la figure 3 on a NbOcc 3
6. ment cha n e de type Liste d fini figure 1 page 1 Cette liste a une sentinelle de t te pour rendre les algorithmes r guliers Dans votre code vous devez utiliser cette sentinelle et viter des analyses par cas inutiles Cette sentinelle est allou e l initialisation du paquetage et elle n est jamais lib r e Cette variable est donc simplement appel e Senti et d clar e comme ci dessous dans le paquetage Senti Liste new Cellule Dans les deux impl mentations l invariant du paquetage garantit que Senti est une liste sim plement cha n e non vide et bien form e sans cycle et sans pointeur pendant et que les l ments de la file sont ceux accessibles depuis la liste de t te Senti Suiv Par exemple les deux listes cha n es dessin es ci dessous peuvent repr senter la file obtenue l issue de la s quence donn e figure 3 Dans cette figure le champ Val de la cellule point e par Senti est laiss e vide pour signifier que sa valeur n est jamais utilis e a Ka Val Suiv Val Suiv Val Suiv Val Suiv 5 J 10 J Val Suiv Val Suiv 3 Val Suiv Val Suiv Val Suiv Val Suiv a Val Suiv Val Suiv gt a Val Suiv Val Suiv 10 r 3 7 Val Suiv Val Suiv 3 null 3 null 2008 2009 page 4 5 Ensimag 1 re ann e
7. ur respecter ce nouvel invariant La proc dure DetruireMax doit lib rer la cellule qui n est plus utilis e 2008 2009 page 5 5
Download Pdf Manuals
Related Search