Travaux Pratiques#

Consignes / Instructions

Parcourez les exercices suivants et piochez en un pour préparer une présentation courte d’environ trois à cinq minutes. Soulignons qu’il s’agit d’un menu à la carte et que vous pouvez choisir d’étudier certains points, pas tous, pas nécessairement dans l’ordre, et de façon plus ou moins fouillée. Vous pouvez aussi vous poser d’autres questions que celles proposées. Vos investigations devront comporter une partie traitée sur ordinateur et, chaque fois que pertinent, des représentations graphiques de vos résultats.

Pour rédiger le support de votre présentation, vous téléchargerez ce modèle.ipynb. Lorsque vous aurez terminé, vous déposerez votre présentation dans ce dossier partagé, après l’avoir renommé sous la forme Prénom1-Nom1-Prénom2-Nom2-Présentation.ipynb. Si vous utilisez des fichiers annexes, vous les déposerez aussi en prenant soin de les nommer en suivant la même convention.

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.

Exercice: 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.