Travaux Pratiques

Parcourir les exercices suivants et en piocher un pour préparer une démonstration courte (5 minutes). Ensuite, jouer avec les exercices de votre choix. En fin de séance (vers 11h30), chacun d’entre vous présentera sa démonstration aux autres.

Exercice: Karatsuba

  1. Implanter l’algorithme naïf pour multiplier deux polynômes

  2. Implanter l’algorithme de Karatsuba pour multiplier deux polynômes

  3. Faire un banc d’essai pour ces deux algorithmes, et tracer un graphe permettant de comparer simultanément leur complexité pratique entre elles et avec leur complexité théorique.

  4. Avec votre implantation, à partir de quel seuil est-il préférable d’utiliser l’algorithme de Karatsuba?

Prolongements possibles:

  1. Implanter un algorithme mixte Karatsuba/naïf qui tienne compte du seuil obtenu. Comparer.

  2. Comparer la complexité pratique de votre implantation du produit avec celle de la bibliothèque de Sage.

  3. Deviner, d’après sa complexité pratique, le ou les algorithmes utilisés par Sage.

  4. Implanter le produit de deux entiers par Karatsuba; comparer avec l’implantation pour les polynômes.

Transformée de Fourier rapide

Voir ce sujet de TP.

Exercice: Illustration de Newton numérique

Réaliser une animation similaire à celle de l”article de la Wikipedia.

Exercice: Convergence de Newton numérique

  1. Choisir une équation de la forme \(f(x) = 0\) et calculer des approximations successives \(x_0, x_1, \dots,\) de l’une de ses solutions à l’aide d’une itération de Newton.

  2. Tracer le graphe du nombre de décimales correctes en fonction du nombre d’itérations.

Exercice: Inversion de séries formelle par itération de Newton

Soit \(B(z)\) une série formelle dans \(K[[z]]\) dont on veut calculer l’inverse \(A(z)=B^{-1}(z)\). En particulier, on supposera que son terme constant \(b_0=B(0)\) est inversible dans \(K\).

On pose la fonction \(F(X) = B(z) - 1/X\), de sorte que \(A(z)\) satisfait l’équation fonctionnelle implicite \(F(A(z))=0\).

  1. Choisir \(A_0(z)\) tel que \(A_0(z)\equiv A(z) [z]\)

  2. Supposer que l’on ait trouvé \(A_i(z)\) tel que \(A_i(z)\equiv A(z)[z^k]\). Appliquer une itération de Newton pour retrouver l’expression de \(A_{i+1}\) vue en cours, et donner sa précision (i.e. combien de termes de \(A(z)\) sont obtenus).

Exercice: Comptage des arbres par itération de Newton

Cet exercice est un complément pour la section 15.1.2 «Dénombrement d’arbres par séries génératrices» du livre «Calcul Mathématique avec Sage».

On rappelle que l’ensemble \(C\) des arbres binaires complets est défini récursivement en spécifiant qu’un arbre binaire complet est soit une feuille, soit consiste en une racine à laquelle sont attachés un sous-arbre gauche et un sous-arbre droit. Soit \(C(z)\) la série génératrices des arbres binaires complets comptés par nombres de feuilles.

  1. Écrire l’équation ensembliste satisfaite par \(C\).

  2. La traduire en équation algébrique satisfaite par \(C(z)\).

  3. Choisir \(C_0(z)\) tel que \(C_0(z)\equiv C(z) [z]\).

  4. Par itération de Newton, calculer successivement \(C_1(z)\), \(C_2(z)\), … et indiquer le nombre de termes de \(C(z)\) obtenus à chaque étape. Indication: on pourra au choix représenter les \(C_i(z)\) par:

    • Des fractions rationnelles (représentées par des expressions), en utilisant la commande taylor pour les développer en série entière.

    • Des séries tronquées à l’ordre approprié (éventuellement représentées par des polynômes), en utilisant l’exercice précédent pour les calculs d’inverse.