IN-202-Cours

Description

IN202 - AlgorithmiqueNotes de CoursLaurent CanetLe 8 juin 2002Table des mati`eres1 Syst`eme formel de preuve de programme de O’Hare 31.1 R`egles et axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Construction de programmes sur invariant . . . . . . . . . . . . . . . 41.2.1 Exemple : somme des ´el´ements d’un tableau . . . . . . . . . . 52 Probl`emes de recherches 62.1 Remarques sur l’´evaluation de complexit´e d’un programme . . . . . . 62.2 Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.1 Code Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.2 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Recherche s´equentielle . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.2 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4 Recherche arri`ere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.2 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Tris 113.1 Slowsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.1.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.1.2 Complexit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . ...

Informations

• Publié par: Phuwyor
• Nombre de lectures: 11
• Langue: Français

Extrait

IN202 - Algorithmique Notes de Cours

LaurentCetan

Le

8

juin

2002

Tabledesmatie`res

1Syste`meformeldepreuvedeprogrammedeO’Hare 1.1R`eglesetaxiomes............................. 1.2 Construction de programmes sur invariant . . . . . . . . . . . . . . . 1.2.1Exemple:sommedese´le´mentsd’untableau.......... 2Proble`mesderecherches 2.1Remarquessurl’´evaluationdecomplexit´ed’unprogramme...... 2.2 Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Code Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2Complexite´............................ 2.3 Recherche ´ ntielle . . . . . . . . . . . . . . . . . . . . . . . . . . seque 2.3.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2Complexite´............................ 2.4Recherchearrie`re............................. 2.4.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2Complexite´............................ 3 Tris 3.1 Slowsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Complexit´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Segmenter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Code Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3Complexit´eduQuicksort..................... 3.2.4Ame´liorationduquicksort.................... 3.3Complexit´eminimumd’unalgorithmedetri.............. 4Approchediviserpourregn´er 4.1Diviserpourr´egner............................ 4.1.1 Tri Fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2Limitesdel’approchediviserpourr`egner................ 5Complexit´edesalgorithmes 5.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2Calculscourantsdanslecalculdescomplexit´es.............

1

3 3 4 5 6 6 6 7 7 8 8 8 9 9 10 11 11 11 11 12 12 13 13 15 15 16 16 16 16 18 18 18

6

Programmation Dynamique 6.1 Cas concret : fibonnaci . . . . . . . . . . . . . . . . . . . . . . . 6.2 Exemple : Multiplication de matrices . . . . . . . . . . . . . . . 6.2.1Exempledel’importanceduparenth`esage........ 6.2.2 Algorithme de calcul. . . . . . . . . . . . . . . . . . . . . 6.2.3Couˆtminimum....................... 6.2.4 Calcul optimal du produit . . . . . . . . . . . . . . . . . Exemple:Recherchedupluslongsous-motcommun`a2chaines 6.3.1Tailleduproble`me..................... 6.3.2 Reconstruction de la solution . . . . . . . . . . . . . . . 6.3.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.4 Affichage du plus long sous mot . . . . . . . . . . . . . .

6.3

2

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

19 19 20 20 21 21 22 23 23 23 24 24

Chapitre 1

Syst`emeformeldepreuvede programme de O’Hare

Onpeutre´sumerunprobl`emeenuneformelogique: E P S |{z} |{z} |{z} Logique du 1er ordre  Programme Logique  du 1er ordre Dela`,plusieursreglesagissentsurcesenonces: ` ´ ´

1.1R`eglesetaxiomes R´egledelapost-condition: EP S 0 ;S 0 ⇒S−7→EP S

Re´gledelapr´e-condition: E 0 P S;E 0 ⇒E7−→EP S

R´egleduou: EP S;E 0 P S−→7(E∨E 0 )P S

Re´gledutextitet:

EP S;EP S 0 7−→EP(S∧S 0 )

3

R`egledusi-sinon: (E∧B)P S; (E∧B)QS→7−E{Si B alors P sinon Q}S Remarque:L’e´valuationdeBnedoitpasmodifierE. Re`gledutant-que: (E∧B)P E;−7→E{tant que B f aire P}(E∧B)

Axiomes d’affectation : EP A;AQS→7−E{P;Q}S

Exemple ::trermeno´D EP S;E 0 P S 0 7−→(E∧E 0 )P(S∨S 0 ) 1.EP S 2.E 0 P S 0 3.E∧E 0 ⇒E 4. (E∧E 0 )P Ste1rusnoitidnocer´(P3) 5. (E∧E 0 )P S 0 oisnrue2e´ocdnti(Pr)t3 6. (E∧E 0 )P(S∧S 0 udeR()lge`ETsur 4 et 5) 7. (S∧S 0 )⇒(S∨S 0 ) 8. (E∧E 0 )P(S∨S 0 ) (Postcondition sur 7 et 8)

1.2 Construction de programmes sur invariant Construire un prog d´crit par l’invariant, c’est utiliser une proposition ramme e bool´eenneI(x 1 , x 2 ,∙ ∙ ∙, x n ), fonction de plusieurs variablesx i tleprobluid´ecriq,e`em a`uninstantdonne´.Lorsquel’onveutfaireunalgorithmequire´soudEP Sas´ebsur un invariant, on doit donner plusieurs propositions : Invariant :selbD´ecritlaposiitnoudrpbo`lmeeenfonctiondevariax i . Initialisation :Ce sont des conditions sur les variablesx i , tels que la proposition Eerv´itsoet´eifiI(x i t´egalem)lesoine.t Conditiond’arrˆet:Ce sont des conditions sur les variablesx i , tels que la propo- sitionS´ifilee,ogprmmraa’dneˆrrtsetre´v.Leefi´ri´etvoisoitidnocaleuqsro e e doit avoir fini son traitement, etSe´fiirevt.ees Implications :Elles sont de la formeI(x 1 , x 2 ,∙ ∙ ∙, x n ) V i (P i vraies)⇒I(x 0 1 , x 0 2 ,∙ ∙ ∙, x 0 3 ). Ou`P i sopisitnontdespropresentee´r Onende´duitl’expression: I(x i )T AN T QU EoC(ˆet)’arriondnditF AIRE P i I(x i )∧(oiodCndntieˆ)ta’rr

4

1.2.1Exemple:sommedese´le´mentsd’untableau Soitunprogrammere´alisantlasommedetousles´ele´mentsde0a`n−1 d’un tableauTutpnorrgmaemvPe´.Onveu:tnaviusl’ntfiari´encno´e n−1 (n >0)P
S= X T[i] ! i=0

Onseproposedede´crireceprogrammeparl’invariant: Invariant :I(s, k)≡s= P i k = − 0 1 T[i] .sest la somme deskrpmeeientsders´el´emT. Initialisation :s= 0 etkedessommmier0pree´em´sleia0ttnfs.effEnlaet0.= DoncI(0,v´st)e0.e´fiire Conditiond’arrˆet:k=n.Onsa’rreˆetolsruqlena’oear´s´lilaeemmosseden premierse´le´ments,commedemande´. Implication :I(s, k)∧(s=s+T[k])⇒I(s, k+ 1).

En sortie du programme, on auraI(s, k)∧(k=n). La translation de cet algorithme enpseudolangageesttre`ssimple:

s <- 0 k <- 0 // Ici on a I(0,0) tant que (k != n) faire : s <- s + T[k] // Ici on a I(s,k+1) k <- k + 1 // Ici on a I(s,k) fin tant que // Ici on a I(s,n)

5

Chapitre 2

Proble`mesderecherches

Leprobl`emequenousnousposonsestderechercherune´l´ement(nombre,carac- te`reouautre)dansuntableauhomog`ened’e´lements.Laparticularite´decetableau estqu’ilestdejatrie´dansl’ordrecroissant(cequiimposed’avoirunerelationd’ordre ` entreles´el´ements).

2.1Remarquessurl’e´valuationdecomplexite´d’un programme Dansceparagrapheetceuxquisuivront,nousallons´evaluerletempsd’e´xecution des programmes en fonction de la taillenargosemm,orlbdpu.Com`emer2prpare c’estcomparerlestempsd’e´xecutiondanslespiresdescasrespectifs.Lesconstantes de´pendentdelamachinequi´executeral’algorithme.

D´efinition:LesePecedtgorpmmar´eomplexitO(f(n)) s’il existeαetn 0 tels que : ∀n≥n 0 T p (n)≤αf(n) O`uT p (nas.descpiresnelPeadarmmrpgoticuduond’psxe´eletnmeterperese´) Remarque :Si le programme P est enO(n), alors il est aussi enO(2n),O( n 2 ) ou O(n 2 ).

2.2 Recherche dichotomique Supposonsquel’onchercheun´ele´mentnot´eedans un tableauT. Le programme derecherchedichotomiquequenousallonsmettreaupointre´pond`al’´enonc´esui- vant : (T[0]≤e≤T[n−1])RD(T[k]≤e≤T[k+ 1]) Invariant :I(i, j)≡T[i]≤e≤T[j−1] Conditiond’arrˆet:j=i+ 2 Initialisation :(i= 0)∧(j=n)

6