Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours complexite1 pdf Cours complexit ?e Christophe Ritzenthaler November Quelques notions g ?en ?erales Principes Le temps d ? ex ?ecution d ? un programme d ?epend de plusieurs donn ?ees du type d ? ordinateur utilis ?e du langage utilis ?e repr ?esenta

Cours complexit ?e Christophe Ritzenthaler November Quelques notions g ?en ?erales Principes Le temps d ? ex ?ecution d ? un programme d ?epend de plusieurs donn ?ees du type d ? ordinateur utilis ?e du langage utilis ?e repr ?esentation des donn ?ees de la complexit ?e abstraite de l ? algorithme sous-jacent Pour le mesurer en MAPLE on peut utiliser les commandes suivantes ici pour un programme g S seq i time g i i En g ?en ?eral on veut s ? abstraire des deux premieres donn ?ees Pour se faire il faut etre en mesure de donner un cadre th ?eoriquea l ? algorithmique Pour le premier point ceci se fait par la d ?e ?nition d ? un ordinateur ? universel ? une machine de Turing qui bien qu ? extr emement simple peut reproduire le comportement de n ? importe quel ordinateur existant Pour s ? abstraire du second point on regardera des classes d ? ?equivalence de complexit ?e voir plus bas pluto t que la complexit ?e elle- m eme ce qui permettra de ne pas se pr ?eoccuper des constantes qui interviennent dans les changements de repr ?esentations ? naturelles ? et dans la d ?e ?nition des op ?erations ?el ?ementaires La mesure de la complexit ?e d ? un algorithme c ? est ?evaluer les ressources m ?emoire et CPU utiles Comparer deux algorithmes pour le m eme probl eme donner une borne sur ce qui est e ?ectivement possible de r ?esoudre On considere aujourd ? hui qu ? on peut r ?ealiser en temps raisonnable op ?erations Quanta la m ?emoire elle est de l ? ordre de octets On peut donc s ? int ?eresser adeux types de complexit ?e en temps et en m ?emoire Nous ne consid ?ererons que la premiere La complexit ?e abstraite se mesure en fonction de la taille des entr ?ees CExample Pour un entier il s ? agit du nombres de chi ?res n ?ecessaires ason ?ecriture On peut bien su r imaginer des circonstances ou d ? autres facteurs seraient plus importants Par exemple si un algorithme factorise un nombre al ?eatoire de plus en plus grand a chaque fois qu ? il rencontre un dans l ? ?ecriture du nombre On notera a b la taille de a en base b On a bien su r a b logb a Remarquons qu ? un changement de base multiplie la taille par une constante Pour une liste le parametre est le cardinal de la liste On peut noter que ceci est coh ?erent avec la complexit ?e pour les entiers car le tableau pourrait contenir les chi ?res du nombre Dans l ? algorithme de la division euclidienne on a deux entiers a b en entr ?ee On mesurera la complexit ?e en fonction du sup a b Pour une matrice carr ?ee de taille n c ? est n le parametre Dans le cas d ? op