Licence informatique L3 Annee

Description

Niveau: Supérieur, Licence, Bac+3
Licence informatique - L3 Annee 2011/2012 Conception d'algorithmes et applications (LI325) COURS 5 Resume. Dans cette cinquieme seance, nous continuons l'exploration des algorithmes de type Programmation Dynamique. Nous traiterons grace a ce principe un probleme numerique (mul- tiplications de matrices enchaınees) et un probleme issu de la theorie des mots (recherche d'une plus longue sous-sequence commune). 1. Programmation Dynamique appliquee a l'Algorithmique Numerique 1.1. Multiplications Matricielles Enchaınees. Nous allons ici illustrer le principe de la Pro- grammation Dynamique par un algorithme qui resout le probleme des multiplications matricielles enchaınees. On suppose que l'on dispose d'une sequence (A1, A2, ..., An) de n matrices a coefficients entiers, et que l'on souhaite calculer le produit A1A2...An. Bien evidemment, il y a plusieurs fac¸ons de faire ce calcul qui dependent de l'ordre dans lequel on fait les multiplications. Cet ordre est clas- siquement determine par un parenthesage qui indique les priorites. Par exemple, pour la sequence de matrices (A1, A2, A3, A4), le produit A1A2A3A4 peut etre calcule de cinq fac¸ons distinctes : (A1(A2(A3A4))), (A1((A2A3)A4)), ((A1A2)(A3A4)), ((A1(A2A3))A4), (((A1A2)A3)A4).

• multiplication


• sequence


• calcul suivant le parenthesage


• dimension pi?1 ?


• parenthesage optimal

Sujets

• Multiplication

Informations

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

Extrait

Licence informatique - L3

Anne´e2011/2012

Conception d’algorithmes et applications (LI325) COURS 5

R ´ esume ´ .sn’lxelpoctnniouesalgoriorationdepyemhttedsetscanDuinqciteae´seme`suon,ecn ProgrammationDynamique.Noustraiteronsgrˆace`aceprincipeunproble`menum´erique(mul- tiplicationsdematricesenchaˆıne´es)etunprobl`emeissudelathe´oriedesmots(recherched’une pluslonguesous-s´equencecommune).

1.lg’Aitor ´ equale ` aeuqilppyDnoimanPoramitrgma ´ mreqieumhqieuuN 1.1.s.een´ˆıhancEselleicirtaMsnoiplicatiMultNous allons ici illustrer le principe de la Pro- grammationDynamiqueparunalgorithmequir´esoutleprobl`emedesmultiplicationsmatricielles enchaıˆne´es.Onsupposequel’ondisposed’unese´quence(A 1 , A 2 , ..., A n ) denstneicffieoca`secimatr entiers, et que l’on souhaite calculer le produitA 1 A 2 ...A n .ive´mmedneiBuspluriet,enyailnscoa¸sf defairececalculquide´pendentdel’ordredanslequelonfaitlesmultiplications.Cetordreestclas- siquementd´etermine´parunparenthe´sagequiindiquelespriorit´es.Parexemple,pourlas´equence de matrices (A 1 , A 2 , A 3 , A 4 ), le produitA 1 A 2 A 3 A 4 sf:a¸consdi´setdienccitneqeraccllupueˆtte (A 1 (A 2 (A 3 A 4 ))), (A 1 ((A 2 A 3 )A 4 )), ((A 1 A 2 )(A 3 A 4 )), ((A 1 (A 2 A 3 ))A 4 ), (((A 1 A 2 )A 3 )A 4 ).On par- lera alors deneptranehte´´seemtduiodprmere`itnesecirta(inductivement,undorpetiu`itnmereten parenth´ese´estunematriceuniqueouleproduitentreparenthe`sesdedeuxproduitsmatriciels enti`erementparenthe´se´s).Lamanie`redontunesuitedematricesestparenthe´s´eefaitvarierle nombred’ope´rationsn´ecessairespourobtenirleproduit.Faisonsl’hypothe`sedansl’exemplesui- vantquelenombredemultiplicationsd’entierseffectue´espourmultiplierdeuxmatricesdedimen- sions respectivesp×q(plignes etqcolonnes) etq×restpqrqec(oˆutdel’uiestlecemlaogirht naı¨fdemultiplicationdedeuxmatrices). Pourmettreenlumi`erelesdiff´erentscouˆtsinduitsparlesdiff´erentsparenthe´sagesd’unproduit dematrices,consid´eronsunese´quence(A 1 , A 2 , A 3 ) de trois matrices de dimensions respectives 10×100, 100×5 et 5×50.iS’lsage((nerae´htnavipeltlccasuulfaonleitA 1 A 2 )A 3 ), on effectue 10.100.5 = 5000 multiplications d’entiers pour calculer la matrice produitA 1 A 2 de dimension 10×5, plus 10.5.50 = 2500 multiplications scalaires pour multiplier cette matrice avecA 3 , pour untotalde7500multiplicationsd’entiers.Sionmultiplieselonleparenthe´sage(A 1 (A 2 A 3 )), on effectue 100.5.50 = 25000 multiplications d’entiers pour calculer la matrice produitA 2 A 3 de di- mension 100×50, plus 10.100.50 = 50000 multiplications pour multiplierA 1 par cette matrice, pouruntotalde75000multiplicationsscalaires.Lecalculduproduitselonlepremierparenth´esage n´ecessitedonc10foismoinsdemultiplicationsd’entiers.

Leproble`medesmultiplicationsmatriciellesenchaıˆne´espeutˆetree´nonc´ecommesuit:e´tant donn´eeunes´equence(A 1 , A 2 , ..., A n ) denmtadse’ireco`rsienturpou,i= 1,2, ..., n, la matrice A i est de dimensionp i−1 ×p i e`itemereltndorppantntreesh´enerc,moemiutA 1 A 2 ...A n edaf`a¸con minimiser le nombre de multiplications scalaires. Notezque,dansleprobl`emedesmultiplicationsmatriciellesenchaıˆn´ees,onnemultipliepasles matrices.Oncherchesimplementunordredemultiplicationquiminimiselecouˆt.Ge´n´eralement, letempspasse´a`d´eterminercetordreoptimalestplusquecompense´parlegaindetempsquel’on obtiendra quand on fera les multiplications matricielles proprement dites (par exemple, quand on fera 7 500 multiplications scalaires au lieu de 75 000). 1