Abstract FR:

On étudie quelques problèmes de complexité en algèbre élémentaire. On introduit la notion de structure algébrique complètement C-calculable. On rappelle trois sortes de calculabilité en temps polynomial pour l'algèbre linéaire sur un corps : celle des déterminants, celle du produit d'une liste de matrices et celle de la méthode du pivot ameliorée à la Bareiss. On étudie le bon fonctionnement de la version formelle de la suite de Sturm appelée suite de Sturm-Habicht pour le comptage des racines réelles sur un intervalle et la calculabilité en temps polynomial d'une relation de Bezout complète entre plusieurs polynômes. On discute la calculabilité des opérations arithmétiques et de la recherche des zéros, pour une description des nombres algébriques, réels ou complexes, basée sur le système D5