1. Prenons un nombre réel x, un entier naturel n, et un tableau contenant un n nombres réels. Considérons le
algorithme suivant:
ALG (x, a, n)
1. Y ← 1
2. z 0 ←
3. pour i = 1, n fais
4. z ← z + a [i] * y
5. y ← y*x
6. retour z
1. Déterminer le nombre de multiplications réelles requises pour calculer ALG (2, [1, -2,1,3, -2, -1], 6). Qu'est ce que cet
algorithme de calcul?
b. Montrer que cet algorithme est correct (selon l'objectif fixé à un)
c. Quelle est la complexité de cet algorithme?
ré. Développer une version améliorée de cet algorithme qui utilise seulement la moitié du nombre de multiplications réelles
utilisée par ALG. Quelle est la complexité de cette algorithme amélioré?
2. Supposons que vous travaillez pour une entreprise qui développe des logiciels pour le traitement algébrique. Votre tâche est de
élaborer un programme pour faire des calculs avec des ensembles de nombres entiers. Les ensembles peuvent avoir jusqu'à 10000 éléments où
un élément est un nombre entier dans la plage de -108
*... 108
.
un. Il est important de concevoir une représentation pour les jeux afin de permettre une mise en œuvre efficace des opérations de réglage.
Supposons que vous choisissez pour représenter un ensemble de nombres entiers comme une paire composée de: (i) un nombre entier qui représente la
nombre d'éléments de réglage; (ii) une liste chaînée de plus en plus triés qui stocke les éléments de décor, avec le plus bas
élément stocké à la tête de la liste. Votre tâche est de concevoir O (m + n) algorithmes pour calculer le syndicat et la
intersection de deux ensembles avec m et n éléments.
b. Afin de rendre votre programme à la disposition des autres membres de la société, vous devez mettre en œuvre des ensembles comme
un type de données abstrait. Développer une application de C d'un type de données abstrait qui représente ensembles d'entiers comme
suggérée à l'étape a). Votre mise en œuvre procurent les opérations suivantes: construire un ensemble vide, union
de deux ensembles, intersection de deux ensembles, et en ajoutant un élément à un ensemble.
Partager