Les algorithmes

Complexes

Algorithmes

1

Prof : M.QBADOU

Complexes

Algorithmes

2

 Etudier la complexité des algorithmes :

• Evaluation théorique et calcul asymptotique

• Mesure expérimentale

 Etudier des algorithmes de recherches optimaux

• Algorithmes de Recherche de complexité Log(N )

• Etudier les techniques d’hachage de données

Objectifs

Prof : M.QBADOU

Complexes

Algorithmes

3

Chap I : Analyse et complexité des algorithmes

Sommaire

Prof : M.QBADOU

 Introduction - Exemple de problème

 Méthodes de calcul

• Méthode théorique

• Méthode expérimentale

 Complexités représentatives – cas Meilleur, Cas Pire, Moyenne

 Notation de Landau – Analyse asymptotique

 Classes de complexité

 Applications

Chap II : Etude des algorithmes de recherche avancée

 Rappel des algorithmes naïfs

 Les structures d’arbres – Définition, représentations- Manipulations

Complexes

Algorithmes

4

Sommaire

Prof : M.QBADOU

 Arbres binaires de recherche

• Arbres de recherche AVL

• Arbres de recherche Rouge et Noir (bicolore)

 Table de Hachage

• Fonction Hachage

• Résolution des collisions

• Modification de la taille de la table

 Applications

Complexes

Algorithmes

5

Chapitre II :

Analyse et complexité

des algorithmes

Objectifs :

Mesurer les ressources (temps, mémoire) utilisées par un

programme, ou nécessaires à la résolution d’un problème Prof : M.QBADOU

Complexes

Algorithmes

6

I. Introduction

1. Position du problème

Question

soient A1 et A2 deux algorithmes pour le même problème.

Comment faire le choix de l’une des Solutions A1 et A2?

Réponse

Mesurer le temps T1(A1) et le temps T2(A2) pour les mêmes

données et pour différentes configurations et choisir le plus rapide.

Question

Comment Mesurer le temps d’un algorithme A ?

Réponse

Procéder selon une méthode de mesure

Chap II : Analyse et complexité des algorithmes

Prof : M.QBADOU

Complexes

Algorithmes

7

Remarques :

On distingue aussi la notion de complexité spatiale. Elle correspond

à la capacité mémoire exigée par une solution algorithmique.

Cette complexité est moins importante que la complexité

temporelle. La suite du cours sera consacrée à cette dernière. En

effet la complexité temporel reflète indirectement la complexité

spatiale

2. Méthodes de mesure de la complexité Temporelle

Pour évaluer la complexité temporelle d’un algorithme A on distingue

deux démarches possibles :

• Méthode expérimentale (Empirique)

• Méthode Théorique (Mathématique)

Chap II : Analyse et complexité des algorithmes

Prof : M.QBADOU

Complexes

Algorithmes

8

II. Méthode expérimentale

1. Principe

Cette méthode consiste à :

• Programmer l’algorithme dans un langage (choix du langage ?)

• Exécuter le programme pour des taille de données différentes

• évaluer le temps pour chaque exécution.

2. Inconvénients

cette méthode très limitée pour les raisons suivantes :

• Nécessite de programmer l’algorithme

• La mesure dépend de la machine utilisée, de l’environnement

d’exécution, de l’environnement de programmation choisi

...