Cours 1: Introduction à l'algorithmique

De
Publié par

Cours 1: Introduction a l'algorithmique Olivier Bournez LIX, Ecole Polytechnique 2011-12 Algorithmique 1
  • maximum complexite
  • suffit de faire
  • ecole polytechnique 2011-12 algorithmique
  • probleme probleme
  • methode binaire
  • peut faire mieux
  • probleme probleme du maximum trier
  • y2 ∗
  • binaire cc
  • reformulation de la methode binaire
  • nb de chiffres en base
  • polytechnique
  • xn
  • methode
Publié le : mardi 27 mars 2012
Lecture(s) : 69
Tags :
Source : lix.polytechnique.fr
Nombre de pages : 35
Voir plus Voir moins

Cours 1: Introduction a l’algorithmique
Olivier Bournez
bournez@lix.polytechnique.fr
LIX, Ecole Polytechnique
2011-12 Algorithmique
1Aujourd’hui
nCalcul de x
Maximum
Complexite d’un probleme
Probleme du maximum
Trier
2nRecherche d’un algorithme pour calculer x .
On part avec
I y = x (un entier, un reel, une matrice, . . . )0
I et un entier n.
nOn souhaite calculer x le plus rapidement possible.
3Plus formellement:
I On doit construire une suite y ;y ; ;y .1 2 k
I Regle du jeu: si j’ai deja calcule y ;y ; ;y , alors je peux0 1 i 1
calculer y = y y , pour 0 j;k < i.i j k
I Question: trouver le meilleur algorithmque:
nopt(n) = minfrj9y ;y ; ;y suite correcte avec y = x g:0 1 r r
4Premiere solution: Algorithme na f
On peut le faire avec n 1 etapes.
En e et, il sut de faire:
I y = x,0
I pour i = 1 a n,
y = y y .i i 1 0
5Methode plus astucieuse: methode binaire
Plus astucieux:
n n=2 2I n pair, x = (x ) .
n bn=2c 2I n impair, x = (x ) x.
nI n = 0, x = 1
nI n = 1, x = x.
D’ou le programme:
fonction carre(int x) {
retourner x*x
}
fonction puissance (int x, int n) {
si n==0 alors retourner 1
si n==1 alors retourner x
si n est pair alors
retourner carre(puissance(x,n div 2))
si n est impair alors
retourner carre(puissance(x, n div 2))*x
}
6Est-ce le meilleur algorithme?
Reponse non:
I (plus petit contre exemple:) 15.
I Pour 15, methode binaire prend 6 multiplications.
3I On peut faire mieux: y = x se calcule en deux multiplications,
5 15et y = x en trois multiplications, soit un total de 5.
7Reformulation de la methode binaire
Sur un exemple:
I 13 en binaire: 1101.
on barre le premier 1
pour chaque 1, on fait carre(x)x: note cx
pour chaque 0, on fait carre(x): note c.
I Ici: 1101 donne cxccx:
2 3 6 12 13 on calcule x ,x , x , x , x .
nCout cc(n) pour calculer x par cette methode: nombre de
chi res en base 2 de n + nombre de 1 - 2.
nb de chi res en base 2 de n:blog nc + 12
On obtient:
blog nc cc(n) 2blog nc:2 2
8Retour sur le contre-exemple
15 = 1111 en binaire
cc(15) = 6.
15 = 5*3.
1 2 2 3
I y = x , y = x .
3 1 1 4 4 3 5
I y = y y = x , y = y x = x .
5 2 4I y = y y .
Idee: methode des facteurs.
9Methode des facteurs
On considere n = pq, ou p est le plus petit facteur premier
de n.
n pOn calcule x en calculant x et en elevant le resultat a la
puissance q.
n 1Si n est premier, on calcule x et on multiplie par x.
Sur un exemple:
I 55 = 5 11.
5 4 2 2I On calcule y = x = x x = (x ) x
11 10 2 5I On calcule y = y y = (y ) y.
I Au total 8 multiplications.
10

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.