Algorithme correction complexite
12
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
12
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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.
Voir
- analyse de complexite
- cout moyen
- recherche dichotomique
- preconditions
- meme sans connaıtre
- preuves dans le code source
- preuve de correction
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´e aregarderdepluspr eslanotio 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 probl eme 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.A larecherchedutempsperdu. 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´thodescandidates are´soudreceproble me. 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
