Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Algorithme correction complexite

De
12 pages
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


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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin