Licence informatique L3 Annee

Description

Niveau: Supérieur, Licence, Bac+3
Licence informatique - L3 Annee 2011/2012 Conception d'algorithmes et applications (LI325) COURS 4 CONCEPTIONS D'ALGORITHMES ET APPLICATIONS COURS 4 Resume. Dans cette quatrieme seance, nous abordons les algorithmes de type Programmation Dynamique. Nous illustrons ce type de programmation par un premier exemple introductif concernant le calcul du n-ieme nombre de Fibonacci, puis par un algorithme plus consequent permettant de construire des arbres de recherche optimaux. 1. Programmation Dynamique La programmation dynamique, comme le principe Diviser pour Regner, est un principe algo- rithmique reposant sur une approche recursive des problemes. Certains problemes, quand on les scinde, font appel plusieurs fois aux memes sous-problemes, ou a des sous-problemes qui ne sont pas independants les uns des autres. Dans ce cas, les methodes Diviser pour Regner ne sont pas aussi efficaces. En voici un exemple tres simple. 1.1. Suite de Fibonacci. La suite de Fibonacci est definie recursivement par F0 = 0, F1 = 1 et Fn+2 = Fn+1 + Fn pour n ≥ 0. Supposons que l'on cherche a calculer le k-ieme terme de cette suite. Si on utilise directement le principe Diviser pour Regner suivant : Diviser : On remarque que pour calculer Fk, il suffit de savoir calculer Fk?1 et Fk?2. Regner : On resout le probleme recursivement pour Fk?1 et Fk?2 si l'indice est superieur a 2, sinon on remplace directement.

• cout moyen


• arbre binaire de recherche optimal


• cles ki


• fibo-pg-rec

Sujets

• Coût moyen

Informations

• Publié par: thieg
• Nombre de lectures: 30
• Langue: Français

Extrait

Licence informatique - L3

Anne´e2011/2012

Conception d’algorithmes et applications (LI325) COURS 4

CONCEPTIONS D’ALGORITHMES ET APPLICATIONS COURS 4

R ´ esume ´ .Dnaatri`emescettequsuonrobaae´s,ecnorlghmitnsdosalearmmrPgoytepseednatio Dynamique. Nous illustrons ce type de programmation par un premier exemple introductif concernant le calcul dunlanurapsemhtirogonibeFedui,pciac-`imenemorbconsplusent´equ permettant de construire des arbres de recherche optimaux.

1.Programmation Dynamique Laprogrammationdynamique,commeleprincipeDiviserpourRe´gner,estunprincipealgo- rithmiquereposantsuruneapprocher´ecursivedesproble`mes.Certainsprobl`emes,quandonles scinde,fontappelplusieursfoisauxmeˆmessous-proble`mes,oua`dessous-proble`mesquinesont pasind´ependantslesunsdesautres.Danscecas,lesm´ethodesDiviserpourR´egnernesontpas aussiefficaces.Envoiciunexempletr`essimple.

1.1.Suite de Fibonacci.Lrsivementpartseifie´dreinuce´uiasdeteboFiccnaF 0 = 0,F 1 = 1 et F n+2 =F n+1 +F n pourn≥ellureaccleha`rchenc’oelqunssooppuS.0kcettmedeeteri`em-e suite.SionutilisedirectementleprincipeDiviserpourR´egnersuivant: Diviser :On remarque que pour calculerF k , il suffit de savoir calculerF k−1 etF k−2 . Re ´ gner:Onlbe`peoruolt´rsentmevesiurecr´meruopF k−1 etF k−2 ’lniidecsestpue´riiseur`a2, sinon on remplace directement. Combiner :On additionneF k−1 etF k−2 .

On obtient le pseudo-code ci-dessous :

Algorithme 1: FIBO(n) Entr´ees: Un entier positifn. Sorties: LendeFebinomenemorb-i`.ciac 1 sin <2alors 2 retournern 3 sinon 4 retournerFIBO(n−1)+FIBO(n−2)

Analyse de l’algorithme FIBO : Preuve de Terminaison : Imme´diat. PreuvedeValidite´: Imme´diat. AnalysedelaComplexite´en nombre d’additions : Onaclairementlarelationdere´currencesuivantepourlenombred’additions:T(0) = 0,T(1) = 0 √ n etT(n) =T(n−1)+T(n−2)+1. Un calcul rapide montre queT(n) = Θ(φ) avecφ5)= (1+ /2.

Cetteapprochesere´v`eletropcouteuse,caroncalculeplusieursfoislesmˆemessous-proble`mes commelemontrelede´roulementdel’algorithmepourtrouverF 5 : 1