Exercices

Questions d'examens de Structures dedonnées

ainsi que leurs corrigés

Contrôle continu du 7 mai 2001 (notes)

Arbre lexicographique●

Arbre de tri●

Examen écrit du 4 octobre 2000 (notes)

Arbres + chaînes●

Les listes●

Les B-arbres●

Examen écrit du 3 juillet 2000 (notes)

Conversion arbre-chaîne●

Arbres multiples●

Listes●

Graphes orientés●

Contrôle continu du 22 juin 2000 (notes)

Fermeture transitive●

Graphe orienté●

parcours d'un B-arbre●

Contrôle continu du 11 mai 2000 (notes)

Chaînes●

Chaînes●

Arbre de tri●

Questions d'examens de Structures de données ainsi que leurs corrigés

http://cuisung.unige.ch/std/questions.html (1 of 5) [23-09-2001 15:57:36]

Examen écrit du 28 février 2000Structures statiques●

Anneaux bidirectionnels●

Arbres dépliables●

B-arbres●

Examen écrit du 11 octobre 1999Anneaux bidirectionnels●

Arbres●

Listes●

Chemin le plus court dans un graphe●

Examen écrit du 30 juin 1999 (notes)


Arbres dépliables●

Le chemin le plus court●

Hash-Coding●

Contrôle continu du 14 juin 1999 (notes)

Graphes orientés●

B-Arbres●

Adressage associatif par transformation de clés (Hash-code)●

Contrôle continu du 29 avril 1999 (notes)

Chaînes bidirectionelles●


Examen écrit de février 1999●



Examen écrit du 7 octobre 1998Arbre binaire●

Structures de graphes orientés (tri topologique inverse)●

comparaison de B-arbres et B*-arbres●

Hash-coding●

Examen écrit du 25 juin 1998Arbres dépliables●

Recherche dichotomique●

Hash-coding●

Tables de décision●

Contrôle continu du 15 juin 1998Fichiers séquentiels indexés●

Recherche dans un B-arbre●

Le chemin du moindre coût●

Contrôle continu du 4 mai 1998Chaînes bidirectionnelles●

Chaînes mono-directionnelles●


Arbre syntaxique●

Examen écrit de février 1998arbre dépliable de tri●

Fichiers séquentiels indexés●

Examen écrit du 13 octobre 1997Structures de graphes●

un réseau de transport●



Examen écrit de juillet 1997Arbres binaires●

Graphe orienté●

B-arbre●

Contrôle continu du 16 juin 1997Arbre lexicographique●

Hash-code●

Tables de décision●

Contrôle continu du 28 avril 1997Chaînes bidirectionnelles●

Chaînes bidirectionnelles●

Arbre généalogique●

Examen écrit du 5 mars 1997Tri dans une chaîne●

Arbres syntaxiques et chaînes●

B-arbre●

Examen écrit du 15 octobre 1996Chaînes bidirectionnelles●

Fichiers séquentiels indexés et B-arbres●

Examen écrit du 9 juillet 1996Chaînes mono-directionnelles●

Réseau autoroutier●



Contrôle continu du 17 juin 1996Anneaux bidirectionnels●

Arbre de tri●

Tri topologique inverse●

B-arbre●

Contrôle continu de mars 1996Structure de chaîne●

Contrôle continu du 20 juin 1995Chaînes bidirectionnelles●


Plus courts chemins dans un graphe●



TITRE: STRUCTURES DE DONNEESEnseignant: Bertrand Ibrahim (MER)

No: 1803 Heures totales: 84 Par semaine: Cours: 4 Exercices: 2 Pratique:

Destinataire Semestre Oblig. Facult. Option Créditslicence informatique 2 10diplôme informatique 2 10certificat . info et stat. 2 10dipl. math.info. 4

ObjectifsCe cours a pour but d'introduire un panorama des structures de données complexes en suivant l'approchede la programmation procédurale.

ContenuNote: un calendrier d'avancement dans le cours est disponible pour vous permettre de déterminer ce qui aété abordé à chaque leçon.

structures de données statiques, types abstraits, notion de pointeur,●

structures dynamiques fondamentales:

chaînes (monodirectionnelles, bidirectionnelles), anneaux (monodirectionnels,bidirectionnels), piles, files d'attentes,

❍

listes généralisées,❍

arbres ,❍

graphes❍

algorithmes de construction, de parcours et de manipulation; représentations internes, opérationsde base,

●

transformation de clés et «hash-coding»,●

structures complexes: séquentiel indexé et B-arbres,●

tables et arbres de décision.●

Forme de l'enseignement:Cours ex-cathedra, exercices, travaux pratiques

Description du cours "Structures de donnees"

http://cuisung.unige.ch/std/Descr.html (1 of 2) [23-09-2001 15:58:15]

http://cuisung.unige.ch/Bertrand.html

http://cuisung.unige.ch/std/Cal0103.html

http://cui.unige.ch/pcnet/groupes/labo/exercice/std/00-01/labo0001.html

Evaluation:Contrôles continus :

lundi 7 mai 2001 de 14h00 à 16h00, auditoire U600 (Uni Dufour, 1er sous-sol) - notes❍

jeudi 21 juin de 14h00 à 16h00, salle 259❍

●

Examen écrit, juillet●

Evaluation du cours par les étudiants (année 2000)●

Note: dans les deux formes d'évaluation des étudiants (contrôle continu ou examen écrit), la note seralaissée en suspend jusqu'à avoir satisfait aux exigences des travaux pratiques (avoir 75% des TPsacceptés par l'assistant).

Encadrement:Bertrand Ibrahim (bur. 350), Wolfgang Müller (bur. 336), Yvan Petroff (bur. 306).

Documentation:livre support de cours et liste d'ouvrages de référence. Liste des questions d'examens avec leurs corrigés.Enregistrements sonores

Liaison avec d'autres cours:

Préalable requis: Algorithmique ou Introduction à l'informatique.

Préparation pour: informatique théorique, initiation à la recherche opérationnelle et langagesinformatiques.

B. Ibrahim19.04.01

Description du cours "Structures de donnees"

http://cuisung.unige.ch/std/Descr.html (2 of 2) [23-09-2001 15:58:15]

http://eval.unige.ch/cours/1803CR01/results/raptot.html


http://cui.unige.ch/~muellerw/

http://cuisung.unige.ch/std/table.html

http://cuisung.unige.ch/std/audio/

http://cui.unige.ch/eao/www/std/Algo.html


Structures de Données

Notes du contrôle continu du 7 mai 2001

Nom Q1 Q2 Note

ALBUQUERQUE Michel 5 19 2,3

BAERTSCHIGER Didier 30 35 6,0

BELKABIR M?? 3 0 0,3

BOUDJNANE Yassin 13 26 3,9

BRUNSCHWIG Guillaume 4 2 0,6

CABY Gerda 1 14 1,5

CHARPILLOZ Christophe 25 16 4,1

COSTANITA Rodrigue 9 23 3,2

DUCIMETIERE Jérôme 1 29 3,0

EL HASNAOUI Hassan 4 10 1,4

EMIYAN Stéphane 15 29 4,4

ETIENNE Julien 20 27 4,7

FERROUKHI Sid-Ahmed 0 13 1,3

FIRST Jean 22 33 5,5

FONTIGNIE Jacques 30 29 5,9

GULATI Asheesh 22 35 5,7

JAMES Mélanie 30 35 6,0

JOSS Olivier 30 27 5,7

LAGROUNI Kamal 25 24 4,9

MAGPANTAY Tristan 19 29 4,8

MARQUIS Samuel 22 29 5,1

NGUYEN Duy 22 29 5,1

Répartition des notes

[5,5-6,0] xxxxx xxxx

[5,0-5,5[ xxxxx x

[4,5-5,0[ xxxxx xx

[4,0-4,5[ xxxx

[3,5-4,0[ xxx

[3,0-3,5[ xxxxx

[2,5-3,0[

[2,0-2,5[ x


http://cuisung.unige.ch/std/CC/010507/Notes.html (1 of 2) [23-09-2001 15:58:19]

http://cui.unige.ch/eao/www/std/table.html

NGUYEN Thi Anh Thu 25 12 3,7

PINEIRO Elvis 25 22 4,7

PORTA Jonathan 9 29 3,8

PRAPLAN Christophe 22 30 5,2

QUANG Anh 15 26 4,1

REVERDON Ludovic 4 26 3,0

RIVERA CAMACHO Ernesto A. 25 35 6,0

ROSSET Giles 27 35 6,0

SARTORETTI Fabien 25 26 5,1

SAYAH Saïd 15 26 4,1

SCHALLER Cynthia 25 28 5,3

STURB Ronald 1 14 1,5

SUHNER Thierry 12 35 4,7

STRUMIELLO Olivier 24 24 4,8

TUVERI Jairo 25 24 4,9

UMER Ali 4 26 3,0

VILLALBA Alfredo 30 35 6,0

VILLASUSO Pablo 22 29 5,1

WANG ia Ying 12 18 3,0

[1,5-2,0[ xx

[1,0-1,5[ xx

[0,5-1.0[ x

[0-0,5[ x

Dernière modification: 15.06.01



Arbre lexicographique

Question posée au contrôle continu du 7 mai 2001

On a construit un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de façon queles chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante

Les arcs sont étiquettés avec les lettres de l'alphabet (on suppose ici que l'on ne tient pas compte desaccents sur les lettres) et les noeuds contiennent un booléen indiquant si le chemin de la racine à cenoeud représente un mot complet ou pas (sur le dessin - = faux et * = vrai).

Sur la base des déclarations suivantes, écrivez une fonction Trouve indiquant si un mot se trouve dans ledictionnaire.

type VersNoeud= ^Noeud; Noeud= record Desc: array['a'..'z'] of VersNoeud; Complet: boolean; end; { Noeud }var Dico: VersNoeud;

function Trouve(Mot: string; Dico: VersNoeud):boolean;

Solution

Structuration des Données Informatiques - 8.2, exercice 5

http://cuisung.unige.ch/std/ex/8/2e.html [23-09-2001 15:58:24]

Arbre de tri


Complétez le code des procédures ajouteElement, sommeArbre et produitArbre. La procédureaccumulerArbre est facultative et vaut un bonus de 5 points.

{ Ajoutez le code necessaire }program completer;

type pElement = ^TElement; TElement = record mContenu : integer; mDroite,mGauche : pTElement; end; { TElement } {un type de FONCTION} TFonction = function(x, y:integer):integer;

var gRacine: pElement; i,gSomme,gProduit, gNouveau : integer;{ multiplier: Cette fonction multiplie deux nombres entiers

parametres: inX, inY: les deux nombres a multiplier

resultat: inX*inY }function multiplier(inX,inY:integer):integer;begin multiplier:=inX*inY;end; { multiplier }

{ ajouter: Cette fonction ajoute inX a inY

parametres: inX, inY: les deux nombres a additionner

resultat:


http://cuisung.unige.ch/std/ex/8/1h.html (1 of 5) [23-09-2001 15:58:29]

inX+inY }function ajouter(inX,inY:integer):integer;begin ajouter:=inX+inY;end; { ajouter }{---------------------------------------- gestion d'arbres ----------------------------------------}{ creeElement_Contenu Cette fonction cree un nouveau element d'un arbre avec un contenu donné.

Les pointeurs de l'element a creer vont etre mis a NIL. parametres: inNouveauContenu : le contenu de l'element a creer var outElement: le pointeur sur l'element cree }procedure creeElement_Contenu(inNouveauContenu : integer; var outElement : pElement);begin new(outElement); outElement^.mDroite:=nil; outElement^.mGauche:=nil; outElement^.mContenu:=inNouveauContenu;end; { creeElement_Contenu }

{ Ajoute un element a l'arbre pour que l'arbre soit un arbre de tri, les elements les plus petits a gauche.

parametres: inNouveauContenu: le contenu de l'element a ajouter inoutRacine: la racine de l'arbre a qui un element va etre ajoute }procedure ajouteElement(inNouveauContenu:integer; var inoutRacine: pElement);begin {QUESTION:



AJOUTEZ LE CODE NECESSAIRE POUR QUE ajouteElement FASSE CE QUI EST DIT DANS LE COMMENTAIRE.

Vous n'avez pas besoin de variables supplementaires. Toutefois, on autorise l'ajout de variables LOCALES. }

end; { ajouteElement }{ Cette procedure calcule la somme de tous les elements dans l'arbre et l'ajoute a inoutSomme

parametres: var inoutSomme: le parametre d'entree et le resultat var inRacine: la racine de l'arbre a traiter }procedure sommeArbre(var inoutSomme:integer; var inRacine: pElement);begin {QUESTION: AJOUTEZ LE CODE NECESSAIRE POUR QUE sommeArbre FASSE CE QUI EST DIT DANS LE COMMENTAIRE.

Vous n'avez pas besoin de variables supplementaires. Toutefois, on autorise l'ajout de variables LOCALES. }

end; { sommeArbre }

{ La procedure qui suit calcule le produit de tout les elements dans l'arbre et le multiplie avec inoutProduit

parametres: var inoutProduit: le parametre d'entree et le resultat var inRacine: la racine de l'arbre a traiter

}procedure produitArbre(var inoutProduit:integer; var inRacine: pElement);begin {QUESTION: AJOUTEZ LE CODE NECESSAIRE POUR QUE produitArbre FASSE CE QUI EST DIT DANS LE COMMENTAIRE. }



...end; { produitArbre }

{ La procedure qui suit traverse l'arbre en-ordre et applique inFonction au contenu de la racine et inoutAccumulateur dans la maniere suivante:

parametres: inoutAccumulateur: contient un nombre entier apres l'appel il contient le resultat de l'appel inFonction: contient une fonction de type TFonction; inRacine: contient la racine d'un arbre de tri genere par ajouteElement

Car inRacine contient un arbre de tri, les elements de l'arbre sont trie du plus petit au plus grand si on fait un parcours en-ordre:

n_1 < n_2 < ... < n_m

1..m sont les numeros de visite, donc n_1 est visite avant n_2, n_3 etc. Apres un apel d'accumulerArbre avec

inoutAccumulateur=i, inFonction=f,

et un arbre comme parametre, inoutAccumulateur va contenir:

inoutAccumulateur=f(n_m,f(...,f(n_2,f(n_1,i))))

}procedure accumulerArbre(var inoutAccumulateur : integer; inFonction : TFonction; var inRacine: pElement);begin {QUESTION FACULTATIVE: AJOUTEZ LE CODE NECESSAIRE POUR QUE accumulerArbre FASSE CE QUI EST DIT DANS LE COMMENTAIRE.

Vous n'avez pas besoin de variables supplementaires. Toutefois, on autorise l'ajout des variables LOCALES.



} ...end; { accumulerArbre }

{ SI TOUS LES QUESTIONS SONT BIEN RESOLUES, LE PROGRAMME DOIT AFFICHER TROIS FOIS LES MEMES gSomme ET gProduit RESPECTIVEMENT }begin gRacine:=nil; gSomme:=0; gProduit:=1;

{ cree arbre aleatoire de 4 elements } for i:=1 to 4 do begin gNouveau:=random(10)+1; ajouteElement(gNouveau, gRacine); gSomme:= gSomme + gNouveau; gProduit:= gProduit * gNouveau; end; { for }

write('gSomme:'); writeln(gSomme); write('gProduit:'); writeln(gProduit); gSomme:= 0; gProduit:= 1; sommeArbre(gSomme, gRacine); produitArbre(gProduit, gRacine); write('gSomme:'); writeln(gSomme); write('gProduit:'); writeln(gProduit);

gSomme:= 0; gProduit:= 1; accumulerArbre(gSomme, ajouter, gRacine); accumulerArbre(gProduit, multiplier, gRacine); write('gSomme:'); writeln(gSomme); write('gProduit:'); writeln(gProduit);end.

Solution




Notes de l'examen du 4 octobre 2000

Nom Q1 Q2 Q3 Note

Albuquerque Paul absent

Bajrami Gent 5 12 11 3,0

Ben Hadj Noureddine absent

Benkacem Omar 5 20 13 en attente des TPs

Benouataf Khalil 0 0 9 1,0

Coron Olivier 10 30 13 5,5

Londo Ilia 5 18 5 en attente des TPs

Maddi Brahim 3 6 3 1,0

Nguyen Thi Amh Thu 4 8 7 2,0

Schaller Cynthia 8 1 11 2,0


[5,5-6,0] x

[5,0-5,5[

[4,5-5,0[

[4,0-4,5[ x

[3,5-4,0[

[3,0-3,5[ xx

[2,5-3,0[

[2,0-2,5[ xx

[1,5-2,0[

[1,0-1,5[ xx

[0,0-1,0[


Notes du contrôle continu du 22 juin 2000

http://cuisung.unige.ch/std/Exa/Notes001004.html [23-09-2001 15:58:32]


Exercice suivant

Arbres + chaînes

Question posée à l'examen écrit du 4 octobre 2000

Soit une structure d'arbre de tri et une structure de chaîne bidirectionnelle représentées par lesdéclarations suivantes:

type pNoeudArbre = ^NoeudArbre; NoeudArbre = record nombre: integer; gauche, droite: pNoeudArbre; end; { NoeudArbre }

PtrNoeudCh = ^NoeudCh; NoeudCh = record Element: pNoeudArbre; Precedent, Suivant: PtrNoeudCh; end; { NoeudCh }

Ecrivez une fonction "Chemin" qui prend en paramètre un arbre et une valeur et retourne en résultat unechaîne pointant sur les éléments successifs de l'arbre qui auront été examinés pour trouver la valeur dansl'arbre de tri:

function Chemin(MonArbre: pNoeudArbre; MaValeur: integer): PtrNoeudCh;

Il faut bien entendu traiter tous les cas particuliers, p.ex. si l'arbre est vide la chaîne sera vide, si la valeurfournie n'existe pas dans l'arbre, il faudra retourner le chemin parcouru jusqu'à trouver que la valeur ne setrouve pas dans l'arbre.

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/8/1g.html [23-09-2001 15:58:34]

Listes

Question posée à l'examen du 4 octobre 2000

{ Voici un programme qui gère les listes à la façon de Scheme }program liste_scheme;

type PPaireOuValeur = ^TPaireOuValeur; TPaireOuValeur = record mEstValeur : boolean; mValeur : integer; mPremier : PPaireOuValeur; mDeuxieme : PPaireOuValeur; end; var i : integer; gChaine : PPaireOuValeur; function cons_paire_paire(inPremier, inSecond: PPaireOuValeur) : PPaireOuValeur;var lResultat: PPaireOuValeur;begin new(lResultat); lResultat^.mEstValeur:=false; lResultat^.mPremier:= inPremier; lResultat^.mDeuxieme := inSecond; cons_paire_paire:=lResultat;end; { cons_paire_paire }

function cons_integer_paire(inPremier: integer; inSecond: PPaireOuValeur): PPaireOuValeur;var lInteger: PPaireOuValeur;begin new(lInteger);

lInteger^.mEstValeur:=true; lInteger^.mValeur:=inPremier;

cons_integer_paire:=cons_paire_paire(lInteger,inSecond); end; { cons_integer_paire }

function cons_integer_integer(inPremier : integer; inSecond: integer): PPaireOuValeur;


http://cuisung.unige.ch/std/ex/9/1c.html (1 of 3) [23-09-2001 15:58:37]

var lInteger : PPaireOuValeur; lPaire : PPaireOuValeur;begin new(lInteger);

lInteger^.mEstValeur:=true; lInteger^.mValeur:=inSecond;

cons_integer_integer:=cons_integer_paire(inPremier,lInteger);end; { cons_integer_integer }

{ QUESTION:

Ecrivez une fonction qui crée une liste à la façon de Scheme avec les entiers dans l'intervalle de inBegin à inEnd. cree_chaine(5,8) devrait retourner l'equivalent de (list 5 6 7 8). cree_chaine(5,5) devrait retourner l'equivalent de (list 5), cree_chaine(5,4) devrait donner nil comme resultat. }function cree_chaine(inBegin,inEnd : integer ):PPaireOuValeur;var lLastCreated: PPaireOuValeur;var i: integer;begin { <VOTRE SOLUTION ICI> }end;

{ QUESTION:

Créez une procedure qui parcourt et affiche des chaînes simples à la Scheme de façon à donner p.ex. pour affiche_chaine(cree_chaine(5,7))

la procédure affiche "(5 6 7)" à l'écran

La procedure peut être limitée aux chaines simples (pas de listes imbriquées, donc p.ex. "(list 1 2 3 4)" mais pas "(cons (list 1 2) (list 3 4))") }procedure affiche(inPaireOuValeur: PPaireOuValeur);var lCourant: PPaireOuValeur;begin {



<VOTRE SOLUTION ICI> }end; { affiche }

begin gChaine:=cree_chaine(1,10); writeln('Chaine cree'); affiche(gChaine);

affiche(cree_chaine(5,8)); affiche(cons_paire_paire(cree_chaine(1,2), cons_integer_integer(3,4)));end.

Solution



http://cuisung.unige.ch/std/ex/9/1c.sol.html

Les B-Arbres


Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 25:.

Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de l'insertion de la valeur20

b.

Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de l'insertion de la valeur14

c.

Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de l'insertion de la valeur 6d.

Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de la suppression de lavaleur 60

e.


f.


g.

Solution


http://cuisung.unige.ch/std/ex/14/3h.html [23-09-2001 15:58:43]


Notes de l'examen du 3 juillet 2000

Nom Q1 Q2 Q3 Q4 Note

Bajrami Gent 6 15 2 0 2,5

Ben Hadj Noureddine 2 8 0 0 1,0

Benkacem Omar 5 6 5 0 1,5

Benouataf Khalil 0 11 0 0 1,0

Bobo Ngawouo Aimé Patrick 0 1 2 0 0,5

Braik Ahcene 10 15 0 4 3,0

Buhler Stéphane 10 13 10 7 4,0

Coron Olivier 8 13 5 2 3,0

Etienne Julien 12 13 11 9 4,5

Habachi Arash 6 4 15 13 4,0

Maddi Brahim 3 6 2 0 1,0

Nguyen Thi Amh Thu 1 12 0 0 2,5

Petrini Geo 12 0 13 0 2,5

Schaller Cynthia 6 12 0 0 2,0


[5,5-6,0]

[5,0-5,5[

[4,5-5,0[ x

[4,0-4,5[ xx

[3,5-4,0[

[3,0-3,5[ xx

[2,5-3,0[ xxx

[2,0-2,5[ x

[1,5-2,0[ x

[1,0-1,5[ xxx

[0,0-1,0[ x





Exercice suivant

Conversion arbre-chaîne

Question posée à l'examen écrit du 3 juillet 2000

Soit une structure d'arbre de tri et une structure de chaîne bidirectionnelle représentées par lesdéclarations suivantes:

type pNoeudArbre = ^NoeudArbre; NoeudArbre = record nombre: integer; gauche, droite: pNoeudArbre; end; { tNoeudArbre }

PtrNoeudCh = ^NoeudCh; NoeudCh = record Donnee: integer; Precedent, Suivant: PtrNoeudCh; end;

Ecrivez une fonction "Conversion" qui prend en paramêtre un arbre et retourne en résultat une chaînecontenant les valeurs de l'arbre dans l'ordre croissant.

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/8/1f.html [23-09-2001 15:58:54]

Exercice suivant

Arbre multiple


Le langage XML est un langage de balises destiné à succéder au langage HTML. En simplifiant, on peutdire qu'un document XML contient un élément racine. Cet élément racine est un élément complexe,c'est-à-dire qu'il contient un ou plusieurs autres éléments. Chaque élément est soit du texte simple, soit unélément vide composé uniquement d'une balise de la forme "<NomBalise />", soit un élément complexedélimité, à son début, par une balise d'ouverture de la forme "<NomBalise>", à sa fin, par une balise defermeture de la forme "</NomBalise>" et contenant, entre deux, une succession d'éléments.

Un document XML peut être vu comme une structure arborescente du type arbre multiple. En supposantque <X>Y</X> est représenté par

en appliquant cette représentation récursivement et et en tenant compte des différentes possibilités dereprésenter des arbres multiples, dessinez deux représentations arborescentes différentes pour ledocument suivant:

<article> <titre>Un journaliste <souligne>accuse</souligne>, un policier <souligne>dément</souligne></titre> <auteur>Alain Connu</auteur> <date>14 juin 1972</date> <lieu>banquise</lieu> <texte> <grand>Un journaliste de la place accuse</grand> les autorités ... </texte></article>

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/8/2d.html [23-09-2001 15:58:58]

Exercice suivant

Listes

Question posée à l'examen du 3 juillet 2000

program SchemeList;{ une structure qui peut contenir soit une valeur, soit une paire}type PSchemePaireOuValeur = ^TSchemePaireOuValeur; TSchemePaireOuValeur = record { le record contient-il une valeur } mEstValeur:boolean;

{si ce record est une valeur} mValeur : integer;

{si ce record est une paire} { car de la paire} mCar : PSchemePaireOuValeur; { cdr de la paire } mCdr : PSchemePaireOuValeur; end; { TSchemePaireOuValeur }

var gSchemePaire: PSchemePaireOuValeur;

{Une fonction qui cree une valeur}function creeValeur(inValeur : integer): PSchemePaireOuValeur;var lResultat : PSchemePaireOuValeur;begin new(lResultat); lResultat^.mEstValeur:=true; lResultat^.mValeur:=inValeur; lResultat^.mCar:=nil; lResultat^.mCdr:=nil; creeValeur:=lResultat;end; { creeValeur }

{Une fonction qui cree une paire}function creePaire(inCar,inCdr: PSchemePaireOuValeur):PSchemePaireOuValeur;var lResultat : PSchemePaireOuValeur;begin new(lResultat); lResultat^.mEstValeur:=false;


http://cuisung.unige.ch/std/ex/9/1b.html (1 of 2) [23-09-2001 15:59:01]

lResultat^.mValeur:=0; lResultat^.mCar:=inCar; lResultat^.mCdr:=inCdr; creePaire:=lResultat;end; { creePaire }

{ Une procedure pour afficher}procedure display(inPaire : PSchemePaireOuValeur);{vous etes autorise(es) de mettre des variables ici}begin {Mettez votre code ici. Les commentaires du programme principal vous indiquent ce que la procedure Display est censee imprimer}end;

begin gSchemePaire:=creePaire(creeValeur(1), creePaire(creeValeur(2), creePaire(creeValeur(3),nil))); display(nil) {donne "()"}; writeln; display(gSchemePaire); {donne "(1 . (2 . (3 . ())))"}

gSchemePaire:=creePaire(creePaire(creeValeur(1), creeValeur(2)), creePaire(creeValeur(3), creeValeur(4))); writeln; display(gSchemePaire); {donne "((1.2).(3.4))"}end.

Solution

Exercice suivant



Graphe orienté


L'on modélise un planning à l'aide des structures suivantes :

var Debut: array [1..NbTaches] of Integer; { pour chaque tâche, le jour auquel elle est censée débuter } Duree: array [1..NbTaches] of Integer; { la durée de chaque tâche, en nombre de jours } Avant: array [1..NbTaches,1..NbTaches] of Boolean; { Avant[X,Y] vrai si la tâche X doit être achevée avant le début de Y }

Écrire une procédure/fonction étudiant la cohérence de ces données, c.-à-d. :

vérifier que chaque tâche peut bien commencer au jour prévu, en tenant compte de la durée de sesantécédentes;

1.

si cela n'est pas vérifié, imprimer où se situe l'erreur, et quel est l'enchaînement des tâchesprécédentes (depuis l'origine) à prendre en compte pour déterminer la date de début correcte ;

2.

le cas échéant, proposer des améliorations locales du planning (quand une tâche pourraitcommencer plus tôt que prévu).

3.

Il n'est pas demandé de modifier les données initiales, ni de réaliser plusieurs passes, chacune tenantcompte des corrections ( avancée ou retardement d'une tâche) de la précédente. Toutefois, s'il vous restedu temps, cela pourra constituer un bonus...

Attention : il n'est pas spécifié que les tâches doivent s'effectuer l'une après l'autre, certaines peuvents'accomplir en parallèle. De même, la racine du processus n'est pas nécessairement unique (ni le grapheconnexe).

NB: Les variables Debut, Duree et Avant sont globales, et peuvent être utilisées comme telles dans votrecode.

Solution

Structuration des Données Informatiques - 11. exercice 4

http://cuisung.unige.ch/std/ex/11/d.html [23-09-2001 15:59:04]

http://cuisung.unige.ch/std/ex/11/d.txt


Notes du contrôle continu du 22 juin2000

Nom Q1 Q2 Q3 Note

ARRIS Latifa 5 7 5 1,7

BLANC Jérémy 17 18 20 5,5

BOUGET M. 20 20 20 6,0

COLA Stéphane 17 11 17 4,5

GEROME-BAUQUIS Isis 16 6 8 3,0

HAENGGELI Christophe 17 18 20 5,5

HEUBERGER Joris 17 20 19 5,6

HYSI Hilda 17 10 10 3,7

JABRI Abdelmajid 15 2 8 2,5

LOGEAY Camille 17 15 13 4,5

POSKRIAKOV Sergei 17 20 16 5,3

RAY Nicolas 17 17 11 4,5

RENQUIN Johan 18 18 20 5,6

SARAZIN Benoît 17 7 8 3,2

YAPY Luis 20 18 14 5,2


[5,5-6,0] xxxxxx

[5,0-5,5[ x

[4,5-5,0[ xxx

[4,0-4,5[

[3,5-4,0[ x

[3,0-3,5[ xx

[2,5-3,0[ x

[2,0-2,5[

[1,5-2,0[ x

[1,0-1,5[



http://cuisung.unige.ch/std/CC/000622/Notes.html [23-09-2001 15:59:06]


Graphes orientés

Question posée au contrôle continu du 22 juin 2000

Dessinez la fermeture transitive de chacun de ces quatre graphes:

Solution



Exercice suivant

Graphe orienté


Il est aisément démontrable que lorsque l'on élève un nombre N au carré, les deux derniers chiffres durésultat ne dépendent que des deux derniers chiffres de N. Ainsi, un nombre se terminant par 05 auratoujours son carré se terminant par 25 ( 105->11025, 1905->3629025 ).

L'on peut donc définir une application reliant chacun des nombres de 00 à 99 à un autre de ces nombres,correspondant à la valeur de son carré modulo 100. Ceci compose bien entendu un graphe orienté...

Considérant que chacun des noeuds est l'origine d'un et un seul arc, déterminez la structure dedonnées la plus simple adaptée à la représentation des arcs de ce graphe.

1.

La propriété précédente amène logiquement ceci :

puisqu'un noeud a au plus un successeur (en fait, exactement un), l'on peut définir en suivant les arcs(c'est-à-dire en réitérant le calcul) un chemin unique qui en est issu;

puisque tous les noeuds ont au moins un successeur, ce chemin aboutit obligatoirement à un cycle (lenombre de noeuds étant limité).

L'on aimerait donc associer à chaque noeud la "séquence terminale" (cycle) qui lui correspond.

Écrivez une fonction imprimant, pour un noeud passé en paramètre, les noeuds composant le cycleterminal qui lui est associé.

2.

Pensez que chaque composante du graphe ne comporte qu'un seul cycle; rappelez-vous qu'un cycle est uncas particulier de composante fortement connexe...

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/11/c.html [23-09-2001 15:59:16]

http://cuisung.unige.ch/std/ex/11/c.sol.html

Exercice suivant

B-Arbres


Complétez les procédures pour parcourir des B-arbres.

NB: Ces procédures sont sensées marcher avec tous les B-arbres possibles! Une solutions qui marchejuste avec l'arbre donné dans ce programme n'est pas considérée comme réponse à cette question (0points). Sont marquées en caractères gras les parties du code qui sont essentielles à l'élaboration de lasolution.

program b_arbre;const cTaillePage= ...;

type PPage = ^TPage;

{ un element d'une page de b-arbre} TPageElement = record mCle : integer; { Cle } mEnfant : PPage; { Pointeur } end;

{ une page du b-arbre = un noeud du b-arbre } TPage = record mPremierEnfant : PPage;{ Le premier Enfant } mNombreElements : integer; mElements : array[1..cTaillePage] of TPageElement; end;

var gArbre : PPage; gAuxiliaire : PPage; gTest : boolean;

{ Initialiser un element de page }procedure initialisePageElement(var outInitialise : TPageElement);begin outInitialise.mCle:=0; outInitialise.mEnfant:=nil;end;

{ Creer une page vide


http://cuisung.unige.ch/std/ex/14/3f.html (1 of 4) [23-09-2001 15:59:20]

parameter: outNouveauNoeud, la variable qui va contenir la nouvelle page }procedure creePage(var outNouveauNoeud : PPage);var i : integer;begin { creePage } new(outNouveauNoeud);

outNouveauNoeud^.mPremierEnfant:=nil; outNouveauNoeud^.mNombreElements:=0;

for i:=1 to cTaillePage do initialisePageElement(outNouveauNoeud^.mElements[i]);end; { creePage }

{ Ajoute une cle a une page existante parametres: inCle : la nouvelle Cle inoutPage : la page a modifier

valeur de resultat: true, si la page n'etait pas encore pleine false, si la page etait pleine }function ajouteCleAPage(var inoutPage: TPage; inCle:integer) :boolean;begin if (inoutPage.mNombreElements<cTaillePage) then begin inoutPage.mNombreElements:=inoutPage.mNombreElements + 1; inoutPage.mElements[inoutPage.mNombreElements].mCle:=inCle; ajouteCleAPage:=true; end else ajouteCleAPage:=false;end; { ajouteCleAPage }

{ Ajoute une pair de cle et pointeur a une page existante }function ajouteCleEtPointeurAPage(var inoutPage : TPage; inCle :integer; inNouveauEnfant: PPage) :boolean;begin if (inoutPage.mNombreElements<cTaillePage)then begin inoutPage.mNombreElements:=inoutPage.mNombreElements + 1; inoutPage.mElements[inoutPage.mNombreElements].mCle:= inCle; inoutPage.mElements[inoutPage.mNombreElements].mEnfant :=



inNouveauEnfant; ajouteCleEtPointeurAPage := true; end else ajouteCleEtPointeurAPage := false;end; { ajouteCleEtPointeurAPage }

{ Ajoute le premier pointeur a la page }function ajoutePremierPointeurAPage(var inoutPage: TPage; inNouveauEnfant: PPage) :boolean;begin inoutPage.mPremierEnfant:=inNouveauEnfant; ajoutePremierPointeurAPage:=true;end; { ajoutePremierPointeurAPage }

{ Parcourir et afficher a l'ecran }procedure parcourirBArbreEnOrdre(inArbre: PPage );{ ICI VOUS AVEZ LE DROIT DE METTRE DES VARIABLES }var i : integer;begin { parcourirBArbreEnOrdre } {METTEZ VOTRE SOLUTION ICI!}end; { parcourirBArbreEnOrdre }{ Parcourir EN ORDRE INVERSE et afficher a l'ecran }procedure parcourirBArbreEnOrdreInverse(inArbre: PPage );{ ICI VOUS AVEZ LE DROIT DE METTRE DES VARIABLES }var i : integer;begin { parcourirBArbreEnOrdreInverse } {METTEZ VOTRE SOLUTION ICI!}end; { parcourirBArbreEnOrdreInverse }

begin

creePage(gArbre);

creePage(gAuxiliaire); gTest:= ajouteCleAPage(gAuxiliaire^,1); gTest:= ajouteCleAPage(gAuxiliaire^,2);



gTest:= ajouteCleAPage(gAuxiliaire^,3); gTest:= ajoutePremierPointeurAPage(gArbre^,gAuxiliaire);

creePage(gAuxiliaire); gTest:= ajouteCleAPage(gAuxiliaire^,5); gTest:= ajouteCleAPage(gAuxiliaire^,6); gTest:= ajouteCleAPage(gAuxiliaire^,7);

gTest:= ajouteCleEtPointeurAPage(gArbre^, 4, gAuxiliaire);

parcourirBArbreEnOrdre(gArbre); { donne 1 2 3 4 5 6 7 } writeln; writeln; parcourirBArbreEnOrdreInverse(gArbre); { donne 7 6 5 4 3 2 1 } writeln;end.

Solution

Exercice suivant




Notes du contrôle continu du 11 mai2000

Nom Q1 Q2 Q3 Note

ARRIS Latifa 20 16 16 5,2

BEURET Séverine 18 8 9 3,5

BLANC Jérémy 20 19 18 5,7

BOUGET M. 19 15 16 5,0

BRAIK Ahcène 15 4 12 3,1

BUHLER Stéphane 13 13 2 2,8

COLA Stéphane 18 17 15 5,0

CORON Olivier 16 12 13 4,1

GEROME-BAUQUIS Isis 17 18 18 5,3

HABACHI Arash 15 15 16 4,6

HAENGGELI Ch. 18 18 10 4,6

HEUBERGER Joris 20 19 16 5,5

HYSI Hilda 18 17 13 4,8

JABRI Abdelmajid 18 13 10 4,1

JULIEN Etienne 18 14 0 3,2

LOGEAY Camille 18 13 14 4,5

LUONG Fayou 20 15 11 4,6

MADDI Brahim 0 2 8 1,0

PELLEGRINI David 18 10 0 2,8

PETRINI Geo 20 16 15 5,1

POSKRIAKOV Sergei 20 20 19 5,9


[5,5-6,0] xxxxx

[5,0-5,5[ xxxxx

[4,5-5,0[ xxxxxxx

[4,0-4,5[ xx

[3,5-4,0[ x

[3,0-3,5[ xx

[2,5-3,0[ xx

[2,0-2,5[

[1,5-2,0[

[1,0-1,5[ x



http://cui.unige.ch/eao/www/std/table.html

RAY Nicolas 16 16 14 4,6

RENQUIN Johan 20 20 15 5,5

SARAZIN Benoît 17 10 18 4,5

YAPY Luis 20 19 18 5,7




Exercice suivant

Chaînes


Complétez ce programme pour que toutes les fonctions fassent ce qui est dit dans les commentaires:

program chaines;type{ un pointeur sur des elements d'une chaine. } PElement = ^TElement;{ un element d'une chaine: } TElement = record {chaque element de la chaine contient un entier} mContenu : integer; { mSuivant: pointeur sur l'element suivant de la chaine, nil pour le dernier element } mSuivant : PElement; end;

var gChaineDOrigine : PElement; gChaineResultat : PElement;{ VOUS ETES AUTORISES A AJOUTER QUELQUES FONCTIONS ICI (Si vous voulez. Ce n'est pas forcement necessaire, mais ca peut ameliorer la lisibilite de votre solution).

DES VARIABLES SUPPLEMENTAIRES NE SONT PAS AUTORISEES. }{ La fonction suivante prend la chaine inChaine et retourne une nouvelle chaine, qui contient les memes valeurs que inChaine, mais en ordre inverse: Si inChaine est (1 2 3) le resultat va etre la chaine (3 2 1).

AUCUNE VALEUR QUI APPARTIENT A INCHAINE NE DOIT ETRE MODIFIEE }function creeChaineInversee(inChaine:PElement):PElement;{ VOUS ETES AUTORISES A METTRE DES VARIABLES ICI.



LES TABLEAUX SONT INTERDITS!!!! }begin { VOTRE SOLUTION ICI

Mon conseil: Copier la liste d'entree, en ajoutant les nouveaux elements AU DEBUT de la nouvelle liste }end; { creeChaineInversee }

begin { VOUS N'ETES PAS AUTORISE A AJOUTER QUOI QUE CE SOIT ICI } new(gChaineDOrigine); gChaineDOrigine^.mContenu:=2;

new(gChaineDOrigine^.mSuivant); gChaineDOrigine^.mSuivant^.mContenu:=4; new(gChaineDOrigine^.mSuivant^.mSuivant); gChaineDOrigine^.mSuivant^.mSuivant^.mContenu:=6; gChaineDOrigine^.mSuivant^.mSuivant^.mSuivant:=nil;

gChaineResultat:=creeChaineInversee(gChaineDOrigine);

writeln('Si toutes ces expressions sont correctes, il est', 'probable que le programme est lui aussi correct'); write('6 = ');writeln(gChaineResultat^.mContenu); write('4 = ');writeln(gChaineResultat^.mSuivant^.mContenu); write('2 = '); writeln(gChaineResultat^.mSuivant^.mSuivant^.mContenu);end.

Solution

Exercice suivant



Chaînes


Étant données deux listes chaînées, comportant des entiers rangés selon l'ordre croissant, et définiescomme suit:

type pElement = ^tElement; tElement = record nombre : integer; suivant : pElement; end;var debut1, debut2 : pElement;

Écrivez une fonction qui opèrera une fusion de ces deux chaînes dans une troisième, respectantégalement l'ordre croissant de ses éléments, en enlevant les doublons.

Ainsi, à partir de:

liste 1 : 1 3 5 7 9liste 2 : 1 2 4 7 11 16

l'on doit obtenir:

liste 3 : 1 2 3 4 5 7 9 11 16

Solution


http://cuisung.unige.ch/std/ex/7/1c.html [23-09-2001 15:59:27]

http://cuisung.unige.ch/std/ex/7/1c.txt

Exercice suivant

Arbre de tri

Question posée au controle continu du 11 mai 2000

Soit un arbre de tri représenté par la structure suivante:

type pNoeud = ^tNoeud; tNoeud = record nombre : integer; gauche, droite : pNoeud; end;var racine : pNoeud;

On suppose que la racine est instanciée à un arbre existant. Proposez alors une fonction permettant devérifier que cet arbre est bien construit, c'est-à-dire que tous les nombres présents dans le sous-arbregauche (resp. droit) sont inférieurs (resp. supérieurs) au nombre correspondant au noeud courant, et celaà chaque niveau de l'arbre.

Solution

Exercice suivant



Tableaux

Question posée au contrôle continu du 28 février 2000

program question1;

var gHeap : array [1..7] of integer;

procedure affiche(inValeurCourant, inValeurFin : integer);begin if (inValeurCourant<=inValeurFin) then begin writeln('a: ',gHeap[inValeurCourant]); affiche(inValeurCourant*2,inValeurFin); writeln('b: ',gHeap[inValeurCourant]); affiche(inValeurCourant*2+1,inValeurFin); writeln('c: ',gHeap[inValeurCourant]); end (* then *) else begin writeln('d: ',inValeurCourant); end; (* if *)end; { affiche }procedure remplir;var i : integer;begin gHeap[1]:=4; gHeap[2]:=2; gHeap[3]:=5; gHeap[4]:=1; gHeap[5]:=3; gHeap[6]:=6; gHeap[7]:=7; gHeap[7]:=8;end; { remplir }

begin remplir writeln('----------premiere partie'); affiche(1,1); writeln('----------deuxieme partie'); affiche(1,3); writeln('----------troisieme partie'); affiche(1,5); writeln('----------fin')end.

Qu'est-ce que ce programme affiche à l'écran?


http://cuisung.unige.ch/std/ex/3/1a.html [23-09-2001 15:59:31]

Anneaux bidirectionnels

Question posée à l'examen écrit du 28 février 2000

Sur la base des déclarations suivantes:

type VersAnneau = ÊlementAnneau;

ElementAnneau = RECORD Donnee: integer; Preced, Suivant: VersAnneau; END;

Ecrivez une procédure Tri(var Anneau: VersAnneau)qui trie par permutation les données d'unanneau bidirectionnel. On supposera que les données sont tellement volumineuses que la permutation sefera en manipulant les pointeurs et non pas en changeant le champ Info.

Solution


http://cuisung.unige.ch/std/ex/7/4j.html [23-09-2001 15:59:38]

Arbres dépliables

Question posée aux examens écrits du 30 juin 1999 et du 28 février 2000

Dessiner un arbre dépliable de tri, qui sera construit à partir des mots de la phrase suivante, entraitant les mots en séquence de gauche à droite:

John also reviews the use of increasingly important industry specifications andstandards in platform or system issues.

.

Détruire l'élément qui contient le mot "increasingly" et dessiner l'arbre dépliable résultant.b.

Solution


http://cuisung.unige.ch/std/ex/8/3b.html [23-09-2001 15:59:40]

Exercice suivant

B-Arbres

Question posée à l'examen du 28 février 2000

Soit un B-arbre construit à partir des déclarations suivantes:

const NodeSize = 4;

type PNode = ^TNode; TNode = record UsedSize : integer; Content : array [1..NodeSize] of integer; Children : array [0..NodeSize] of PNode; end; (* TNode *)

var gRoot : PNode;

Ecrivez une procédure "afficher(Root : PNode)" qui écrit le contenu du B-arbre en ordrecroissant.

solution

Exercice suivant

Structuration des Donn es Informatiques - 14.3, exercice 5


http://cuisung.unige.ch/std/ex/14/3e.sol.html

Exercice suivant



Etant donné les déclarations suivantes pour un anneau bidirectionnel:

type PtrNoeud = ^Noeud;

Noeud = RECORD Donnee: integer; Preced, Suivant: PtrNoeud; END;

var TeteAnneau: PtrNoeud; (* pointeur vers premier element *)

Ecrire une procédure InsereFin(Anneau, Donnee) pour insérer une donnée à la fin del'anneau

1.

Ecrire une fonction NbElem(Anneau), qui retourne un entier, pour compter le nombred'éléments de l'anneau

2.

Ecrire une procédure Split(Ring, Data, LowerRing, HigherRing), qui prend lesdonnées contenues dans le premier paramètre (anneau) pour les recopier dans le troisième ou lequatrième paramètre (eux aussi des anneaux) suivant que ces données sont respectivement soitinférieures, soit supérieures ou égales à la donnée passée en second paramètre.

3.

N.B.: à chaque fois, vous devez envisager tous les cas possibles

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/7/4i.html [23-09-2001 15:59:44]

Exercice suivant

Arbre syntaxique


En supposantque l'on dispose des fonctions suivantes pour contruire une structure d'arbre:

type PtrNoeud: ^Noeud;

function Feuille(Contenu: char): PtrNoeud; { crée par allocation dynamique un noeud sans descendant et contenant un caractère }

function Arbre(ContenuRacine:char; Gauche, Droit: PtrNoeud): PtrNoeud; { crée, par allocation dynamique, un nouveau noeud racine auquel seront rattachés les sous-arbres gauche et droit fournis en paramêtre, de façon à former un nouvel arbre }

Quelle sera l'expression, composée d'appels imbriqués aux fonctions Arbre et Feuille, quipermettra de construire, en une seule instruction Pascal, l'arbre suivant:

1.

Si, au lieu de créer une structure dynamique en mémoire, on voulait directement évaluerl'expression arithmétique représentée par l'expression Pascal de la première partie de cettequestion, quel devrait être l'entête et le code des fonctions Feuille et Arbre, en supposant qu'ellesretournent des valeurs entières

2.

N.B.: on suppose que les opérateurs + et - peuvent être utilisés comme opérateurs monadiques,c'est-à-dire ne portant que sur un seul argument (opérateurs de signe).

Solution

Exercice suivant



Exercice suivant

Listes


Indiquez ligne après ligne ce qu'imprime le programme suivant:

program listes;var gDe,gA:integer;

procedure compter1(inDe,inA : integer);begin if(inDe<inA) then begin writeln(inDe); compter1(inDe+1,inA); end; (* if *)end;

procedure compter2(inDe,inA : integer);begin if(inDe<inA) then begin compter2(inDe+1,inA); writeln(inDe); end; (* if *)end;

procedure compter3(inDe,inA : integer);begin if(inDe<inA) then begin writeln(inDe); compter3(inDe+1,inA); writeln(inDe); end; (* if *)end;

procedure compter4(var inDe,inA : integer);begin if(inDe<inA) then begin writeln(inDe); inDe:=inDe+1; compter4(inDe,inA); writeln(inDe); end; (* if *)end;

begin


http://cuisung.unige.ch/std/ex/9/1a.html (1 of 2) [23-09-2001 15:59:52]

gDe:=1; gA:=4; writeln('Avant compter1'); compter1(gDe,gA);



gDe:=1; gA:=4; writeln('Avant compter4'); compter4(gDe,gA);end.

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/9/1a.html (2 of 2) [23-09-2001 15:59:52]

http://cuisung.unige.ch/std/ex/9/1a.sol.html

Exercice suivant

Le chemin le plus court


Soit un graphe avec 4 noeuds (1,2,3,4), avec des arcs pondérés: Les arcs sont:

Départ Arrivée Distance

1 2 1

2 3 1

3 4 1

1 3 10

2 4 100

4 3 1000

Pour trouver les "distances" correspondant aux chemins les plus courts entre le noeud 1 et tous les autresnoeuds, exécutez l'algorithme suivant:

Soit une liste L et une liste A, toutes deux initialement vides.1.

Ajoutez à la liste L la paire (1;0) pour le noeud 1 et la "distance" 0.Ajoutez pour chaque arc qui lie les noeuds x et y avec une "distance" z le triplet (x;y;z) à la liste A.

2.

Retirez la paire (x;y) avec le deuxième élément (y) le plus petit de la liste L.3.

Pour chaque paire (x;y) avec le deuxième élément (y) le plus petit de la liste L, retiré à l'étape 3,faites ce qui suit:

Pour chaque arc (x,a,b) qui lie le noeud x à a avec une distance b ajoutez la paire (a;y+b) àla liste L.

❍

Retirez (x,a,b) de A❍

4.

Pour chaque paire (x;y) dans L: S'il existe une paire (x;z) dans L avec z plus petit ou égal à yeffacez (x;y) de L.

5.

Continuez en 3 tant qu'il y a encore des éléments dans A6.

Donnez le contenu de A et de L après chaque pas.

Exercice suivant


http://cuisung.unige.ch/std/ex/11/b.html [23-09-2001 15:59:54]

Structures de donnéesNotes de l'examen du 30 juin 1999

Nom Note Remarque

Tiana Andriaharifara 0,0 absente

Patrick Arbus 0,5

José Barba 3,0

Ahcene Braik 2,0

Denis Bucher 4,5 note en attente des TPs

Hechmi Chnina 0,5

Baba Diao 0,0 absent

Yves Fomekong 3,5

Mouhamed Gningue 3,0

Nicolas Hurzeler 1,0

Sylvan Laurence 1,0

Thomas Pfund 4,0 note en attente des TPs

Bruno Rosa Martins 5,0

Cengiz Ulkü 0,5

N.B.: les notes du contrôle continu sont aussi disponibles

Notes de l'examen du 30 juin 1999


http://cuisung.unige.ch/std/CC/Notes1999.html

Exercice suivant


Question posée à l'examen écrit du 30 juin 1999

Sur la base des déclarations suivantes:

type VersAnneau = ÊlementAnneau; ElementAnneau = record Info: ...; Precedent, Suivant: VersAnneau; end; { ElementAnneau }

écrivez une fonction Pascal Inverse qui prend en paramètre un anneau bidirectionnel et retournecomme résultat un pointeur vers un autre anneau qui a les mêmes éléments que le paramètre, maisdans l'ordre inverse:

function Inverse(Ring: VersAnneau): VersAnneau;

1.

écrivez une fonction Pascal EstInverse qui prend en paramètres deux anneaux bidirectionnelset qui indique s'ils sont l'inverse l'un de l'autre:

function estInverse(Ring1, Ring2: VersAnneau): boolean;

2.

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/7/4h.html [23-09-2001 15:59:59]

Exercice suivant

Le chemin le plus court

Question posée l'examen écrit du 30 juin 1999

Imaginez un graphe orienté qui est donné par sa matrice de connectivité:

sommets d'arrivée

1 2 3 4 5 6 7

sommetsde

départ

1 x x

2 x

3 x

4 x

5 x

6 x

7

Dessinez ce graphe.

Trouvez maintenant le chemin le plus court entre les noeuds 1 et 6. Pour ça vous avez besoin d'unefile d'attente FIFO permettant de stocker des chaînes Li. Chaque Li=(Vi,1,...,Vi,n_i) contient uneséquence de sommets. L'algorithme à utiliser pour trouver le chemin le plus court entre deuxnoeuds Vs et Vf est le suivant:

Videz la FIFO1.

Insérez la liste (Vs) dans la FIFO.2.

Tirez la première liste de la FIFO. Appelez cet élément L13.

Si le premier noeud V1,1 contenu dans L1 est égal à Vf, affichez L1 de la fin au début: Laséquence dans L1 est un chemin de longueur minimale entre Vs et Vf (il peut y en avoirplusieurs). L'algorithme est terminé.

4.

Sinon (le premier noeud V1,1 contenu en L1 n'est pas égal à Vf): visitez V1,1 de la façonsuivante: Ajoutez pour chaque voisin v de V1,1 la liste résultant de (cons v L1) .

5.

Continuez avec le pas 3, tant que la FIFO n'est pas vide et le chemin le plus court n'a pas ététrouvé au pas 4.

6.

Les limitations de cet algorithme sont claires. Il doit être possible d'atteindre Vf a partir de Vs. Lasolution doit donner le contenu de la FIFO à chaque étape de l'algorithme!

b.

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/11/a.html [23-09-2001 16:00:01]

Adressage associatif par transformation de clés (Hash-code)


Etant donné le programme en Pascal suivant:

program fabrique_fonction_de_H_code_parfaite;

const TailleMax = ...; { taille maximale de la table } MaxIndice = TailleMax-1; { indice maximal dans la table } NbMots = ...; { nombre de mots a stocker } MaxCoeff = ...; { valeur max pour les coefficients } LongueurMax = ...; { longueur max. des mots du vocabulaire}

type StringMax = string[LongueurMax];

var Taille : integer; {Nombre d'éléments utilisables dans la table} T : array[0..MaxIndice] of StringMax; Coeff : array[1..LongueurMax] of 1..MaxCoeff; { coefficients de la fonction H } Vocabulaire : array[1..NbMots] of StringMax;

function H( Mot : StringMax ) : integer; begin H := 0; for i := 1 to Length(Mot) do H := H + Coeff[i] * ord( Mot[i] ); H := H mod Taille end; { H }

procedure ChercheCoefficients; begin { ChercheCoefficients } { ajustement des coefficients Coeff[i] et Taille } ... end; { ChercheCoefficients }begin { fabrique_fonction_de_H_code_parfaite } ChercheCoefficients;end. { fabrique_fonction_de_H_code_parfaite }

Ecrire la procédure 'ChercheCoefficients', permettant de fixer les coefficients ( Coeff[i] et'Taille' ) de la fonction de H-code, afin qu'elle soit parfaite pour le remplissage du tableau avec lesmots du 'Vocabulaire'.

La solution doit impérativement minimiser le paramètre 'Taille'. Idéalement, la taille du tableauserait égale au nombre de mots.

Il est conseillé d'utiliser la force brute pour résoudre ce problème. Il s'agira donc de tester toutes lesvaleurs possibles pour les coefficients, jusqu'à tomber sur une fonction de H-code parfaite, ou quel'espace des possibilités soit épuisé.

.



Le but de cette question est d'essayer de minimiser le nombre de collisions dans une structure dedonnées remplie à l'aide de l'algorithme de H-code. Nous avons:

un tableau de strings appelé T, dont les éléments T[i] sont initialisés à '' (string vide)❍

une fonction H(X) retournant l'indice dans le tableau T où l'élément X devrait être stocké.❍

une fonction P(X) retournant la probabilité d'apparition de l'élément X sur l'ensemble desdonnées traitées.

❍

L'optimisation proposée est la suivante :

Lors de l'insertion d'un mot X, si l'emplacement T[H(X)] est déjà occupé, le nouveaumot X aura la priorité si sa probabilité est plus élevée que celle du mot dansl'emplacement occupé.

Pour sa réalisation, il suffira de compléter la procédure ci-dessous, déjà vue au cours.

function Insert( X : string ) : integer;var H0, hi : integer;begin H0 := H(X); hi := H0; while ( T[hi] <> '' ) and ( T[hi] <> X ) do begin

{ Ajouter ici le code de l'optimisation }

hi := (hi+1) mod MaxElements; if hi = H0 then begin writeln('tableau plein'); exit(program); end; { if } end; { while } if T[Hi] = '' then T[Hi] := X; Insert := hi;end; { Insert }

b.

Solution



Notes du contrôle continu du 14 juin1999

Nom Q1 Q2 Q3 Note

Roberto Campelo 8 5 0 1,3

Frederic Ehrler 14 20 10 4,4

Christiane James 12 12 20 4,4

Dimitri Kalas 17 18 16 5,1

Julie Lutz 17 12 16 4,5

Alexandre Nevski 9 10 16 3,5



exercice suivant

Graphes orientés


Soit un graphe défini sur la base des relations de dépendances suivantes concernant les ages respectifsd'un groupe de personnes:

Jean est plus jeune que Paul et Pierre, mais plus agé que Jeanne.●

Jacques est plus jeune que Jeanne et Pierre, mais plus vieux que Marie●

Pierre est plus jeune que Paul, mais plus vieux qu'André et Alice●

Yves est plus jeune que Paul, mais plus vieux que Claude et Alice●

Claude est plus jeune que Pierre et plus vieux qu'André●

dessinez le graphe en question.

donnez la matrice de connectivité de ce grapheb.

donnez la matrice de connectivité de la fermeture transitive de ce graphe indiquez à quel type dequestion la fermeture transitive permet de répondre plus facilement

c.

donnez une séquence de sommets correspondant à un tri topologique, indiquez s'il existe une autresolution possible (si oui, proposez en une).

d.

Solution

exercice suivant



Exercice suivant

B-Arbres


Soit un B-Arbre d'ordre 1, c'est-à-dire que chaque page peut avoir soit 1 soit 2 données.

Insertion: Insérez dans l'ordre indiqué les nombres: 1,2,3,6,7,4,5,8,9 dans le B-arbre et dessinezaprès chaque insertion le B-arbre résultant.

.

Complexité d'espace: En supposant que chaque page occupe 512 octets (2 octets pour le nombre dedonnées dans la page, 4 octets par "pointeur" vers une autre page et 249 octets par donnée),indiquez l'espace minimum et maximum nécessaires pour stocker 10'000 données dans ce B-arbred'ordre 1.

b.

Profondeur: Quelle profondeur minimum et maximum aura le B-arbre avec 10'000 données.c.

Solution

Exercice suivant



exercice suivant

Adressage associatif par transformation de clés (Hash-code)


Soit une fonction H qui retourne les valeurs numériques suivantes pour les mots suivants:

mot: du esprit etait forte illumination jour la lumiere qu si son soudaine traversa uneH(mot): 6 13 3 12 9 10 7 15 5 6 5 8 10 2

On décide de placer ces mots dans un tableau de 15 positions (indices 1..15) par la méthode de l'adresseouvert, en utilisant l'expression suivante pour traiter les collisions:

Hi(K) = [(H(K) + i*length(K)) mod 15] + 1, où i représente le nombre de collisions déjà subies lors del'insertion de K (i = 0 au début) et length(K) est la fonction qui retourne le nombre de caractères d'unmot.

N.B.: Au cas où on essaye de placer un nouveau mot dans une position occupée par un mot ayantlui-même été déplacé, on donnera la priorité au nouveau mot.

Dessinez le tableau résultant de l'insertion des mots énumérés ci-dessus en les prenant dans l'ordre où ilssont écrits.

Solution

exercice suivant



Université de GenèveFaculté des SciencesDépartement d'Informatique

29 avril 1999


Contrôle Continu - Première épreuve

Rappel:

Ce contrôle continu est un examen. Vous n'êtes donc pas autorisés à communiquer avec d'autrespersonnes par quelque moyen que ce soit (communication verbale, par support papier ou électronique,courrier électronique, Web, espace disque), à l'exception des assistants chargé de la surveillance de cetexamen. Une vérifications des "logs" des serveurs Web, proxy et courrier électronique peut être effectuéepour déterminer si quelqu'un a contrevenu à cette interdiction. Toute tricherie sera sanctionnée par unenote de 0 à l'examen final pour tous les contrevenants.

Vous êtes par contre autorisés à consulter toute la documentation que vous désirez, que ce soit le livre ducours ou d'autres livres, vos notes personnelles, le site Web du cours (y compris les anciennes questionsd'examens et leurs corrigés), ou même des fichiers vous appartenant.

Comment rendre vos réponses aux questions:

Les questions portent sur des exercices de programmation. Vos réponses vont donc consister en du codePascal complétant des programmes qui vous seront fournis. Vous devez rendre vos réponses sur unedisquette portant une étiquette sur laquelle votre nom est clairement inscrit. Ces disquettes vous serontrendues par la suite.

Si pour une raison quelconque, vous vous trouviez dans l'impossibilité de rendre une disquette, vousdevez laisser une copie des fichiers contenant vos réponses dans votre espace disque personnel, enindiquant à au moins un assistant le problème que vous avez rencontré et en lui expliquant où se trouventvos réponses.

Recommandation:Si vous n'arrivez pas à faire correctement fonctionner votre code pour une des deux questions, nerestez pas bloqués dessus plus de deux heures pour avoir le temps de traiter l'autre question.

Contrôle Continu de Structures de Données du 29 avril 1999

http://cuisung.unige.ch/std/CC/990429/ (1 of 4) [23-09-2001 16:00:26]

http://www.unige.ch/

http://www.unige.ch/sciences/

http://cui.unige.ch/ScDep/

Questions

Question 1

DescriptionIci vous trouvez le fichier qui contient un programme en Pascal.

Ce programme traite des chaînes bidirectionelles qui ont deux bouts facilement accessibles. Pour l'acces,c'est a dire l'ajout et la suppression des elements et pour la construction et destruction des listes tout lesfonctions necessaires sont fournies avec les commentaires. Lisez et comprenez ces procedures. C'estnécessaire pour le reste de cette question.

Question:Completez maintenant les fonctions et procedures suivantes:

estPalindrome_ChaineCette fonction verifie si une chaine est un palindrome, c'est a dire sile n-ième element est egale au (n-1)-avant-dernier-element

newReverse_ChaineCette fonction genère une nouvelle chaîne qui est exactement lachaîne d'entrène lu a'l envers.

ajouteApresChaine_Chaine

Cette fonction ajoute une chaine (deuxième paramètre) a la find'une autre (premier paramètre). La chaîne qui était donée commepremier paramètre est entierement vide apres exécution de cettefonction.

Conseil:Lisez et comprenez vraiment les procédures données. Sinon la question devient beaucoup plus difficile.

Question 2: arbre lexicographiqueOn a construit un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de façon queles chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante:



http://cuisung.unige.ch/std/CC/990429/CC2_01_01.html


Sur la base des déclarations suivantes, écrivez une fonction Lecture qui construira la structure dedictionnaire à partir d'un fichier Text où les mots sont fournis, un par ligne, et une fonction NbMotscomptant les mots du dictionnaire ayant une longueur donnée. Si la longueur est 0, il faut retourner lenombre total de mots, quelle que soit leur longueur.

type VersNoeud= ^Noeud; Noeud= record Desc: array['a'..'z'] of VersNoeud; Complet: boolean; end; { Noeud }var Dico: VersNoeud;

function Lecture(NomFichier: string): VersNoeud; (* cette fonction doit lire les mots du dictionnaire dans un fichier et construire la structure d'arbre au fur et a mesure de la lecture des mots *)

function NbMots(Longueur: integer; Dico: VersNoeud):integer; (* cette fonction doit retourner le nombre de mots contenus dans le dictionnaire, dont le nombre de lettres=Longueur *)

Fournis:

programme avec function PseudoLecture: VersNoeud;●

jeu de données de test●

Indication: Nous vous recommandons de commencer par la fonction NbMots, en invoquant la fonction"PseudoLecture" fournie, à la place de la fonction Lecture qui vous est demandée. Lorsque la fonctionNbMots sera au point et si vous en avez encore le temps, vous pourrez essayer de remplacer l'appel à lafonction PseudoLecture par un appel à la fonction Lecture que vous aurez écrite.

Solution



http://cuisung.unige.ch/std/CC/990429/Q2.pas

http://cuisung.unige.ch/std/CC/990429/Q2.dat

Questions? Wolfgang Müller, Jean-Marc Küffer, Hidenori Yoshizumi, José Bernardo, Bertrand Ibrahim

ou plutôt oralement

Quelques photos sont disponibles, ainsi que le résultat de l'évaluation



http://cui.unige.ch/~muellerw/

http://cui.unige.ch/~kuffer/

http://cuisung.unige.ch/Hidenori/

http://cui.unige.ch/~bernardo/


http://cuisung.unige.ch/std/CC/990429/photos/

Notes du contrôle continu du 29 avril1999

Nom Q1 Q2 Note

Tiana Andriharifara 18 1 1,9

Patrick Arbus 10 0 1,0

Jose Barba 8 0 0,8

Roberto Campelo 27 5 3,2

Frederic Ehrler 24 3 2,7

Yves Fomekong 17 0 1,7

Chnina Hechmi 0 0 0

Nicolas Hurzeler 0 0 0

Christiane James 17 0 1,7

Dimitri Kalas 27 20 4,7

Sylvain Laurence 24 3 2,7

Julie Lutz 21 20 4,1

Bruno Martins 22 5 2,7

Alexandre Nevski 29 20 4,9

Notes du contrôle continu du 29 avril 1999


Tri topologique inverse


En s'inspirant de la description de graphes orientés en termes de type abstrait vue au cours, nous allonssupposer que les types "Graphe" et "SerieDeSommets" ont été définis, sans que vous ne connaissiez lesdétails de ces structures. Nous allons aussi supposer que les primitives suivantes sont à votre disposition:

function Index(NomSommet: string; LeGraphe: Graphe): integer; { retourne un numero compris entre 1 et MaxNbSommets }

function NomSommet(IndexSommet: integer; LeGraphe: Graphe) :string; { retourne le nom du sommet dont l'index est fourni }

function NombreDeSommets(LeGraphe: Graphe): integer; {retourne le nombre de sommets effectifs composant le graphe}

function SommetsVoisins(IndexSommet: integer; LeGraphe: Graphe): SerieDeSommets; { retourne une structure permettant de retrouver l'index des voisins immédiats }

function ExtraitSommet(var UneSerie: SerieDeSommets): integer; { extrait un sommets de la série et retourne son index }

function FinDeSerie(UneSerie: SerieDeSommets): boolean; { vrai s'il n'y a plus de sommet suivant dans la serie }

En utilisant ces primitives, tout en ignorant de quelle façon la structure de graphe est implantée, écrivezune procédure de tri topologique inverse qui imprime les sommets du graphe fourni en paramêtre:

TriTopologiqueInverse(LeGraphe: Graphe)

Solution



Exercice suivant

Comparaison de B-arbres et B*-arbres

Question posée à l'écrit du 7 octobre 1998

Rappel: un B*-arbre est une variante de B-arbre dans laquelle les pages (à l'exception de la racine) sontmaintenues au moins au deux tiers pleines

Soit un ensemble d'un million de données occupant chacune 47 octets. En supposant que l'on utilise despages de 1024 octets et des références occupant 4 octets, effectuez les calculs suivants pour le cas où onconstruit un B-arbre et le cas où on construit un B*-arbre. Expliquez à chaque fois votre raisonnementpour arriver aux résultats que vous fournissez.

ordre du B-arbre et du B*-arbre.

taille minimale et maximale de l'espace disque occupéb.

profondeur minimale et maximale de la structurec.

Solution

Exercice suivant



Exercice suivant

Arbres dépliables


Dessiner un arbre dépliable de tri, qui sera construit à partir des mots suivants, en prenant laséquence de gauche à droite :

la, lumiere, du, jour, etait, si, forte, qu, une, illumination, soudaine, traversa, son,esprit.

.

Détruire l'élément qui se trouve à la racine et dessiner l'arbre dépliable résultant.b.

Solution

Exercice suivant



Tables de décision

question posée à l'examen écrit du 25 juin 1998

Avec les déclarations suivantes définissant une table de décision ainsi qu'un arbre binaire ordonné,écrivez une fonction «ConstruitArbre» qui convertisse une table de décision condensée (paramètred'entrée) en arbre binairee (paramètre de sortie) où les feuilles contiennent les indicateurs d'actions d'unerègle et les noeuds intermédiaires contiennent le texte des conditions de façon que l'arborescencepermette de sélectionner la règle qui s'appliquera à un cas donné.

Indication: il faut s'inspirer de l'algorithme de conversion d'une table de décision en cascade de tests,mais construire une structure d'arbre au lieu de produire du code Pascal.

const MaxNbCond = ...; MaxNbRegles = ...; MaxNbActions = ...;

type Conditions =(Vrai, Faux, Indetermine);

TableDecision = record NbConditions: 1..MaxNbCond; NbRegles: 1..MaxNbRegles; ValCond: array[1..MaxNbRegles, 1..MaxNbCond] of Conditions; NbActions: 1..MaxNbActions; Agir: array[1..MaxNbRegles, 1..MaxNbActions] of boolean; TxtConditions:array[1..MaxNbCond] of string[30]; TxtActions:array[1..MaxNbActions] of string[30]; end; { TableDecision }

PtrNoeud: ^Noeud;

Noeud = record case Feuille: boolean of false: (TxtCond: string[30]; Vrai, Faux: PtrNoeud); true: (Actions: array[1..MaxNbActions] of boolean); end; { Noeud }

function ConstruitArbre(Table: TableDecision): PtrNoeud;

solution

solution de l'exercice 2, sectionn 15.1


Fichiers séquentiels indexés


Soit une structure de fichier séquentiel indexé contenant des données occupant chacune 80 octets, dont 8octets contiennent la clé d'accès.

1.a)

Quelle taille minimale de bloc de données permet d'éviter d'avoir de l'espace disque inutilisé dansle fichier? (en supposant des pages qui sont des multiples de 512 octets)

1.b)

Combien de données par bloc cela représente-t-il?

Si l'on prend la taille que vous avez trouvé en 1.a) aussi bien pour les blocs de données que pour les blocsd'index et si l'on suppose qu'une référence d'un bloc d'index vers un autre bloc (d'index ou de données)occupe 4 octets,

1.c)

Combien de données par bloc faudrait-il mettre pour atteindre un taux de remplissage d'environ80%?

1.d)

Quelle place disque occupera le fichier lorsqu'il contiendra 100'000 éléments si on remplit lesblocs de données à ~80%?

1.e)

Indiquez aussi la profondeur de l'arborescence d'index,

1.f)

le nombre de blocs d'index à chaque niveau de l'arborescence ainsi que

1.g)

le nombre total de blocs de données.

Solution



Exercice suivant

Recherche B-Arbre


Soit le B-Arbre d'ordre 1 suivant.

2.a)

Dessinez le B-arbre résultant de l'insertion de la valeur L dans le B-arbre ci-dessus.

2.b)

Dessinez le B-arbre résultant de la suppression de la valeur C dans le B-arbre ci-dessus.

2.c)

Dessinez le B-arbre résultant de l'insertion de la valeur Z dans le B-arbre ci-dessus.

2.d)

Dessinez le B-arbre résultant de la suppression de la valeur S dans le B-arbre ci-dessus.

2.e)

Dessinez le B-arbre résultant de la suppression de la valeur P dans le B-arbre ci-dessus.

Solution

Exercice suivant



Le chemin du moindre coût

Question posée au contrôle continu du 15 juin 1998 1997

Un concurrent d'un cross-country doit traverser un terrain difficile du point A au point B. Avant lacourse, il veut choisir le chemin à suivre. Il a une carte du terrain:

La légende montre les types de terrains, et un nombre associé à chaque type qui indique la difficulté de satraversée. D'une case de la carte on ne peut accéder qu'à ses quatre voisines au nord, au sud, à l'est et àl'ouest (le déplacement en diagonale est interdit).

Le concurrent est équipé d'un ordinateur, dans lequel la carte peut être stockée. On vous a demandé departiciper à l'écriture d'un programme qui lui permette de trouver le meilleur chemin dans cette situation,c'est-à-dire le chemin du moindre coût.

3.a)

Comment représenteriez-vous l'ensemble des données fournies par la carte en utilisant un graphe?(Donnez juste une courte explication - ne dessinez pas le graphe entier.)

3.b)

Quelle(s) structure(s) de données serait la(les) plus efficace(s) pour stocker les noeuds et arcs d'untel graphe? Ecrivez les déclarations Pascal qui définissent la(les) structure(s) que vous proposez.

3.c)

Quel algorithme de recherche utiliseriez-vous pour trouver le chemin le moins coûteux entre lespoints A et B? Justifier votre réponse, en considérant d'autres algorithmes possibles.

3.d)

Ecrivez une description précise, en pseudo-code, de l'algorithme de recherche choisi.



Solution



Exercice suivant

Chaînes bidirectionnelles


Supposons qu'un programme d'édition de texte utilise la structure de chaîne de strings suivante pourreprésenter le texte en cours d'édition:

type VersLigne = ÛneLigne; UneLigne = record Texte: string; LignePrecedente, LigneSuivante: VersLigne; end; { UneLigne }var LeTexte: VersLigne;

Ecrivez une procédure "Paragraphes", selon les déclarations suivantes, qui parcourt la structure dedonnée pour détermine où se trouvent les paragraphes du texte (les paragraphes sont composés de une ouplusieurs lignes non vides séparées par une ou plusieurs lignes vides). Le résultat sera fourni comme unechaîne bidirectionnelle de descripteurs de paragraphes (type Para). Prenez bien soin à traiter tous les casparticuliers qui peuvent survenir

type PtrPara: ^Para; Para = record Debut, Fin: integer; Preced, Suivant: PtrPara; end; { Para }

procedure Paragraphes(UnTexte: VersLigne; var ChainePara: PtrPara);

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/7/4f.html [23-09-2001 16:02:09]

Exercice suivant

Chaînes mono-directionnelles


Compléter le programme suivant en donnant le corps des procédures Insertion et Afficher, étant donnéela structure de données citée par la suite

N.B. On conserve dans un tableau TabElement des chaînes avec leur taille respective.

Program Chaines;{Programme qui permet d'affecter des valeurs aux chaînes qui se trouvent dans un tableau et d'afficher le contenu de ce tableau}CONST MaxNbSommets = ...; MaxNumChaine = ...;TYPE PtrNoeud = ^Noeud;

Noeud = RECORD Donnee: integer; Suivant: PtrNoeud; END;

EltNoeud = RECORD Taillechaine: Integer; Chaine: PtrNoeud; END;

VAR TabElement: ARRAY[1..MaxNumChaine] OF EltNoeud;

Procedure Insertion(Valeur, NumChaine : integer); {Procédure permettant d'insérer une valeur à la fin de la NumChaine-ème chaîne}

Procedure Afficher; {Procédure permettant d'afficher le contenu du champs "Donnee" pour toutes les chaînes du tableau}

Solution

Exercice suivant



Exercice suivant



Avec les déclarations suivantes définissant un anneau bidirectionnel, on aimerait ranger une valeur dansl'anneau où les données sont triées dans l'ordre croissant. Pour ce faire, écrire d'abord la procédured'insertion ChercherInsertion, qui permet de déterminer le noeud d'insertion pour une valeur donnée.Puis écrire la procédure RangerValeur, qui fait appel à ChercherInsertion pour trouver où insérer lanouvelle valeur et fait l'insertion proprement dite à l'aide de la procédure InsererNoeud que noussupposerons déjà exister.

N.B. On suppose que le code de la procédure InsererNoeud est déjà fourni.

TYPE PtrNoeud = ^Noeud;

Noeud = RECORD Donnee : integer; Precedent, Suivant: PtrNoeud; END;

VAR Entete : PtrNoeud; {Entête pour l'anneau} AnneauVide : boolean; {Indicateur d'anneau vide}

Procedure InsererNoeud(var NPtr,TPtr : PtrNoeud);{Insère le Noeud NPtr après TPtr Vous n'avez pas besoin d'écrire le code de cette procédure}

Procedure ChercherInsertion(Valeur: Integer; VAR NoeudInsertion: PtrNoeud); {Permet de déterminer le noeud d'insertion pour la valeur donnée. ChercherInsertion retourne, dans NoeudInsertion, un pointeur vers le plus grand élément encore inférieur à la valeur passée en paramètre, ou NIL, si Valeur existe déjà dans l'anneau. }

Procedure RangerValeur(Valeur: Integer); {Permet de ranger une valeur donnée dans l'anneau trié }

Solution

Exercice suivant



Exercice suivant

Arbre syntaxique


En supposantque l'on dispose des fonctions suivantes pour contruire une structure d'arbre:

type PtrNoeud: ^Noeud;

function Feuille(Contenu: char): PtrNoeud; { crée par allocation dynamique un noeud sans descendant et contenant un caractère }

function Arbre(ContenuRacine:char; Gauche, Droit: PtrNoeud): PtrNoeud; { crée, par allocation dynamique, un nouveau noeud racine auquel seront rattachés les sous-arbres gauche et droit fournis en paramêtre, de façon à former un nouvel arbre }

Quelle sera l'expression qui permettra de construire, en une seule instruction Pascal, l'arbresuivant:

.

Donnez une déclaration possible pour le type Noeud ainsi que le code des deux fonctionsFeuille et Arbre.

b.

Solution

Exercice suivant



exercice suivant

Structures de graphes


En s'inspirant de la description de graphes non-orientés en termes de type abstrait vue au cours, nousallons supposer que les types "Graphe" et "SerieDeSommets" ont été définis, sans que vous neconnaissiez les détails de ces structures. Nous allons aussi supposer que les primitives suivantes sont àvotre disposition:

function Index(NomSommet: string; LeGraphe: Graphe): integer; { retourne un numero compris entre 1 et MaxNbSommets }function NomSommet(IndexSommet: integer; LeGraphe: Graphe) :string; { retourne le nom du sommet dont l'index est fourni }function NombreDeSommets(LeGraphe: Graphe): integer; {retourne le nombre de sommets effectifs composant le graphe}function SommetsVoisins(IndexSommet: integer; LeGraphe: Graphe): SerieDeSommets; { retourne une structure permettant de retrouver l'index des voisins immédiats }function PremierSommet(var UneSerie: SerieDeSommets): integer; { extrait le premier des sommets de la série et retourne son index }function SommetSuivant(var UneSerie: SerieDeSommets): integer; { extrait le prochain sommet de la serie & retourne son index}function FinDeSerie(UneSerie: SerieDeSommets): boolean; { vrai s'il n'y a plus de sommet suivant dans la serie }

En utilisant ces primitives, tout en ignorant de quelle façon la structure de graphe est implantée, écrivezune procédure de parcours en profondeur qui imprime les noms des sommets du graphe fourni enparamêtre:

procedure DFS(LeGraphe: Graphe);

Solution

exercice suivant





On veut construire un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de sorteque les chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante


Sur la base des déclarations suivantes, écrivez une procédure imprimant touts les mots du dictionnairedans l'ordre croissant de longueur de mot et, pour des mots d'une même longueur, par ordre alphabétique:

type VersNoeud= ^Noeud; Noeud= record Desc: array['a'..'z'] of VersNoeud; Complet: boolean; end; { Noeud }

var Dico: VersNoeud;

procedure Imprime(LeDico: VersNoeud);

Note: vous avez intérêt à considérer cet arbre lexicographique comme un graphe orienté et appliquer unedes méthodes de parcours de graphe. Vous pouvez aussi considérer, si vous en avez besoin, que vousdisposez d'un type "Pile" ou "FileDAttente" avec leurs procédures de manipulation. Vous pouvez aussiutiliser des strings pour réconstituer une séquence de lettres formant un mot.

Solution



exercice suivant

Hash-code


Soient deux fonctions de hash-code H1 et H2 retournant les valeurs numériques suivantes:

mot: les examens du premier cycle pour lesquels il n y aurait quH1(mot): 15 6 11 1 3 6 2 5 7 15 2 9

H2(mot): 8 5 12 14 2 10 17 7 5 13 8 22

mot: un examen oral a subir sont admis si chaque note atteint quatreH1(mot): 13 18 16 11 10 23 8 8 9 20 15 22

H2(mot): 9 6 1 4 3 7 13 6 17 2 12 16

On suppose que l'on utilise la méthode du chaînage externe à partir d'un tableau de 11 positions, enutilisant H1 pour déterminer quelle chaîne utiliser et H2 pour trier les éléments d'une même chaîne(c'est-à-dire qu'au sein d'une même chaîne, un mot mi sera placé avant un autre mot mj siH2(mi)<H2(mj)). Dessinez le tableau des chaînes que l'on obtient, en mettant un mot et le résultat de H2pour ce mot dans chaque élément de chaîne. Indiquez quelle expression basée sur H1 vous avez utiliséepour le choix de la chaîne.

Solution

exercice suivant



exercice suivant

Tables de décision


Avec les déclarations suivantes définissant des tables de décision, écrivez une procédure "Extension" quiconvertisse une table de décision condensée (paramètre d'entrée) en table étendue (paramètre de sortie):

const MaxNbCond = ...; MaxNbRegles = ...; MaxNbActions = ...;

type Conditions =(Vrai, Faux, Indetermine);

TableDecision = record NbConditions: 1..MaxNbCond; NbRegles: 1..MaxNbRegles; ValCond: array[1..MaxNbRegles, 1..MaxNbCond] of Conditions; NbActions: 1..MaxNbActions; Agir: array[1..MaxNbRegles, 1..MaxNbActions] of boolean; TxtConditions:array[1..MaxNbCond] of string[30]; TxtActions:array[1..MaxNbActions] of string[30]; end; { TableDecision }

procedure Extension(Entree: TableDecision; var Sortie: TableDecision);

Note: Pour simplifier l'écriture, vous pourrez supposer que l'affectation d'enregistrements ou de tableauxest autorisée en Pascal.

Solution

exercice suivant



Exercice suivant


Question posée au contrôle continu du 28 avril 1997



a)

Ecrivez une procédure "EchangeLignes", selon la déclaration suivante, qui échange deux élémentsde la structure (on ne veut pas juste échanger le contenu du champs Texte):

procedure EchangeLignes(var UnTexte: VersLigne; NoLigne1, NoLigne2: integer);

b)

Ecrivez une procédure "InverserLignes", selon la déclaration suivante, qui inverse complètementl'ordre des lignes dans la structure de donnée:

procedure InverserLignes(var UnTexte: VersLigne);

Dans les deux cas, il faudra prendre soin de vérifier tous les cas particuliers et diagnostiquer toutesles erreurs éventuelles.

Solution

Exercice suivant



Exercice suivant



Dans le programme suivant, vous disposez d'une chaine bidirectionnelle qui a un pointeur supplémentaire(appelé ici S2):

program test(input, output);type Ptr = ^Noeud; Noeud = record info : integer; Preced, Suiv, S2 : Ptr; end;var LaChaine, P : Ptr;

procedure CreeS2(Depart:Ptr);var Deplacement, i:integer; Courant, Etape : Ptr; FinEtape : boolean;begin Etape := Depart; while Etape <> nil do begin Deplacement := Etape^.info; i := 1; Courant := Etape; FinEtape := false; if Deplacement > 0 then begin while (i <= Deplacement) and (not FinEtape) do if Courant^.Suiv <> nil then begin i := i+1; Courant := Courant^.Suiv; end {then} else begin Courant := nil; FinEtape := true; end; {if} Etape^.s2 := Courant; end {then} else begin Deplacement := -Deplacement; while (i <= Deplacement) and (not FinEtape) do if Courant^.Preced <> nil then begin i := i+1; Courant := Courant^.Preced;


http://cuisung.unige.ch/std/ex/7/4e.html (1 of 2) [23-09-2001 16:02:39]

end {then} else begin Courant := nil; FinEtape := true; end; {if} Etape^.s2 := Courant; end; {else} Etape := Etape^.Suiv; end; {while}end; {CreeS2}begin initialise(LaChaine); CreeS2(LaChaine); P := LaChaine; if P <> nil then repeat write(P^.info:1,'->'); P := P^.s2; until P = nil; else writeln('nil');end.

où la procédure initialise(var Depart:Ptr); est utilisée pour faire les initialisations: créer la chaine etinitialiser le pointeur S2 à nil. Quel résultat sera affiché quand LaChaine pointe sur:

2 -> 0 -> 1 -> 1 -> -31.

3 -> -1 -> 2 -> -1 -> -32.

Solution

Exercice suivant


http://cuisung.unige.ch/std/ex/7/4e.html (2 of 2) [23-09-2001 16:02:39]

Exercice suivant

Arbre généalogique


program arbre_genealogique;

const MaxLongueurNom = 30;

type Genre = (Masculin, Feminin); Noms = array[1..MaxLongueurNom] of char; ChaineFreresSoeurs = ^NoeudFrereSoeur; PersonnePtr = ^Personne;

NoeudFrereSoeur = record FrereOuSoeur: PersonnePtr; FrereSoeurSuivant: ChaineFreresSoeurs; end; {NoeudFrereSoeur}

Personne = record Nom: Noms; Prenom: Noms; Sexe: Genre; Epoux: PersonnePtr; FreresEtSoeurs: ChaineFreresSoeurs; Enfants: ChaineFreresSoeurs; end; {Personne}

function NouvellePersonne(SonNom, SonPrenom: Noms; SonSexe: Genre):PersonnePtr; var laPersonne: PersonnePtr; begin new(laPersonne); with laPersonne^ do begin Nom := SonNom; Prenom := SonPrenom; Sexe := SonSexe; Epoux := nil; FreresEtSoeurs := nil; end; {with} NouvellePersonne := laPersonne; end; {NouvellePersonne}



http://cuisung.unige.ch/std/ex/8/2c.html

procedure Epouse(epoux1, epoux2: PersonnePtr);begin epoux1^.Epoux := epoux2; epoux2^.Epoux := epoux1;end; {Epoux}

procedure AjouteEnfant(Parent, Enfant: PersonnePtr);var NouveauNoeud, EnfantCourant, EnfantPrecedent: ChaineFreresSoeurs;begin new(NouveauNoeud); with NouveauNoeud^ do begin FrereOuSoeur := Enfant; FrereSoeurSuivant := nil; end; {with} EnfantCourant := Parent^.Enfants; if EnfantCourant = nil then begin {Ce nouvel Enfant est leur premier Enfant} Parent^.Enfants := NouveauNoeud; if Parent^.Epoux <> nil then Parent^.Epoux^.Enfants := NouveauNoeud; Enfant^.FreresEtSoeurs := NouveauNoeud; end {if} else begin Enfant^.FreresEtSoeurs := EnfantCourant; {cherche le dernier Enfant} while EnfantCourant <> nil do begin EnfantPrecedent := EnfantCourant; EnfantCourant := EnfantCourant^.FrereSoeurSuivant; end; {while} EnfantPrecedent^.FrereSoeurSuivant := NouveauNoeud; end; {else}end; {AjouteEnfant}

Sur la base des déclarations et procédures ci-dessus, qui permettent de construire un arbre généalogique:

dessinez un diagramme qui montre l'utilisation de cette structure pour une famille contennant aumoins deux generations;

1.

écrivez une procédure qui trouvera tous les petits-enfants d'une personne et imprimera leurs nomset prénoms:

procedure ImprimePetitsEnfants(LaPersonne: PersonnePtr);

2.

Solution

Exercice suivant



http://cuisung.unige.ch/std/ex/8/2c.html

Exercice suivant

Arbre syntaxique et chaîne

Question posée à l'écrit du 5 mars 1997

Soit un arbre syntaxique contenant une expression arithmétique, basé sur les déclarations suivantes:

type Contenus = (Operande, Operateur); Operations=(Addition, Soustraction, Multiplication, Division); VersNoeud = ^Noeud; Noeud = record case Contenu: Contenus of Operande: (Valeur: integer); Operateur:(Operation: Operations; Gauche,Droite: VersNoeud); end; (* Noeud *)

Ecrivez une procédure qui convertira un tel arbre syntaxique en une chaîne contenant la mêmeexpression arithmétique en notation polonaise postfixée. Vous utiliserez à cet effet les déclarationssuivantes:

type VersMaillon = ^Maillon; Maillon = record Suivant: VersMaillon; case Contenu: Contenus of Operande: (Valeur: integer); Operateur:(Operation: Operations); end; (* Maillon *)

Pour rappel, la notation polonaise postfixée consiste à noter une expression arithmétique avec l'opérateurà la suite des opérandes sur lesquels il porte. Cette notation ne nécessite donc pas de parenthèses. Parexemple, l'expression (85 - 9) * ((78 + 45) / (6 - 2)) est notée, en notation polonaise postfixée, de la façonsuivante: 85 9 - 78 45 + 6 2 - / *. Pour vous aider, sachez que cette conversion correspond à une desméthodes classiques de parcours d'arbre.

Solution

Exercice suivant



http://cuisung.unige.ch/std/ex/8/1b.sol.html

Exercice suivant

B-arbre

Question posée à l'écrit du 5 mars 1997

a) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 10

b) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 21

c) Avec le même B-arbre de départ qu'au point b, dessinez le B-arbre résultant de la suppression de lavaleur 55.

d) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 23

e) Avec le même B-arbre de départ qu'au point d, dessinez le B-arbre résultant de l'insertion de la valeur4.

f) Avec le même B-arbre de départ qu'au point d, dessinez le B-arbre résultant de la suppression de lavaleur 15.

Solution

Exercice suivant



Exercice suivant





a)

Ecrivez une procédure "EffaceLigne", selon la déclaration suivante, qui change la structure dedonnée pour refléter la suppression d'une ligne du texte:

procedure EffaceLigne(var UnTexte: VersLigne; NumeroLigne: integer);

b)

Ecrivez une procédure "JoindreLignes", selon la déclaration suivante, qui change la structure dedonnée pour combiner la ligne courante et la ligne suivante en une seule ligne (le contenu de laligne suivante est inséré à la fin de la ligne courante et la ligne suivante est alors supprimée):

procedure JoindreLignes(var UnTexte: VersLigne; LigneCourante: integer);

Dans les deux cas, il faudra prendre soin de vérifier tous les cas particuliers et diagnostiquer toutesles erreurs éventuelles.

Solution

Exercice suivant



Exercice suivant

Fichiers séquentiels indexés et B-arbres


a)

Quelle est la taille de l'espace disque nécessaire pour être sûr de pouvoir créer un fichier séquentielindexé qui doit contenir 1'000'000 éléments, sachant qu'un élément nécessite une place de 76octets, dont une clé de 8 octets, que les blocs de données ont une taille de 1536 octets et les blocsd'index 1024 octets et que les pages de données sont initialement remplies à 80%? On supposeraque les références, dans un bloc d'index, à un autre bloc d'index ou à un bloc de donnée, tiennentsur 4 octets. Justifiez votre réponse et donnez le détail des calculs. En plus de la taille de l'espacedisque, vous indiquerez, entre autres, le nombre de blocs de données, la profondeur del'arborescence des blocs d'index et le nombre de blocs d'index à chaque niveau.

b)

Pour les mêmes données (même nombre et même taille d'élément), quelle sera la taille de l'espacedisque nécessaire et le nombre de niveaux si l'on utilise une structure de B-arbre avec des pages de1024 octets (donnez les valeurs minimales et maximales possibles, dans l'hypothèse de pages àmoitié pleines ou entièrement pleines)? Là aussi, justifiez votre réponse et donnez le détail descalculs: ordre du B-arbre, nombre de pages minimum et maximum, ...N.B. Comme pour le séquentiel indexé, les références à une page occupent 4 octets.

Solution

Exercice suivant



Chaînes mono-directionnelles


Soit une dùne chaîne monodirectionnelle avec des éléments entiers. Ecrivez une procédure Pascal quisupprime à la fois le premier et le dernier élément de la chaîne, et ceci de manière répétitive, jusquà cequ'il ne reste qu'un seul élément, ou jusqu'a ce que la chaîne soit vide. La procédure donnera commerésultat soit le dernier élément restant, soit le pointeur "nil".

Exemples:

Dans ce cas, on supprime les éléments contenant les valeurs entièlres 2 et -1, et le résultat de laprocédure sera alors 3.

1.

Dans ce cas, on supprimera d'abord 2 et 5, ensuite 3 et -1, et le résultat sera alors "nil".

2.

Solution



Exercice suivant

Réseau autoroutier

Soit un réseau autoroutier tel que celui-ci:

Quelle structure(s) de donnée(s) utiliseriez-vous pour le représenter; dessinez-la.1.

Donnez le détail des déclarations que vous feriez, en Pascal.2.

Ecrivez une fonction qui déterminera la distance minimale à parcourir entre deux villes données enparamètre.

3.

Solution

Exercice suivant



Exercice suivant


Question posée au conctrôle continu du 17 juin 1996

On vous fournit un entier ainsi qu'un anneau bidirectionnel ayant comme éléments des entiers, pouvantêtre négatifs. On vous demande de vous déplacer dans l'anneau à la position absolue donnée par l'entierqui vous est donné. Là, vous prenez l'entier qui se trouve dans l'élément courant, vous supprimezl'élément courant, et vous vous déplacez dans l'anneau, cette fois-ci de façon relative à la positioncourante en fonction du nombre qui s'y trouvait. Vous devez répéter ces pas (prendre l'entier, supprimerl'élément, se déplacer) jusqu'à ce que il n'y ait plus d'élément dans l'anneau, jusqu'à ce que vous sortiezde l'anneau, ou bien jusqu'à ce que vous rencontriez la valeur 0 (zéro) dans l'anneau. (Attention, si vousarrivez à la fin de l'anneau, il ne faut pas repartir depuis le début; de même, si on arrive au début,il ne faut pas continuer à la fin).

On vous demande de fournir, dans un paramètre de sortie, le type d'arrêt et d'imprimer, dans laprocédure, les valeurs se trouvant dans les éléments visités. Utilisez les déclarations suivantes:

type TypeArret = (SortieAnneau, ElementNul, AnneauVide); Anneau = Êlement; Element = record Entier : Integer; Predecesseur, Succeseur : Anneau; end; { Element }

procedure DeplacerDansAnneau(var UnAnneau : Anneau; Deplacement: integer; var Arret : TypeArret);

Exemple:

Dans le cas ci-dessus, si l'entier donné initialement est 1, on va à la première position, on prend 2, onl'imprime et on supprime la première position de l'anneau. On se déplace en avant de 2 positions(correspondant à la position 3 dans l'anneau initial), on prend -2, on l'imprime et on supprime l'é lément.Ensuite il faut signaler la fin du programme, parce qu'avant l'élément que l'on vient de suprimer il n'y aqu'un seul élément (contenant 4) et l'on ne peut donc pas se déplacer de 2 éléments en arrière.

Solution

Exercice suivant



Exercice suivant

Arbre de tri


a) Etant donné l'arbre de tri suivant, donnez une séquence possible des données fournies en entrée quiaurait permis d'aboutir à l'arbre de tri en question:

b) idem pour l'arbre suivant:

Solution

Exercice suivant



Exercice suivant

Tri topologique inverse


En s'inspirant de la description de graphes non-orientés en termes de type abstrait vue au cours, nousallons supposer que les types "Graphe" et "SerieDeSommets" ont été définis, sans que vous neconnaissiez les détails de ces structures. Nous allons aussi supposer que les primitives suivantes sont àvotre disposition:

function Index(NomSommet: string; LeGraphe: Graphe): integer; { retourne un numero compris entre 1 et MaxNbSommets }

function NomSommet(IndexSommet: integer; LeGraphe: Graphe) :string; { retourne le nom du sommet dont l'index est fourni }

function NombreDeSommets(LeGraphe: Graphe): integer; {retourne le nombre de sommets effectifs composant le graphe}

function SommetsVoisins(IndexSommet: integer; LeGraphe: Graphe): SerieDeSommets; { retourne une structure permettant de retrouver l'index des voisins immédiats }

function PremierSommet(var UneSerie: SerieDeSommets): integer; { extrait le premier des sommets de la série et retourne son index }

function SommetSuivant(var UneSerie: SerieDeSommets): integer; { extrait le prochain sommet de la serie & retourne son index}

function FinDeSerie(UneSerie: SerieDeSommets): boolean; { vrai s'il n'y a plus de sommet suivant dans la serie }

En utilisant ces primitives, tout en ignorant de quelle façon la structure de graphe est implantée, écrivezune procédure "TriTopologiqueInverse(LeGraphe: Graphe)" qui imprime les sommets dugraphe dans l'ordre topologique inverse.

Solution

Exercice suivant



Exercice suivant

B-arbre


Dessinez le B-arbre résultant de la suppression de la valeur g dans le B-arbre d'ordre 1 suivant:

Solution

Exercice suivant



Exercice suivant



On dispose d'une chaîne bidirectionnelle avec des éléments contenant un nombre entier (pouvant êtrenégatif). Ecrire une procédure qui reçoive en paramètre la chaîne et un entier, puis se déplace à laposition dans la chaîne indiquée par cet entier et utilise le contenu de cette position (nombre entierpouvant être négatif) pour se déplacer à nouveau, mais cette fois de manière relative à la positioncourante. La procédure réitère ces déplacement relatifs en fonction de la nouvelle position courantejusqu'à ce qu'un déplacement la fasse sortir de la chaîne ou que l'on revienne sur un élément déjà visité.La procédure retournera alors le type d'arrêt et la position du dernier élément examiné.

Exemple:

Si l'on donne à la procédure le nombre 1, elle ira examiner le 1er élément de la chaîne, quicontient la valeur 2. Elle ira ensuite examiner la position 3 (position courante=1,déplacement relatif=2), puis la position 2 (position courante=3, déplacement relatif=-1) ets'arrêtera là car la prochaine position serait 6 et que la chaîne est de longueur 4.

N.B.: En plus de la procédure, donner les déclarations de type nécessaires pour la structure de chaîne.

Solution

Exercice suivant



exercice suivant



On veut construire un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de sorteque les chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante


En utilisant la possibilité que donne le langage Pascal d'indexer un tableau de pointeurs à l'aide d'unintervalle de caractères afin de représenter les étiquettes des arcs, donner:

a) les déclarations de types et de variables nécessaires à la construction d'un tel dictionnaire,

b) une fonction booléenne ayant pour paramètre le dictionnaire et un string et indiquant si le mot contenudans le string se trouve dans le dictionnaire,

c) une procédure imprimant touts les mots du dictionnaire dans l'ordre alphabétique.

Solution

exercice suivant



Exercice suivant

Plus courts chemins dans un graphe


En s'inspirant de la méthode de Warshall (page 157 du livre) pour déterminer la fermeture transitive d'ungraphe représenté par une matrice de connectivité, dériver un algorithme construisant une matrice devaleurs numériques indiquant la longueur du plus court chemin entre tous les divers noeuds d'un graphe.Une approche simple consiste à d'abord construire la matrice résultat à partir de la matrice deconnectivité, en mettant la valeur 1 là où il y a des arcs dans la matrice de connectivité. Puis, selon laméthode de Warshall, examiner toutes les combinaisons X->Y->Z telles qu'il existe un chemin de X versY et de Y vers Z et comparer la longueur de X->Y + Y->Z avec le contenu de la matrice résultat pour lacase (X,Z). Si la somme est plus petite, elle remplacera l'ancienne valeur de la case (X,Z). (Faites bienattention à l'initialisation de la matrice résultat!)

Solution

Exercice suivant



http://cuisung.unige.ch/std/11.3.html#Warshall

type versElement = Êlement; Element = record info : integer; suivant : versElement; end;

{ Debut est le pointeur de debut de chaine, Resultat contiendra le resultat - nil ou un pointeur vers un element de la chaine }

procedure Suppression(var Debut, Resultat : versElement);

var courant : versElement; fin : boolean;

begin fin := false; while not fin do begin if Debut = nil then begin {chaine vide} fin := true; Resultat := nil; end else if Debut^.suivant = nil then begin {un seul element} Resultat := Debut; fin := true; end else begin {on efface le premier element} courant := Debut; Debut:= Debut^.suivant; dispose(courant); if Debut^.suivant = nil then begin {il y avait 2 el} dispose(Debut); Resultat := nil; fin := true; end else begin {plus de 2 elements} courant := Debut; { on est sur qu'il n'est pas nil} while courant^.suivant^.suivant <> nil do courant := courant^.suivant; dispose(courant^.suivant); courant^.suivant:=nil; {c'est bien necessaire afin d'indiquer la fin de la chaine} end; {else/begin} end; {else/begin} end; {while}end; {Suppression}

http://cuisung.unige.ch/std/ex/7/2a.txt

http://cuisung.unige.ch/std/ex/7/2a.txt [23-09-2001 16:06:38]

{ version recursive }function Trouve(Mot: string; Dico: VersNoeud): boolean;begin { Trouve } if Dico=nil then Trouve := false else if Mot = '' then Trouve := Dico^.Complet else Trouve := Trouve(Dico^.Desc[Mot[1]], copy(Mot,2,length(Mot)-1));end; { Trouve }

{ version non-recursive }function Trouve(Mot: string; Dico: VersNoeud) : boolean;var i: integer; Courant: VersNoeud;begin { Trouve } i:=1; Courant := Dico; while (i<=Length(Mot)) and (Courant<>nil) do begin Courant := Courant^.Desc[Mot[i]]; i := i+1; end; { while } if Courant=nil then Trouve := false else Trouve := Courant^.Complet;end; { Trouve }

http://cuisung.unige.ch/std/ex/8/2e.txt

http://cuisung.unige.ch/std/ex/8/2e.txt [23-09-2001 16:07:08]

procedure ajouteElement(inNouveauContenu:integer; var inoutRacine: pElement);begin if (inoutRacine=nil)then begin creeElement_Contenu(inNouveauContenu, inoutRacine); end else begin if (inoutRacine^.mContenu < inNouveauContenu) then begin ajouteElement(inNouveauContenu,inoutRacine^.mGauche); end else begin ajouteElement(inNouveauContenu,inoutRacine^.mDroite); end; end;end; { ajouteElement }

procedure sommeArbre(var inoutSomme:integer; var inRacine: pElement);begin if (inRacine<>nil)then begin sommeArbre(inoutSomme,inRacine^.mGauche); sommeArbre(inoutSomme,inRacine^.mDroite); inoutSomme := inoutSomme + inRacine^.mContenu; end;end; { sommeArbre }

procedure produitArbre(var inoutProduit:integer; var inRacine: pElement);begin if (inRacine<>nil)then begin produitArbre(inoutProduit,inRacine^.mGauche); produitArbre(inoutProduit,inRacine^.mDroite); inoutProduit:= inoutProduit * inRacine^.mContenu; end;end; { produitArbre }

procedure accumulerArbre(var inoutAccumulateur : integer; inFonction : TFonction; var inRacine: pElement);begin if (inRacine<>nil)then begin accumulerArbre(inoutAccumulateur, inFonction, inRacine^.mGauche); inoutAccumulateur := inFonction(inRacine^.mContenu, inoutAccumulateur); accumulerArbre(inoutAccumulateur, inFonction, inRacine^.mDroite); end;end; { accumulerArbre }

http://cuisung.unige.ch/std/ex/8/1h.txt

http://cuisung.unige.ch/std/ex/8/1h.txt [23-09-2001 16:07:33]

function Chemin(MonArbre: pNoeudArbre; MaValeur: integer): PtrNoeudCh;var Courant: pNoeudArbre; DebutChaine, FinChaine: PtrNoeudCh; procedure AjouteFinChaine(UnNoeud: pNoeudArbre); var Fin: PtrNoeudCh; begin Fin := FinChaine; if DebutChaine = nil then begin new(DebutChaine); FinChaine := DebutChaine; end else begin new(FinChaine^.Suivant); FinChaine := FinChaine^.Suivant; end; with FinChaine^ do begin Element := UnNoeud; Precedent := Fin; Suivant := nil; end; { with } end; { AjouteFinChaine }begin { Chemin } if MonArbre = nil then Chemin := nil else begin Courant := MonArbre; DebutChaine := nil; FinChaine := nil; while (Courant <> nil) do begin AjouteFinChaine(Courant); if MaValeur = Courant^.Valeur then Courant := nil else if MaValeur < Courant^.Valeur then Courant := Courant^.Gauche else Courant := Courant^.Droite; end; { while } Chemin := DebutChaine; end; { if }end; { Chemin }

http://cuisung.unige.ch/std/ex/8/1g.txt

http://cuisung.unige.ch/std/ex/8/1g.txt [23-09-2001 16:08:03]

La valeur 25 devrait normalement venir dans la deuxième feuille à partir de la gauche. La page en question étantpleine, on examine les pages adjacentes pour voir s'il y a de la place pour opérer une "roccade". En l'occurrence, lavoisine de droite a une place libre. La valeur 40, de la page parente, va donc occuper cette place libre et estremplacée par la valeur 30, qui est la plus grande valeur de la page devant subir l'insertion. La feuille qui contenaitla valeur 30 a maintenant une place libre permettant d'accueillir la valeur 25.

.

mécanisme similaire pour l'insertion de la valeur 20.b.

La valeur 14 devrait normalement venir dans la feuille qui se trouve à l'extrème gauche. La page en question étantpleine et sa voisine aussi, il faut scinder la page en deux et insérer l'élément milieu (9) dans la page parente

c.

La valeur 6 devrait normalement venir dans la feuille qui se trouve à l'extrème gauche. La page en question étantpleine et sa voisine aussi, il faut scinder la page en deux et insérer l'élément milieu (6) dans la page parente. C'estdonc la nouvelle valeur qui vient s'insérer dans la page parente.

d.

Pour supprimer la valeur 60, il faut la remplacer par la plus grande valeur du sous-arbre gauche ou la plus petitevaleur du sous-arbre droit. Ici, nous avons choisi la valeur 51 (plus grande valeur du sous-arbre gauche). La feuillequi contenait la valeur 51 a encore 2 éléments, ce qui est suffisant pour ne pas nécessiter plus d'opérations.

e.

solution de l'execrcice

http://cuisung.unige.ch/std/ex/14/3h.sol.html (1 of 3) [23-09-2001 16:09:52]

Par contre, si nous choisissons de remplacer la valeur 60 par la plus petite valeur du sous-arbre droit (63), la feuillecontenant 63 tombera en dessous du seuil minimum (il ne restera que la valeur 70). Comme sa voisine de droite estau seuil minimum, on ne peut pas lui emprunter d'élément. Il faut donc combiner la page ne contenant plus que 70avec sa voisine de droite contenant 76 et 79, en absorbant au passage la valeur de la page parente (75) qui se trouveentre les deux pages à combiner. On obtient ainsi une page contenant 70, 75, 76 et 79. Mais la page parente necontient plus que la valeur 80. Sa voisine de gauche étant au seuil minimum (valeurs 15 et 40), il faut combiner lesdeux pages en absorbant la valeur de la page parente (63) qui se trouve entre elles. On obtient ainsi une pagecontenant 15, 40, 63 et 80. L'autre page, maintenant vide, peut être supprimée, ainsi que la page racine qui, elleaussi, est maintenant vide.

La page contenant la valeur 63 étant déjà à son seuil minimum, la suppression de la valeur 63 implique soit derééquilibrer en empruntant une valeur d'une page voisine (ayant même page parente) si une de celles-ci a assezd'éléments, ou en la recombinant avec une page voisine sinon. En l'occurrence, la page voisine de droite est elleaussi au seuil minimum. Il faut donc recombiner les deux pages en une en absorbant par la même occasionl'élément (75) qui se trouvait dans la page parente, entre les deux pages à combiner. On a donc une page quicontient les valeurs 70, 75, 76 et 79. Mais la page parente est maintenant au-dessous du seuil minimum (elle necontient que la valeur 80) et l'on doit donc soit emprunter une valeur à une des pages adjacentes (il n'y en a qu'une,qui contient 15 et 40), soit combiner la page (80) avec sa voisine (15, 40) tout en absorbant l'élément de la pageau-dessus (60) qui se trouvait entre les deux pages en question. On obtient ainsi une page contenant 15, 40, 60 et80. L'autre page, maintenant vide, peut être supprimée, ainsi que la page racine qui, elle aussi, est maintenant vide.

f.

La suppression de la valeur 80 se fait en la remplaçant par la plus grande valeur du sous-arbre gauche (79) ou laplus petite valeur du sous-arbre droit (85). Si l'on prend la valeur 79, la page qui contenait cette valeur initialementva tomber en dessous du seuil minimum (elle ne contient plus que 76). Comme on ne peut pas emprunter unevaleur d'une page voisine, il faut combiner la page ne contenant plus que 76 avec une de ses voisines. Si l'on prendla voisine de droite (contenant 85 et 90) et que l'on absorbe la valeur qui se trouve entre ces deux pages dans lapage parente (79), on obtient une page contenant 76, 79, 85 et 90. Mais la page parent ne contient plus que lavaleur 75 et se trouve donc en dessous du seuil minimum. Comme cette page n'a pas de voisine à laquelleemprunter de valeur, il faut la combiner avec sa voisine (contenant 15 et 40) en absorbant la valeur de la pageparente qui se trouve entre elles (60). On obtient donc une page contenant 15, 40, 60 et 75. La page racine devientvide et peut être supprimée.

g.



Si l'on avait échangé la valeur 80 par la valeur 85 (plus petite valeur du sous-arbre droit), on aurait quand mêmeabouti au même résultat.



On peut soit parcourir l'arbre dans l'ordre Droite-Racine-Gauche et faire des insertions en debut de chaine, soit parcourirl'arbre en ordre et faire des insertions en fin de chaine.La solution qui suit correspond a la premiere approche:

function Conversion(Arbre: pNoeudArbre): PtrNoeudCh;var Res: PtrNoeudCh; procedure ParcoursEnOrdreInverse(P: pNoeudArbre); var Tmp: PtrNoeudCh; begin { ParcoursEnOrdreInverse } if P <> nil then begin ParcoursEnOrdreInverse(P^.droite); new(Tmp); with Tmp^ do begin Donnee := P^.nombre; Precedent := nil; Suivant := Res; end; { with } if Res<> nil then Res^.Precedent := Tmp; Res := Tmp; ParcoursEnOrdreInverse(P^.gauche); end; { if } end; { ParcoursEnOrdreInverse }begin Res := nil; ParcoursEnOrdreInverse(Arbre); Conversion := Res;end; { Conversion }

http://cuisung.unige.ch/std/ex/8/1f.txt

http://cuisung.unige.ch/std/ex/8/1f.txt [23-09-2001 16:10:14]

La première solution consiste à représenter le document XML comme un vrai arbre multiple, où la racinede l'arbre représente l'élément principal du document XML et chaque sous-arbre représente un élémentdirectement imbriqué dans l'élément principal du document XML:

Cette structure d'arbre multiple peut aussi être représentée comme un arbre binaire avec un pointeur filspointant sur le premier sous-élément et un pointeur frère pointant d'un descendant vers un autredescendant du même ancêtre immédiat:

solution de l'exercice

http://cuisung.unige.ch/std/ex/8/2d.sol.html [23-09-2001 16:10:54]

procedure display(inPair : PSchemePairOuValeur);{vous etes autorise(es) de mettre des variables ici}begin if(inPair<>nil)then begin if(inPair^.mEstValeur)then begin write(inPair^.mValeur); end else begin write('(');

display(inPair^.mCar); write(' . ');

display(inPair^.mCdr);

write(')'); end; end else begin write( '()' ); end;end;

http://cuisung.unige.ch/std/ex/9/1b.txt

http://cuisung.unige.ch/std/ex/9/1b.txt [23-09-2001 16:11:21]

La fermeture transitive est l'opération qui consiste à ajouter un arc entre toute paire de noeuds pourlaquelle il existe un chemin du premier noeud vers le deuxième. Il ne faut bien entendu pas oublierd'ajouter un arc d'un noeud vers lui-même s'il existe un chemin simple qui part de ce noeud pour yrevenir (comme dans l'exemple b).

Structuration des Données Informatiques - 11.3, solution exercice 4

http://cuisung.unige.ch/std/ex/11/3d.sol.html [23-09-2001 16:12:15]

{ Parcourir et afficher a l'ecran }procedure parcourirBArbreEnOrdre(inArbre : PPage );var i : integer;begin { parcourirBArbreEnOrdre } if (inArbre<>nil)then begin if (inArbre^.mPremierEnfant <> nil)then begin parcourirBArbreEnOrdre(inArbre^.mPremierEnfant); end; for i:=1 to inArbre^.mNombreEnfants do begin

write(inArbre^.mElement[i].mCle); write(' '); if (inArbre^.mElement[i].mEnfant <> nil)then begin parcourirBArbreEnOrdre(inArbre^.mElement[i].mEnfant); end; { if } end; { for } end; { if }end; { parcourirBArbreEnOrdre }

{ Parcourirr EN ORDRE INVERSE et afficher a l'ecran }procedure parcourirBArbreEnOrdreInverse(inArbre : PPage );var i : integer;begin { parcourirBArbreEnOrdreInverse } if (inArbre<>nil)then begin for i:=inArbre^.mNombreEnfants to 1 do begin if (inArbre^.mElement[i].mEnfant <> nil)then begin parcourirBArbreEnOrdreInverse(inArbre^.mElement[i].mEnfant); end; { if } write(inArbre^.mElement[i].mCle); write(' '); end; { for } if (inArbre^.mPremierEnfant <> nil)then begin parcourirBArbreEnOrdreInverse(inArbre^.mPremierEnfant); end; { if } end; { if }end; { parcourirBArbreEnOrdreInverse }

http://cui.unige.ch/eao/www/std/ex/14/3f.txt

http://cui.unige.ch/eao/www/std/ex/14/3f.txt [23-09-2001 16:13:21]

{

Cette fonction prend la chaine inChaine et retourne une nouvelle chaine, qui contient les memes valeurs que inChaine, mais en ordre inverse: Si inChaine est (1 2 3) le resultat va etre la chaine (3 2 1).

AUCUNE VALEUR QUI APPARTIENT A INCHAINE NE DOIT ETRE MODIFIE }function creeChaineInversee(inChaine:PElement):PElement;

var lRoot : PElement; lNouveau : PElement; lIterator : PElement;

begin

lRoot:=nil; lIterator:=inChaine;

while(lIterator<>nil) do begin

new(lNouveau); lNouveau^.mContenu:=lIterator^.mContenu;

{ N.B.: Ca marche pour le premier element de la nouvelle liste aussi. }

lNouveau^.mSuivant:=lRoot; lRoot:=lNouveau;

lIterator:=lIterator^.mSuivant; end; { while }

creeChaineInversee:=lRoot; end; { creeChaineInversee }



Solution de Wolfgang Mueller:question concernant cette solution:

lors de l'appel initial à la fonction, que doit valoir le deuxième paramêtre?●

function verifieArbre(inRacine: PNoeud; var inoutDerniereVisitee:integer):boolean;var lReturnValue : boolean;begin if(inRacine=nil)then begin { un arbre vide est un arbre de tri valide } return true; end else begin {verifie qu'a gauche c'est bien trie} lReturnValue:=verifieArbre(inRacine^.mLeft, inoutDerniereVisitee);

{ verifie que la valeur de la racine courante est plus grande que celle du dernier noeud parcouru }

lReturnValue:= lReturnValue and (inoutDerniereVisitee <= inRacine^.mValue);

{ maintenant la valeur de la racine courante est la derniere visitee }

inoutDerniereVisitee:= inRacine^.mValue;

{ verifie qu'a droite c'est bien trie }

lReturnValue:=lReturnValue and verifieArbre(inRacine^.mRight, inoutDerniereVisitee); verifieArbre := lReturnValue; end; (* if else *)end; (* verifieArbre *)

Solution de Bertrand Ibrahim:function verifieArbre(Racine: PNoeud):boolean;(* effectue un parcours en-ordre et verifie, a chaque valeur traitee, qu'elle est bien superieure a la derniere valeur traitee jusqu'a present. Arrete la verification des qu'une erreur est trouvee.*)var Ok: boolean; LastVal: integer; (* derniere valeur traitee, modifiee par effet de bord *) procedure Parcours(P: PNoeud); (* accede a la variable LastVal par effet de bord *) begin if (P<>nil) and Ok then begin

Structuration des Données Informatiques - 8.1, exercice 5, solution

http://cuisung.unige.ch/std/ex/8/1eSol.html (1 of 2) [23-09-2001 16:15:13]

Parcours(P^.gauche); if LastVal > P^.nombre then Ok := false else LastVal := P^.nombre Parcours(P^.droite); end; (* Parcours *)

begin Ok:= true; LastVal:= -MaxInt; Parcours(Racine); return Ok;end; (* verifieArbre *)

Structuration des Données Informatiques - 8.1, exercice 5, solution

http://cuisung.unige.ch/std/ex/8/1eSol.html (2 of 2) [23-09-2001 16:15:13]

procedure Tri(var Anneau: VersAnneau);var P1, P2, Dernier, Pred, Suiv, NextInnerStep, NextOuterStep: VersAnneau;begin (* Tri *) if Anneau <> nil then if Anneau <> Anneau^.Suivant then begin (* anneau a au moins 2 elem. *) Dernier := Anneau^.Precedent; if Dernier = Anneau^.Suivant then begin (* que 2 elem. au total *) if P1^.Info > P2^.Info then Anneau := Dernier; end else begin (* l'anneau a au moins 3 elem. *) P1 := Anneau; while P1 <> Dernier do begin NextOuterStep := P1^.Suivant; P2 := NextOuterStep; while P2 <> Anneau do begin NextInnerStep := P2^.Suivant; if P1^.Info > P2^.Info then begin if P1^.Suivant = P2 then (* permute deux elem. adjascents *) with P1^ do begin Pred := Precedent; Suiv := P2^.Suivant; Precedent := P2; Suivant := Suiv; Pred^.Suivant := P2; P2^.Precedent := Pred; P2^.Suivant := P1; Suiv^.Precedent := P1; end (* with *) else if P1^.Precedent = P2 then (* perm. premier et dernier *) with P1^ do begin Pred := P2^.Precedent; Suiv := P1^.Suivant; Precedent := Pred; Suivant := P2; Suiv^.Precedent := P2; Pred^.Suivant := P1; P2^.Precedent := P1; P2^.Suivant := Suiv; end (* with *) else with P1^ do begin (* perm. 2 el. separes par au moins 1 el *) Pred := Precedent; Suiv := Suivant; Precedent := P2^.Precedent; Suivant := P2^.Suivant; Pred^.Suivant := P2; Suiv^.Precedent := P2; P2^.Precedent := Pred; P2^.Suivant := Suiv; Pred := Precedent; Suiv := Suivant; Pred^.Suivant := P1; Suiv^.Precedent := P1; end; (* with *) if Anneau = P1 then Anneau := P2; P2 := NextInnerStep; end; (* while P2 *) P1 := NextOuterStep; end; (* while P1 *) end; (* if *) end; (* if *)end; (* Tri *)

http://cui.unige.ch/eao/www/std/ex/7/4j.txt

http://cui.unige.ch/eao/www/std/ex/7/4j.txt [23-09-2001 16:16:25]

1.

2.

solution, 8.3 exercice 2

http://cui.unige.ch/eao/www/std/ex/8/3b.sol.html [23-09-2001 16:16:54]

procedure InsereFin(var Anneau: PtrNoeud; LaDonnee: integer);var Nouveau: PtrNoeud;begin if Anneau = nil then begin new(Anneau); with Anneau^ do begin Preced:= Anneau; Suivant:= Anneau; Donnee:= LaDonnee; end; (* with *) end (* then *) else begin new(Nouveau); with Nouveau^ do begin Donnee:= LaDonnee; Suivant:= Anneau; Preced:= Anneau^.Preced; Anneau^.Preced^.Suivant := Nouveau; Anneau^.Preced := Nouveau; end; (* with *) end; (* if *)end; (* InsereFin *)

function NbElem(Anneau: PtrNoeud): integer;var Courant: PtrNoeud; Nb: integer;begin if Anneau = nil then NbElem := 0 else begin Courant := Anneau^.Suivant; Nb := 1; while Courant <> Anneau do begin Courant := Courant^.Suivant; Nb := succ(Nb); end; (* while *) NbElem := Nb; end; (* if *)end; (* NbElem *)

procedure Split(Ring: PtrNoeud; Data: integer; var LowerRing, HigherRing: PtrNoeud);var Courant: PtrNoeud;begin LowerRing := nil; HigherRing := nil; if Ring <> nil then begin Courant := Ring; repeat if Courant^.Donnee < Data then InsereFin(LowerRing, Courant^.Donnee) else InsereFin(HigherRing, Courant^.Donnee); Courant := Courant^.Suivant; until Courant=Ring; end; (* if *)end; (* Split *)

http://cuisung.unige.ch/std/ex/7/4i.txt

http://cuisung.unige.ch/std/ex/7/4i.txt [23-09-2001 16:17:45]

1)

Arbre('-', Arbre('*', Feuille('5'), Arbre('-', Feuille('4'), Arbre('+', Feuille('3'), Arbre('-', nil, Arbre('-', nil, Feuille('2') ) ) ) ) ), Arbre('/', Arbre('-', Feuille('1'), Feuille('9') ), Arbre('+', nil, Arbre('*', Feuille('8'), Feuille('7') ) ) ) )

2)

function Feuille(Contenu: integer): integer;begin Feuille := Contenu;end; (* Feuille *)

function Arbre(ContenuRacine: char; Gauche, Droit: integer): integer;(* Dans ce cas, il faut remplacer dans l'expression 1) les "nil" par des "0" *)begin case ContenuRacine of '+': Arbre := Gauche + Droit; '-': Arbre := Gauche - Droit; '*': Arbre := Gauche * Droit; '/': Arbre := Gauche div Droit; end; (* case *)end; (* arbre *)

http://cuisung.unige.ch/std/ex/8/1d.txt

http://cuisung.unige.ch/std/ex/8/1d.txt [23-09-2001 16:18:07]

function Inverse(Ring: VersAnneau): VersAnneau;var Fin, { sert a memoriser la fin de l'anneau resultant } Courant, { sert a parcourir l'anneau d'entree } Invers: VersAnneau; { pointeur debut de l'anneau resultant }begin if Ring=nil then Inverse:=nil { si l'anneau est vide, le resultat est vide } else begin new(Fin); { cree l'element qui sera a la fin de l'anneau resultant } Fin^.Info := Ring^.Info; { y copie l'info du ler elt. de l'anneau d'entree } Invers := Fin; { le pointeur debut pointe sur l'elt que l'on vient de creer} Courant := Ring^.Suivant; { on va parcourir le reste de l'anneau d'entree } while Courant<>Ring do begin {boucle tant qu'on n'est pas revenu au 1er elt} new(Tmp); { cree un nouvel element } with Tmp^ do begin Info := Courant^.Info; { y copie l'info de l'element courant } Suivant := Invers; { fait une insertion debut dans l'anneau } Suivant^.Precedent := Tmp; { resultant sans se preoccuper de fermer } end; { with } { l'anneau a chaque fois } Invers := Tmp; Courant := Courant^.Suivant; end; { while } Fin^.Suivant := Invers; { reste a ferme l'anneau en reliant le premier } Invers^.Precedent := Fin;{ element au dernier, dans les deux sens } Inverse:= Invers; end; { if }end; { Inverse }

function estInverse(Ring1, Ring2: VersAnneau): boolean;var Different: boolean; Cur1, Cur2: VersAnneau;begin if Ring1=nil then estInverse := Ring2=nil else if Ring2=nil then estInverse := false else begin Cur1 := Ring1; Cur2 := Ring2^.Precedent; repeat Different := Cur1^.Info<>Cur2^.Info; Cur1 := Cur1^.Suivant; Cur2 := Cur2^.Precedent; until Different or (Cur1=Ring1) or (Cur2=Ring2); estInverse := not Different and (Cur1=Ring1) and (Cur2=Ring2); end; { if }end; { estInverse }

http://cuisung.unige.ch/std/ex/7/4h.txt

http://cuisung.unige.ch/std/ex/7/4h.txt [23-09-2001 16:19:11]

Le chemin le plus courtSolution pour la question posée à l'examen écrit le 30.6.1999

étapecontenu du FIFO

en notation SchemeL1

1 () non défini

2 ((1)) non défini

3 () (1)

4 () (1)

5 ((2 1) (4 1)) (1)

3 ((4 1)) (2 1)

4 ((4 1)) (2 1)

5 ((4 1) (5 2 1)) (2 1)

3 ((5 2 1)) (4 1)

4 ((5 2 1)) (4 1)

5 ((5 2 1) (7 4 1)) (4 1)

3 ((7 4 1)) (5 2 1)

4 ((7 4 1)) (5 2 1)

5 ((7 4 1) (6 5 2 1)) (5 2 1)

3 ((6 5 2 1)) (7 4 1)

4 ((6 5 2 1)) (7 4 1)

5 ((6 5 2 1)) (5 2 1)

3 () (6 5 2 1)

4 (TROUVE) () (6 5 2 1)

Le chemin le plus court est:

1 2 5 6

Wolfgang Müller Last modified: Thu Aug 19 00:11:24 MEST 1999

Le chemin le plus court/Examen 30.6.1999

http://cuisung.unige.ch/std/ex/11/a_solution.html [23-09-2001 16:19:43]

mailto:[email protected]

Les parties importantes du code à réaliser sont:

Initialisation des coefficients (1 pt)1.

Parcours de l'espace des solutions (6 pts)2.

Fonction vérifiant si les coefficients trouvés produisent un H-code parfait (3 pts)3.

Boucle principale, testant toutes les solutions, minimisant la taille (2 pts)4.

1) procedure initialiseCoefficients; var i : integer; begin for i = 1 to LongueurMax do Coeff[i] := 0; end;

2) function incrementeCoefficients : boolean; begin while ( index < LongueurMax AND Coeff[index] = MaxCoeff ) do begin Coeff[index] := 0; index := index + 1; end; {while} if ( index > LongueurMax ) then begin incrementeCoefficients := false; else begin Coeff[index] := Coeff[index] + 1; index := 0; end; {if} end; {function}

3) function estParfaite : boolean; var i : integer, code : integer; begin for i = 1 to MaxIndice do tab[i] := false; for i = 1 to NbMots do begin code := H(Vocabulaire[i]); if ( tab[code] = true ) then begin estParfaite := false; exit function; end tab[code] := true; end; {for} end; {function}

4)begin for Taille = NbMots to TailleMax do begin initialiseCoefficients; while incCoeffs do if estParfaite then exit procedure; end; {while}

.

13.4 exercice 3, solution

http://cuisung.unige.ch/std/ex/13/4c.sol.html (1 of 2) [23-09-2001 16:20:13]

end; {for} { si on arrive la, aucune fonction parfaite n'a été trouvée. }end. {procedure chercheCoefficients}

Les parties importantes du code a réaliser sont:

Comparaison des probabilités du mot à insérer et du mot se trouvant déjà dans la table (1 pt)1.

Remplacement du mot dans la table par le nouveau mot (si sa prob est supérieure) (1 pt)2.

Insertion du mot qui vient d'être remplacé (1 pt)3.

function Insert( X : string ) : integer;var H0, hi : integer; temp : string;begin H0 := H(X); hi := H0; while ( T[hi] <> '' ) and ( T[hi] <> X ) do begin------------------------------------------------------1) if ( P(X) > P(T[hi]) ) then begin

2) temp := T[hi]; T[hi] := X;

{ solution 1 : simplement rappeler la fonction insert ... }

3a) Insert( temp );

{ solution 2 : trouver la nouvelle valeur de hi et continuer... mais comme les collisions sont traitées de façon linéaire, cette partie est inutile dans ce cas. }3b) X = temp;

else begin--------------------------------------------------------------------- hi := (hi+1) mod MaxElements; if hi = H0 then begin writeln('tableau plein'); exit(program); end; end; end; if T[Hi] = '' then T[Hi] := X; Insert := hi;end;

b.

13.4 exercice 3, solution


(question)

Si l'on adopte la convention que x->y signifie "x est plus jeune que y", on obtient le graphesuivant:

Si l'on adopte la convention que x->y signifie "x est plus vieux/vieille que y", on obtient le graphesuivant:

.

Arc:ligne vers colonne

=est plus jeune que

Alice

André

Claude

Jean

Jeanne

Jacques

Marie

Paul

Pierre

Yves

Alice F F F F F F F F V V

André F F V F F F F F V F

Claude F F F F F F F F V V

Jean F F F F F F F V V F

Jeanne F F F V F F F F F F

Jacques F F F F V F F F V F

Marie F F F F F V F F F F

b.

Structuration des Donn es Informatiques - 11.3, solution ex. 3


Paul F F F F F F F F F F

Pierre F F F F F F F V F F

Yves F F F F F F F V F F

avec cette même matrice, on pourrait considérer que les arcs vont de la colonne vers la ligne etsignifient "est plus vieux que"

Arc:ligne vers colonne

=est plus jeune que

Alice

André

Claude

Jean

Jeanne

Jacques

Marie

Paul

Pierre

Yves

Alice F F F F F F F V V V

André F F V F F F F V V V

Claude F F F F F F F V V V

Jean F F F F F F F V V F

Jeanne F F F V F F F V V F

Jacques F F F V V F F V V F

Marie F F F V V V F V V F

Paul F F F F F F F F F F

Pierre F F F F F F F V F F

Yves F F F F F F F V F F

Cette fermeture transitive permet de facilement trouver qui est certainement plus jeune ou plusvieux qu'une personne donnée. Pour trouver qui est certainement plus vieux que X, il suffit deregarder la ligne contenant X et chercher les colonnes où il y a un "V". Pour trouver qui estcertainement plus jeune que X, il suffit de regarder la colonne contenant X et chercher les lignescontenant un "V"

On ne peut par contre pas dire qui est lel plus vieux ou le plus jeune, car nous ne sommes pas enprésence d'une relation d'ordre totale et il n'y a peut-être aucun moyen de dire qui est le plus vieux(la plus vielle) ou le (la) plus jeune. En l'occurrence, Alice, André et Marie sont les trois plusjeunes, mais on ne peut rien dire sur leurs ages respectifs.

c.

Marie, Alice, André, Jacques, Claude, Yves, Jeanne, Jean, Pierre, Paul. D'autres possibilitésconsisteraient à permuter Alice, Marie et André (toutes les permutations sont possibles puisqu'iln'y a aucune relation directe entre eux).

d.



(question)

Insertion de 1, puis de 2:

1 - 1 2

Insertion de 3, puis de 6, puis de 7:

2

1 3 -

2

1 3 6 -

3

1 2 6 7

Insertion de 4, puis de 5:

3 6

1 2 4 7 -

3 6

1 2 4 5 7

Insertion de 8:

3 6

1 2 4 5 7 8

Insertion de 9:

6

3 8

1 2 4 5 7 9

.

Si chaque page occupe 512 octets et qu'une page contient au minimum 1 donnée et au maximum 2données (b-arbre d'ordre 1), le cas le plus défavorable est quand toutes les pages ne contiennentqu'une donnée chacune et le cas le plus favorable est lorsque toutes les pages contiennent deuxdonnées chacune. L'espace utilisé est respectivement:

10'000 données et 1 donnée/page => 10'000 pages = 10'000*512 octets❍

10'000 données et 2 données/page => 5'000 pages = 5'000*512 octets❍

b.

Quand les pages sont pleines, les différents niveaux contiennent:

niveau nb. pages du niveau nb. pages cumulés

1 1 1

2 3 4

3 9 13

4 27 40

c.


http://cuisung.unige.ch/std/ex/14/3d.sol.html (1 of 2) [23-09-2001 16:21:50]

5 81 121

6 243 364

7 729 1093

8 2187 3280

9 6561 9841

Quand les pages ne sont qu'à moitié pleines, les différents niveaux contiennent:

niveau nb. pages du niveau nb. pages cumulés

1 1 1

2 2 3

3 4 7

4 8 15

5 16 31

6 32 63

7 64 127

8 128 255

9 256 511

10 512 1'023

11 1024 2'047

12 2048 4'095

13 4096 8'191

14 8192 16'383

On voit donc qu'il faut au minimum 9 niveaux pour avoir 5'000 pages pleines et au plus 14 niveauxpour avoir 10'000 pages à moitié pleines


http://cuisung.unige.ch/std/ex/14/3d.sol.html (2 of 2) [23-09-2001 16:21:50]

(question)

Pour le tableau ci-dessous, on a supposé que la position initiale d'un mot est calculée comme étantH0(K)=(H(K) mod 15)+1

indice contenu Nb.collisions positions examinées

1 lumiere 0 1

2 soudaine 1 9, 2

3 une 0 3

4 etait 0 4

5 traversa 3 11, 4, 12, 5

6 qu 0 6

7 du 0 7

8 la 0 8

9 si 1 7, 9

10 illumination 0 10

11 jour 0 11

12 son 2 6, 9, 12

13 forte 0 13

14 esprit 0 14

15

Structuration des Donn es Informatiques - 13.4, solution exercice 2

http://cuisung.unige.ch/std/ex/13/4b.sol.html [23-09-2001 16:22:27]

program Lexico;


var Dico: VersNoeud; Longueur: integer;

function Lecture(NomFichier: string): VersNoeud;var F: text; Status: integer32; i: integer; l: char; Mot: string; Rac, P: VersNoeud;begin (* Lecture *) new(Rac); open(F, NomFichier,'old', Status); if Status <> 0 then begin writeln('probleme pour ouvrir le fichier'); halt; end; reset(F); while not eof(F) do begin Read(F,Mot); P:= Rac; (* for i := 1 to length(Mot) do begin *) i := 1; while Mot[i]<> ' ' do begin if P^.Desc[Mot[i]] = nil then begin new(P^.Desc[Mot[i]]); with P^.Desc[Mot[i]]^ do begin Complet := false; for l:='a' to 'z' do Desc[l] := nil; end; (* with *) end; (* if *) P:= P^.Desc[Mot[i]]; i:= i+1; end; (* while *) P^.Complet := true; readln(F); end; (* while not eof *) Lecture := Rac;end; (* Lecture *)

function NbMots(Longueur: integer; Dico: VersNoeud):integer;var Nb: integer;

procedure Parcours1Niveau(Rac: VersNoeud; NiveauxRestants: integer); var Reste: integer; l: char; begin (* Parcours1Niveau *) if Rac <> nil then if NiveauxRestants = 0 then begin if Rac^.Complet then Nb := succ(Nb) end else begin if NiveauxRestants = -1 then begin Reste := NiveauxRestants;


http://cuisung.unige.ch/std/ex/8/2c.txt (1 of 2) [23-09-2001 16:23:02]

if Rac^.Complet then Nb := succ(Nb) end else Reste := pred(NiveauxRestants); for l := 'a' to 'z' do if Rac^.Desc[l] <> nil then Parcours1Niveau(Rac^.Desc[l], Reste); end; (* else *) end; (* Parcours1Niveau *)

begin (* NbMots *) Nb := 0; if Longueur = 0 then Parcours1Niveau(Dico, -1) else Parcours1Niveau(Dico, Longueur); NbMots := Nb;end; (* NbMots *)

begin (* Dico := PseudoLecture; *) readln(Longueur); Dico := Lecture('990229.dat'); writeln('Nb. mots de longueur', Longueur, '=', NbMots(Longueur,Dico));end.


http://cuisung.unige.ch/std/ex/8/2c.txt (2 of 2) [23-09-2001 16:23:02]

procedure TriTopoInverse(LeGraphe: Graphe);

const MaxNbSommets=20;

var i, CmptrVisite, IndexSommet : 0..MaxNbSommets;

NumDOrdre : array[1..MaxNbSommets] of integer; Parcouru:array[1..MaxNbSommets] of boolean;

NbSommets: integer;

procedure Visite (IndexSommet : integer);var AutreSommet : integer; Voisins: SerieDeSommets;begin CmptrVisite := CmptrVisite + 1; NumDOrdre[IndexSommet] := CmptrVisite; Parcouru[IndexSommet] := true; Voisins := SommetsVoisins(IndexSommet, LeGraphe); while not FinDeSerie(Voisins) do begin AutreSommet := ExtraitSommet(Voisins); if Parcouru[AutreSommet] then writeln(NomSommet(AutreSommet,LeGraphe), ' fait partie d''un cycle') else if NumDOrdre[AutreSommet] = 0 then Visite (AutreSommet); end; { while } Parcouru[IndexSommet] := false; write(NomSommet(IndexSommet,LeGraphe));end; { Visite }

begin { TriTopoInverse } NbSommets := NombreDeSommets(LeGraphe); CmptrVisite := 0; for IndexSommet := 1 to NbSommets do NumDOrdre[IndexSommet]:=0; for IndexSommet := 1 to NbSommets do if NumDOrdre[IndexSommet]=0 then begin for i := 1 to NbSommets do Parcouru[i] := false; Visite (IndexSommet); end; { if }end; { TriTopoInverse }



Nous allons considérer deux cas, suivant que l'on considère qu'une page ne contient que les données etles pointeurs vers les pages descendantes ou que l'on compte, en plus, un compteur indiquant le nombreeffectif de données dans la page

Cas où une page ne contient pas de compteurPuisqu'il y a un pointeur de plus que de données, le nombre de données par page est:

(1024-4) div (47+4) = 20

l'ordre du B-arbre est donc de 10 et nous arondissons celui du B*-arbre à 14.

.

Pour le B-arbre:La page racine peut contenir au minimum 1 donnée, reste 999'999 données à répartir auminimum 10 par page. Le nombre total de pages, quand celles-ci sont remplies au minimumest:

1+(999'999 div 10) = 100'000 pages (soit 100'000 KiloOctets)

❍

Si toutes les pages sont entièrement remplies, le nombre total de pages est:

1'000'000 div 20 = 50'000 pages (soit 50'000 KiloOctets)

❍

Pour le B*-arbre:La page racine peut contenir au minimum 1 donnée, reste 999'999 données à répartir auminimum 14 par page. Le nombre total de pages, quand celles-ci sont remplies au minimumest:

1+(999'999 div 14) = 71'429 pages (soit 71'429 KiloOctets)

❍

Si toutes les pages sont entièrement remplies, le nombre total de pages est le même que pourle B-arbre, soit 50'000 pages.

❍

b.

Pour le B-arbre:Quand les pages sont remplies au minimum, les niveaux successifs contiennent le nombrede pages suivant:

1, 2, 22, 242, 2662, 29'282, 322'102

Il faut donc au moins 7 niveaux pour arriver à un total de 100'000 pages

❍

Quand les pages sont remplies au maximum, les niveaux successifs contiennent le nombrede pages suivant:

1, 21, 441, 9'261, 194'481


❍

Pour le B*-arbre:Quand les pages sont remplies au minimum, les niveaux successifs contiennent le nombrede pages suivant:

1, 2, 30, 450, 6'750, 101'250


❍

c.

Structuration des Données Informatiques - 14.3, solution 3


Quand les pages sont remplies au maximum, le nombre de niveaux est le même que pour leB-arbre, soit 5 niveaux.

❍

Cas où une page contient un compteur.



la constrution est très similaire à celle d'un arbre binaire de tri, si ce n'est qu'à chaque fois qu'unnoeud n'a pas de descendant droit, son pointeur droit pointe vers l'ancêtre dont le contenu estimmédiatement supérieur au contenu du noeud courant, selon l'ordre de tri:

.

la suppression se fait de manière similaire à un arbre de tri: si l'élément à détruire a deuxdescendants, on échange le contenu du noeud à détruire avec celui du noeud le plus à droite de sonsous-arbre gauche (ou le plus à gauche de son sous-arbre droit), puis l'on détruit ce dernier:

b.

solution de l'exercice 1, section 8.3

http://cuisung.unige.ch/std/ex/8/3a.sol.html [23-09-2001 16:25:42]

procedure AjouteRegle(Table:TableDecision;R:integer;var NewTable:TableDecision);{ AjouteRegle insere la regle R de la table "Table" dans la table "NewTable" en supprimant la premiere condition }var c: integer;begin {AjouteRegle} NewTable.NbRegles := succ(NewTable.NbRegles); for c:=2 to Table.NbConditions do NewTable.ValCond[NewTable.NbRegles,c-1] := Table[R,c];end; {AjouteRegle}

function ConstruitArbre(Table: TableDecision): PtrNoeud;var NewTable: TableDecision; P: PtrNoeud;begin { ConstruitArbre } { si la table n'a pas de conditions, l'arbre sera vide } if Table.NbConditions <= 0 then ConstruitArbre := nil else begin { on va traiter la 1ere condition } new(P); with P^ do begin Feuille := false; TxtCond := Table.TxtConditions[1]; Vrai := nil; Faux := nil; end; {with} { si la table n'a qu'une seule condition, on cree directement les noeuds descendants (il ne devrait rester qu'au plus 2 regles dans la table) } if Table.NbConditions = 1 then begin for R := 1 to Table.NbRegles do if Table.ValCond[R,1] <> Faux then begin new(P^.Vrai); with P^.Vrai^ do begin Feuille := true; for a := 1 to Table.NbActions do Actions[a] := Table.Agir[R,a]; end; {with} end; if Table.ValCond[R,1] <> Vrai then begin new(P^.Faux); with P^.Faux^ do begin Feuille := true; for a := 1 to Table.NbActions do Actions[a] := Table.Agir[R,a]; end; {with} end end else begin { si la table a plus qu'une condition, on va creer deux sous-tables avec chacune une condition de moins que la table courante } NewTable.NbConditions := pred(Table.NbConditions); (* on construit la sous-table pour le cas ou la condition 1 est fausse *) NewTable.NbRegles := 0; for R := 1 to Table.NbRegles do if Table.ValCond[R,1] <> Vrai then AjouteRegle(Table, R, NewTable); { on appelle recursivement ConstruitArbre pour traiter cette sous-table } P^.Faux := ConstruitArbre(NewTable); (* on construit la sous-table pour le cas ou la condition 1 est vrai *) NewTable.NbRegles := 0; for R := 1 to Table.NbRegles do if Table.ValCond[R,1] <> Faux then AjouteRegle(Table, R, NewTable); { on appelle recursivement ConstruitArbre pour traiter cette sous-table } P^.Vrai := ConstruitArbre(NewTable); end


http://cuisung.unige.ch/std/ex/15/1b.txt (1 of 2) [23-09-2001 16:27:44]

end;end; { ConstruitArbre }


http://cuisung.unige.ch/std/ex/15/1b.txt (2 of 2) [23-09-2001 16:27:44]

Ce qui suit est basé sur l'hypothèse que les blocs de données ne contiennent pas de référence à un blocde débordement

1.a)

Si les blocs de données ne contiennent pas de référence à un bloc de débordement, le plus petitmultiple de 512 qui soit aussi multiple de 80 est 2'560.

1.b)

on a 2'560 octets/bloc et 80 octets/donnée => 1 bloc=(2'560/80) données=32 données.

1.c)

round(32*80)/100) = round(25,6)=> il faudra 26 données/bloc.

1.d)

Avec 26 données/bloc, 100'000 données occuperont (100'000/26) =3'847 blocs dedonnées

❍

une paire (clé+réf. à une page) occupe 12 octets => 1 bloc d'index de 2'560 octets peut

contenir 2'560/12 =213 paires clé+réf.

❍

la couche d'index la plus basse doit contenir 3'847/213 =19 blocs d'index❍

la couche immédiatement supérieure contiendra 18/213 =1 bloc d'index❍

le nombre total de blocs = 3'847 + 19 + 1 = 3'867 blocset comme chaque bloc occupe 2'560 octets => la place disque occupée = (3'867*2'560)octets = 9'899'520 octets.

❍

1.e)

l'arborescence d'index a 2 niveaux

1.f)

niveau 1: 1 blocniveau 2: 19 blocs

1.g)

3'847 blocs de données

Si l'on prend l'hypothèse que les blocs de données contiennent chacun une référence à un bloc dedébordement, il ne peut pas y avoir de solution à la question 1.a, c'est-à-dire qu'il n'y a pas de taille debloc de données qui permette de ne pas avoir d'espace disque inutilisé. Par contre, avec 19 données et desblocs de 1'536 octets on aura le plus petit gaspillage possible (12 octets). Pour s'en convaincre, on peutdémontrer qu'il suffit d'examiner les 32 premiers multiples de 80 et calculer le nombre de pages de 512octets qui permette de les contenir.

En effet,

si

(n*80) + 4 = m*512 + gaspillage

alors

((n+32) *80) + 4 = ((m+5)*512) + gaspillage

Structures de Données, 2ème contrôle continu 1998, solution à la question 1

http://cuisung.unige.ch/std/ex/14/2b.sol.html (1 of 2) [23-09-2001 16:28:47]

En d'autres termes, pour n données/bloc et (n+32) données/bloc, on a le même gaspillage (en valeurabsolue!).

1.a)

avec des blocs de 1'536 octets, on n'a que 12 octets de gaspillage

1.b)

on a 1536 octets/bloc et 80 octets/donnée => 1 bloc=(1'536-4) div 80=19 données/bloc1.c)

round(19*80/100)=round(15,2)=15 données/bloc1.d)

avec 15 données/bloc, 100'000 données occuperont (100'000/15) =6'667 blocs de données❍

une paire (clé+réf. à une page) occupe 12 octets => 1 bloc d'index de 1'536 octets peut

contenir 1'536/12 =128 paires clé+réf.

❍

la couche d'index la plus basse doit contenir 6'667/128 =53 blocs d'index❍

la couche immédiatement supérieure contiendra 53/128 =1 bloc d'index❍

le nombre total de blocs = 6'667 + 53 + 1 = 6'721 blocset comme chaque bloc occupe 1'536 octets => la place disque occupée = (6'721*1'536)octets = 10'323'456 octets.

❍

1.e)

l'arborescence d'index a 2 niveaux

1.f)

niveau 1: 1 blocniveau 2: 53 blocs

1.g)

6'667 blocs de données

Structures de Données, 2ème contrôle continu 1998, solution à la question 1


B-arbre résultant de l'insertion de la valeur L dans le B-arbre initial:.

B-arbre résultant de la suppression de la valeur C dans le B-arbre initial:b.

B-arbre résultant de l'insertion de la valeur Z dans le B-arbre initial:c.

B-arbre résultant de la suppression de la valeur S dans le B-arbre initial:d.

Structures de données: 2ème contrôle continu 1998, solution à la question 2

http://cuisung.unige.ch/std/ex/14/3g.sol.html (1 of 3) [23-09-2001 16:29:58]

autre solution:

B-arbre résultant de la suppression de la valeur P dans le B-arbre initial:

autre solution:

e.





3.a)

On peut imaginer deux genres de solution. Dans la première, on utilise un graphe dont les arcs ne sont ni orientés, nipondérés. Chaque noeud du graphe représente une case de la carte, et le nombre correspondant à son type de terrain eststocké dans l'enregistrement du noeud. Il y a un arc de chaque noeud à chacun de ses voisins accessibles. Il n'est pasnécessaire de représenter les cases impraticables dans le graphe. La représentation de la case B9 et ses voisines serait

L'autre genre de solution utilise un graphe dont les arcs sont orientés et pondérés. Un arc représente le coût d'aller d'unecase à une de ses voisines (c'est-à-dire le coût pour arriver à la case voisine). La partie du graphe autour de la case B9serait

3.b)

Une matrice de connectivité serait la façon la plus efficace pour stocker les arcs, parce que leur densité(NbSommets*~4/NbSommets^2 = ~0.04) dépasse 3%, en fait. Puisque le nombre de noeuds est constant, on peututiliser un tableau pour les stocker. Pour la première structure proposée ci-dessus, on pourrait utiliser les structuressuivantes:

const MaxNoeuds = 100; {Pour la carte donnée}type NoeudIntervalle = 1..MaxNoeuds;var {Matrice de connectivité} Connexe: packed array[NoeudIntervalle, NoeudIntervalle] of boolean; {On ne stocke que le coût associé a chaque noeud} CoutDeNoeud: array[NoeudIntervalle] of integer;

3.c)

Pour trouver le chemin le plus court, j'utiliserai la recherche en largeur, parce qu'elle évite de visiter les chemins pluslongs que le chemin recherché. Mais ce problème est différent: on ne cherche pas le chemin le plus court, on cherche lechemin du moindre coût. On ne peut pas dire qu'on a trouvé le bon chemin dès qu'on arrive au point B - il est possible



qu'il y ait un autre chemin, peut-être plus long, mais moins coûteux.

J'utiliserais donc la recherche en profondeur avec "back-tracking" ainsi que quelques petites modifications: à toutinstant, je garde le chemin du moindre coût déjà trouvé (dans un tableau, p. ex.), ainsi que le coût lui-même. Si le coûtdu chemin qu'on est en train de parcourir dépasse le coût du meilleur chemin déjà trouvé jusqu'à ce noeud là, on peutarrêter de suivre ce chemin. Sinon, quand on arrive au noeud d'arrivée, si le coût du chemin suivi est inférieur à celui dumeilleur chemin déjà trouvé, on les échange. On continue jusqu'à ce qu'on ait essayé (peut être incomplètement) tousles chemins possibles.

3.d)

Le programme principal:Lire les données;Créer le matrice de connectivité;Obtenir les noeuds de départ et arrivée;Initialiser les variables: MeilleurCoût := MaxNoeuds*MaxNoeuds*MaxCoûtDeNoeud; CheminTrouvé := Faux; Mettre CoûtJusquIci[i] à zero pour tous les noeuds i;TrouverCheminDuMoindreCoût(0, 1, NoeudDeDepart, NoeudDArrivee);si CheminTrouvé alors Ecrire MeilleurChemin et son coûtsinon Ecrire "Pas de chemin entre NoeudDeDepart et NoeudDArrivée!"

La procédure TrouverCheminDuMoindreCoût, qui est récursive:procedure TrouverCheminDuMoindreCoût(Coût, NombreDEtapes, Noeud, NoeudDArrivee);begin {Ajoute le noeud actuel au chemin qu'on est en train d'explorer} CeChemin[NombreDEtapes] := Noeud; inc(NombreDEtapes); {Est-ce qu'on a trouvé le noeud d'arrivée?} si Noeud = NoeudDArrivée begin CheminTrouvé := Vrai; si Coût < MeilleurCoût {On a trouvé un meilleur chemin, donc on le stocke} begin MeilleurCout := Coût; LongueurDuChemin := NombreDEtapes - 1; Copier CeChemin dans MeilleurChemin; end; end; sinon {ce n'est pas le noeud d'arrivée} begin {Ajoute le coût du noeud actuel au coût du chemin qu'on explore, et le stocke pour le noeud actuel} Coût := Coût + CoûtDeNoeud[Noeud]; CoûtJusquIci[Noeud] := Coût; Pour tous les noeuds i faire si Connexe[Noeud, i] et ((CoûtJusquIci[i] = 0) ou {c'est-à-dire pas encore visité} (Coût + CoûtDeNoeud[i] < CoûtJusquIci[i])) {Si on a déjà trouvé ce noeud en passant par un chemin moins coûteux, on n'étend plus ce chemin. Cette astuce réduit beaucoup le coût de la recherche.}



TrouverCheminDuMoindreCoût(Coût, NombreDEtapes, i, NoeudDArrivée); {sinon la procédure retourne, et le "back-tracking" commence} end;end;



procedure Paragraphes(UnTexte: VersLigne; var ChainePara: PtrPara);var P: VersLigne; Para: PtrPara; L: integer; NotDone: boolean;begin { Paragraphes } ChainePara := nil; P := UnTexte; L := 1; repeat { determine s'il y a lieu de sauter des lignes vides } if P=nil then NotDone := false else NotDone := P^.Texte=''; { tant que NotDone est vrai, on saute des lignes vides } while NotDone do begin P := P^.LigneSuivante; L := L+1; if P=nil then NotDone := false else NotDone := P^.Texte=''; end; { while } { on a fini de sauter des lignes vides, reste-t-il encore qq chose?} if P<>nil then begin { on est sur le debut d'une serie de lignes non vides, il faut donc creer un nouveau descripteur de paragraphes } if ChainePara = nil then begin new(ChainePara); Para := ChainePara; Para^.Preced := nil; end else begin new(Para^.Suivant); Para^.Suivant^.Preced := Para; Para := Para^.Suivant; end; Para^.Suivant := nil; Para^.Debut := L; NotDone := true; { maintenant, cherche la fin du bloc de lignes non vides } while NotDone do begin P := P^.LigneSuivante; L := L+1; if P=nil then NotDone := false else NotDone := P^.Texte<>'' end; { while } Para^.Fin := L-1; end; { if } until P = nil;end; { Paragraphes }

http://cuisung.unige.ch/std/ex/7/4f.txt

http://cuisung.unige.ch/std/ex/7/4f.txt [23-09-2001 16:31:54]

procedure Insertion( Valeur, NumChaine : integer);{Procedure permettant d'affecter une valeur a la liste qui se trouvre a NumChaine dans le tableau}var Courant,Entete: PtrNoeud;

begin if (NumChaine> MaxNbSommets) OR (NumChaine < 1) then begin writeln('L''indice du tableau doit etre entre 1 et ', MaxNbSommets); readln; halt end else begin {Creation du noeud a inserer} New(Entete); with Entete^ do begin Donnee:= Valeur; Suivant:= nil; end; { with } if TabElement[NumChaine].Chaine = NIL then TabElement[NumChaine].Chaine:= Entete else begin Courant:= TabElement[NumChaine].Chaine; while Courant^.Suivant<>NIL DO Courant:= Courant^.Suivant; {Insertion de Entete dans Courant} Courant^.Suivant := Entete; end; { if TabElement... else } TabElement[NumChaine].Taillechaine := succ(TabElement[NumChaine].Taillechaine); end; { if (NumChaine> MaxNbSommets)... else }end; { Insertion }

Procedure afficher;{Parcourir la Chaine et afficher le contenu de la Chaine}var j: integer; PtCourant: PtrNoeud;begin { afficher } for j:= 1 to MaxNumChaine do begin writeln('TabElement[',j,']'); PtCourant:= TabElement[j].Chaine;

while PtCourant <> nil do begin writeln(PtCourant^.Donnee); PtCourant:= PtCourant^.Suivant; end; { while } readln; end; { for }end; { afficher }



Procedure ChercherInsertion(Valeur: Integer; VAR NoeudInsertion: PtrNoeud); {Permet de determiner le noeud d'insertion pour la valeur donnee: NoeudInsertion retourne NIL, si Valeur existe deja dans l' anneau} Var Courant: PtrNoeud; begin Courant:= Entete^.Suivant; while (Courant <> Entete) and (Courant^.Donnee < Valeur) do Courant:= Courant^.Suivant; if Courant = Entete then NoeudInsertion:= Courant^.Precedent else {Courant^.Donnee >= Valeur} if Courant^.Donnee = Valeur then NoeudInsertion := NIL else NoeudInsertion := Courant^.Precedent; end; {Chercher Insertion}

Procedure RangerValeur(Valeur: Integer); {Permet de ranger une valeur donnee dans l'anneau trié} VAR NInsertion, Nouveau : PtrNoeud; begin AnneauVide := False; New(Nouveau); Nouveau^.Donnee:= Valeur; if Entete=nil then InsererNoeud(Nouveau,Entete) else begin ChercherInsertion(Valeur, NInsertion); if (NInsertion = Entete) and (Entete^.Donnee < Valeur) then Entete := Nouveau; {On changera l'entete si la valeur donnee est plus grande que celle de l'entete} if NInsertion <> NIL then InsererNoeud(Nouveau,NInsertion) else writeln('Cette Valeur existe deja dans la liste'); end; { if Entete=nil ... else } end;{RangerValeur}

http://cuisung.unige.ch/std/ex/7/4g.txt

http://cuisung.unige.ch/std/ex/7/4g.txt [23-09-2001 16:32:46]

a)

Arbre('-', Arbre('*', Arbre('-', Feuille('a'), Arbre('+', Feuille('b'), Feuille('c') ) ), Feuille('d') ), Arbre('/', Arbre('-', Feuille('e'), Feuille('f') ), Arbre('*', Feuille('g'), Feuille('h') ) ) )

b)

type Noeud = record Operateur: char; G, D: PtrNoeud; end; { Noeud }

function Feuille(Contenu: char): PtrNoeud;var P: PtrNoeud;begin new(P); with P^ do begin Operateur := Contenu; G := nil; D := nil; end; {with} Feuille:=P;end; { Feuille }

function Arbre(Contenu: char; Gauche, Droit: PtrNoeud): PtrNoeud;var P: PtrNoeud;begin new(P); with P^ do begin Operateur := Contenu; G := Gauche; D := Droit; end; {with} Arbre:=P;end; { Arbre }


http://cuisung.unige.ch/std/ex/8/1c.txt [23-09-2001 16:33:07]

procedure DFS( LeGraphe: Graphe);var CmptrVisite, IndexSommet : 0..MaxNbSommets; NumeroDOrdre: array[1..MaxNbSommets] of integer;

procedure Visite (IndexSommet : integer);var Voisins: SerieDeSommets; Voisin: integer;begin CmptrVisite := CmptrVisite + 1; NumeroDOrdre[IndexSommet]:=CmptrVisite; write(NomSommet(IndexSommet,LeGraphe), ' '); Voisins := SommetsVoisins(IndexSommet,LeGraphe); Voisin := 0; if not FinDeSerie(Voisins) then begin repeat if Voisin=0 then Voisin := PremierSommet(Voisins) else Voisin := SommetSuivant(Voisins); if NumeroDOrdre[Voisin]=0 then Visite (Voisin); until FinDeSerie(Voisins); end; { if not FinDeSerie }end; { Visite }

begin { DFS } CmptrVisite := 0; for IndexSommet:= 1 to NombreDeSommets(LeGraphe: Graphe) do NumeroDOrdre[IndexSommet]:=0; for IndexSommet := 1 to NombreDeSommets(LeGraphe: Graphe) do if NumeroDOrdre[IndexSommet] = 0 then Visite (IndexSommet)end; { DFS }

http://cuisung.unige.ch/std/ex/10/3a.sol.txt

http://cuisung.unige.ch/std/ex/10/3a.sol.txt [23-09-2001 16:33:39]

procedure Imprime(LeDico: VersNoeud);const TailleFile = 100;type Objet=record Mot: String80; Place: VersNoeud; end; { Objet } FileCirculaire=record Element: array[0..TailleFile] of Objet; IndexIn, IndexOut: 0..TailleFile; Plein:boolean; end; { FileCirculaire }var MaFile: FileCirculaire; Obj: Objet;

procedure Avance(N: VersNoeud; S: String80); var c:char; Splus:String80; l: integer; O: Objet; begin { Avance } if N^.Complet then writeln(S); Splus := S; l := length(Splus)+1; Insert(' ',Splus, l); for c := 'a' to 'z' do if N^.Desc[c]<>nil then begin Splus[l] := c; O.Mot := Splus; O.Place := N^.Desc[c]; Met(MaFile, O); end; { if N^.Desc[c]<>nil } end; { Avance }

begin { Imprime } MaFile.IndexIn := 0; MaFile.IndexOut := 0; MaFile.Plein := false;

if LeDico<>nil then Avance(LeDico, ''); while not Vide(MaFile) do begin Ote(MaFile, Obj); Avance(Obj.Place, Obj.Mot); end; {while}end; { Imprime }



indice dutableau

chaîne associéevaleur entre () = H2(Mot)

0 a (4)->du (12)->quatre (16)

1 sont (7)->premier (14)

2 aurait (2)->un (9)->lesquels (17)

3 cycle (2)

4 les (8)->atteint (12)->y (13)

5 oral (1)->le (7)

6 examens (5)->pour (10)

7 n (5)->examen(6)

8 si (6)->admis(13)

9 note (2)->chaque (17)->qu (22)

10 subir (3)



procedure Extension(Entree: TableDecision; var Sortie: TableDecision);var Regle: 0..MaxNbRegles; Condition, Cond: 0..MaxNbCond; Action: 0..MaxNbActions;

begin { Extension } Sortie.NbConditions := Entree.NbConditions; Sortie.NbRegles := Entree.NbRegles; Sortie.NbActions := Entree.NbActions;

for Regle := 1 to Entree.NbRegles do begin for Condition := 1 to Entree.NbConditions do Sortie.ValCond[Regle,Condition] := Entree.ValCond[Regle,Condition]; for Action := 1 to Entree.NbActions do Sortie.Agir[Regle,Action] := Entree.Agir[Regle,Action]; end; { for }

Regle := 1; while Regle <= Sortie.NbRegles do begin for Cond := 1 to Sortie.NbConditions do if Sortie.ValCond[Regle,Cond] = Indetermine then begin Sortie.ValCond[Regle,Cond] := Vrai; Sortie.NbRegles := succ(Sortie.NbRegles); for Condition := 1 to Sortie.NbConditions do Sortie.ValCond[Sortie.NbRegles,Condition] := Sortie.ValCond[Regle,Condition]; Sortie.ValCond[Sortie.NbRegles,Cond] := Faux; for Action := 1 to Sortie.NbActions do Sortie.Agir[Sortie.NbRegles,Action] := Sortie.Agir[Regle,Action]; end; { if } Regle := succ(Regle); end; { while }end; { Extension }



procedure EchangeLignes(var UnTexte: VersLigne; NoLigne1,NoLigne2:integer);var Ligne, L1, L2, L1Suiv, L2Pred: VersLigne; No: integer;begin { EchangeLignes } { recherche des pointeurs correspondant aux numeros de ligne donnes } Ligne := UnTexte; L1 := nil; L2 := nil; No := 0; while (Ligne<>nil) and ( (L1=nil) or (L2=nil)) do begin No := No + 1; if No = NoLigne1 then L1 := Ligne; if No = NoLigne2 then L2 := Ligne; Ligne := Ligne^.LigneSuivante; end; { while }

{ validation des parametres } if (L1=nil) or (L2=nil) then begin if L1=nil then writeln('Le numero de ligne ',NoLigne1, ' n''est pas dans l''intervalle 1..',No); if L2=nil then writeln('Le numero de ligne ',NoLigne2, ' n''est pas dans l''intervalle 1..',No); end else if NoLigne1<>NoLigne2 then begin { on arrive ici si les parametres fournis sont valides et differents }

{ pour faciliter le traitement on va s'assurer que L1 pointe toujours sur un element qui precede celui pointe par L2 } if NoLigne1 > NoLigne2 then begin Ligne := L1; L1 := L2; L2 := Ligne; end;

{ ici, on procede a l'echange proprement dit } if L1=UnTexte then UnTexte := L2 else L1^.LignePrecedente^.LigneSuivante := L2; L2Pred := L2^.LignePrecedente; L2^.LignePrecedente := L1^.LignePrecedente; L1Suiv := L1^.LigneSuivante; L1^.LigneSuivante := L2^.LigneSuivante; if L2^.LigneSuivante <> nil then L2^.LigneSuivante^.LignePrecedente := L1; if L1Suiv=L2 then begin L2^.LigneSuivante := L1; L1^.LignePrecedente := L2 end else begin L2^.LigneSuivante := L1Suiv; L1^.LignePrecedente := L2Pred; L2Pred^.LigneSuivante := L1; L1Suiv^.LignePrecedente := L2; end; { if L1Suiv=L2 } end; { if }end; { EchangeLignes }

procedure InverserLignes(var UnTexte: VersLigne);


http://cuisung.unige.ch/std/ex/7/4d.txt (1 of 2) [23-09-2001 16:34:35]

var Ligne, Tmp: VersLigne;begin { InverserLignes } Ligne := UnTexte; while Ligne<>nil do begin Tmp := Ligne^.LigneSuivante; Ligne^.LigneSuivante := Ligne^.LignePrecedente; Ligne^.LignePrecedente := Tmp; UnTexte := Ligne; Ligne := tmp; end; { while }end; { InverserLignes }


http://cuisung.unige.ch/std/ex/7/4d.txt (2 of 2) [23-09-2001 16:34:35]

la chaîne 2 -> 0 -> 1 -> 1 -> -3 produira2->1->1->-3->0->0->0->0->0->0->0... avec la valeur 0 qui se répète à l'infini.

1.

la chaîne 3 -> -1 -> 2 -> -1 -> -3 produira la séquence 3->-1->2->-3->-1->...qui se répète à l'infini.

2.

Structuration des Données Informatiques - 7.4, solution de l'exercice 5

http://cuisung.unige.ch/std/ex/7/4e.sol.html [23-09-2001 16:34:53]

1)Solution de l'exercice 2, chapître 8 section 2


2)

procedure ImprimePetitsEnfants(LaPersonne: PersonnePtr);var CourantEnfant, CourantPetitEnfant: ChaineFreresSoeurs;begin if (LaPersonne = nil) then writeln('Erreur: pointeur nil passe a la procedure ImprimePetitsEnfants') else begin {trouve le NoeudFrereSoeur de son premier enfant} CourantEnfant := LaPersonne^.Enfants; while (CourantEnfant <> nil) do begin {trouve le NoeudFrereSoeur de son premier petit-enfant. Note: Il faut utiliser le champ FrereOuSoeur pour acceder au pointeur de type PersonnePtr} CourantPetitEnfant := CourantEnfant^.FrereOuSoeur^.Enfants; while (CourantPetitEnfant <> nil) do begin write(CourantPetitEnfant^.FrereOuSoeur^.Nom,', '); writeln(CourantPetitEnfant^.FrereOuSoeur^.Prenom); CourantPetitEnfant := CourantPetitEnfant^.FrereSoeurSuivant; end; {while (CourantPetitEnfant <> nil)} CourantEnfant := CourantEnfant^.FrereSoeurSuivant; end; {while (CourantEnfant <> nil)} end; {else}end; {ImprimePetitsEnfants}

Solution de l'exercice 2, chapître 8 section 2


a) La page racine étant déjà pleine, l'adjonction de la valeur 10 va nécessiter la scission de cette page endeux et la création d'une page au niveau au-dessus contenant l'élément charnière (qui est 10). Le B-arbrerésultant est:

b) La page dans laquelle devrait venir la nouvelle valeur (21) est déjà pleine. La page de même niveauqui est à sa gauche peut recevoir un élément supplémentaire. L'élément intermédiaire (20) qui se trouvedans le niveau au dessus est donc déplacé dans la page de gauche et la place ainsi libérée peut êtreoccupée par le plus petit élément de la page excédentaire. Le B-arbre résultant est:

c) En supprimant la valeur 55, la page en question tombe en dessous du nombre minimum d'éléments. Lapage d'à côté ayant plus que le minimum d'éléments, on peut lui emprunter un élément (42) qui vientremplacer l'élément intermédiaire (50) qui se trouve dans le niveau au dessus. Cet élément intermédiaire(50) vient alors dans la page dans laquelle il manquait un élément. Le B-arbre résultant est:

d) La page dans laquelle devrait venir la nouvelle valeur (23) est déjà pleine. Les deux pages voisines demême niveau sont aussi pleines. Il faut donc scinder la page excédentaire en deux, avec comme élémentcharnière la valeur 23 qui ira dans la page du niveau au-dessus. Les deux pages résultant de la scissionseront connectées à l'élément charnière nouvellement rajouté au niveau au-dessus. Le B-arbre résultantest:

e) La page dans laquelle devrait venir la nouvelle valeur (4) est déjà pleine. La page voisine de mêmeniveau est aussi pleine. Il faut donc scinder la page excédentaire en deux, avec comme élément charnièrela valeur 4 qui ira dans la page du niveau au-dessus. Les deux pages résultant de la scission serontconnectées à l'élément charnière nouvellement rajouté au niveau au-dessus. Le B-arbre résultant est:



f) Pour supprimer la valeur 15, on va d'abord l'échanger avec la valeur qui se trouve le plus à droite dusous-arbre gauche, en l'occurence la valeur 7. La valeur 7 remplace donc la valeur 15 dans la page racineet doit être supprimée de la feuille dans laquelle elle se trouvait précédemment. Cette page feuille ayantassez d'éléments, la suppression peut se faire sans autre. Le B-arbre résultant est:



procedure EffaceLigne(var UnTexte: VersLigne; NumeroLigne: integer);var courant: VersLigne; i: integer;begin if NumeroLigne < 1 then writeln ('NumeroLigne doit etre >= 1') else begin courant := UnTexte; i := 1; while (courant<>nil) and (i < NumeroLigne) do begin courant := courant^.LigneSuivante; i := i+1; end; (* while *) if courant=nil then writeln('La chaine est trop courte') else begin with courant^ do begin if courant = UnTexte then UnTexte := LigneSuivante else LignePrecedente^.LigneSuivante := LigneSuivante; if LigneSuivante <> nil then LigneSuivante^.LignePrecedente := LignePrecedente; end; (* with *) dispose(courant); end; (* if courant=nil *) end; (* if NumeroLigne < 1 *)end; (* EffaceLigne *)

procedure JoindreLignes(var UnTexte: VersLigne; LigneCourante: integer);var courant, LigneADetruire: VersLigne; i: integer;begin if LigneCourante < 1 then writeln ('LigneCourante doit etre >= 1') else begin courant := UnTexte; i := 1; while (courant<>nil) and (i < LigneCourante) do begin courant := courant^.LigneSuivante; i := i+1; end; (* while *) if courant=nil then writeln('La chaine est trop courte') else if courant^.LigneSuivante = nil then writeln('On est sur la derniere ligne') else begin with courant^ do begin Texte := concat(Texte, LigneSuivante^.Texte); if LigneSuivante^.LigneSuivante = nil then dispose(LigneSuivante) else begin LigneSuivante^.LigneSuivante^.LignePrecedente := courant; LigneADetruire := LigneSuivante; LigneSuivante := LigneSuivante^.LigneSuivante; end; (* if LigneSuivante... *) end; (* with *) dispose(LigneADetruire); end; (* if courant^.LigneSuivante = nil *) end; (* if LigneCourante < 1 *)end; (* JoindreLignes *)


http://cuisung.unige.ch/std/ex/7/4c.txt [23-09-2001 16:37:37]

a)

Etant donné qu'un bloc de données dispose de 1536 octets et qu'une donnée occupe 76 octets, ilpeut y avoir au plus 20 données par bloc (1536 div 76=20 et restent 16 octets qui peuvent êtreutilisés pour pointer vers le bloc suivant et vers un eventuel bloc de débordement).

Du fait que les blocs ne sont initialement remplis qu'à 80%, il n'y aura que 16 données par bloc(20*80/100 = 16). Il faudra donc 62'500 blocs de données pour stocker 1'000'000 éléments(1'000'000/16 = 62'500).

Pour ce qui est des blocs d'index, chaque élément du bloc est composé d'une clé de 8 octets etd'une référence de 4 octets, soit 12 octets par élément. Il y a donc 85 éléments par bloc d'index(1024 div 12 = 85, reste 4).

La première couche de blocs d'index, qui pointent vers des blocs de données, doit contenir unélément par bloc de données. Il y a donc 736 blocs (62'500 div 85 = 735, reste 25; c'est-à-dire qu'ily a 735 blocs entièrement pleins et le dernier bloc ne contenant que 25 éléments).

La deuxième couche de blocs d'index occupe 9 blocs (736 div 85 = 8, reste 56 -> 8 blocs pleins etle neuvième avec 56 éléments). La troisième et dernière couche de blocs d'index ne contient qu'unseul bloc, avec seulement 9 éléments sur 85 occupés.

La taille de l'espace disque occupé est donc: (nombre de blocs de données*taille d'un bloc dedonnées) + (nombre de blocs d'index*taille d'un bloc d'index) = 62'500*1536 + (736+9+1)*1024 =96'763'904 octets.

En résumé:

nombre de blocs de données = 62'500❍

profondeur de l'arborescence d'index = 3❍

nombre de blocs d'index = 736 puis 9 puis 1❍

espace disque occupé = 96'763'904❍

b)

Etant donné qu'une page du B-arbre dispose de 1024 octets et qu'il faut stocker une référence deplus que de données, en supposant que l'on utilise 2 octets pour stocker le nombre d'élémentseffectifs dans la page, il peut y avoir ((1024-4-2) div (76+4) = 12, reste 58 octets inutilisés). LeB-arbre est donc d'ordre 6.

Si l'on suppose que toutes les pages sont pleines, 1'000'000 éléments occuperaient alors 83'334pages (1'000'000 div 12 = 83'333, reste 4 éléments qui vont occuper partiellement la 83'334èmepage).

Si, à l'autre extrème, l'on suppose que les pages ne sont qu'à moitié pleines, 1'000'000 élémentsoccuperont alors 166'667 pages (1'000'000 div 6 = 166'666, reste 4 éléments qui vont occuper unepage de plus).

L'espace disque nécessaire sera donc compris entre 85'334'016 octets (83'334*1024) et170'667'008 octets (166'667*1024).

Pour ce qui est du nombre de niveaux de l'arborescence, il faut là aussi envisager les 2 cas


http://cuisung.unige.ch/std/ex/14/2a.sol.html (1 of 2) [23-09-2001 16:38:00]

extrèmes de pages toutes entièrement pleines ou toutes à moitié pleines:

Quand les pages sont entièrement pleines, chaque page a 13 descendants. On peutfacilement calculer le nombre de pages à chaque niveau puisque ce sont les puissancessuccessives de 13: 1, 13, 169, 2197, 28561, 371'293. On voit alors facilement qu'il faut 6niveaux pour avoir les 83'334 pages nécessaires pour stocker les 1'000'000 éléments.

❍

Dans le cas le plus défavorable où la racine ne contient qu'un seul élément (et deuxdescendants) et toutes les autres pages 6 éléments (et 7 descendants), les niveaux successifscontiennent: 1, 2, 14, 98, 686, 4802, 16'807 et, finalement 235'298 pages. Cela correspond à2*7n-2 pages pour le niveau n. On voit donc qu'il faut 8 niveaux dans ce cas.

❍

En résumé:

nombre de pages: entre 83'334 et 166'667❍

espace disque: entre 85'334'016 et 170'667'008 octets❍

niveaux: entre 6 et 8.❍


http://cuisung.unige.ch/std/ex/14/2a.sol.html (2 of 2) [23-09-2001 16:38:00]

Comme il s'agit d'un graphe pondéré, il faudra une matrice d'entiers pour représenter les arcs et une autrestructure pour représenter les sommets, par exemple un tableau de strings.

En supposant que les sommets sont rangés dans le tableau dans l'ordre suivant: ['Bern', 'Genève', 'Lausanne','Lucerne', 'Lugano', 'Milan', 'Neuchâtel', 'Zürich'], la matrice de pondération pourrait être ainsi (l'absenced'arc est notée -1):

0 -1 96 92 -1 -1 -1 120 -1 0 60 -1 -1 325 -1 -1 96 60 0 -1 -1 -1 68 -1 92 -1 -1 0 174 -1 -1 -1 -1 -1 -1 174 0 78 -1 206 -1 325 -1 -1 78 0 -1 -1 -1 -1 68 -1 -1 -1 0 -1 120 -1 -1 -1 206 -1 -1 0

1.

Les déclarations Pascal pourraient être:

var Distance:array[1..MaxNbSommets,1..MaxNbSommets] of integer; Villes: array[1..MaxNbSommets] of string; NbSommets: integer;

2.

Une possibilité est de calculer le graphe de fermeture transitive indiquant la longueur du plus court cheminentre deux sommets (en utilsant une variante de l'algorithme de Warshall):

for y:= 1 to NbSommets do for x:= 1 to NbSommets do if Distance[x,y] > -1 then for j:= 1 to NbSommets do if Distance[y,j] > -1 then if (Distance[x,j] > (Distance[x,y]+Distance[y,j])) or (Distance[x,j] = -1) then Distance[x,j] := Distance[x,y]+Distance[y,j];

Après quoi, la fonction pour déterminer la distance minimale entre deux villes x et y n'aura qu'à retournerDistance[index(x),index(y)]:

function MinDist(Ville1, Ville2: string): integer; { accès à la matrice de fermeture transitive "Distance" par effet de bord. Retourne la plus courte distance entre Ville1 et Ville2. Retourne -1 s'il n'y a pas de chemin entre Ville1 et Ville2. } begin MinDist := Distance[index(Ville1),index(Ville2)]; end; { MinDist }===================================================================

Une autre possibilité consiste à reprendre l'algorithme de DFS et à ajouter des paramètres à la procédureVisite pour conserver la longueur du chemin partiel et retourner la distance minimale quand on a atteind lenoeud de destination (on pourrait utiliser le BFS, mais cela impliquerait de mémoriser la longueur de tous leschemins partiels pour effectuer la comparaison à l'arrivée):

3.



http://cuisung.unige.ch/std/11.3.html#Warshall

function MinDist(Ville1, Ville2: string): integer;{ accès à la matrice "Distance" par effet de bord. Retourne la plus courte distance entre Ville1 et Ville2. Retourne MaxInt s'il n'y a pas de chemin entre Ville1 et Ville2. }var DistMin, i, Index2: integer; Parcouru: array[1..MaxNbSommets] of boolean;

procedure Visite (IndexSommet : integer; DistPartielle:integer; var DistMin: integer); var AutreSommet : integer; begin if IndexSommet=Index2 then begin { on est arrivé à destination. Par un chemin plus court qu'avant? } if DistPartielle < DistMin then DistMin := DistPartielle end else begin Parcouru[IndexSommet]:=true; { marque par où on passe } for AutreSommet := 1 to NbSommets do { Y a-t-il un arc vers AutreSommet et pas de cycle? } if (Distance[IndexSommet,AutreSommet] > 0) and not Parcouru[AutreSommet] then Visite(AutreSommet, DistPartielle+Distance[IndexSommet,AutreSommet], DistMin); { ôte la marque en rebroussant chemin pour pouvoir repasser par ce même noeud par un autre chemin } Parcouru[IndexSommet]:=false; end; { if } end; { Visite }

begin { MinDist } for i := 1 to NbSommets do Parcouru[i]:= false; Index2 := index(Ville2); DistMin := MaxInt; Visite(index(Ville1), 0, DistMin); MinDist := DistMin;end; { MinDist }

Le bût du tableau Parcouru est d'éviter de boucler dans des cycles, en marquant chaque noeud par lequelon passe. On enlève la marque dès que l'on fait marche arrière pour permettre à l'algorithme de repasseréventuellement par ce même noeud, au cas où celui-ci se trouverait le long d'un autre chemin qui serait pluscourt.



procedure DeplacerDansAnneau(UnAnneau: Anneau; var Arret: TypeArret; Depl: integer);var i : integer; pointeur : Anneau; { pointe normalement sur l'elem. qui serait detruit si Depl=1} ALaFin, { sera vrai si on detruit l'elem. en derniere position de l'anneau } PasFini : boolean;

procedure Supprime(var Courant : Anneau; var ALaFin: boolean); {procedure pour supprimer un element de l'anneau et ajuster le pointeur "Courant" en consequence. Si on detruit le permier element, ajuste UnAnneau en consequence. ALaFin sera vrai si on est en train de detruire le dernier element. } var temp : Anneau; begin {1} if Courant^.predecesseur = Courant then begin {2} { on detruit l'unique element restant } dispose(Courant); UnAnneau := nil; end {2} { if ... then } else begin {3} {on efface l'element de l'anneau} Courant^.predecesseur^.successeur := Courant^.successeur; Courant^.successeur^.predecesseur := Courant^.predecesseur; ALaFin := Courant^.successeur=UnAnneau; temp := Courant; {on ajuste le pointeur} Courant := Courant^.successeur; {si on detruit le 1er elem., ajuster "UnAnneau" } if temp=UnAnneau then UnAnneau := Courant; {on efface physiquement l'element} dispose(temp); end; {3} { if ... else } end; {1} { Supprime }


http://cuisung.unige.ch/std/ex/7/4a.txt (1 of 2) [23-09-2001 16:39:11]

begin {4} { DeplacerDansAnneau } PasFini := UnAnneau<>nil; Arret := AnneauVide; ALaFin := false; pointeur := UnAnneau; while PasFini do begin {5}{si le deplacement est nul, on s'arrete} if Depl = 0 then begin {6} Arret := ElementNul; PasFini := false; end {6} { if ... then } else if Depl > 0 then begin {7}{si le deplacement est positif et on est a la fin, on s'arrete } if ALaFin then begin {8} PasFini := false; Arret := SortieAnneau; end {8} { if ALaFin then } else begin {9}{si le deplacement est positif} i := 1; while i < Depl do begin {10}{on se deplace} pointeur := pointeur^.successeur;{on verifie qu'on sort pas de l'anneau} if pointeur = UnAnneau then begin {11} Arret := SortieAnneau; i := Depl; PasFini := false; end {11} { if then } else i := i+1; end; {10} { while } end {9} { If ALaFin ... else } end {7} { if Depl > 0 } else begin {12}{de meme, pour le cas ou le deplacement est negatif} i := 0; while i > Depl do begin {13}{ on veut reculer d'un cran, a moins d'etre au debut } if (pointeur=UnAnneau) and not ALaFin then begin {14} Arret := SortieAnneau; i := Depl; PasFini := false; end {14} { if } else begin {15} pointeur := pointeur^.predecesseur; i := i-1; end; {15} { if ... else } end; {13} { while } end; {12} { if ... else } if PasFini then begin {16}{on prend la nouvelle valeur pour le deplacement et on l'imprime} Depl := pointeur^.Entier; writeln(pointeur^.Entier);{on supprime l'element de l'anneau } Supprime(pointeur, ALaFin);{si l'anneau est vide apres cette suppression, il faudra s'arreter} PasFini := pointeur <> nil; end; {16} { if PasFini } end; {5} { while PasFini }end; {4} { DeplacerDansAnneau }


http://cuisung.unige.ch/std/ex/7/4a.txt (2 of 2) [23-09-2001 16:39:11]

Il y a bien entendu beaucoup de solutions possibles. Le tout est de ne pas mettre un descendant avant unde ses ancêtres. On peut donc envisager de sérialiser les données de l'arbre, une ligne après l'autre, de laracine vers les feuilles:

a) 20 18 42 3 26 14 39 7 30 10 34

b) vos beaux yeux amour marquise d mourir font me

On aurait pu aussi imaginer faire un parcours en pré-ordre de l'arbre...



procedure TriTopoInverse(LeGraphe: Graphe);

const MaxNbSommets=20;

var i, CmptrVisite, IndexSommet : 0..MaxNbSommets;

NumDOrdre : array[1..MaxNbSommets] of integer; Parcouru:array[1..MaxNbSommets] of boolean;

NbSommets: integer;

procedure Visite (IndexSommet : integer);var AutreSommet : integer; Voisins: SerieDeSommets;begin CmptrVisite := CmptrVisite + 1; NumDOrdre[IndexSommet] := CmptrVisite; Parcouru[IndexSommet] := true; Voisins := SommetsVoisins(IndexSommet, LeGraphe); if not FinDeSerie(Voisins) then begin AutreSommet := PremierSommet(Voisins); repeat if Parcouru[AutreSommet] then writeln(NomSommet(AutreSommet,LeGraphe), ' fait partie d''un cycle') else if NumDOrdre[AutreSommet] = 0 then Visite (AutreSommet); if FinDeSerie(Voisins) then AutreSommet := 0 else AutreSommet := SommetSuivant(Voisins); until AutreSommet = 0; end; { if } Parcouru[IndexSommet] := false; write(NomSommet(IndexSommet,LeGraphe));end; { Visite }

begin { TriTopoInverse } NbSommets := NombreDeSommets(LeGraphe); CmptrVisite := 0; for IndexSommet := 1 to NbSommets do NumDOrdre[IndexSommet]:=0; for IndexSommet := 1 to NbSommets do if NumDOrdre[IndexSommet]=0 then begin for i := 1 to NbSommets do Parcouru[i] := false; Visite (IndexSommet); end; { if }end; { TriTopoInverse }



Le B-arbre résultant est:

Pour y arriver, on passe par les étapes suivantes:

En supprimant g, on se trouve dans la situation suivante qui va nécessiter de fusionner la page oùse trouvait g avec sa voisine de gauche et l'élément charnière du niveau au-dessus:

En effet, la page où se trouvait g est tombée en dessous du seuil minimum et la page voisine est auseuil minimum. On ne peut donc pas lui "emprunter" d'élément.

●

On aboutit donc à la situation suivante, où la page qui contenait g doit être supprimée et la page duniveau au-dessus est tombée en dessous du seuil minimum et doit fusionner avec sa voisine dedroite puisque celle-ci est au seuil minimum:

●

On aboutit ainsi à la situation finale, où la page qui contenait q ainsi que la page racine doiventêtre supprimées.

●



type VersMaillon = ^Maillon; Maillon = record Precedent, Suivant: VersMaillon; Contenu: integer; Visite: boolean; end; { Maillon }

Arrets = (SortieChaine, Cycle);

procedure Deplacement(LaChaine: VersMaillon; PremierSaut: integer; var TypeArret: Arrets; var PositionArret: integer);var Courant: VersMaillon; Deplace, Tmp: integer;begin PositionArret := 1; Deplace := PremierSaut-1; Courant := LaChaine; while Courant <> nil do begin Courant^.Visite := false; Courant := Courant^.Suivant; end; { while } Courant := LaChaine;

while Deplace <> 0 do begin Tmp := Deplace; while ((Deplace < 0) and (Courant^.Precedent <> nil)) or ((Deplace > 0) and (Courant^.Suivant <> nil)) do if Deplace > 0 then begin Courant := Courant^.Suivant; Deplace := Deplace-1; end else begin Courant := Courant^.Precedent; Deplace := Deplace+1; end; if Deplace <> 0 then begin TypeArret := SortieChaine; Deplace := 0; end else if Courant^.Visite then begin TypeArret := Cycle; Deplace := 0; end else begin PositionArret := PositionArret + Tmp; Deplace := Courant^.Contenu; Courant^.Visite := true; end; {if } end; { while }end; { Deplacement }




var Dico: VersNoeud;

function Trouve(LeDico: VersNoeud; LeMot: string) : boolean;begin { Trouve } if LeDico=nil then Trouve := false else if LeMot = '' then Trouve := LeDico^.Complet else Trouve := Trouve(LeDico^.Desc[LeMot[1]], copy(LeMot,2,length(LeMot)-1));end; { Trouve }

{ version non-recursive }function Trouve(LeDico: VersNoeud; LeMot: string) : boolean;var i: integer; Courant: VersNoeud;begin { Trouve } i:=1; Courant := LeDico; while (i<=Length(LeMot)) and (Courant<>nil) do begin Courant := Courant^.Desc[LeMot[i]]; i := i+1; end; { while } if Courant=nil then Trouve := false else Trouve := Courant^.Complet;end; { Trouve }

procedure Imprime(LeDico: VersNoeud);

procedure Print(N: VersNoeud; S: string); var i:char; Splus:string; begin if N^.Complet then writeln(S); Splus := Insert(' ',S, length(S)+1); for i := 'a' to 'z' do if N^.Desc[i]<>nil then begin Splus[length(Splus)] := i; Print(N^.Desc[i],Splus); end; { if N^.Desc[i]<>nil } end; { Print }

begin { Imprime } if LeDico<>nil then Print(LeDico, '');end; { Imprime }



(* variation de la methode de Warshall pour calculer le chemin le plus court entre tous les sommets d'un graphe oriente*)

for x:= 1 to MaxNbSommets do for y:= 1 to MaxNbSommets do Longueur[x,y]:=0;

... (* lecture du graphe dans "Longueur" *)

for y:= 1 to NbSommets do for x:= 1 to NbSommets do if Longueur[x,y]>0 then for j:= 1 to NbSommets do if Longueur[y,j]>0 then if (Longueur[x,j] > (Longueur[x,y]+Longueur[y,j])) or (Longueur[x,j]=0) then Longueur[x,j] := Longueur[x,y]+Longueur[y,j];



Documents

Exercices