Licence informatique L3 Annee

Description

Niveau: Supérieur, Licence, Bac+3
Licence informatique - L3 Annee 2011/2012 Conception d'algorithmes et applications (LI325) COURS 1 Resume. Ce cours est une initiation a quelques grands principes algorithmiques (Diviser pour Regner, Programmation Dynamique, Algorithmes Gloutons,...) par leur mise en application dans des situations variees (numerique, graphique, geometrique,...). Cette premiere seance introduc- tive est consacree a quelques conventions et rappels (pseudo-code, comportement asymptotique), nous introduirons aussi la notion d'algorithme Diviser pour Regner, avec des applications dans le cas du probleme du tri (Tri-fusion, Quicksort) et de systeme de pesees. En conclusion, nous donnerons le ”theoreme maıtre” qui permet d'obtenir des bornes asymptotiques sur la plupart des fonctions rencontrees lors de l'analyse de cout des algorithmes Diviser pour Regner. 1. Introduction De tout temps les hommes ont cherche des methodes pour « systematiser » leurs raisonnements. La division ou l'algorithme d'Euclide pour trouver le PCGD de deux nombres remontent a 400 ans avant notre ere. « Systematiser », c'est assurer la reproductibilite (et donc l'apprentissage) des methodes, c'est aussi assurer leur transmissibilite dans le temps et dans l'espace sous une forme comprehensible par tous. Afin de transmettre, il faut garantir que les methodes proposees donnent bien ce a quoi l'on aspire (sinon on parle d'heuristique), a la fois dans le but de convaincre l'autre, mais aussi dans le souci constructiviste de garantir la coherence de l'edifice des savoirs (par la certification de chacune de ses briques).

• pseudo-code


• insertion


• sequence


• boucle tant


• tri


• fusion


• expor- tation vers les differents langages informatiques


• algorithmique numerique

Sujets

• Machiavel
• Pseudo-code
• Insertion
• Fusión

Informations

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

Extrait

Licence informatique - L3

Anne´e2011/2012

Conception d’algorithmes et applications (LI325) COURS 1

R ´ esume ´ .rpniicepsergnasdhmiques(salgoritruoiviDpresrsouecCinnetuesnoitaitiuqleuqa` Re´gner,ProgrammationDynamique,AlgorithmesGloutons,...)parleurmiseenapplicationdans dessituationsvarie´es(num´erique,graphique,g´eom´etrique,...).Cettepremi`erese´anceintroduc- tiveestconsacr´eea`quelquesconventionsetrappels(pseudo-code,comportementasymptotique), nousintroduironsaussilanotiond’algorithmeDiviserpourR´egner,avecdesapplicationsdans lecasduprobl`emedutri(Tri-fusion,Quicksort)etdesyste`medepes´ees.Enconclusion,nous donneronsle”th´eor`ememaıˆtre”quipermetd’obtenirdesbornesasymptotiquessurlaplupart desfonctionsrencontre´eslorsdel’analysedecoˆutdesalgorithmesDiviserpourR´egner.

1.Introduction Detouttempsleshommesontcherch´edesm´ethodespour«ystsitese´amr»leurs raisonnements. Ladivisionoul’algorithmed’EuclidepourtrouverlePCGDdedeuxnombresremontenta`400 ansavantnotree`re.«atist´emSysre»e)desentissagcn’lparp´t(eteodtiuclibirelaodprssatreru,se’c m´ethodes,c’estaussiassurerleurtransmissibilit´edansletempsetdansl’espacesousuneforme compre´hensiblepartous.Afindetransmettre,ilfautgarantirquelesm´ethodespropos´eesdonnent biencea`quoil’onaspire(sinononparled’heuristiquelafo),`aelsnadsinocedtubelcrinva,reut’a maisaussidanslesouciconstructivistedegarantirlacoh´erencedel’e´dificedessavoirs(parla certificationdechacunedesesbriques).Plusre´cemment,avecl’ave`nementdel’informatique,on accordaunsointoutparticuliera`ladescriptionformelledesalgorithmesafind’enfaciliterl’expor- tationverslesdiff´erentslangagesinformatiquesmodernes.C’estlebutdel’´ecriturealgorithmique enpseudo-codequiferal’objetdupremierpre´ambule.Ledernierpoint,etcen’estpaslemoindre quandl’onpensealgorithmique,consiste`atrouverlesm´ethodeslespluse´conomiquespossibles quecesoitentermesdetemps,deme´moireoudetoutautrechose.Voila`donccequel’onentend iciparalgorithmiqueetc’estcequenouspouvonsre´sumerainsi: l’algorithmiquecitiareneab`le´erbehtamame´wari-Khu’unczmidtnudvieimolAusnrqumeer(t (780-850ap.JC)`aquil’ondoitaussilemotalg`ebre)estlasciencequiconsiste`atrouverdes me´thodesformellesetcertifi´eespourre´soudredemani`ereautomatiqueetleplusefficacement possibledesproble`mesdonne´s. Danscecours,nousnousproposons,plusqu’a`l’e´tudeoua`larecherched’algorithmeparticu- lier,demettreenlumi`eretrois”types”universelsd’algorithmesquesont:lesalgorithmesdetype DiviserpourR´egner, les algorithmes de typeProgrammation dynamiqueet les algorithmes de typeGloutonNo.it´ftenartoejbceerqu’iletdemontrmudsusseduaetsixesrdieulngsideon algorithmes,degrandsprincipesalgorithmiquescommuns.Pourinsistersurlecaract`eretrans- versal de ces principes, pour chacun d’eux nous proposerons des applications qui couvrent un champlargedel’algorithmiqueclassique,disonspourrestercate´gorieldanssescinqramifications suivantes:l’algorithmiquenum´eriqueetmatriciel,lag´eome´triealgorithmique,l’algorithmique desgraphes,l’ordonnancementetlestris,l’algorithmiquedess´equences.Cecourss’architecturera autourdecetteide´eprincipale.

1