Scribd
Importer
12 vues2 pages

TD 3

Le document présente plusieurs exercices sur la conception d'algorithmes, notamment sur la séquence de Fibonacci, la recherche de maximum et minimum dans un tableau, la recherche de pics, l'évaluation de polynômes, et la recherche du k-ième plus petit élément. Chaque exercice propose des algorithmes naïfs et optimisés, souvent en utilisant la technique de diviser pour régner, ainsi que des analyses de complexité. Les exercices visent à renforcer la compréhension des algorithmes et de leur efficacité en termes de temps et d'opérations.

Transféré par

seggarikamal
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
12 vues2 pages

TD 3

Le document présente plusieurs exercices sur la conception d'algorithmes, notamment sur la séquence de Fibonacci, la recherche de maximum et minimum dans un tableau, la recherche de pics, l'évaluation de polynômes, et la recherche du k-ième plus petit élément. Chaque exercice propose des algorithmes naïfs et optimisés, souvent en utilisant la technique de diviser pour régner, ainsi que des analyses de complexité. Les exercices visent à renforcer la compréhension des algorithmes et de leur efficacité en termes de temps et d'opérations.

Transféré par

seggarikamal
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Conception d’algorithmes

TD3: Diviser pour régner

Exercice 1 : Encore Fibonnacci !


Le n-ième nombre de la séquence de Fibonacci Fn est défini comme : F0 = 0, F1 = 1 et ∀n ≥ 2,
Fn = Fn−1 + Fn−2 . Soit T (n) le nombre d’opérations élémentaires effectuez par un algorithme qui calcule
F (n).
a. Proposez un algorithme récursif pour ce problème de sorte que
√
Ω(( 2)n ) ≤ T (n) ≤ O(2n ).

b. Proposez un algorithme linéaire pour ce problème (c-à-d, T (n) = Θ(n)).


c. Notez que, pour n ≥ 2, Fibonnaci peut se récrire comme :
! ! !
Fn 1 1 Fn−1
=
Fn−1 1 0 Fn−2

Utilisez cette information pour proposer un nouvel algorithme pour le calcul du n-ième nombre de la
séquence de Fibonacci. Analysez la complexité de votre algorithme (c-à-d, nombre totale d’opérations
effectuées).

Exercice 2 : MaxMin d’un tableau


Soit A un tableau d’entiers de taille n. On désire calculer simultanément les valeurs maximum et minimum
contenus dans A.
a. Proposez un algorithme naïf qui exécute au plus 2n − 2 comparaisons entre éléments du tableau.
3
b. En utilisant la technique de diviser par régner, proposez un algorithme qui exécute au plus 2n −2
comparaisons entre éléments du tableau.

Exercice 3 : Recherche de pics


Soit A un tableau d’entiers de taille n. On dit que A[i] est un "pic" s’il n’est pas plus petit que ses voisins :
A[i − 1] ≤ A[i] ≥ A[i + 1]. On supposera que A[−1] = A[n] = −∞. Donc, un pic A[i] est un maximum
local. Par exemple, si A = [1, 2, 6, 5, 3, 7, 4], on a que A[2] = 6 et A[5] = 7 sont des pics. Notez que si l’on
permute les valeurs dans les positions 0 et 1 du tableau précédent A, on aura que A[0] = 2 est aussi un pic,
car −∞ ≤ 2 ≥ 1. Le but de cet exercice est de trouver un pic dans un tableau (n’importe lequel).
a. En remarquant qu’il existe toujours un pic, proposez un algorithme naïf utilisant O(n) comparaisons
des éléments du tableau.
b. Supposez que A[q + 1] > A[q] et pourtant A[q] n’est pas un pic, avec 0 < q < n − 1. Prouvez qu’il
existe un pic dans l’intervalle A[q + 1..n − 1].
c. En utilisant l’exercice précédent (3.b), proposez un algorithme diviser pour régner qui résoudre le
problème de pic en temps O(log n).

1
Exercice 4
Soit S un ensemble de n entiers et soit x un entier donné. Développez un algorithme de complexité
Θ(n log n) qui détermine s’il existent a, b ∈ S tels que a + b = x.

Exercice 5 : Évaluation d’un polynôme


Soit P (Z) = an−1 Z n−1 + an−2 Z n−2 + . . . + a1 Z + a0 un polynôme, où les ai sont des coefficients réels.
Soit x un nombre réel. On désire évaluer P dans le point x.
a. Concevoir un algorithme itératif pour ce problème qui utilise Θ(n2 ) multiplications.
b. Concevoir un algorithme récursif pour ce problème qui utilise Θ(n) multiplications. Justifier formelle-
ment votre réponse.

Exercice 6
On cherche le k-ième plus petit élément dans un tableau non trié.
a. Proposer un algorithme utilisant le principe diviser pour régner en s’inspirant de celui du tri rapide.
b. Faire la trace de l’algorithme sur le tableau A = {2, 4, 1, 6, 3, 5} pour k = 4.
c. Donnez la complexité (en nombre de comparaisons entre éléments du tableau) dans le pire de cas de
cet algorithme en fonction de la taille n du tableau.
d. Que se passe-t-il si, à chaque étape de l’algorithme, le tableau considéré est coupé en 2 sous-tableaux
de taille équivalentes ?

Vous aimerez peut-être aussi