Algo Part 1 [PDF]

Zitiervorschau

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