Licence informatique L3 Annee

Documents
11 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Informations

Publié par
Nombre de lectures 22
Langue Français
Signaler un problème
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), nousintroduironsaussilanotiondalgorithmeDiviserpourR´egner,avecdesapplicationsdans lecasduprobl`emedutri(Tri-fusion,Quicksort)etdesyste`medepes´ees.Enconclusion,nous donneronsleth´eor`ememaıˆtrequipermetdobtenirdesbornesasymptotiquessurlaplupart desfonctionsrencontre´eslorsdelanalysedecoˆutdesalgorithmesDiviserpourR´egner.
1.Introduction Detouttempsleshommesontcherch´edesm´ethodespour«ystsitese´amr»leurs raisonnements. LadivisionoulalgorithmedEuclidepourtrouverlePCGDdedeuxnombresremontenta`400 ansavantnotree`re.«atist´emSysre»e)desentissagcnlparp´t(eteodtiuclibirelaodprssatreru,sec m´ethodes,cestaussiassurerleurtransmissibilit´edansletempsetdanslespacesousuneforme compre´hensiblepartous.Andetransmettre,ilfautgarantirquelesm´ethodespropos´eesdonnent biencea`quoilonaspire(sinononparledheuristiquelafo),`aelsnadsinocedtubelcrinva,reuta maisaussidanslesouciconstructivistedegarantirlacoh´erencedele´dicedessavoirs(parla certicationdechacunedesesbriques).Plusre´cemment,aveclave`nementdelinformatique,on accordaunsointoutparticuliera`ladescriptionformelledesalgorithmesandenfaciliterlexpor-tationverslesdi´erentslangagesinformatiquesmodernes.Cestlebutdel´ecriturealgorithmique enpseudo-codequiferalobjetdupremierpre´ambule.Ledernierpoint,etcenestpaslemoindre quandlonpensealgorithmique,consiste`atrouverlesm´ethodeslespluse´conomiquespossibles quecesoitentermesdetemps,deme´moireoudetoutautrechose.Voila`donccequelonentend iciparalgorithmiqueetcestcequenouspouvonsre´sumerainsi: l’algorithmiquecitiareneab`le´erbehtamame´wari-KhuunczmidtnudvieimolAusnrqumeer(t (780-850ap.JC)`aquilondoitaussilemotalg`ebre)estlasciencequiconsiste`atrouverdes me´thodesformellesetcerti´eespourre´soudredemani`ereautomatiqueetleplusecacement possibledesproble`mesdonne´s. Danscecours,nousnousproposons,plusqua`le´tudeoua`larecherchedalgorithmeparticu-lier,demettreenlumi`eretroistypesuniverselsdalgorithmesquesont:lesalgorithmesdetype DiviserpourR´egner, les algorithmes de typeProgrammation dynamiqueet les algorithmes de typeGloutonNo.it´ftenartoejbceerquiletdemontrmudsusseduaetsixesrdieulngsideon algorithmes,degrandsprincipesalgorithmiquescommuns.Pourinsistersurlecaract`eretrans-versal de ces principes, pour chacun d’eux nous proposerons des applications qui couvrent un champlargedelalgorithmiqueclassique,disonspourrestercate´gorieldanssescinqramications suivantes:lalgorithmiquenum´eriqueetmatriciel,lag´eome´triealgorithmique,lalgorithmique desgraphes,lordonnancementetlestris,lalgorithmiquedess´equences.Cecourssarchitecturera autourdecetteide´eprincipale.
1