Théorie de la programmation - TDA et structures de données 2005 Génie Informatique Université de Technologie de Belfort Montbéliard

Crenaud

Description

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Théorie de la programmation - TDA et structures de données 2005. Retrouvez le corrigé Théorie de la programmation - TDA et structures de données 2005 sur Bankexam.fr.

Sujets

• 2005

Informations

• Publié par: bankexam
• Publié le: 18 août 2008
• Nombre de lectures: 46
• Langue: Français

Extrait

UTBM le 9 mai 2005

LO42 - médian P2005 - page1/2
Médian – LO42


Les documents de cours et TD ne sont pas autorisés (la copie ou les idées du voisin non plus). Le barème est
indicatif.
Le soin donné à la rédaction sera évalué. Toute réponse devra être claire et justifiée (toute ambiguïté sera mal
interprétée). L’élégance de la solution sera jugée.
Sauf indication contraire, dans le cas d’algorithmes les réponses doivent être rédigées en pseudo code.



1) La récursivité, dominer et effacer, vous pourrez ! (8p)

Ecrivez une fonction récursive permettant de calculer la valeur de la fonction, où i est un entier positif et n un entier
quelconque avec :

P
i
(n) = ( P
i-1
(n -1) + P
i-2
(n -1) ) / n pour n > 0
P
i
(n) = ( P
i-1
(n+1) + P
i-2
(n+1) ) / n pour n < 0
Avec
P
i
(0) = 1 pour i > 1
P
0
(n) = 1 pour n ‡ 0
P
0
(n) = -1 pour n < 0
P
1
(n) = n pour n ‡ 0
P
1
(n) = -n pour n < 0

Réduisez à 2 le nombre d’appels récursifs en utilisant une variable locale.
Transformez votre fonction de manière à pouvoir utiliser la méthode générale d’élimination de la récursivité.
Eliminez les paramètres de votre algorithme et optimisez si possible, avec justifications.

(Question subsidiaire : Eliminez la récursivité de votre algorithme.)


2) La Complexité, peur, jamais ne vous fera ! (5p)

Voici deux fonctions récursives :

Fonction fr1Exp(t : réel) : réel ;
Début
Si abs(t) < epsilon Alors fr1Exp ‹ t ;
Sinon fr1Exp ‹ sqr(fr1Exp(t/2)) + 2 * fr1Exp(t/2) ;
Fsi ;
Fin ;

Fonction fr2Exp(t : réel) : réel ;
Var réel y ;
Début
Si abs(t) < epsilon Alors fr2Exp ‹ t ;
Sinon y ‹ fr2Exp(t/2) ;
fr2Exp ‹ sqr(y )+ 2 * y ;
Fsi ;
Fin ;
Où sqr est la fonction d’élévation au carré.
Déterminez leurs complexités. Quelle conclusion pouvez-vous en tirer ?

On posera k \ 2
k
est la plus petit entier puissance de 2 telle que abs(t) < epsilon * 2
k
. Donc $ a ˛ [0, 1[ vérifiant
abs (t) = a * epsilon * 2
k



3) Toujours, la preuve vous rechercherez ! (7p)
On considère les trois programmes suivants :
P
1
:
debut
z ‹ 0; u ‹ 0;
tantque (u <= x) faire
u ‹ u + (2 * z) + 1; z ‹ z + 1
ftq ;
fin UTBM le 9 mai 2005

LO42 - médian P2005 - page2/2
P
2
:
debut
z ‹ 0; u ‹ 0;
tantque (u <= x) faire
z ‹ z + 1; u ‹ u + (2 * z) + 1
ftq ;
fin
P
3
:
debut
z ‹ 0; u ‹ 1;
tantque (u <= x) faire
z ‹ z + 1; u ‹ u + (2 * z) + 1
ftq ;
fin
1. Pour chaque programme P
i
(i ˛ {1,2,3}), déterminez si l'assertion A
i
suivante est vraie :

{ x ‡ 0} P
i
{z*z £ x < (z+1)*(z+1)}
Lorsque A
i
est fausse on le montrera en exécutant P
i
sur une donnée x particulière ; Lorsque A
i
est vraie on le
montrera en fournissant un invariant de la boucle tantque (on ne demande pas ici de preuve formelle).
2. Choisissez un i ˛ {1,2,3} tel que A
i
est vraie et donnez une preuve formelle de A
i
; montrez que le programme
P
i
est un algorithme totalement correct pour calculer la fonction x fi
x
(où x ˛ I N).

3. Que pensez-vous du programme suivant ?
P
4
:
debut
z ‹ 0; u ‹ 0;
tantque (u <> x) faire
z ‹ z + 1; u ‹ u + (2 * z) - 1
ftq ;
fin