View
4
Download
0
Category
Preview:
Citation preview
Diviser pour régner
François Schwarzentruber
Applications
Agrégation de mathématiques option informatique
● C'est une leçon !
Diviser pour régner
● Théorème fondamental● Applications
- Calcul : multiplications de nombres et matrices
- Traitement du signal : FFT
- Géométrie : deux points les plus proches● Circuit LVSI
Théorème fondamental
nb
a
d
...
Cas où divise beaucoup / peu d'appels
nb
Cas « équilibre »
nb
Cas où on divise peu / beaucoup d'appels
nb
Algorithme rapide de multiplication de grands nombres (1960-1962)
Karatsuba
123497861423156479354531258496331X 1325468791431234786415356984321
Algorithme rapide de multiplication de matrices (1969)
X
Strassen
Multiplication de matrices
FFT
FFT (1962... but 1805)
TukeyCooley Gauss
Géométrie
Deux points les plus proches
Recommended