Algorithme correction complexite

De
Publié par

CHAPITRE VIII Algorithme, correction, complexite All is well that ends well. William Shakespeare Objectifs Un des objectifs de ce cours est de developper une notion de plus en plus precise de complexite de calcul. Pour ceci il faut preciser la methode utilisee. Afin de choisir parmi les methodes admises il faut d'abord une specification. On est ainsi mene a regarder de plus pres la notion d'algorithme. Ce chapitre discutera ce concept, en soulignant les trois points cles : terminaison, correction, complexite. Sommaire 1. Qu'est-ce qu'un algorithme ? 1.1. Algorithme = specification + methode. 1.2. Preuve de cor- rection. 1.3. Le probleme de terminaison. 2. La notion de complexite et le fameux « grand O » . 2.1. Le cout d'un algorithme. 2.2. Le cout moyen, dans le pire et dans le meilleur des cas. 2.3. Complexite asymptotique. 2.4. Les principales classes de complexite. 2.5. A la recherche du temps perdu. 1. Qu'est-ce qu'un algorithme ? Exemple 1.1. En utilisant l'arithmetique des entiers, on veut calculer le coefficient binomial ( n k ) : Specification VIII.1 Calcul du coefficient binomial ( n k ) Entree: deux entiers n et k Sortie: le coefficient binomial ( n k ) En voici quatre methodes candidates a resoudre ce probleme.

  • analyse de complexite

  • cout moyen

  • recherche dichotomique

  • preconditions

  • meme sans connaıtre

  • preuves dans le code source

  • preuve de correction


Publié le : lundi 18 juin 2012
Lecture(s) : 132
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 12
Voir plus Voir moins
CHAPITRE VIII
All is well that ends well. William Shakespeare
Algorithme,correction,complexit´e Objectifs Undesobjectifsdececoursestdede´velopperunenotiondeplusenpluspr´ecisede complexite´ de calcul.Pourceciilfautpr´eciserla me´thode utilise´e. An de choisir parmi les me´thodes admises il faut d'abord une spe´cication .Onestainsimen´earegarderdepluspreslanotio d n 'algorithme . Ce chapitre discuteraceconcept,ensoulignantlestroispointscl´es: terminaison , correction , complexit´e . Sommaire 1. Qu'est-ce qu'un algorithme ? 1.1.Algorithme=spe´cication+m´ethode.1.2.Preuvedecor-rection. 1.3. Le probleme de terminaison. 2. La notion de complexite´ et le fameux « grand O » . 2.1. Le co ˆut d'un algorithme. 2.2. Le co ˆut moyen, dans le pire et dans le meilleur des cas. 2.3. Complexite´ asymptotique. 2.4. Les principalesclassesdecomplexit´e.2.5.Alarecherchedutempsperdu. 1. Qu'est-ce qu'un algorithme ? Exemple 1.1. En utilisant l'arithme´tique des entiers, on veut calculer le coefcient binomial kn : n Spe´cication VIII.1 Calcul du coefcient binomial k Entre´e: deux entiers n et k Sortie: le coefcient binomial kn Envoiciquat´thodescandidatesare´soudreceprobleme. re me Me´thode VIII.2 Calcul du coefcient binomial nk si k < 0 ou k > n alors retourner 0 sinon retourner kn −− 11 + n k 1 Cetteme´thodeestcarr´ementfausse.Voyez-vouspourquoi? M´ethodeVIII.3 Calcul du coefcient binomial kn si k = 0 ou k = n alors retourner 1 sinon retourner kn −− 11 + nk 1 Cettem´ethodeestfaussedanslesensqu'elleneseterminepastoujours.(Expliquerpourquoi.)D'un autrecote´,quandelles'arrˆete,ellerenvoieler´esultatcorrect.(Led´etailler.) M´ethodeVIII.4 Calcul du coefcient binomial kn si k < 0 ou k > n alors retourner 0 si k = 0 ou k = n alors retourner 1 retourner kn −− 11 + n k 1 Cetteme´thodesetermineetdonneler´esultatcorrect.(Lemontrer.) Me´thode VIII.5 Calcul du coefcient binomial nk si k < 0 ou k > n alors retourner 0 b 1, k min ( k n k ) pour i de 1 a k faire b b ( n i + 1 ) i retourner b Cettem´ethodeeste´galementcorrecte,maisplusefcacequelapr´ec´edente.(Pourquoi?) 139
140
ChapitreVIII—Algorithme,correction,complexite´
1.1.Algorithme=spe´cication+m´ethode. Commeonned´evelopperapaslathe´orieabstraitedes algorithmes, nous nous contentons ici d'une de´nition pragmatique : D´enition1.2. Unalgorithmed´ecritunproce´de´,susceptibled'unere´alisationme´canique,pourre´soudre un probleme donne´. Il consiste en une sp´ecication (ce qu'il doit faire) et une m´ethode (comment il le fait) : – La spe´cication pre´ciselesdonn´eesd'entre´eavecles pr´econditions que l'on exige d'elles, ainsi que les donne´es de sortie avec les postconditions que l'algorithme doit assurer. Autrement dit, les pre´conditions de´nissent les donne´es auxquelles l'algorithme s'applique, alors que les postcondi-tionsr´esumentler´esultatauquelildoitaboutir. – La m´ethode consiste en une suite nie d'instructions, dont chacune est soit une instruction pri-mitive (directement exe´cutable sans explications plus de´taille´es) soit une instruction complexe (qui ser´ealiseenfaisantappelaunalgorithmede´jad´e.niE)nparticulierchaqueinstructiondoitˆetre exe´cutabledemaniereunivoque,etnedoitpaslaisserplaceal'interpr´etationoual'intuition. Exemple 1.3. Un algorithme de´crit souvent le calcul d'une application f : X Y . –Ladonne´ed'entr´eeestd'uncertaintype,elleappartientauneclasse X 0 . –Lapre´conditionpre´ciseledomaineded´enition X X 0 , e´ventuellement restreint. – La donne´e de sortie est d'un certain type, elle appartient a une classe Y . – La postcondition pre´cise pour tout x X la valeur cherche´e y = f ( x ) . –Lam´ethodeexplicitelese´tapesducalculentoutde´tail. Dansl'exemple1.1lesdonne´esd'entr´ee ( n k ) appartiennent a l'ensemble X 0 = Z 2 , et on exige que la methode s'applique a tout l'ensemble X = X 0 .Ler´esultatestunentieretappartientdonca Y = Z . La ´ postcondition exige que f ( n k ) soit´egalaucoefcientbinomial nk . Remarque 1.4 (premiere reformulation . )Lasp´ecicationde´critleproblemequel'onchercheaesro´udre, en spe´ciant les « conditions aux bords » :lepointdede´partestx´eparlesdonne´esd'entre´e,donton supposecertainespre´conditions;lebutestd'arriveradesdonn´eesdesortie,pourlesquellesondoitgarantir certainespostconditions.La´ethodenesolutionaceprobleme,c'est-a-direuncheminallantdu m propose u de´part au but. (Le mot « me´thode » estd´erive´dugrec` Ι≅Ι ´ V ( hodos ) signiant « la voie » .) Bien s ˆur, pour unproblemedonn´e,plusieursme´thodessontpossibles,plusieurscheminsmenentaubut. Exemple 1.5. Il existe plusieurs solutions pour le probleme de recherche d'un objet dans une liste (cf. cha-pitreV).Lorsquelapre´conditionassurequelesdonn´eessontordonn´ees,lam´ethodepeutenproter.Ainsi l'algorithmesuivanteffectuecorrectementunerecherchedichotomiquesurunelisteordonn´ee.Travaille-t-iltoujourscorrectementsurunelistenonordonn´ee?(Donneruncontre-exemplelecas´eche´ant.) Algorithme VIII.6 Recherche dichotomique Entre´e: un e´le´ment b et une liste ordonne´e A = ( a 1 a 2      a n ) . Sortie: le premier indice k tel que a k = b ,oubiennontrouv´esi b n'appartient pas a A . i 1, j n tant que i < j faire m j i + 2 k : si b a m alors j m sinon i m + 1 si a i = b alors retourner i sinon retourner nontrouve´ Remarque 1.6 (deuxieme reformulation . ) Souvent on interprete la spe´cication comme un contrat : si l'instanceappelanteassurelespre´conditions,alorslam´ethodeappel´eesecharged'assurerlespostcondi-tions.Commentellelefaitestexplicit´edansla me´thode . (La me´thode ne fait pas partie du contrat ; dans lecasextrˆeme,ellepeutresterunsecretprofessionneldel'instanceappele´e.)Ilnefautpass'´etonnersila me´thodee´chouesilespr´econditionsnesontpasremplies.Cecin'estpaslafautealame´thode:lesdonne´es ne sont simplement pas dans son domaine d'application. Exemple 1.7. Danslapratiqueilesteng´en´eralprudentdetesterlespre´conditionsdansleslimitesdurai-sonnable.Maisjuridiquementparlantc'estlaresponsabilit´edel'instanceappelanteetnondelam´ethode pel´ee.Souventdetelstestssontcoˆuteux(voireimpossibles).Unexemplefrappantestlarecherchedi-ap chotomique : elle requiert une liste ordonne´e pour effectuer une recherche efcace, mais il serait ridicule, ende´butdechaquerecherche,deparcourirtoutelalistepourv´erierl'ordre. MAE 22 juin 2009
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.