Théorème d'accélération linéaire

Le théorème d'accélération linéaire ou de speedup linéaire est un théorème de théorie de la complexité, un domaine de l'informatique théorique. On peut en fait distinguer deux théorèmes, l'un concernant les classes de complexité en espace et l'autre les classes de complexité en temps. Tous deux ont pour conséquence de regrouper les mesures de complexité qui ne diffèrent que d'une constante, et justifie donc la notation grand O utilisée dans le domaine.

Le théorème de d'accélération en temps est dû à Juris Hartmanis et Richard Stearns^[1].

Énoncés[modifier | modifier le code]

Théorème d'accélération en temps[modifier | modifier le code]

Pour toute machine de Turing $T$ , calculant une fonction $g$ en temps $f(n)$ (où $n$ est la taille de l'entrée) et toute constante $1>c>0$ , il existe une machine de Turing $T'$ calculant $g$ en temps $2+n+cf(n)$ ^[2].

Théorème d'accélération en espace[modifier | modifier le code]

Pour toute machine de Turing $T$ , calculant une fonction $g$ en espace $f(n)$ (où $n$ est la taille de l'entrée) et toute constante $1>c>0$ , il existe une machine de Turing $T'$ calculant $g$ en espace $cf(n)$ .

Idée de la démonstration[modifier | modifier le code]

L'idée principale de la preuve est de coder plusieurs lettres en une seule : en faisant des groupes de lettres on peut utiliser moins de place (puisque seul compte le nombre de cases utilisées et pas la taille des lettres) et « sauter » de groupe de lettres en groupe de lettres, ce qui prend moins de temps. En faisant des groupes de 1/c lettres on obtient les résultats annoncés.

L'idée est simplement que plusieurs calculs peuvent être faits en une étape de calcul. Ceci est comparable au changement de taille des registres de processeur de 32 à 64 bits^[3].

Conséquences[modifier | modifier le code]

En théorie de la complexité, les constantes multiplicatives ne sont pas prises en compte.

Notes et références[modifier | modifier le code]

↑ (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7)
↑ (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993 (ISBN 978-0-201-53082-7) chapitre 2.4. Linear speedup
↑ Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.1.1 (« Classes de complexité en temps »), Un peu de recul, p. 33.

Portail de l'informatique théorique

[1] (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7)

[2] (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993 (ISBN 978-0-201-53082-7) chapitre 2.4. Linear speedup

[3] Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.1.1 (« Classes de complexité en temps »), Un peu de recul, p. 33.

[1]

[2]

[3]