La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

Publications similaires

Vous aimerez aussi

Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Types abstraits de donn´ees
Cours d’Algorithmique et de Programmation en Pascal
C´elineRobardet http://liris.cnrs.fr/celine.robardet/
InstitutNationaldesSciencesAppliqu´eesdeLyonFrance
Algorithmique et Programmation en Pascal (20062007)
2006  2007
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Types construits et structur´es Proce´dureetfonctions Typesabstraitsdedonne´es
Qu’estce qu’un algorithme ?
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
De´nitiondupetitRobert Suite finieuqnese´letiellesqr`egdeinnounrembqilpa`euleupano dedonn´ees,permettantder´esoudredesclassesdeprobl`emes semblables.
Calcul:enchaˆınementdesactionsn´ecessaires`a laccomplissementdunetaˆche De´nitionnonambigu¨edelase´quencedactions Un exemple : comment multiplier deux entiers ? la multiplication par glissement ´ la multiplication en Egypte antique la multiplication rapide selon la technique de Karatsuba
Algorithmique et Programmation en Pascal (20062007)
1 / 108
3 / 108
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Typesabstraitsdedonne´es
Introduction
Algorithmique et Programmation en Pascal (20062007)
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proc´edure et fonctions Types abstraits de donn´ees
Multiplication par glissement
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Algorithmeindien,de´critparAlKwarizmien830.
6
3 125×613
Algorithmique et Programmation en Pascal (20062007)
1
3 3
1
2
5
2 / 108
4 / 108
8 6
3 1
1
2
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
9 3
1
Al Kwarizmi en 830.
1
1
3 3
8 6
5
2
Algorithmique et Programmation en Pascal (20062007)
1
Algorithme indien,
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Algorithmeindien,de´critpar
1
1
3 3
3 1
8 6
2
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Multiplication par
Algorithmeindien,d´ecritparAlKwarizmien830.
glissement
glissement
On note que 9 prend la place du 3 qui servait de multiplicateur.
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Types abstraits de donn´ees
6 / 108
Algorithmique et Programmation en Pascal (20062007)
Algorithmique et Programmation en Pascal (20062007)
3 125×613
3 125×613
glissement
5
8 / 108
1
3 125×613
3 125×613
Multiplication par
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Types abstraits de donn´ees
2
Algorithmeindien,de´critpar
1
6
5
3 3
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Al Kwarizmi en 830.
d´ecritparAlKwarizmien830.
7 / 108
5
5 / 108
Multiplication par
glissement
Algorithmique et Programmation en Pascal (20062007)
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Typesabstraitsdedonne´es
Multiplication par
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proc´edure et fonctions Types abstraits de donn´ees
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Typesabstraitsdedonne´es
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proc´edure et fonctions Typesabstraitsdedonne´es
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Types construits et structur´es Proce´dureetfonctions Typesabstraitsdedonne´es
1
8
3 6
9 1
3 125×613
1 3
Algorithmique et Programmation en Pascal (20062007)
Algorithmeindien,d´ecritpar
glissement
Multiplication par
9 / 108
Multiplication par
Algorithmique et Programmation en Pascal (20062007)
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
5
11 / 108
Al Kwarizmi en 830.
Al Kwarizmi en 830.
Multiplication par
Algorithmeindien,de´critparAlKwarizmien830.
5
Algorithmeindien,de´critpar
2
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Multiplication par
8
Algorithmeindien,d´ecritparAlKwarizmien830.
Algorithmique et Programmation en Pascal (20062007)
1
1 3
9 1
3 6
5
2
9 1
1 3
2
1
8
9 6
0 1
0 6
2
1 3
9
1
Onde´caledunrang
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Algorithmique et Programmation en Pascal (20062007)
3 125×613
3 125×613
3 125×613
glissement
glissement
glissement
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Typesabstraitsdedonne´es
10 / 108
5
12 / 108
Algorithmeindien,d´ecritparAlKwarizmien830.
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
On note que 3 prend la place du 1 qui servait de multiplicateur.
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
5
2 3
Al Kwarizmi en 830.
2 6
3 1
2 3
9
1
2 3
3 1
0 6
0
9
1
1
Algorithmique et Programmation en Pascal (20062007)
15 / 108
Algorithmique et Programmation en Pascal (20062007)
5
2
Multiplication par
13 / 108
Algorithmeindien,de´critpar
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proc´edure et fonctions Types abstraits de donn´ees
Multiplication par
Multiplication par
Al Kwarizmi en 830.
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Algorithmeindien,d´ecritpar
Algorithmique et Programmation en Pascal (20062007)
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Ond´ecaledunrang
Algorithmique et Programmation en Pascal (20062007)
3 125×613
3 125×613
3 125×613
glissement
glissement
0 6
1
0
3 125×613
3 1
9
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Types construits et structur´es Proce´dureetfonctions Typesabstraitsdedonne´es
Algorithmeindien,d´ecritparAlKwarizmien830.
16 / 108
14 / 108
5
glissement
0 6
0 1
3 3
9
1
5
glissement
Multiplication par
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Types construits et structur´es Proc´edure et fonctions Types abstraits de donn´ees
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Types abstraits de donn´ees
glissement
Onde´caledunrang
2 3
2 6
1
5
5 1
Algorithmeindien,d´ecritpar
9
1
Algorithmique et Programmation en Pascal (20062007)
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
6 1
1
9
5 6
2
1
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
19 / 108
5 3
Algorithmique et Programmation en Pascal (20062007)
5 6
3 125×613
1
2
1
9
Algorithmique et Programmation en Pascal (20062007)
17 / 108
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proce´dureetfonctions Types abstraits de donn´ees
Multiplication par
6 1
Algorithme indien,
Al Kwarizmi en 830.
d´ecritparAlKwarizmien830.
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
Algorithme Multiplication par glissement ´ Multiplication en Egypte antique Multiplication rapide selon la technique de Karatsuba Pragramme
6 3
5 1
2 6
1
9
1
Multiplication par
Algorithmeindien,d´ecritpar
Al Kwarizmi en 830.
qui servait de multiplicateur.
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Types construits et structur´es Proce´dureetfonctions Types abstraits de donn´ees
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Typesconstruitsetstructure´s Proc´edure et fonctions Typesabstraitsdedonne´es
Multiplication par
Introduction Qu’estce qu’une variable ? Les types simples Programme et compilation Les instructions Types construits et structur´es Proce´dureetfonctions Types abstraits de donn´ees
Multiplication par
glissement
Algorithmique et Programmation en Pascal (20062007)
glissement
glissement
Algorithmeindien,de´critparAlKwarizmien830.
3 125×613
3 125×613
3 125×613
5 3
20 / 108
5
18 / 108
On note que 6 prend la place du 2