Cours1 amphi .pdf



Nom original: Cours1-amphi.pdfTitre: Introduction à l'algorithmique Design and Analysis of Computer Algorithms - Cours 1 : introduction et notions de base

Ce document au format PDF 1.4 a été généré par LaTeX with beamer class version 3.07 / dvips + GPL Ghostscript 8.64, et a été envoyé sur fichier-pdf.fr le 23/09/2011 à 23:35, depuis l'adresse IP 80.11.x.x. La présente page de téléchargement du fichier a été vue 2960 fois.
Taille du document: 1.2 Mo (64 pages).
Confidentialité: fichier public


Aperçu du document


Introduction `a l’algorithmique
Design and Analysis of Computer Algorithms
Cours 1 : introduction et notions de base

22 septembre 2011

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

1 / 64

Pcs et r´epartition

15 Pcs :
Pc d’algorithmique avanc´ee (pour l’instant les ´el`eves ayant suivi
l’option informatique en pr´epa)
14 pcs sans niveaux requis en algorithmique et programmation dont
une en anglais. La pc en anglais est r´eserv´ee aux ´el`eves non times (`a
l’exception des ´el`eves times francophones)
L’affectation aux diff´erentes PCs se fera sur Claroline par inscription.
Rappel : La pr´esence en pc et en cours est obligatoire.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

2 / 64

Introduction

Objectifs du cours

Avoir les outils n´
ec´
essaires pour concevoir un bon algorithme

esolvant un probl`
eme donn´
e
Conception des algorithmes.
Acc`es aux donn´ees : les diff´erentes structures de donn´ees.
Algorithmes de bases et leurs applications.
Analyse des algorithmes : quels sont les crit`eres caract´eristiques ?
Langage de programmation utilis´e : Python

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

3 / 64

Introduction

Organisation du cours

Chaque s´eance
Apports th´eoriques sous forme de cours.
Pratique sous forme d’exercices et/ou travaux pratiques.

Evaluation
Contrˆ
ole interm´ediaire d’1h1/2 le 13 octobre 2011.
Contrˆ
ole final sur papier

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

4 / 64

Introduction

Programme du cours
Les grandes notions
Les bases de l’algorithmique : notion de complexit´e
La r´ecursivit´e et le paradigme Diviser pour R´egner
Structures de donn´ees basiques et avanc´ees : listes, files, piles, tas,
arbres ...
Arbres de recherche et algorithmique sur les graphes (ce cours sera
approfondi dans l’´electif S2 ”Th´eorie des graphes : algorithmes et
applications”)
Notions de programmation avanc´ee : structuration, traitements
d’exceptions et tests structurels
Un peu de preuves de programmes par la logique de Hoare

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

5 / 64

Introduction

L’algorithmique ?
D´efinition (informelle)
Un algorithme est la composition d’un ensemble fini d’´etapes, chaque
´etape ´etant form´ee d’un nombre fini d’op´erations dont chacune est :
d´efinie de fa¸con rigoureuse et non ambigue ;
effective (i.e. pouvant ˆetre r´ealis´ee en un temps fini).
La notion d’algorithme est plus g´en´erale que celle de programme
(ind´ependant du langage de programmation utilis´e).

Un peu d’histoire
Le mot algorithme vient du nom du math´ematicien Al Khwarizmi (820) :
introduction de la num´erotation d´ecimale et des calculs s’y rapportant.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

6 / 64

Introduction

Des besoins contradictoires

Un algorithme doit :
ˆetre simple `a comprendre, `a mettre en oeuvre et `a mettre au point ;

mettre intelligement `a contribution les ressources de l’ordinateur, et
plus pr´ecis´ement, il doit s’ex´ecuter rapidement.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

7 / 64

Introduction

Introduction

Un algorithme : c’est quoi ?

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

8 / 64

Introduction

Introduction

Algorithme : d´efinitions
Un algorithme =
Description pr´ecise des op´erations `
a faire pour r´esoudre un probl`eme (suite
d’instructions).
Proc´edure de calcul bien d´efinie qui prend en entr´ee une valeur, ou un ensemble de
valeurs et qui donne en sortie une valeur, ou un ensemble de valeurs.

Un bon algorithme =
Un algorithme correct : i.e. pour chaque instance en entr´ee, l’algorithme se termine
en produisant la bonne sortie
⇒ Savoir prouver un algorithme
Un algorithme efficace : mesure de la dur´ee que met un algorithme pour produire
un r´esultat
⇒ Savoir analyser la complexit´e d’un algorithme : i.e. d´etermination de l’espace
m´emoire et du temps d’ex´ecution n´ec´essaire `
a la r´esolution du probl`eme.
Pour un probl`eme donn´e, plusieurs algorithmes ou aucun sont possibles.
Un algorithme se termine en un temps fini.
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

9 / 64

Introduction

Introduction

Un exemple simple
Probl`eme de tri
Donn´ees : une suite de n nombres, (e0 , e1 , ..., en−1 )






R´esultat : permutation de la suite donn´ee en entr´ee (e0 , e1 , ..., en−1 )



de telle sorte que e0 ≤ e1 ≤ ... ≤ en−1

Principe du tri par insertion
On parcourt enti`erement la liste en appliquant `a chaque it´eration la
strat´egie suivante :
Recherche de la place du i`eme ´el´ement.
Parall`ele avec le tri d’un jeu de cartes : le jeu est initialement sur la
table et le joueur trie les cartes en les ins´erant une par une dans sa
main en les comparant avec les cartes d´ej`a pr´esentes. A tout moment,
les cartes dans sa main sont tri´ees.
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

10 / 64

Introduction

Introduction

Tri par insertion
Principe
On veut trier la liste :
3
1

2

5

2

7

1

5

On met l’´el´ement d’indice 1 `a sa place dans la liste[0..1]
2

3

1

On part du constat que liste[0..0] est tri´ee
3

2

7

3

7

1

5

liste[0..1] est maintenant tri´ee. On recommence `a l’´etape 2 avec
l’´el´ement suivant.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

11 / 64

Introduction

Introduction

Un algorithme simple
Consid´erons un tableau A contenant une s´equence `a trier de longueur n
Algorithm 1 TRI-INSERTION (A)
1: for j ← 2 to n do
2:
key ← A[j]
3:
i ←j −1
4:
while i > 0 and A[i] > key do
5:
A[i + 1] ← A[i]
6:
i ←i −1
7:
end while
8:
A[i + 1] ← key
9: end for
On verra comment implanter cet algorithme en Python (pc 2)
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

12 / 64

Introduction

Introduction

Analyse d’un algorithme

Analyser c’est :
Montrer que l’algorithme est correct, i.e. pour chaque instance en
entr´ee, l’algorithme se termine en produisant la bonne sortie.
Montrer que l’algorithme se termine.
Quantifier la place utilis´ee en m´emoire par l’algorithme.
Quantifier le temps d’execution de l’algorithme.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

13 / 64

Introduction

Introduction

Correction totale
Correction de l’algorithme
V´erifier que pour chaque instance en entr´ee, l’algorithme se termine
en produisant la bonne sortie.
Deux approches compl´ementaires :


Tests : on g´en`ere un ensemble de tests pour ´eprouver l’algorithme sur
des donn´ees r´eelles :





Permet d’augmenter la confiance dans la correction d’une implantation
d’un algorithme.
Ne permet pas de garantir la correction de l’algorithme

V´erification et preuve de programmes : prouver qu’il correspond `a la
sp´ecification donn´ee : manipulations de repr´esentations formelles.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

14 / 64

Introduction

Introduction

Correction d’un algorithme

Pourquoi ?
Contrˆ
ole de pilotage automatique : avion, m´etro (Meteor).
Centrale Nucl´eaire.
Bases de donn´ees critiques : banque, transport,...
Chirurgie assist´ee, robotique m´edicale.
...

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

15 / 64

Introduction

Introduction

Correction d’un algorithme
Notion d’invariants
Un invariant de boucle est une propri´et´e qui reste vraie `a chaque passage
dans la boucle.

Principe de la v´erification par invariants de boucle
D´efinir un invariant qui assure qu’`a la fin la propri´et´e voulue est
satisfaite
Trois ´etapes :






Initialisation : v´erifier qu’il est vrai avant la premi`ere it´eration de la
boucle.
Conservation : si il est vrai avant une it´eration de la boucle, il le reste
avant l’it´eration suivante.
Terminaison : une fois la boucle termin´ee, l’invariant fournit une
information utile qui aide `a montrer la validit´e de l’algorithme.

Ressemblance avec la r´ecurrence math´ematique.
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

16 / 64

Introduction

Introduction

Un exemple simple : tri par insertion

Invariant de boucle
Au d´ebut de chaque it´eration de la boucle For des lignes 1 `a 8, le sous
tableau A[1..j − 1] se compose des ´el´ements qui occupaient initialement
les positions A[1..j − 1] mais qui sont maintenant tri´es

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

17 / 64

Introduction

Introduction

Un exemple simple : tri par insertion
V´erification par l’invariant
Initialisation : l’invariant est vrai avant la 1`ere it´eration quand j = 2.
Le sous tableau A[1..j − 1] se compose de l’´element A[1] qui est
l’´el´ement originel de A[1] et il est trivialement tri´e.
Conservation : chaque it´eration conserve l’invariant. On peut le
prouver par une analyse informelle en regardant le fonctionnement de
l’algorithme. Le corps de la boucle d´eplace A[j − 1], A[j − 2],... d’une
case vers la droite jusqu’`a trouver la bonne position pour A[j] (ligne
4-7) auquel cas on ins`ere la valeur de A[j]. De mani`ere formelle, il
faut aussi prouver un invariant pour la boucle While.
Terminaison : la boucle prend fin pour j = n + 1. On substitue n + 1
`a j dans la formulation de l’invariant de boucle. On a le tableau
A[1..n] qui se compose bien des ´elements originels de A[1..n] et il est
tri´e.
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

18 / 64

Introduction

Introduction

Terminaison d’un algorithme

Principe
Prouver que le calcul se termine en un temps fini en trouvant un
param`etre qui varie de mani`ere strictement monotone au cours du calcul

D´efinition : Terminaison des boucles
D´efinir une fonction f `a valeurs dans N d´ependante des variables du
programme. Montrer que la valeur de f d´ecroˆıt strictement `a chaque
ex´ecution de la boucle

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

19 / 64

Introduction

Introduction

Un exemple simple

Terminaison de l’algorithme du tri par insertion
La boucle While s’arrˆete toujours : elle comprend au plus n it´erations
La boucle For produit n − 1 it´erations
L’algorithme se termine donc apr`es un nombre fini d’´etapes

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

20 / 64

Introduction

Introduction

Analyse d’un algorithme

Simplicit´e et intelligibilit´e de l’algorithme
Efficacit´e de l’algorithme :






Temps d’ex´ecution
Occupation de la m´emoire
Quantit´e de trafic g´en´er´e sur un r´eseau
Quantit´e de donn´ees d´eplac´ees sur le disque
...

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

21 / 64

Introduction

Introduction

Un exemple simple
Calculer x n
Donn´ees : x : r´eel, n : entier
M´ethode 1 : algorithme naif
x0 = 1
x i = x.x i−1 , i > 0
M´ethode 2 :
x0 = 1
i
i
x i = x 2 .x 2 si i est pair
i
i
x i = x.x ⌊ 2 ⌋ .x ⌊ 2 ⌋ si i est impair
Quel est l’algorithme le plus efficace ?
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

22 / 64

Introduction

Introduction

Complexit´e d’un algorithme

Permet de quantifier les algorithmes et de pr´evoir les ressources n´ec´essaires
aux algorithmes.

Deux types de complexit´e :
En espace : Quelle quantit´e de place en m´emoire va t-on utiliser ?
En temps : Combien d’op´erations va t-on effectuer ?
Int´
erˆ
et : comparer deux algorithmes

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

23 / 64

Introduction

Introduction

Mod`ele de machines (cours ´electif en S4 ”Fondements de
l’informatique”)
L’analyse d’un algorithme n´ecessite d’avoir un mod`ele de la technologie
employ´ee.

Mod`ele utilis´e : mod`ele RAM
Machine `a acc`es al´eatoire (RAM) et processeur unique : les instructions
sont ex´ecut´ees l’une apr`es l’autre, sans op´erations simultan´ees

Hypoth`ese simplificatrice
Les op´erations ´el´ementaires requi`erent une unit´e de temps.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

24 / 64

Introduction

Introduction

Mesurer le temps d’ex´ecution
Le temps d’ex´ecution d´epend de l’entr´ee : par exemple dans le cas
d’un algorithme de tri, si le tableau est d´eja tri´e ou la taille de l’entr´ee.
On cherche une fonction T (n) repr´esentant le temps d’ex´
ecution
d’un algorithme en fonction de la taille de l’entr´
ee n (nombre
d’´elements constituant l’entr´ee (tri), nombre de bits n´ec´essaires `a la
repr´esentation de l’entr´ee (multiplication de deux entiers,...)
Le calcul exact ´etant souvent impossible `a appr´ehender exactement,
on s’int´eresse aux :




Meilleur des cas
Pire de cas
Cas moyen : n´ec´essite d’avoir des connaissances sur la distribution
statistique des entr´ees

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

25 / 64

Introduction

Introduction

Mesurer le temps d’ex´ecution
Cas du tri par insertion
Algorithm 2 TRI-INSERTION (A)
1: for j ← 2 to n do
2:
key ← A[j]
3:
i ←j −1
4:
while i > 0 and A[i] > key do
5:
A[i + 1] ← A[i]
6:
i ←i −1
7:
end while
8:
A[i + 1] ← key
9: end for
Soit ci , le coˆ
ut temporel de chaque instruction.
On a P
alors :
P
P
T (n) = c1 n + c2 (n − 1) + c3 (n − 1) + c4 nj=2 tj + c5 nj=2 (tj − 1) + c6 nj=2 (tj − 1) + c8 (n − 1)
tj nombre de fois que le test de la boucle While est ex´
ecut´
ee pour cette valeur de j, c7 = 0
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

26 / 64

Introduction

Introduction

Mesurer le temps d’ex´ecution
Cas du tri par insertion
Cas le plus favorable : le tableau est d´eja tri´e et donc pour tout
j = 2..n on a tj = 1 car A[i] ≤ key .
Temps d’ex´ecution :
T (n) = (c1 + c2 + c3 + c4 + c8 )n − (c2 + c3 + c4 + c8 )
Temps sous la forme an + b : fonction lin´
eaire de n.
Cas le plus d´
efavorable : la tableau est tri´e dans l’ordre d´ecroissant
donc tj = j pour tout j = 2..n.
Temps d’ex´ecution : T (n) = c1 n + c2 (n − 1) + c3 (n − 1) +
c4 ( n(n+1)
− 1) + c5 ( n(n−1)
) + c6 ( n(n−1)
) + c8 (n − 1)
2
2
2
2
Temps sous la forme an + bn + c : fonction quadratique de n

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

27 / 64

Introduction

Introduction

Mesurer le temps d’ex´ecution

Vers un ordre de grandeur ind´ependant des machines
Exemple : analyse du cas le plus d´efavorable du tri par insertion :
doit-on consid´erer les constantes propres `a la machine et si oui
lesquelles (vitesse moyenne d’ex´ecution, vitesse absolue,...) ?
⇒ On approxime le temps de calcul en :



Ignorant les constantes d´ependantes de la machine
Regardant l’augmentation de T (n) quand n → ∞

On fait une analyse asymptotique : notation Θ

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

28 / 64

Introduction

Introduction

Caract´erisation asymptotique : notation O
D´efinition math´ematique : borne sup´erieure asymptotique
O(g (n)) = {f (n) telle qu’il existe des constantes positives r´eelle c et
enti`ere n0 telles que 0 ≤ f (n) ≤ cg (n) pour tout n ≥ n0 }

On dit de f est domin´ee asymptotiquement par g .
Ex. 2n = O(n2 ), 2n = O(n)
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

29 / 64

Introduction

Introduction

Analyse asymptotyque : notation Θ - Plus pr´ecis
D´efinition math´ematique
Θ(g (n)) = {f (n) telle qu’il existe des constantes positives r´eelles c1 , c2 et enti`ere n0
telles que 0 ≤ c1 g (n) ≤ f (n) ≤ c2 g (n) pour tout n ≥ n0 }

Plus pratiquement
1

Les facteurs constants sont ignor´es

2

Les termes d’ordre inf´erieur sont n´egligeables

g (n) est une borne asymtotiquement approch´ee de f (n)

Ex. 2n 6= Θ(n2 ) par contre 2n = Θ(n)
()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

30 / 64

Introduction

Introduction

Classes de complexit´e

Algorithmes sub-lin´eaires : Θ(log n)
Algorithmes lin´eaires : Θ(n) et Θ(n log n)
Algorithmes polynomiaux : Θ(nk )
Algorithmes exponentiels : Θ(2n )

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

31 / 64

Introduction

Introduction

Algorithmique et Programme : Mod`ele complet
Programme = expression de l’algorithme dans un langage informatique.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

32 / 64

Introduction

Langages de programmation

Ensembles de mots clefs et de r`egles pour former des phrases pouvant ˆetre
traduites par la machine (binaire).

Plusieurs niveaux
Langages de bas niveau : instructions ´el´ementaires tr`es proches de la
machine (ex : Assembleur : V AX, [0110] signifie copier le contenu de
0110 dans le registre AX ; langage machine)
Langages de haut niveau : instructions plus abstraites (C, C++, Perl,
Java, Python).

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

33 / 64

Introduction

Paradigmes de programmation

Proc´edural (imp´eratif)
Fonctionnel
Logique
Orient´e-objet
Hybride

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

34 / 64

Introduction

Paradigmes de programmation

Programmation proc´edurale
D´eclaration de proc´edures accomplissant des tˆaches sp´ecifiques n´ecessaires
au programme. Les ´etapes sont expliqu´ees ligne par ligne, et l’instruction
atomique est l’affectation de variables. Le programme est ex´ecut´e.

Exemples
FORTRAN,C,PASCAL

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

35 / 64

Introduction

Paradigmes de programmation

Programmation fonctionnelle
Langage d’utilisation et de d´eveloppement de fonctions. Tout programme
est construit par fonctions, retournant un r´esultat en sortie et prenant en
entr´ee la sortie d’autres fonctions. Le programme est ´evalu´e.
Diviser un probl`eme complexe en sous probl`emes
R´ecursivit´e

Exemples
CAML, SCHEME, LISP, ...

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

36 / 64

Introduction

Paradigmes de programmation

Programmation logique
Langage d´eductif utilisant des r`egles et des faits. Un moteur d’inf´erence
permet de donner le r´esultat. Le programme est une th´eorie axiomatique `a
partir de laquelle on inf`ere (d´emonstrations logiques/math´ematiques) les
r´esultats.

Exemple
PROLOG

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

37 / 64

Introduction

Paradigmes de programmation

Couche au-dessus des autres paradigmes de programmation.

Programmation orient´ee-objet
Bas´ee sur le principe que des choses peuvent avoir des points communs,
des similarit´es en elles-mˆemes ou en leur fa¸con d’agir. On con¸coit des
fabriques (classes) qui servent `a construire des composants (objets). Les
classes contiennent des donn´ees(attributs) et des actions (m´ethodes).

Exemples
C++, JAVA, SMALLTALK, O-CAML...

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

38 / 64

Introduction

Paradigmes de programmation

Programmation hybride
Langage combinant plusieurs paradigmes de programmation.

Exemples
C++, JAVA, PYTHON,PERL,RUBY, ...

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

39 / 64

Introduction

Production de programmes : Interpr´etation
Interpr´etation

Chaque ligne du code source est traduite au fur et `a mesure en
instructions qui sont directement ex´ecut´ees, i.e. l’interpr´eteur est utilis´e `a
chaque ex´ecution.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

40 / 64

Introduction

Production de programmes : Compilation
Compilation

Compilation = traduction du code ecrit dans un langage dit source en
langage objet ou cible (analyse lexicale, syntaxique, s´emantique et
production du code objet). L’´edition de liens ..

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

41 / 64

Introduction

Production de programmes : Technique mixte
Bon compromis entre la facilit´e de developpement et la rapidit´e
d’ex´ecution

Interpr´etation du bytecode compil´e
Le bytecode (forme interm´ediaire) est portable sur tout ordinateur muni
d’une machine virtuelle.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

42 / 64

Algorithmes r´
ecursifs

Conception d’algorithmes : la r´ecursivit´e (formalisation en
cours ´el´ectif du S4 ”Fondements de l’info”)

Introduction
De nombreux probl`emes se r´esolvent par r´ep´etition de tˆaches.
Tous les langages de programmation sont munis de structures
r´ep´etitives.
La r´ecursivit´e est une technique de programmation qui permet de
remplacer ces structures r´ep´etitives par des appels de fonctions

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

43 / 64

Algorithmes r´
ecursifs

Algoritmes r´ecursifs

D´efinition
Un algorithme est dit r´ecursif s’il s’appelle lui mˆeme.

R´ecursivit´e
Principe qui consiste `a d´ecrire les ´etapes n´ec´essaires `a la r´esolution de
probl`emes en utilisant la r´esolution du mˆeme probl`eme sur des entr´ees plus
petites.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

44 / 64

Algorithmes r´
ecursifs

Algoritmes r´ecursifs : exemple

Factorielle d’un nombre
On peut d´efinir la factorielle d’un nombre de la mani`ere suivante :

1
si n ≤ 1
n! =
n(n − 1)! sinon

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

45 / 64

Algorithmes r´
ecursifs

Algoritmes r´ecursifs : exemple

Factorielle : algorithme it´eratif
Algorithm 3 FACTORIEL-ITERATIF (n : entier positif)
1: x ← 1
2: for i ← 1 to n do
3:
x ←i ∗x
4: end for
5: return x

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

46 / 64

Algorithmes r´
ecursifs

Algoritmes r´ecursifs : exemple

Factorielle :algorithme r´ecursif
Algorithm 4 FACTORIEL-RECURSIF (n : entier positif)
1: if n = 1 then
2:
return 1
3: else
4:
return n FACTORIEL-RECURSIF(n − 1)
5: end if

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

47 / 64

Algorithmes r´
ecursifs

Exercice : Tours de Hanoi

Description du probl`eme
Le probl`eme des tours de Hanoi est un jeu de r´eflexion propos´e par le
math´ematicien Edouard Lucas. Le but est de d´eplacer des disques de
diam`etres diff´erents d’une tour de d´epart `a une tour d’arriv´ee en passant
par une tour interm´ediaire en un minimum de coups. Les r`egles suivantes
doivent ˆetre respect´ees :
On ne peut d´eplacer qu’un disque `a la fois
Un disque ne peut ˆetre plac´e que sur un disque plus grand que lui ou
sur un emplacement vide.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

48 / 64

Algorithmes r´
ecursifs

Exercices : Tours de Hanoi

1

Avec ce principe, ecrivez un algorithme qui utilise la r´ecursivit´e pour
r´esoudre le probl`eme des tours de Hanoi. L’algorithme affichera les
d´eplacements des disques.

2

Montrer par r´ecurrence que si n est le nombre de disques `a d´eplacer
alors on peut r´esoudre le probl`eme en 2n − 1 coups.

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

49 / 64

Algorithmes r´
ecursifs

Tours de Hanoi : R´esultat

Soit A, B, C les trois emplacements. B est l’emplacement
interm´ediaire.
On d´eplace, comme on sait le faire n − 1 disques de A vers B
On d´eplace le dernier disque de A vers C
On d´eplace les n − 1 disques de B vers C

()

Introduction `
a l’algorithmique Design and Analysis of Computer
22 septembre
Algorithms
2011

50 / 64


Cours1-amphi.pdf - page 1/64
 
Cours1-amphi.pdf - page 2/64
Cours1-amphi.pdf - page 3/64
Cours1-amphi.pdf - page 4/64
Cours1-amphi.pdf - page 5/64
Cours1-amphi.pdf - page 6/64
 




Télécharger le fichier (PDF)


Cours1-amphi.pdf (PDF, 1.2 Mo)

Télécharger
Formats alternatifs: ZIP



Documents similaires


cours1 amphi
cours2
cours d analyse et conduite de projet algorithmique
info s1
algo ch1 3
liste des ouvrages inf

Sur le même sujet..