Scribd
Importer
41 vues1 page

Complexité des Algorithmes en TP

Ce document présente plusieurs exercices sur la complexité des algorithmes, notamment sur les nombres de Fibonacci, la puissance d'un nombre et le problème des tours de Hanoi.

Transféré par

Rayane Ben
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
41 vues1 page

Complexité des Algorithmes en TP

Ce document présente plusieurs exercices sur la complexité des algorithmes, notamment sur les nombres de Fibonacci, la puissance d'un nombre et le problème des tours de Hanoi.

Transféré par

Rayane Ben
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

USTOMB, Dép.

D’Informatique, L2 2021-2022
Algorithmique et Structures de Données 3

TP1 Complexité des Algorithmes

[Link] en pratique de l’exercice 1 de la fiche de TD.

[Link] l’exercice 2 et l’exercice 3 de la fiche de TD en pratique pour :

a/Estimer et afficher la complexité des programmes en terme de nombre d’itérations effectuées.


b/Tracer les courbes de complexité.

3. Les nombres de Fibonacci sont calculés par la formule de récurrence ci-dessous, donner le code de la fonction
récursive correspondante. Vu le nombre d’appels récursifs nécessaires pour n donné, peut-on faire mieux ?

𝐹0 = 0 𝑒𝑡 𝐹1 = 1
𝐹𝑛 = {
𝐹𝑛−1 + 𝐹𝑛−2 𝑛>1

[Link] une fonction récursive puissance(float x,int n) permettant de calculer 𝑥 𝑛 selon la formule de récurrence
suivante :

𝑎) 𝑥 𝑛 = { 𝑥0 = 1 𝑛=0
𝑥 . 𝑥 𝑛−1 𝑛>0

Selon l’algorithme intuitif a) la complexité est T(n) = O(n).

Montrer qu’il est possible de faire mieux que la méthode naïve pour réduire la complexité.

𝑛=0 𝑥0 = 1
𝑛
𝑏) 𝑥 = {𝑛 > 0 𝑒𝑡 𝑝𝑎𝑖𝑟 𝑥 𝑛 = 𝑥 𝑛/2 ∙ 𝑥 𝑛/2
𝑛 > 0 𝑒𝑡 𝑖𝑚𝑝𝑎𝑖𝑟 𝑥 𝑛 = 𝑥 ∙ 𝑥 (𝑛−1)/2 ∙ 𝑥 (𝑛−1)/2

Selon l’algorithme b) T(n) = O(log2 n).

5. Implémenter l’algorithme des tours de Hanoi. Vérifier que la complexité en temps pour résoudre le problème
est : T(n) = 2n – 1 n≥0 ( n est le nombre de disques)

Vous aimerez peut-être aussi