Introduction à l’Algorithmique

IPA – Catherine Faron Zucker

 Introduction à l'Algorithmique

Algorithme

Validité d'un algorithme
 Preuve de sa correction

Analyse d'un algorithme
 Complexité d'un algorithme

Structures de données

Conception d'un algorithme

IPA – Catherine Faron Zucker 2

 Algorithme

Permet de résoudre un problème donné
ex: Trier une liste de noms par ordre alphabétique


Procédure de calcul bien définie
Séquence d'instructions élémentaires

 termine en un temps fini

 prend une ou des valeur(s) en entrée
 donne une ou des valeur(s) en sortie

IPA – Catherine Faron Zucker 3

 Exemple

Exemple de problème à résoudre
Comment trier une liste d'élèves par ordre alpha?


Input: liste non triée

Output: liste triée

Algo: ???

IPA – Catherine Faron Zucker 4

 Types de problèmes

Tris d'éléments d'une liste

Recherche d'un élément

Calcul sur des chaînes (caractères, nombres, bits, ...)

Problèmes de graphes

Problèmes combinatoires

Problèmes géométriques

Problèmes numériques


Algorithmes exacts / d'approximation
IPA – Catherine Faron Zucker 5
 Algorithme et Programme

Un algorithme est implémenté dans un
langage de programmation


Un même algorithme peut être implémenté
dans différents langages (Java, C, Python,
Caml, ...)


Pseudo-code

IPA – Catherine Faron Zucker 6

 Validité d'un algorithme

Précondition

doit être vérifiée avant un traitement donné,

garantit que la possibilité de déroulement du traitement.

Postcondition

doit être vérifiée après le déroulement du traitement,

garantit que le traitement a bien permis de réaliser ce
pourquoi il a été réalisé.

Invariant

condition qui est toujours vraie,

caractérise l'état interne de tout ou partie d'un algo.

IPA – Catherine Faron Zucker 7

 Analyse d'un algorithme

Complexité: mesure de son efficacité
 Taille mémoire nécessaire à son exécution
 Temps d'exécution nécessaire

dans le meilleur des cas

dans le pire des cas

en moyenne

Exemple: recherche d'un élément dans une liste?

Exemple: recherche du plus grand élément d'une liste?

IPA – Catherine Faron Zucker 8

 Efficacité d'un algorithme

Temps d'exécution
 fonction de la taille des données en entrée
choix du bon paramètre

taille d'une liste, degré d'un polynôme

taille d'une matrice?

nombre de noeuds, profondeur, largeur d'un graphe?

nombre de mots d'un fichier ou nombre de caractères?
 fonction du nombre de fois où une opération de
base est répétée dans l'algorithme

IPA – Catherine Faron Zucker 9

 Efficacité d'un algorithme

Temps d'exécution: T(n)  C(n)  t
 C(n) nombre de fois où l'opération de base de
l'algorithme est exécutée
 t temps d'exécution de cette opération de base

C(n) = ½  n (n-1) = ½  n2 - ½  n


Ordre de grandeur: C(n) n2

IPA – Catherine Faron Zucker 10

 Efficacité d'un algorithme

Classes de complexité

1 log n n n log n n2 n3 2n
n!


Notations asymptotiques:
 O(g(n))
 Ω(g(n))
 θ(g(n))
IPA – Catherine Faron Zucker 11
 Structure de Données

Moyen de stocker et organiser les données
d'un algorithme
 accès aux données
 modification, mise à jour des données


Tableaux, listes chaînées

Piles, files

Sets et Maps

Graphes, arbres, arbres binaires de recherche
IPA – Catherine Faron Zucker 12
 Conception d'un algorithme

Stratégie de résolution d'un problème


Approche itérative
 répéter jusqu'à obtention du résultat souhaité


Approche récursive
 diviser pour régner

IPA – Catherine Faron Zucker 13

 Structures de contrôle

Structures de contrôle conditionnelle
 Si cond Alors instr FinSi
 Si cond Alors instr sinon instr FinSi

(imbrications possibles)


Structures de contrôle itératives
 TantQue cond Faire instr FinTantQue
 variantes

(imbrications possibles)

IPA – Catherine Faron Zucker 14

 Itérations
int i = 0;
while(i<10){
System.out.println(“Coucou”);
i +=1;
}

IPA – Catherine Faron Zucker 15

 Itérations
int i = 0;
do{
System.out.println(“Coucou”);
i +=1;
}while(i<10);

for (i=0; i<10; i++) System.out.println(“Coucou”);

IPA – Catherine Faron Zucker 16

 Calcul du pgcd
PGCD(a,b)
n <- a; m <- b;
TantQue m != 0 Faire
r <- n mod m
n <- m
m <- r
FinTantQue
retourner n

IPA – Catherine Faron Zucker 17

 Validité d'une boucle

Invariant de boucle
 Initialisation

Montrer que I est vrai avant d'entrer dans la boucle
 Conservation

Montrer que si C et I sont vrais, alors après la liste
d'instructions, I est encore vrai.
 Terminaison

On en déduit que (I et non C) est vrai à la sortie de la
boucle (si la boucle termine).

IPA – Catherine Faron Zucker 18

 PGCD(a, b)
n <- a; m <- b;
{ Invariant : pgcd(a,b)=pgcd(n,m) et n>=0 et m>=0 }
TantQue m != 0 Faire
r <- n mod m
n <- m
m <- r
{ pgcd(a,b)=pgcd(m,n) et m>=0 et n>0 }
FinTantQue
// pgcd(a,b)=pgcd(n,m) et n>=0 et m=0
// Donc n=pgcd(a,b)

IPA – Catherine Faron Zucker 19

 Fact(n)
i ← 1; fact ← 1
{ Invariant: fact = i ! et i ≤ n }
TantQue i < n Faire
i←i+1
fact ← fact * i
{ Invariant: fact = i ! et i ≤ n }
FinTantQue
(fact = i ! et i ≤ n ) et non(i<n)
retourner fact

IPA – Catherine Faron Zucker 20

 Structures de Données

Moyen de stocker et organiser les données
d'un algorithme
 accès aux données
 modification, mise à jour des données


Tableaux, listes chaînées

Piles, files

Sets et Maps

Graphes, arbres, arbres binaires de recherche
IPA – Catherine Faron Zucker 21
 Tableaux

suite ordonnée d'éléments de taille fixe
int [] tableau = new int[10];

premier élément : tableau[0]

dernier élément :
tableau[tableau.length -1]

i ième élément : tableau[i-1]

init./modif. d'un élément: tableau[i] = 3;

IPA – Catherine Faron Zucker 22

 Tableaux

valeur tableau[i] / indice i

recherche du (des) élément(s) vérifiant une
certaine propriété

vérification de la présence ou l'absence d'une
certaine valeur dans le tableau

recherche de l'indice dans le tableau d'une
valeur donné

tri du tableau selon un certain critère
IPA – Catherine Faron Zucker 23
 Matrices

Tableau de tableaux :
int [][] matrice = new int[10][15];


élément en ligne i et colonne j :
matrice[i][j]


Matrice carrée :
int [][] matriceCarree = new int[7][7];

IPA – Catherine Faron Zucker 24

 Listes

suite ordonnée d'éléments de taille variable
ArrayList<Integer> liste;
liste = new ArrayList<Integer>();


Ne peuvent contenir que des objets


premier élément : liste.get(0)

dernier élément : liste.get(liste.size()-1)

i ième élément : liste.get(i-1)
IPA – Catherine Faron Zucker 25
 Listes

ajout d'un élt: liste.add(new Integer(3));

modif d'un élt: liste.set(i,new Integer(4));

suppression d'un élt: liste.remove(i);


mêmes algos que sur les tableaux

IPA – Catherine Faron Zucker 26

 Piles et Files

Ordonnancements particuliers des éléments
d'un tableau ou d'une liste


Pile : empiler/dépiler des éléments
 statique ou dynamique selon qu'on utilise un

tableau ou une liste


File : enfiler /défiler des éléments
 implémentation par liste plus simple

IPA – Catherine Faron Zucker 27

 Piles
public class Pile{
private Object[] table;
private int hauteur;
public void empiler(Object o)
{table[hauteur]=o; hauteur++;}
public Object depiler()
{hauteur--; return table[hauteur];}
public Object sommet(){}
public boolean vide(){}
public boolean pleine(){}
} IPA – Catherine Faron Zucker 28
 Files
public class Pile{
private ArrayList<Object> liste;
private int longueur;
public void enfiler(Object o)
{liste.add(o); longueur++;}
public Object defiler()
{longueur--; return liste.remove(0);}
public Object tete(){}
public Object queue(){}
public boolean vide(){}
} IPA – Catherine Faron Zucker 29
 Maps

collection de paires d'objets, de taille variable
HashMap<String,String> surnoms;
surnoms = new HashMap<String,String>();

paires clé/valeur, clés uniques


ajout d'un couple clé/valeur :
surnoms.put(“tartampion”, “dupont”);

suppression d'un couple clé/valeur :
surnoms.remove(“tartampion”);
IPA – Catherine Faron Zucker 30
 Maps

plus de premier, dernier, i ième élément,
récupération d'une valeur associée à une clé :
String nom = surnoms.get(“tartampion”);


récupération directe de
 la valeur associée à une clé : get
 de l'information de présence/absence

d'une valeur: surnom.containsKey(“dupont”);

d'une clé : surnom.containsValue(“tartampion”);

IPA – Catherine Faron Zucker 31

 Sets

ensemble non ordonné d'objets, de taille variable
HashSet<String> surnoms;
surnoms = new HashSet<String>();

ajout d'un élément : surnoms.put(“tartampion”);

suppression : surnoms.remove(“tartampion”);

test direct de la présence d'un élément :
surnoms.contains(“tartampion”);

IPA – Catherine Faron Zucker 32

 Maps et Sets

Les structures de Maps et de Sets ne supportent que
les opérations de dictionnaire:
insérer, rechercher, supprimer

HashMap et HashSet sont des implémentations à base
de tables de hachage qui permettent de réduire le coût
de ces opérations.
à suivre...

IPA – Catherine Faron Zucker 33

 Structures de données

listes chaînées : cf. td
 simplement, doublement

arbres

arbres binaires

arbres binaires de recherche

graphes

à suivre...
IPA – Catherine Faron Zucker 34
 Conception d'un algorithme

Stratégie de résolution d'un problème


Approche incrémentale
 itérer jusqu'à obtention du résultat souhaité


Approche récursive
 diviser pour régner:

diviser en sous-problèmes

régner sur les sous-problèmes

combiner les solutions des sous-problèmes
IPA – Catherine Faron Zucker 35
 PGCD(a, b) itératif
n <- a; m <- b;
TantQue m != 0 Faire
r <- n mod m
n <- m
m <- r
FinTantQue
retourner n

IPA – Catherine Faron Zucker 36

 PGCD(a, b) récursif

diviser: pgcd(a,b) = pgcd(b, a mod b)
semblable au problème initial
de taille moindre


régner: pgcd(a,0) = a


combiner: pgcd(a,b)= pgcd(b,a mod b)=...

IPA – Catherine Faron Zucker 37

 PGCD(a, b) récursif
Si b=0
Alors retourner a //terminaison
Sinon retourner pgcd(a, a mod b)
finSi

IPA – Catherine Faron Zucker 38

 Fac(n)

Relation de récurence
fac(n) = n * fac(n-1), n>0
fac(0) = 1


Algorithme
Si n = 0
Alors retourner 1
Sinon retourner n * fac(n-1)
FinSi
IPA – Catherine Faron Zucker 39
 Fac(n)
Complexité
 opération élémentaire : *
 nbre de fois où elle est effectuée

fonction de n: M(n)

relation de récurence:
M(n) = 1 + M(n-1) pour n>0 et M(0) = 0
en développant, on a M(n) = M(n-i) – i pour tout i
pour i=n, on obtient M(n) = M(O) + n = n

cf. module Maths discrètes

IPA – Catherine Faron Zucker 40
 Tours de Hanoï

n disques de tailles décroissantes sur une tige

Problème: comment faire passer les n disques sur
une autre tige, en utilisant une tige intermédiaire
afin qu'un disque ne soit jamais empilé sur un plus
petit?

Algorithme (récursif):
 faire passer n-1 disques sur la tige 2
 faire passer le plus grand disque sur la tige 3
 reste à faire passer les n-1 disques de t2 à t3

IPA – Catherine Faron Zucker 41

 Tours de Hanoï

Algorithme:
 faire passer n-1 disques sur la tige 2
 faire passer le plus grand disque sur la tige 3
 reste à faire passer les n-1 disques de t2 à t3

Complexité
 on compte le nbre de déplacements
 il est fonction du nombre de disques
 M(n) = M(n-1) + 1 + M(n-1) pour n>1 et M(1)=1
 M(n) = 2*M(n-1)+1 = ... = 2n -1 (algo exponentiel)

IPA – Catherine Faron Zucker 42

 Recherche dichotomique

Version itérative vue en TD

Version récursive ?

IPA – Catherine Faron Zucker 43

 Algorithmes de tri

Structures de données ordonnées

Nombreux algorithmes
 tri par sélection
 tri par insertion
 tri à bulles
 tri fusion
 tri rapide (quicksort)

IPA – Catherine Faron Zucker 44

 Tri par sélection

Principe
 recherche du plus petit élt du tableau et échange
avec le premier élt
 recherche du plus petit élt du tableau entre les
positions 2 et n-1 et échange avec le second élt
 ...
 recherche du plus petit élt entre les positions n-2
et n-1 et échange avec l'élt en position n-2

IPA – Catherine Faron Zucker 45

 Tri par sélection

Algorithme itératif
Pour i de 0 à n-2 Faire
min <- i
Pour j de i+1 à n-1 Faire
Si tab[ j ] < tab[min] Alors min <- j FinSi
FinPour
Echanger tab[ i ] et tab[min]
FinPour

IPA – Catherine Faron Zucker 46

 Tri par insertion

Principe
le tableau étant trié jusqu'à l'élt i-1,
insérer l'élt i à sa place parmi les i premiers élts

récursion ou itération

IPA – Catherine Faron Zucker 47

 Tri par insertion

Algorithme itératif
Pour i de 1 à n-1 Faire
val <- tab[ i ]
j <- i-1
TantQue j >= 0 et tab[ j ] > val Faire
tab [ j+1] <- tab [ j ]
j <- j - 1
FinTantQue
tab [ j+1 ] <- val

IPA – Catherine Faron Zucker 48

 Tri à bulles

Principe
comparaison 2 à 2 des éléments adjacents
et échange s'ils ne sont pas ordonnés

comme les bulles, les plus grands élts remonten

en fin de liste

IPA – Catherine Faron Zucker 49

 Tri à bulles

Algorithme itératif
Pour i de 0 à n-2 Faire
Pour j de 0 à n-2-i Faire
Si tab[ j+1 ] < tab[ j ]
Alors échanger tab[ j+1 ] < tab[ j ]
FinSi
FinPour
FinPour

IPA – Catherine Faron Zucker 50

 Tri Fusion

Principe
“divide and conquer”
 division du tableau en 2 sous-tableaux
 tri récursif des 2 sous-tableaux
 fusion des 2 sous-tableaux

Le coeur de l'algorithme est la fusion des 2

sous-tableaux triés

IPA – Catherine Faron Zucker 51

 Tri fusion

Algorithme TriFusion(tab[0 .. n-1])
Si n > 1 Alors
copie de tab[ 0 .. n/2 -1] dans tab1
copie de tab[ n/2 n-1] dans tab2
TriFusion (tab1)
TriFusion (tab2)
Fusion (tab1, tab2, tab)

IPA – Catherine Faron Zucker 52

 Quick Sort

Principe
“divide and conquer”
 partition du tableau en 2 sous-tableaux tel que
l'élt à l'indice de partitionnement est bien placé
 tri récursif des 2 sous-tableaux

Le coeur de l'algorithme est la partition en 2

sous-tableaux

IPA – Catherine Faron Zucker 53

 Quick Sort

Algorithme QuickSort(tab[ g .. d )
Si g < d Alors
s <- Partition(tab)
QuickSort(tab[g .. s-1])
QuickSort(tab[s+1 .. d])

IPA – Catherine Faron Zucker 54