cours-complexite2

Cours : complexiteChristophe RitzenthalerNovember 12, 20081 Quelques notions generales1.1 PrincipesLe temps d’execution d’un programme depend de plusieurs donnees :1. du type d’ordinateur utilise;2. du langage utilise (representation des donnees);3. de la complexite abstraite de l’algorithme sous-jacent.Pour le mesurer en MAPLE, on peut utiliser les commandes suivantes (ici pour unprogramme g) :iS := [seq([i;time(g(10 ))];i = 1::: 10)]:En general, on veut s’abstraire des deux premieres donnees. Pour se faire, il faut ^etreen mesure de donner un cadre theorique a l’algorithmique. Pour le premier point cecise fait par la de nition d’un ordinateur ‘universel’ (une machine de Turing) qui bienqu’extr^emement simple peut reproduire le comportement de n’importe quel ordinateurexistant. Pour s’abstraire du second point, on regardera des classes d’equivalence decomplexite (voir plus bas) plut^ ot que la complexite elle-m^eme, ce qui permettra de ne passe preoccuper des constantes qui interviennent dans les changements de representations‘naturelles’ et dans la de nition des operations elementaires.La mesure de la complexite d’un algorithme c’est :1. evaluer les ressources (memoire et CPU) utiles;2. Comparer deux algorithmes pour le m^eme probleme;3. donner une borne sur ce qui est e ectivement possible de resoudre. On considere60aujourd’hui qu’on peut realiser en temps raisonnable 2 operations. Quant a la10memoire elle ...