Modélisation et algorithmes numériques et symboliques (4I901).
Équipe pédagogique
J. Berthomieu, S. Graillat, M. Safey El Din.
Description générale
Les algorithmes de calcul ont une place centrale dans de nombreux domaines
de l'informatique (cryptologie, intelligence artificielle, vision, etc.) et
des sciences de l'ingénieur. Il convient alors de concilier fiabilité
et efficacité du calcul.
Dans cette UE, nous étudierons deux modèles de représentations des
nombres (exact/multi-précision et approché/flottant) et développeront des
algorithmes symboliques et numériques basés sur ces modèles.
Nous nous attacherons à évaluer la qualité des algorithmes du point de vue
de la fiabilité (précision dans le cas d'algorithmes numériques) que
de l'efficacité (analyses de complexité). Les travaux sur machines permettront de
mettre en oeuvre ces algorithmes dans le cadre de systàmes de calcul (formel ou
numérique) sur des probl&agrav;emes concrets.
Semainier indicatif
- Semaine 1 : Représentations des entiers multi-préision, des flottants. Éléments de Z/pZ, corps finis. Arithmétique de base
- Semaine 2 : Algorithmes algébriques élémentaires (Euclide) et applications
à l'évaluation/interpolation (restes chinois)
- Semaine 3 : Éléments d'algàbre linéaire (Gauss, LU, rang et déterminant)
- Semaine 4 : Polynômes à une indéterminée (gcd, extraction de racines par Sturm)
- Semaine 5 : Polynômes en deux variables (résultant, intersection de courbes).
- Semaine 6 : Méthode de Newton pour les équations non-linéaires
- Semaine 7 : Décomposition en valeurs singulière et application à la compression d'images
- Semaine 8 : Calcul numérique de vecteurs propres, valeurs propres ; application à l'algorithme PageRank
- Semaine 9 : Transformée de Fourier discrète, applications en traitement du signal et au calcul formel
- Semaine 10 : Méthodes de Monte-Carlo, application au pricing en finance