Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

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