Calcul Formel

Informations Importantes

Cette année, les salles ne sont pas totalement fixées.

• CM les Mercredi de 14h à 15h20 - A29 / Vérifiez l’amphi sur CELCAT.
• TD/TP (SageMath) de 15h30 à 18h20 - CREMI, vérifiez la salle sur CELCAT.

Notes de Cours

Vous pouvez trouver le Poly des années passées. Mon cours s’inspire fortement de ce dernier mais quelques modifications pourront avoir lieu ici et là.

Cours 01: Introduction au calcul formel

Contenu du cours

• Quelques résultats d’indécidabilité

• Structures algébriques effectives

• Introduction à l’analyse des algorithmes

• Quelques exemples de calculs prenant moins d’une seconde en Sage sur mon ordinateur: demo.sage.

Séance de TD

• TD01 - Initiation à Sage

Cours 02: Analyse d’algorithmes

Contenu du cours

• Analyse des algorithmes: correction partielle, terminaison, complexité.
• Algorithmes sur les entiers et polynômes.

Séance de TD

• TD02 - Analyse d’algorithmes.

Cours 03: Vers la multiplication rapide

Contenu du cours

• Observation: de nombreux algorithmes dépendent de la multiplication.
• Exemple: Exponentiation, et exponentiation rapide.
• Introduction du paradigme diviser pour régner
• Algorithme de Karatsuba
• Théorème maître

Séance de TD

• TD03 - Diviser pour régner

Cours 04: Transformée de Fourier Rapide

Contenu du cours

• Méthode d’évaluation-Interpolation
• Nouvelle représentation des polynômes
• Racines primitives de l’unité
• Transformée de Fourier Discrète
• Algorithme de transformée de Fourier rapide (Multi-évaluation)
• Application au produit de polynômes
• Ouverture: Vers l’algorithme de Schönhage et Strassen.

Séance de TD

• Aujourd’hui nous vous distribuons deux feuilles de TD (pour les deux prochaines séances)
  • TD04 - FFT et diviser pour régner
  • TD05 - TP FFT