Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Bostan10 algorithmes rapides

Journées Nationales de Calcul Formel Rencontre organisée par Jean- Guillaume Dumas Grégoire Lecerf Delphine Boucher et Thomas Cluzeau Alin Bostan Algorithmes rapides pour les polynômes séries formelles et matrices Vol no p - http ccirm cedram org item id CCIRM Centre international de rencontres mathématiques U M S C N R S S M F Luminy Marseille France cedram Texte mis en ligne dans le cadre du Centre de di ?usion des revues académiques de mathématiques http www cedram org CLes cours du C I R M Vol no - Algorithmes rapides pour les polynômes séries formelles et matrices Alin Bostan Table des matières Avant-propos Chapitre Calcul Formel et Complexité Décider calculer Fondements logiques Structures et constructions de base Équations comme structures de données Calculer rapidement Mesures de complexité La notation O Diviser pour régner Avertissement Notes Bibliographie Chapitre Multiplication rapide Introduction résultats principaux Algorithme na? f Algorithme de Karatsuba Transformée de Fourier rapide Idée de l ? algorithme Racines primitives de l ? unité Transformée de Fourier rapide Interpolation Conclusion Mais o? sont nos racines L ? algorithme de Sch? nhage et Strassen Racines virtuelles de l ? unité L ? algorithme Algorithmes pour les entiers Un concept important les fonctions de multiplication Exercices Notes Bibliographie Chapitre Algèbre linéaire dense de Gauss à Strassen Introduction L ? algorithmique des matrices tentative de classi ?cation Cours professé lors de la rencontre Journées Nationales de Calcul Formel ? organisée par Jean-Guillaume Dumas Grégoire Lecerf Delphine Boucher et Thomas Cluzeau - mai C I R M Luminy CAlin Bostan Résultat principal Applications Multiplication de matrices Multiplication na? ve Algorithme de Winograd Algorithme de Waksman Algorithme de Strassen Interprétation des formules de Strassen Peut-on faire mieux que En pratique Autres problèmes d ? algèbre linéaire Élimination de Gauss Résultat principal La multiplication n ? est pas plus di ?cile que l ? inversion L ? inversion le calcul de déterminant et la résolution de système ne sont pas plus di ?ciles que la multiplication Calcul du polynôme caractéristique Exercices Notes Bibliographie Chapitre Calculs rapides sur les séries Séries formelles La méthode de Newton pour le calcul d ? inverses Convergence quadratique pour l ? inverse d ? une série formelle Algorithme Complexité Division de séries Application à la division Euclidienne Application au logarithme Extension inverse de matrices Itération de Newton formelle et applications Un résultat général Algorithme Applications Exponentielle Sommes de Newton Application à la somme et au produit composés Inverse compositionnel Systèmes La composition des séries Méthode na? ve Pas de bébés ??pas de géants L ? algorithme de Brent Kung Exercices Notes Bibliographie Chapitre Division euclidienne fractions rationnelles et récurrences linéaires à coe ?cients constants Division de polynômes Méthode na? ve Algorithme rapide Le cas des entiers Application aux calculs modulaires Développement de fractions rationnelles CAlgorithmes rapides pour les polynômes séries formelles et matrices Suites récurrentes linéaires à coe ?cients constants Prélude les nombres de Fibonacci Calcul rapide des termes d ? une suite Propriétés de clôture Application tests de primalité