cours sur les algorithmes

Denis Rochat

Description

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, ...

Informations

• Publié par: Enya
• Nombre de lectures: 70
• Langue: Français

Extrait

1

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

prend

la 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 pas

de temps

•

précision:

chaque pas d’un algorithme doit être spécifié sans

ambiguï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 du

papier et du crayon (si l’on avait suffisamment de temps et de

patience)

2

Algorithmes

(3)

En général, pour un problème

P

ayant un algorithme

A(P)

, il existe

un nombre éventuellement infini d’instances, càd de cas spécifiques.

Exemple : tri d’une liste L = ( a

1

, a

2

, ..., a

n

)

trier

L

1

= ( 12, 18, 3, 98, -10, 0 )

L

2

= ( -7, 9, 12, 338, 8, 140 ) ...

"

un algorithme doit fonctionner correctement sur n’importe quelle

instance d’un problème P

1. Etant donné un problème

P

, existe-t-il un algorithme

A(P)

pour ce

problème?

2. S’il existe plusieurs algorithmes pour un problème

P

(soient

A

1

(P)

,

A

2

(p)

, ...,

A

n

(P)

), quels sont les critères qui nous permettent de

choisir le plus adéquat ?

Algorithmes

(4)

Définition :

Informellement, on appelle taille d’une instance un nombre

qui définit le nombre de composantes de l’instance

Exemple :

Si une liste à trier contient

N

éléments, la taille de l’instance

du problème de tri sera

N

Exemple :

Si un graphe contient

N

sommets, la taille de l’instance d’un

problème de graphes telle que la recherche du plus court

chemin entre deux sommets sera égale à

N

Pour les algorithmes numériques (multiplications, divisions, ...), la

taille s’exprime à l’aide de la grandeur des nombres, càd le nombre

de chiffres nécessaires pour représenter les nombres impliqués, celui-ci

étant bien sûr proportionnel au logarithme du nombre.

3

Algorithmes

(5)

Pour juger de l’exactitude d’un algorithme

A(P)

on doit aussi

introduire la notion de

domaine de définition

qui représente le domaine de validité des valeurs d’entrée de

l’algorithme.

Exemple : L’algorithme d’Euclide pour trouver le

pgcd(m,n)

fonctionne si

m

et

n

sont deux entiers positifs arbitraires;

il n’est pas défini pour les valeurs négatives ou pour les

nombres réels.

Recherche linéaire sur un tableau

problème : décider si un élément donné est contenu ou non dans un

tableau donné

L[N-1]

...

L[2]

L[1]

L[0]

L =

int recherche(int a[],

int elem,

int n){

for (int i = 0;

i < n;

i++)

if (elem == a[i])

return i;

return -1;

}

dans le cas le plus défavorable :

n

incrémentations,

n

comparaisons

"

T(N) = O(N)

4

Recherche linéaire avec ‘sentinelle’

c’est une technique servant à simplifier le test de boucle et à

gagner aussi un peu de temps :

int recherche(int a[], int elem, int n){

a[n] = elem;

int i = 0;

while (elem != a[i])

i++;

if (i < n)

return i;

else

return -1;

}

"

T(N) = O(N)

, car le nombre d’opérations est le même

(

N

comparaisons et

N

incrémentations), mais le test de

la boucle coûte environ 1/2

on assume que le tableau ait une cellule

supplémentaire à la fin dans laquelle on

stockera x, l'élément à chercher

Recherche par dichotomie

(1)

Aebischer

Arlettaz

Balmer

Béguin

Cartier

Darbellay

Dietler

Felber

Fournier

Gaillard

Hofstetter

Jaccard

Keller

Maignan

Merbach

Panese

Powell

Rappaz

Terrier

? Arlettaz ?

? Arlettaz < Gaillard ?

? Arlettaz < Cartier ?

? Arlettaz < Balmer ?

? Arlettaz = Arlettaz ?

oui !!!

complexité dans le pire

des cas :

O(log(N))

13

10

12

10

10

9

7

10

6

3

10

2

2

10

1+log(N)

N

5

Recherche par dichotomie

(2)

L =

#

N/2

$

si

x < L(

#

N/2

$

)

alors chercher

dans cette moitié

int rech_bin_rec(int a[], int elem,

int bas, int haut){

int milieu;

if (bas > haut)

return -1;

else {

milieu = (bas + haut) / 2;

if (elem < a[milieu])

return rech_bin_rec(a, elem, bas, milieu-1);

else if (elem > a[milieu])

return rech_bin_rec(a, elem, milieu+1, haut);

else return milieu;

}

}

si

x > L(

#

N/2)

alors chercher

dans cette moitié

Recherche par dichotomie

(3)

à chaque itération

rech_bin

trouve

x

ou se rappelle elle-même sur un tableau

ayant une taille réduite de moitié si la taille initiale est

N

, le tableau ne peut pas être

divisé plus de

log

2

(N)

fois avant de trouver

x

ou d’aboutir à une liste vide

"

complexité :

O(log

2

(N))

int rech_bin(int a[], int elem, int n){

int bas, haut, milieu;

bas = 0;

haut = n - 1;

while (bas <= haut){

milieu = (bas + haut) / 2;

if (elem < a[milieu])

haut = milieu - 1;

else if (elem > a[milieu])

bas = milieu + 1;

else

return milieu;

}

return -1;

}

version

itérative