28 0 2MB
Cours Algorithmique avancée Structures des données Algorithmique
Hafidi Imad
ENSAK
Problème
INFORMATIQUE =
Conception Analyse Expression=Algorithme Exécution Utilisation
2
Introduction Qu’est-ce qu’un algorithme ? Algorithmique Un algorithme est une procédure de calcul bien définie qui prend en entrée une valeur, ou un ensemble de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc une séquence d’´etapes de calcul qui transforment l’entrée en sortie. • • •
On peut considérer un algorithme comme un outil permettant de résoudre un problème de calcule bien spécifié. L’ énoncé du problème spécifie, en termes généraux, la relation désirée entre l’entrée et la sortie. L’algorithme décrit une procédure de calcul spécifique permettant d’obtenir cette relation entrée/sortie.
3
• Exemple d’un problème fréquent dans la pratique : Trier une suite de nombre dans l’ordre croissant
Définition formelle du problème de tri :
4
Terminologie Algorithme correct
Un algorithme est dit correct si, pour chaque instance en entrée, il se termine en produisant la bonne sortie. Un algorithme correct résout le problème donné.
• Un algorithme incorrect risque de ne pas se terminer pour certaines instances en entrée, voire de se terminer sur une réponse autre que celle désirée.
5
Terminologie Algorithme optimal Un algorithme est dit optimal s’il est correct et s’il produit la bonne sortie, pour un problème donné, en utilisant le minimum de ressources possibles.
• Un algorithme optimal doit utiliser le minimum de mémoire machine et fournir la bonne sortie le plus rapidement possible. • La mesure habituelle utilisée pour évaluer l’efficacité d’un algorithme est la vitesse d’exécution. 6
Double problématique de l’algorithmique En algorithmique, pour résoudre un problème donné, il faut : • Trouver une méthode de résolution (un algorithme correct) ; • Trouver une méthode efficace (un algorithme optimal).
Savoir résoudre un problème est une chose et le résoudre efficacement en est une autre !
7
Méthodologie générale de programmation
8
Méthodologie générale de programmation
9
Complexité et optimalité • La théorie de la complexité algorithmique s’intéresse à l’estimation de l’efficacité des algorithmes. • Elle s’attache à connaître la difficulté d’une réponse par algorithme à un problème posé de façon mathématique.
Question de base Entre différents algorithmes réalisant une même tâche, quel est le plus rapide et dans quelles conditions ?
• La théorie de la complexité vise à savoir si la réponse à un problème peut être donnée très efficacement, efficacement ou au contraire être inatteignable en pratique. • Elle se fonde sur une estimation théorique des temps de calcul et des besoins en mémoire informatique.
10
Complexité et optimalité • • •
Dans les années 1960 et au début des années 1970, on a commencé à découvrir des algorithmes fondamentaux . . . Absence de moyens fiables pour mesurer l’efficacité de ces algorithmes . . . Par exemple, on se contentait de dire :
Cet algorithme se déroule en 6 secondes avec un tableau de 50 000 entiers choisis au hasard en entrée, sur un ordinateur IBM 360/91. Le langage de programmation PL/I a été utilisé avec les optimisations standards. • •
Une telle démarche rendait difficile la comparaison des algorithmes entre eux. Une telle mesure est dépendante du : – – – – –
processeur utilisé ; les temps d’accès à la mémoire vive et de masse ; le langage de programmation ; le compilateur utilisé ; etc. 11
Complexité d’un algorithme Définition La complexité d’un algorithme est la mesure du nombre d’opérations fondamentales qu’il effectue sur un jeu de données. La complexité est exprimée comme une fonction de la taille du jeu de données.
• La complexité algorithmique est un moyen d’évaluation du coût d’un algorithme. • Cette complexité mesure le nombre d’opérations élémentaires et le coût mémoire. • Cela permet de connaître le type de croissance en fonction de la taille des données.
12
Formalisation mathématique • On évalue la complexité d’un algorithme T(n) (le nombre de ces opérations élémentaires) en fonction de la taille de la donnée d’entrée n. – Si n est la taille de la donnée d’entrée, – on évalue la complexité de l’algorithme en calculant une fonction T(n).
Notions Dn l’ensemble des données de taille n ; T(d) le coût de l’algorithme sur la données d.
13
Formalisation mathématique
14
Formalisation mathématique
15
Formalisation mathématique
16
Exemple
17
Exemple
18
Exemple
19
Ordre de grandeur
20
Classes de complexité et algorithme optimal
21
Récursivité
22
Exemple
23
Exemple
24
Exemple introductif
25
Algorithmique
26
Modèle général
27
Modèle général
28
Principe et dangers de la récursivité
29
Problèmes récursifs
30
Transformation
31
32
33
Introduction
34
Différences entre pile & file
35
36
37
Manipulation des piles
38
39
40
Manipulation des files
41
42
43
Pointeur
44
Exemple introductif
45
46
47
Définition et terminologie
48
49
Tableau VS. Liste Avantages
50
Tableau VS. Liste Inconvénients
51
Manipulation des Listes
52
53
Structure
54
Ecriture algorithmique
55