Scribd
Importer
28 vues1 page

TD1 Algo Complexité

Le document présente une série d'exercices sur la récursivité et la complexité algorithmique, incluant des démonstrations par récurrence et des résolutions d'équations. Il aborde des algorithmes tels que le tri par insertion et la recherche dichotomique, en demandant des versions récursives et des analyses de complexité. Enfin, il traite de concepts de notation asymptotique et de calcul de complexité pour des procédures spécifiques.

Transféré par

Julio Tagne tegueo
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 DOCX, PDF, TXT ou lisez en ligne sur Scribd
28 vues1 page

TD1 Algo Complexité

Le document présente une série d'exercices sur la récursivité et la complexité algorithmique, incluant des démonstrations par récurrence et des résolutions d'équations. Il aborde des algorithmes tels que le tri par insertion et la recherche dichotomique, en demandant des versions récursives et des analyses de complexité. Enfin, il traite de concepts de notation asymptotique et de calcul de complexité pour des procédures spécifiques.

Transféré par

Julio Tagne tegueo
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 DOCX, PDF, TXT ou lisez en ligne sur Scribd

Ecole Nationale Supérieure Polytechnique

Département de Génie Informatique


BP 8390 Yaoundé

TD ALGORITHMIQUE - 3GI
Récursivité et Complexité
Exercice 1
1. On donne l’équation suivante : T ( 1 ) =1 et ∀ n>1 ,T ( n )=2 ×T ( n−1 )+1. Démontrer par
récurrence que T ( n )=2n−1 pour tout n ≥ 1
2. Résoudre par substitution l’équation T ( 1 ) =1, T ( n )=T ( n2 )+ log ⁡(n)
Exercice 2.
Le tri par insertion peut être exprimé sous la forme d’une procédure récursive de la
manière suivante. Pour trier A[1 ... n], on trie récursivement A[1 ... n − 1] puis on
insère A[n] dans le tableau trié A[1 ... n-1].
- Proposer une version de cet algorithme.
- Écrire une récurrence pour le temps d’exécution de cette version récursive du tri par
insertion et donner sa complexité.
Exercice 3
En reprenant le problème de la recherche dans une séquence, observez que, si la
séquence est triée, on peut comparer le milieu de la séquence avec l’élément
recherché et supprimer la moitié de la séquence pour la suite des opérations. La
recherche dichotomique est un algorithme qui répète cette procédure, en divisant
par deux à chaque fois la taille de la partie restante de la séquence. Écrire le pseudo
code récursif, de la recherche dichotomique. Expliquer pourquoi le temps d’exécution
de la recherche dichotomique, dans le cas le plus défavorable, est O(lg n).
Exercice 4.
3.1. Montrer que : f =Θ( g )⇒ f =Ο ( g )
3.2. Montrer que : f =Ο( g )∧f =Ω( g )⇒ f =Θ(g )
Exercice 5
Calculer la complexité f(n) de la fonction suivante
Procedure MYSTERY ;
var i,j,k : integer;
Begin
for i:= 1 to n-1 do
for j:=i+1 to n do
for k:=1 to j do {instruction}
end MYSTERY;
On supposera que instruction s’exécute en un temps constant c. Préciser la mesure
de la complexité choisie. En déduire l’ordre asymptotique de f(n).
Exercice 6.
Démontrer :
5.1. f =Ο( g )⇒ λf =Ο( g )
5.2. f =Θ( g )⇒ λf =Θ( g )
Exercice 7
Donner les rangs n pour lesquels l’une des deux quantités 2 nnou n2 n est la plus grande.

Vous aimerez peut-être aussi