“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 158 — #168
i
i
i
i
i
i
i
i
158
3
• Techniques de programmation déclarative
fausse mais courante de la loi originale est que la performance doublera environ tous
les deux ans. Cette interprétation semble se vérifier aussi.
11
La loi de Moore ne regarde qu’une petite période de temps par rapport au temps pendant lequel des calculs ont été faits par machine. Depuis le 19ème siècle, il y a eu au
moins cinq technologies pour le calcul par machine, y compris la mécanique, l’électromécanique, les tubes à vide, les transistors individuels et les circuits intégrés. Pendant
cette période plus longue, il est apparent que la croissance de la puissance de calcul à
toujours été exponentielle. Selon Raymond Kurzweil, qui a étudié cette croissance, la
prochaine technologie sera le calcul moléculaire en trois dimensions [57].
12
À cause de cette situation, la performance n’est généralement pas un problème
critique. Si votre problème est soluble en pratique, c’est-à-dire que l’on connaît un
algorithme efficace pour le résoudre, alors si vous utilisez de bonnes techniques de
conception algorithmique, le temps et l’espace effectifs utilisés par l’algorithme seront
presque toujours acceptables. En d’autres termes, si la complexité asymptotique du
programme est raisonnable, le facteur constant ne sera presque jamais critique. C’est
vrai même pour la plupart des applications multimédia (qui utilisent la vidéo et l’audio)
à cause des excellentes bibliothèques qui existent.
Les problèmes insolubles en pratique
Il existe des problèmes qui ne sont pas solubles en pratique. Il y a beaucoup de
problèmes qui sont chers en ressources calculatoires, comme dans les domaines de
l’optimisation combinatoire, la recherche opérationnelle, la simulation et le calcul
scientifique, l’apprentissage par ordinateur, l’infographie et la reconnaissance de la
parole et de la vision. Certains problèmes sont chers simplement parce qu’ils ont
beaucoup de travail à faire. Par exemple, les jeux avec un graphisme réaliste et les
effets spéciaux dans les films sont par définition toujours à la frontière ce qui est
possible. D’autres problèmes sont chers pour des raisons plus fondamentales. Par
exemple, les problèmes NP-complets. Ces problèmes sont dans la classe NP, c’està-dire qu’il est simple de vérifier une solution si on a un candidat.
13 Mais trouver
une solution peut être bien plus difficile. Un exemple simple est le problème de
satisfaisabilité des circuits digitaux. Soit un circuit digital combinatoire fait avec des
portes Et, Ou et Non : existe-t-il un ensemble d’entrées qui rend la sortie vraie ? Ce
problème est NP-complet [17]. Un problème NP-complet est un problème NP avec la
particularité que si on peut le résoudre en temps polynomial, alors on pourra résoudre
11. Par contre, l’augmentation de la fréquence horloge semble avoir nettement ralenti depuis quelques
années.
12. Kurzweil prétend que le taux de croissance est en train d’augmenter et mènera à une « singularité »
quelque part au milieu du XXI
e siècle.
13. NP veut dire « en temps non-déterministe polynomial ».
i
i
i
i
i
i
i
i
158
3
• Techniques de programmation déclarative
fausse mais courante de la loi originale est que la performance doublera environ tous
les deux ans. Cette interprétation semble se vérifier aussi.
11
La loi de Moore ne regarde qu’une petite période de temps par rapport au temps pendant lequel des calculs ont été faits par machine. Depuis le 19ème siècle, il y a eu au
moins cinq technologies pour le calcul par machine, y compris la mécanique, l’électromécanique, les tubes à vide, les transistors individuels et les circuits intégrés. Pendant
cette période plus longue, il est apparent que la croissance de la puissance de calcul à
toujours été exponentielle. Selon Raymond Kurzweil, qui a étudié cette croissance, la
prochaine technologie sera le calcul moléculaire en trois dimensions [57].
12
À cause de cette situation, la performance n’est généralement pas un problème
critique. Si votre problème est soluble en pratique, c’est-à-dire que l’on connaît un
algorithme efficace pour le résoudre, alors si vous utilisez de bonnes techniques de
conception algorithmique, le temps et l’espace effectifs utilisés par l’algorithme seront
presque toujours acceptables. En d’autres termes, si la complexité asymptotique du
programme est raisonnable, le facteur constant ne sera presque jamais critique. C’est
vrai même pour la plupart des applications multimédia (qui utilisent la vidéo et l’audio)
à cause des excellentes bibliothèques qui existent.
Les problèmes insolubles en pratique
Il existe des problèmes qui ne sont pas solubles en pratique. Il y a beaucoup de
problèmes qui sont chers en ressources calculatoires, comme dans les domaines de
l’optimisation combinatoire, la recherche opérationnelle, la simulation et le calcul
scientifique, l’apprentissage par ordinateur, l’infographie et la reconnaissance de la
parole et de la vision. Certains problèmes sont chers simplement parce qu’ils ont
beaucoup de travail à faire. Par exemple, les jeux avec un graphisme réaliste et les
effets spéciaux dans les films sont par définition toujours à la frontière ce qui est
possible. D’autres problèmes sont chers pour des raisons plus fondamentales. Par
exemple, les problèmes NP-complets. Ces problèmes sont dans la classe NP, c’està-dire qu’il est simple de vérifier une solution si on a un candidat.
13 Mais trouver
une solution peut être bien plus difficile. Un exemple simple est le problème de
satisfaisabilité des circuits digitaux. Soit un circuit digital combinatoire fait avec des
portes Et, Ou et Non : existe-t-il un ensemble d’entrées qui rend la sortie vraie ? Ce
problème est NP-complet [17]. Un problème NP-complet est un problème NP avec la
particularité que si on peut le résoudre en temps polynomial, alors on pourra résoudre
11. Par contre, l’augmentation de la fréquence horloge semble avoir nettement ralenti depuis quelques
années.
12. Kurzweil prétend que le taux de croissance est en train d’augmenter et mènera à une « singularité »
quelque part au milieu du XXI
e siècle.
13. NP veut dire « en temps non-déterministe polynomial ».