Université de Limoges Faculté des Sciences et Techniques

larec

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

3 pages

Français

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Niveau: Supérieur, Master, Bac+4
Université de Limoges Faculté des Sciences et Techniques Année Universitaire 2008-2009 Master Mathématiques première année Algorithmique et programmation Examen du 9 janvier 2009 Durée 2h. Documents manuscrits et distribués durant le semestre autorisés. Les exercices sont indépendants. Le barême est indicatif. Exercice 1. (6 points) Tri par bulles. On s'intéresse à l'algorithme suivant : Algorithme Tri_bulle(var T: tableau d'entiers, n: entier) Entrées : T[0],...,T[n-1], tableau de n entiers distincts. Sortie : Le tableau trié en ordre croissant. Début trié ?? faux m ?? n-1 Tant que non trié faire trié ?? vrai Pour i de 0 à m-1 faire Si T[i] > T[i+1] alors tmp ?? T[i] T[i] ?? T[i+1] T[i+1] ?? tmp trié ?? faux fin fin m ?? m-1 fin Fin. On s'intéresse à la complexité de cet algorithme, en nombre de comparaisons d'éléments du tableau. 1. Vérifier qu'à l'issue de chaque exécution de la boucle «Pour», l'élément T[m] est correctement placé. En déduire que l'algorithme fonctionne. 2. Quelle configuration d'entrée correspond au meilleur des cas de cet algorithme? Expliquez.

?ni par expo- nentiation binaire

décomposition de l'exposant en base

entier positif

année algorithmique

int tete

typedef struct

void afficher

expo

Sujets

Université de Limoges

Entier naturel

Informations

Publié par	larec
Nombre de lectures	59
Langue	Français

Extrait

UniversitÉ FacultÉ des

de Limoges Sciences et Techniques

AnnÉe Universitaire 2008-2009

Master MathÉmatiques premiÈre annÉe Algorithmique et programmation Examen du 9 janvier 2009

DurÉe 2h. Documents manuscrits et distribuÉs durant le semestre autorisÉs. Les exercices sont indÉpendants. Le barme est indicatif.

Exercice 1.(6 points)Tri par bulles.On s’intÉresse À l’algorithme suivant : Algorithme Tri_bulle(varTd’entiers,: tableaun: entier) EntrÉes :T[0],...,T[n-1], tableau denentiers distincts. Sortie :Le tableau triÉ en ordre croissant. DÉbut triÉ←−faux m←−n-1 Tant que non triÉ faire triÉ←−vrai Pour i de 0 À m-1 faire Si T[i]>T[i+1] alors tmp←−T[i] T[i]←−T[i+1] T[i+1]←−tmp triÉ←−faux fin fin m←−m-1 fin Fin.

On s’intÉresse À la complexitÉ de cet algorithme, ennombre de comparaisons d’ÉlÉments du tableau. 1. VÉriﬁerqu’À l’issue de chaque exÉcution de la boucle «Pour», l’ÉlÉmentT[m]est correctement placÉ. En dÉduire que l’algorithme fonctionne. 2. Quelleconﬁguration d’entrÉe correspond au meilleur des cas de cet algorithme?Expliquez. Que peut-on dire de la complexitÉ asymptotique dans le meilleur des cas ? 3. Quelleconﬁguration d’entrÉe correspond au pire des cas ?Expliquez. Quepeut-on dire de la complexitÉ asymptotique dans le pire des cas ?

Q r Exercice 2.(6 points) Soitm, m1, . . . , mrdes entiers positifs non nuls tels quem=mi. Soitp i=1 un nombre premier etαun ÉlÉment non nul deZ/pZ. Pour1≤i≤r, notonsniles entiersm/mi. On n1nr cherche À calculer efﬁcacement lesrÉlÉmentsα ,. . . , αdeZ/pZ. ni 1. OnconsidÈre l’algorithme naf suivant :on calcule lesnipuis successivement lesαpar expo-nentiation binaire (utilisant la dÉcomposition de l’exposant en base 2). (a) Quelleest la complexitÉen nombre de multiplications dansZ/pZde cet algorithme (en fonction deret de la taille dem) ? (b) Onsuppose maintenant quepest un entier multiprÉcision. Que peut-on dire de la complexitÉ en nombre d’opÉrations machine de l’algorithme (tenir compte de la taille de l’entierp) ? 2. Ons’intÉresse ensuite À un algorithme de type «diviser pour rÉgner» : Algorithme Expo(β,t,p1, p2, . . . , p2): ensembled’ÉlÉments deZ/pZ t EntrÉes : βde: ÉlÉmentZ/pZ. tentier positif.: un t p1, p2, . . . , p2:2entier positifs. t DÉbut Sit= 0alors renvoyer({β}) a←−p∗p∗ ∙ ∙ ∙ ∗p t−1 1 22 b←−pt−1∗pt−1∗ ∙ ∙ ∙ ∗p2 t 2 +12 +2 a b Renvoyer( Expo(β ,t−1, pt−1, . . . , p2)∪Expo(tβ ,−1, p1, . . . , p2)) t t−1 2 +1 End. (a) Expliciterle fonctionnement de l’algorithme dans le cast= 3. k (b) Onsuppose dans la suite quer= 2. Montrer par rÉcurrence queExpo(α, k, m1, . . . , mr) n1nr renvoieα ,. . . , α. (c) Onsuppose que tous lesmiont sensiblement la mme taille :T(mi) =T(m)/r. Que peut-on dire de la complexitÉ de cet algorithme, en nombre de multiplications dansZ/pZ? (on l’Étudiera en fonction deretm).

Exercice 3.(8 points)Le type de donnÉes abstrait File. (Attention: ilne s’agit pas du mot anglais «ﬁle», qui lui, se traduit par «ﬁchier»). Ce type est destinÉ À reprÉsenter des ﬁles d’attente fonctionnant sur le mode “premier arrivÉ, premier servi” (First In, First Out); penser À une queue À la caisse d’un 1 supermarchÉ . Les primitives que l’on va considÉrer sont:

1.EstVide(F): teste si la ﬁle est vide, 2.Afficher(F): afﬁche les ÉlÉments de la ﬁle, en commenÇant par les ÉlÉments de tte (ceux qui sont entrÉs en premier), 3.DÉfiler(F): Ôte un ÉlÉment en tte de la ﬁleF, 4.Tte(F): renvoie la valeur de l’ÉlÉment en tte de la ﬁleF, sans le dÉﬁler, 5.Enfiler(x,F): ajoute l’ÉlÉmentxÀ la ﬁleF, 6.Vider(F): supprime les ÉlÉments de la ﬁleF.

On souhaite reprÉsenter le type File À l’aide d’une liste chanÉe.Pour cela, il est commode et efﬁcace de conserver un pointeur vers l’ÉlÉment de tte (le premier entrÉ, et donc le premier qui sortira), ainsi qu’un pointeur vers l’ÉlÉment de queue (le dernier À tre entrÉ dans la ﬁle). Ceci conduit aux dÉﬁnitions suivantes:

typedef struct cellule { int valeur; struct cellulelien; * } Cellule;

typedef struct file { CELLULE tete; * CELLULE queue; * } File;

Ecrire le code C correspondant aux primitives ci-dessus. Les champs d’une structure de type amenÉs À tre modiﬁÉs par certaines fonctions;dans ce cas on passera par rÉfÉrence le dÉsignant la ﬁle. Plus prÉcisÉmment, les fonctions auront les prototypes suivants:

int EstVide(File); void Afficher(File); int Tete(File); void Defiler(File ); * void Enfiler(int, File ); * void Vider(File ); *

File seront paramÈtre

1 Pour information: le mode de fonctionnement d’une PILE est “dernier arrivÉ, premier servi” (Last In, First Out).

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

Université de Limoges Faculté des Sciences et Techniques

Université de Limoges

Entier naturel

YouScribe

Le catalogue

Le service

Les conditions