Algorithmes (1)Algorithme: un ensemble fini de règles qui déterminent une suite d’opérations pour résoudre une classe de problèmes Exemple: l’algorithme d’Euclide pour trouver le plus grand commun diviseur (pgcd) de deux nombres entiers m et n (m > n) (i) diviser m par n: appelons r le reste (m = qn + r) (ii) si r = 0, alors pgcd(m,n) = n ; stop (iii) m ! n ; n ! r ; aller au pas (i) [l’écriture v ! e signifie que la variable v prendla valeur de l’expression e]Algorithmes (2)caractéristiques qu’un algorithme doit posséder:• finitude: un algorithme doit se terminer en un nombre fini de pasde temps• précision: chaque pas d’un algorithme doit être spécifié sansambiguïté• un algorithme possède des entrées et une ou plusieurs sorties• les opérations spécifiées par un algorithme doivent êtreélémentaires en ce sens qu’elles pourraient être faites avec dupapier et du crayon (si l’on avait suffisamment de temps et depatience)1Algorithmes (3)1. Etant donné un problème P, existe-t-il un algorithme A(P) pour ceproblème?2. S’il existe plusieurs algorithmes pour un problème P (soient A (P),1A (p), ..., A (P)), quels sont les critères qui nous permettent de2 nchoisir le plus adéquat ?En général, pour un problème P ayant un algorithme A(P), il existeun nombre éventuellement infini d’instances, càd de cas spécifiques.Exemple : tri d’une liste L = ( a , a , ..., a )1 2 ntrier L = ( 12, 18, 3, 98, -10, 0 )1L = ( -7, 9, ...