Scribd
Importer
129 vues8 pages

Correction Algorithmique

Ce document décrit plusieurs algorithmes de recherche et de tri ainsi que leur complexité. Il présente également différentes structures de données et leurs avantages et inconvénients. Enfin, il aborde des sujets comme les listes chainées, les fonctions récursives et itératives.

Transféré par

joel
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
129 vues8 pages

Correction Algorithmique

Ce document décrit plusieurs algorithmes de recherche et de tri ainsi que leur complexité. Il présente également différentes structures de données et leurs avantages et inconvénients. Enfin, il aborde des sujets comme les listes chainées, les fonctions récursives et itératives.

Transféré par

joel
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

Correction algorithmique

1. Définition …

2. Algorithme recherche dichotomique

Complexité : le calcul de la complexité de la version itérative de la recherche


dichotomique peut être assimilé à celle de la hauteur d’un arbre binaire de
recherche qui s’effectue en O(log2n) car on effectue des divisions successives de
la taille du tableau.
3. Algorithme tri insertion

Complexité :
Evaluons la complexité :
i=2 => 2 comparaisons
i=3 => 3 comparaisons
.
.
.
I=N => N comparaison

n
n (n−1)
∑ i= 2
=¿ O(n ²)
i=2

4. Avantage et inconvénients Tableaux, liste chainées, table de hachage


Structure Avantages Inconvénient
Tableaux  Facile à manipuler  Taille statique
 Accès direct aux
données
Liste  Taille dynamique  Manipulation complexe
chainée  Accès au donnée couteux en
termes de temps
Table de  Accès direct au  Risque de collision
hachage données  Taux de remplissage bas

5. Déclaration des structures 


 Liste doublement chainée

 Liste circulaire

6. Algorithme récursif pour calculer C np

{
C np= 1 sip p=0pou p=n
C n−1+C n+ 1 sinon
Complexité :
Evaluons la complexité :
Sachant que la complexité d’un algorithme récursif se calcule selon la formule
aT ( nb )+ f (n) la complexité est
Pour a = 2 et b=1 et f (n) = O(1)
On a
T ( n )=T ( n−1 ) +T (n+1)

T ( n ) ≅ 2T ( n+1 )

7. Fonction PGCD
 Version récursive

 Version itérative
8. …

9. Ecriture des primitives

 Empiler

 Dépiler

 Enfiler
 Défiler

[Link] des complexités

=O ( 2 )
3 n−2 n
3 n +2

4 n3 +12=O( n3)

n2 log ( 5 n4 )=O ( n2 logn )

0,5 n2−10 n−60=O(n2 )

Classement : O ( n2 ) , O ( n2 logn ) ,O ( n3 ) , O ( 2n )
Exercice : Tri Fusion

Complexité :

T ( n )=2 T ( n2 )+ n
a=2 , b=2
a
logb
f ( n )=n =T ( n )
a
log b
¿>O( n logn)

¿>O(nlogn)

Exercice 2 : Matrice de Toeplitz


1. Oui
Démonstrations :
Supposons 2 matrices de toeplitz avec a ij=a(i−1 , j−1)

( ) ( )
2 4 1 1 3 1
A= 8 2 4  ; A= 7 1 3
6 8 2 0 7 1

( )
3 7 2
C= A+ B= 15 3 7
6 15 3

2. Algorithme d’addition de 2 matrices de toeplitz en O(n)


3. Produit de deux matrice toeplitz

Vous aimerez peut-être aussi