[PDF] Cours dAlgorithmique et Structures de Données 3

View - Download Cours dAlgorithmique et Structures de Données 3

Previous PDF

Next PDF

Ministèredel'Enseignement Supérieuret delaRechercheScientifique

UniversitéMohamedKhider-Bisk ra

FacultédesSciencesExact esetdesSc iencesdelaNatureetdel aVie

Départementd'Informatique

2 `eme annéeLMD

Coursd'Algorithm iqueetStructures

deDonné es3

Pr.Abdelh amidDJEFFAL

www.abdelhamid-djeffal.net

AnnéeUnivers itaire2020/2021

Plandu cours

1Introduction

2Récursivité

3Com plexitédesalgorithmes

4Algorithmesdetri

5Structuresséquentielles

6StructuresHiérarchiques

1

Références

[1]D.Beauqu ier,J.Berstel,andP.Chrétien ne.Élémentsd'algorithmi que.Ma sson,Version

6,2005.

[2]T.H.Cormen,C. E.Leiserson,R.L .Rivest,T.H .Cormen,andT.H.Cormen.Introduc- tionàl'alg orithm ique.Dunod,1996. [3]J.Court inandI.Kowarski.Initiationàl'algorithmiqueetaux struct uresdedonnées.

Dunod,1990.

[4]M.C.Gaudel,M .Soria,andC.Fro idevaux .Typesdedonnéesetalgo rithmes2:

Recherche,tri,algorithmes surlesgraphes .1987.

[5]GuillaumePoupard.Algorithmique.Eco leNationaleS upérieuredesTechniquesAvan- cées,2000 . 2

Chapitre1

Introduction

L'utilisationd'unordinateurpourlarésolu tiond'unprob lèmenécessitetoutuntravail deprépa ration.N'ayantaucunecapacitéd'inven tion,l'ordinateurnepeu tene ff etqu 'exé- cuterlesord resquil uisontfournispar l'interméd iaired'un programme.Ced ernierdoit doncêtreétabl idemanièr eàenvisagertoutes leséventu alitésd'untraitement. Exemple:leproblèmeD iv( a,b),n 'oubliezpaslecasb=0!

1.1Résoluti ond'unproblèmeeninformatique

Plusieursétapessontnécessaires pourrésoudre unproblèmeenin formatique: -Etape1:Définitionduproblème Ils'ag itdedéterminertoutesl esinform ationsdisponiblesetla formedesrésultats désirés. -Etape2:Analyseduproblème Elleconsiste àtrouverlemoyendepasser desd onnéesauxrésultats.Da nscerta ins casonpeu têtream enéàfaireu neétudethéo rique.Lerésul ta tdel'étaped'a nalyse estunal gorit hme.Unepremièredéfinitiond'unalgor ithmepeutêt relasuivante: "Onappelle algorithmeunesuit efinied'instructionsindiquantde façonunique l'ordredanslequeldoitêtr ee ff ectuéunensemb led'o pérationspourrésoudr etous lesprob lèmesd'untypedonné." Sachezaussiqu'il existedesproblèmes pourlesquelsonnep euttrouveruneso lution etpa rconséquenti lestimpossiblededonner l'algo rithm ecorrespondant. -Etape3:Ecritured'unalgorithm eavecunlangag ededescriptionalgorithmique Unefoisqu 'ontrouve lemoyendepasserd esdonnéesauxrésultats ,ilfau têtre capablederédigeruneso lutio nclaireetnonambig uë.Commeil estimpossibledele 3 faireenlangag ena turel,l'existenced'unlan gagealgorithmiques'i mpose. -Etape4:Traductiondel'algorithmedan sunlan gagedeprogrammation Lesétapes 1,2et3sefonts ansler ecour sà lam achine. Sionveutren drel'algo- rithmeconcretouprati que,ilfaudrait letra duiredansunlangagedepro gramma tion. Nousdironsal orsqu'unprogramme estunalgorithmeex primédansunlan gagede programmation. -Etape5:Miseaupoi ntd uprogramme Quandonsoumetle progra mmeàlamachine,cet tederni èreletraiteendeuxétapes:

1.Lamach inecorrigel'orthograp he,c'estcequ'onappelles yntaxedanslejargon

delapr ogrammat ion.

2.Lamach inetraduitlesensexprim éparleprogramme.

Silesrés ultats obtenussontceuxattendus,lam iseaupointduprogr ammesetermine. Sinous n'obtenonspas derésultats,ondiraqu'ilyaexi stencedeserr eursdel ogique. Leprog rammesoitnedonneaucunrésulta t,soitdesrésul tatsi nattendussoitdes résultatspartiels.Danscecas ,ilfautrevoirenprioritési l'algorithm eaét ébien traduit,ouencoreest-cequ'il yaeuune bonneanalys e.

1.2Notio nd'algorithme

1.2.1Défin ition

Onpeutd éfinirunal gorithmecommesu it:

Résultatd'unedémarchel ogiquederésolut iond'unproblème.C'est lerésultatdel'anal yse.

Ouencor e:

Uneséquenc edepasdecalculqui prendun ensembledevaleurscommeentr ée(input) et produitunensembledevaleurscomme sortie(output).

1.2.2Propriétés

Onpeutén oncerlescinq propriétéssuiv antesq uedoitsat isfaireunalgorithme:

1.Généralité:unalgorithme doi ttoujou rsêtreconçudemanièreàenvisagertout esles

éventualitésd'untraitement.

2.Finitude:Unalgorithmedo its 'arrêter auboutd'untempsfini.

3.Définitude:touteslesopératio nsd 'unalgorithmedo iventêt redéfiniessansambiguïté

4

4.Répétitivité:généralement,unalgorithm econ tientplusieursitérations,c'està dire

desactio nsquiserépètentplusi eursfois.

5.Efficacité:Idéalement ,un algorithmedoitêtreconçudet elleso rtequ'ilsedéroule

enun tempsm inimaletqu'il consommeunminimumder esso urces.

1.2.3Ex emples

-PGCD(Plu sGrandCommunDivi seur)dedeuxno mbresuetv. -Algorithmenaïf:ontestesuccessivemen tsichaqueno mbr eentieres tdiviseur commun. -Décompositionennombrespremiers. -Algorithmesdetri -Algorithmesderecherche -Recherched'unechaînede caractèredansuntex te(Logicielsdetraitem entde texte). -Recherchedansundictionn aire. -...etc.

1.2.4R emarque

Attention,certainsproblèmesn'ad mettentpasdesolutio nalgorithmiqueexacteetu ti- lisable.Onutilisedans cecasdesa lgorithmesheuristiquesq uifournissent dess olutio ns approchées.

1.3Langage algorithmiqueutilisé

Durantcecours,onvau til iserunlangageal gorith miquep ourladescriptiondesdi ff rentessolutio nsapportéesauxproblèmesabordés. L'algorithmesuivantr ésumelaform e généraled'unalgorit hmeetlaplupar tdesdéclarationsetinstructionsut ili sées. 5

AlgorithmePremierExemple;

TypeTTab=tableau[1..10]deree l;

ConstPi=3.14 ;

ProcédureDouble(x:reel);

Début

Fin;

FonctionInverse(x:reel):reel;

Début

Inverse 1/x;

Fin;

Vari,j, k:entier;

T:TTab;

S:chaine;

R:reel;

Début

Ecrire('Bonjour,do nnerunn ombreentier10:');

Lire(i);

Si(i>10)Alors

Ecrire('Erreur:i doitêtre10')

Sinon

Pourjde1àifaire

Lire(R);

Double(R);

T[j] R;

FinPour ;

k 1;

Tantque(ki)faire

k k+1;

FinTQ;

S 'Programmeterminé';

Ecrire(S);

FinSi;

Fin.

Algorithme1:Algorithmety pe

6quotesdbs_dbs23.pdfusesText_29

[PDF] ORME 212 : Algorithmique en seconde avec Python

[PDF] Ali baba et les quarante voleurs - Gomme Gribouillages

[PDF] Commentaire de l 'article 26 du code de droit international privé

[PDF] 1 Biliographie générale : Droit international privé - Droit du

[PDF] Les différences de retraite entre salariés du privé et fonctionnaires

[PDF] 2 Le rôle des aliments - Académie de Nancy-Metz

[PDF] Usines complètes de production d aliments pour - Amandus Kahl

[PDF] La nutrition active pour prévenir et traiter l 'anémie par déficience en fer

[PDF] Ces aliments qui favorisent le bon cholestérol - Mutualp

[PDF] le ba ba de la vitamine c - RTS

[PDF] Feuille d 'info «Alimentation et allaitement»

[PDF] principes generaux de l 'alimentation animale - La documentation

[PDF] Brochure quot L 'alimentation du bébé de 0-12 mois quot - Gouvernementlu

[PDF] Nourrir votre bébé de 6 ? 7 mois - Middlesex-London Health Unit

[PDF] Nourrir votre bébé - Meilleur départ