Abstract FR:

L'objectif de cette etude est d'avancer dans la recherche d'une borne inferieure du nombre d'additions necessaires a l'evaluation des systemes de formes lineaires. L'originalite de cette these reside dans la multiplicite des approches du probleme: une representation des algorithmes de calcul de ces systemes sous forme de graphes de calculs lineaires nous a permis de definir des simplifications sur ces algorithmes ; grace a l'algebre lineaire, on peut, dans certains cas, dire si un systeme donne peut etre optimise par rapport a l'algorithme de calcul trivial ; la complexite structurelle enfin, nous a permis de prouver la np-completude de 4 questions issues du probleme de base. De plus, une version lineaire de la conjecture forte de strassen a ete demontree sur les entiers modulo 2 (tout algorithme optimal de calcul de 2 formes lineaires a variables disjointes est la reunion de 2 algorithmes disjoints optimaux), et generalisee. Une annexe presente une approche geometrique de la question, ainsi que le probleme de morgenstern: existe-t-il des configurations de points dans le plan projectif reel telles tous les algorithmes optimaux de calcul de ces points soient complexes ? enfin, un logiciel de manipulation symbolique de graphes et de formes lineaires est decrit