Algorithme correction complexite

Algorithme correction complexite

-

Documents
12 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

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


Sujets

Informations

Publié par
Ajouté le 18 juin 2012
Nombre de lectures 134
Langue Français
Signaler un abus
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