Intro Programmation Objet Algorithmes(2).pdf

(369 KB) Pobierz
Qu’est-ce que la programmation ?
Introduction ` la Programmation Objet :
a
Algorithmes
Rachid Guerraoui
1
, Maxime Monod
1
& Jamila Sam
2
1
Laboratoire
2
Laboratoire
Objectif : permettre l’automatisation d’un certain nombre de tˆches
a
` l’aide d’un
automate programmable.
a
de Programmation Distribu´e (LPD)
e
d’Intelligence Articielle (LIA)
Facult´ Informatique & Communications
e
Ecole Polytechnique F´d´rale de Lausanne
e e
Nous tenterons de remplacer l’orgue de barbarie par un ordinateur
LPD & LIA (EPFL)
IPO – Introduction
1 / 14
LPD & LIA (EPFL)
IPO – Introduction
2 / 14
Objectifs
Apprendre ` programmer
a
Formalisation des traitements :
algorithmes
Formalisation des donn´es :
structures de donn´es
e
e
Algorithme ?
e
e
a
e
solution calculatoire/m´
canique/it´rative/... ` un
probl`me
”Sp´cication d’un sch´ma de calcul sous forme d’une suite
e
e
d’op´rations ´l´mentaires ob´issant ` un enchaˆ
e
ee
e
a
ınement
d´termin´”
e
e
[
Encyclopedia Universalis
]
. . . en Java
Vocabulaire
et
Syntaxe
Sp´cicit´s du
langage
e
e
mais parlons d’abord un peu d’algorithmes . . .
LPD & LIA (EPFL)
IPO – Introduction
3 / 14
Algorithme
suite nie de r`gles ` appliquer,
e
a
dans un ordre d´termin´,
e
e
` un nombre ni de donn´es,
a
e
se terminant (i.e., arriver, en un nombre ni d’´tapes, ` un
e
a
r´sultat, et ce quelque soit les donn´es trait´es).
e
e
e
LPD & LIA (EPFL)
IPO – Introduction
4 / 14
Algorithme
Algorithme
Un algorithme est un moyen pour un humain de repr´senter la
e
r´solution par calcul d’un probl`me ` une autre personne physique
e
e
a
(humain) ou virtuelle (calculateur) ; un algorithme est :
s´quentiel si ses op´rations s’ex´cutent en s´quence,
e
e
e
e
parall`le si certaines de ses op´rations s’ex´cutent en parall`le,
e
e
e
e
r´parti si certaines de ses op´rations s’ex´cutent sur plusieurs
e
e
e
machines.
Al Khuwarizmi
: math´maticien perse arabophone
e
9`me si`cle, premier ouvrage d’alg`bre (Al-jabr wa’l-muqˆbalah)
e
e
e
a
Solution des ´quations lin´aires et quadratiques
e
e
e
L’algorithmique est une branche des math´matiques
Son nom, Al Khuwarizmi, latinis´ en Algoritmi, puis transform´ plus
e
e
tard en Algorisme est ` l’origine du mot algorithme.
a
LPD & LIA (EPFL)
IPO – Introduction
5 / 14
LPD & LIA (EPFL)
IPO – Introduction
6 / 14
Algorithmes c´l`bres
ee
Plus proche de nous
e
Babyloniens (-20
`me
si`cle) : calculs des impˆts
e
o
e
Euclide (-3
`me
si`cle) : PGDC
e
e
Al Khawarizmi (9
`me
si`cle) : ´quations
e
e
e
Averro`s (11
`me
si`cle) : notion d’it´ration
e
e
e
e
Descartes (17
`me
si`cle) : Discours de la m´thode
e
e
Tours de Hanoi : illustration de la programmation r´cursive
e
Tri : Comment trier des ´l´ments le plus rapidement possible
ee
Huit dames : placer huit dames sans qu’elles puissent se prendre
Voyageur de commerce : minimiser les nombre total de kms
e
”Diviser chacune des dicult´s que j’examinerois, en autant de
parcelles qu’il se pourroit, et qu’il soit requis pour les mieux
r´soudre” (Descartes)
e
LPD & LIA (EPFL)
IPO – Introduction
7 / 14
LPD & LIA (EPFL)
IPO – Introduction
8 / 14
Toute une th´orie
e
Java Dance (1)
Do you want to
dance with me ?
Formalisation : dans les ann´es (19)30 par des math´maticiens :
e
e
G¨del, Turing, Church, Post,
...
o
fonctions ”calculables”
et
machines de Turing
: abstraction
math´matique des notions de
traitement
(suite d’op´rations
e
e
e
´l´mentaires), de
probl`me
et d’algorithme.
ee
e
de nombreux probl`mes ouverts qui vous attendent
1er algorithme . . .
LPD & LIA (EPFL)
IPO – Introduction
9 / 14
LPD & LIA (EPFL)
IPO – Introduction
10 / 14
Java Dance (2)
Choisir une
personne
Java Dance (2)
i=1
Choisir la
personne i
Voulez−vous
danser?
non
i = i+1
oui
Success story
Voulez−vous
danser?
oui
Success
story
non
i>N
oui
Hopeless
non
l’algorithme se termine n´cessairement,
e
au pire
N
essais successifs,
. . . mais il n’est pas sˆr qu’il soit tr`s ecace !
u
e
Il n’est pas garanti que l’algorithme puisse se terminer !
LPD & LIA (EPFL)
IPO – Introduction
11 / 14
LPD & LIA (EPFL)
IPO – Introduction
12 / 14
Algorithme
Un algorithme est :
une
suite nie
de r`gles ` appliquer,
e
a
dans un
ordre d´termin´
,
e
e
` un
nombre ni
de donn´es.
a
e
e
a
e
arriver, en un nombre ni d’´tapes, ` un r´sultat quelles que soient
les donn´es trait´es.
e
e
On attend d’un algorithme qu’il :
se termine,
produise un r´sultat correct,
e
soit le plus ecace possible.
Il n’y a (mal)heureusement
aucune recette
pour produire un
algorithme !
LPD & LIA (EPFL)
IPO – Introduction
13 / 14
Algorithme = Programme
Un algorithme est
ind´pendant du langage de programmation
e
dans lequel on va l’exprimer
et de l’ordinateur
utilis´ pour le faire
e
tourner.
C’est une description abstraite des ´tapes conduisant ` la solution
e
a
d’un probl`me.
e
Algorithme
= partie conceptuelle d’un
programme
(ind´pendante
e
du langage)
Programme
= impl´mentation (i.e., r´alisation) de l’algorithme,
e
e
dans un langage de programmation et sur un syst`me particulier.
e
LPD & LIA (EPFL)
IPO – Introduction
14 / 14

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin