Algorithmique et Complexité
Un article maintenant célèbre de E. Wigner s'intitule << The
unreasonnable effectiveness of Mathematics in the Natural Sciences >>
Qu'en est-il vraiment ? Que peut-on calculer ? Comment le faire
effectivement, efficacement ?
Dans ce cours, nous essayerons d'apporter des éléments de réponses à ces
interrogations.
Ce module s'adresse en particulier aux étudiants intéressés par les
aspets effectifs et algorithmiques des mathématiques. A travers
des exemples détailés, nous donnerons une présentation
introductive du domaine, en abordant les points suivants:
- Représentation des données, calcul, algorithmes, mesures, coût.
- Algorithmique des structures de base (listes, graphes, ...).
- Arithmétique.
- Algèbre linéaire.
- Algorithmique des polynômes.
- Algorithmique géométrique.
- Classe de complexité, calculabilité.
Références:
- R. Sedgewick, Algorithms, Addison-Wesley, 1983, ISBN : 0-201-06672-6.
- T. Cormen, C. Leiserson, R. Rivest, Introduction à l'algorithmique,
Dunod, 1994, ISBN : 2-10-003128-7.
- K.O. Geddes, S.R. Czapor, G. Labahn, Algorithms for computer algebra,
Kluwer, 1992, ISBN : 0-7923-9259-0
- J.~von~zur~Gathen and Gerhard, J., Modern Computer Algebra,
Cambridge Univ. Press, 1999.
- D.A. Cox, J.B.
Little, D.B. O'Shea, Ideals, varieties and algorithms : an
introduction to computational algebraic geometry
and commutative algebra, Springer, 1992, ISBN : 0-387-97847-X (New York).
- ...