Cours dAlgorithmique et structures de données 1 PDF

CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE

EXERCICES. TERMINALE ES. ALGORITHME DE Pour déterminer l'itinéraire allant de D à A le plus court en temps on utilise l'algorithme de Dijkstra à l'aide d'un.

Théorie des graphes et optimisation dans les graphes Table des

Pour aller de a à f l'algorithme de Dijkstra va trouver le chemin < a

Algorithmique — M1 - Examen du 11/1/11 -corrigé

11 janv. 2011 Algorithmique — M1. Examen du 11/1/11 -corrigé. Université Paris Diderot. On applique un algorithme de cours. Exercice 1 – Routage. Le serveur S ...

Modélisation du mouvement des personnes lors de lévacuation d

4 oct. 2010 ... ALGORITHME. 167. ///./. Aspects alqopifhmiques. 167. ///_2. liions a ... cours de l'incendie (ex: l'exercice d'évacuation peut conditionner ...

Notes de cours Algorithmique avancée

Exercice 6 Donner un algorithme utilisant la programmation dynamique pour résoudre sac à temps polynomial par l'algorithme de Dijkstra évoqué dans le chapitre ...

Cours dAlgorithmique et structures de données 1

12 mars 2013 6.5 Plus court chemin (algorithme de Dijkstra) . ... Examen d'algorithmique 1. 08h-09h30. A1 A2. Exercice 1 (10 pts: 1.5 + 1.5 + 3 + 1.5 + 2 .5).

Conception dalgorithmes Principes et 150 exercices non corrigés

de matériel pour les cours et les séances d'exercices (sans parler des examens). Publié en 1959 par le célèbre informaticien E.W. Dijkstra cet algorithme est.

Introduction à la théorie des graphes

Exercice. Soit G un graphe simple orienté d'ordre n de matrice d'adjacence M. Mon- trer que si Mn n'est pas nulle

GUIDE DES ÉTUDES

6 oct. 2023 Polycopié du cours (exercices compris). Langue de l'enseignement. Français ... - Algorithme de Dijkstra exemple d'utilisation. Les différents ...

Examen du 18 janvier 2008 - corrigé - version α2

18 janv. 2008 Correction. On adapte les algorithmes de cours. Exercice 3 – Poids max de camion. Un réseau routier connecte les villages d ...

Algorithme de Dijkstra

21 oct. 2008 l'algorithme de Dijkstra sur des exemples concrets. Exemple 1. Cherchons les plus courts chemins d'origine A dans ce graphe:.

Théorie des graphes et optimisation dans les graphes Table des

Exercice : Au cours d'une soirée les convives se serrent les mains les uns les l'algorithme de Dijkstra résoud ce problème lorsque tous les coûts sont ...

Cours dAlgorithmique et structures de données 1

29 janv. 2012 6.5 Plus court chemin (algorithme de Dijkstra) . ... 8 Sujets d'examens ... Exercice : Donner l'état de la pile après l'exécution des ...

Quelques rappels sur la théorie des graphes

ce jour un algorithme résolvant ce problème de façon exacte avec une complexité déterminer si l'arête en cours d'examen doit ou non être sélectionnée.

Introduction à la théorie des graphes

Graphes valués et problème du plus court chemin . Solutions des exercices ... Appliquons l'algorithme de Dijkstra au graphe suivant : Initialisation.

Examen du 18 janvier 2008 - corrigé - version ?2

18 janv. 2008 Correction. On adapte les algorithmes de cours. Exercice 3 – Poids max de camion. Un réseau routier connecte les villages d ...

Algorithmique — M1 - Examen du 11/1/11 -corrigé

11 janv. 2011 Examen du 11/1/11 -corrigé. Université Paris Diderot. On applique un algorithme de cours. Exercice 1 – Routage.

GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir

Compilation réalisée à partir d'exercices de BAC TES 4) On utilise l'algorithme du plus court chemin de Dijkstra pour déterminer une chaîne qui minimise ...

Algorithmique I - Cours et Travaux Dirigés L3 Ecole Normale

6.5.5 Algorithme de Dijkstra . and analysis of algorithms contient les notes de cours et exercices (certains corrigés) d'un cours.

Cours APD : algorithmique parallèle et distribuée.

Un examen : Support de cours : transparents + exercices sur la page http://www.prism.uvsq.fr/ joco Algorithme centralisé de Dijkstra. Entrée :.

UniversitMohamedKhider-Bisk ra

FacultdesSciencesExact esetdesSc iencesdelaNatureetdel aVie

DpartementdÕInformatique

2 `eme anneLMD

CoursdÕAlgorith miqueetstructures

dedonne s1

Chargducours:Dr. Abdelh amidDJEFFAL

AnneUnivers itaire2012/2013

Sommaire

1Introduction3

1.2Notiond Õalgorithme...............................4

1.3Langageal gorithmiqueutilis ..........................5

2Com plexitdesalgorithmes7

2.1Introd uction....................................7

2.2O-notation .....................................7

2.4Complexi tdesalgorithmesrcursifs......................13

2.5Typesd ecomplexitalg orithm ique.......................14

2.6Exercices .....................................15

3Structuressquentielles20

3.1Leslist eslinai rescha"nesaLLCg........................20

3.2Lespiles astack sg.................................26

3.3LesFil esdÕatt enteaQueuesg...........................34

4StructuresHirarchiques45

4.1Lesarb res.....................................45

4.2Lesarbr esbinai resderecherche.........................56

4.3Lestas aHeapsg ..................................63

5StructuresenTables69

5.1Introd uction....................................69

5.3Tablet rie.....................................70

5.4Hachag eaHashCodingg..............................70

6Lesgraphes75

6.1Introd uction....................................75

6.2DÞnit ions.....................................75

6.3Reprsent ationdesgraphes...........................78

6.4Parcou rsdegraphes...............................80

6.5Plusco urtcheminaalg orithmedeDi jkstrag..................83

7PreuvedÕalgorithmes86

7.1Introd uction....................................86

7.2Mthod edepreuvedÕalgorit hme........................86

7.3Outil sdepreuvedÕalgorith meaLo giquedeHoareg...............88

7.4Exemple ......................................91

7.5Conclusi on.....................................92

8SujetsdÕexamens93

Rfrences137

Chapitre1

Introduction

deprpa ration.NÕayantaucunecapacitdÕinvent ion,lÕordinateurnepeut ene B etqu Õex- cuterlesordr esquilu isontfournispar lÕintermdi airedÕun programme.Ceder nierdoit IlsÕag itdedterminertoutesl esinform ationsdisponiblesetla formedesrsultats dsirs. Elleconsiste trouverlemoyendepasserd esdo nnesauxrsultats.Da nscertai ns

casonpeu ttream enfaireu netudetho rique.Lersul ta tdelÕtapedÕa nalyse

oOnappelle algorithmeunesuit eÞniedÕinstructionsindiquantde faonunique lÕordredanslequeldoitt ree B ectuunensem bledÕo prationspourrsoud retous etpa rconsquenti lestimpossiblededonner lÕalgo rithm ecorrespondant. ÐEtape3:EcrituredÕunalgorithm eavecunlanga gededescriptionalgorithmique UnefoisquÕ ontrouvel emoyendepasserde sdonnesauxrsultats ,ilfaut tre capablederdigeruneso lutio nclaireetnonambig u.Commeil estimpossibledele 3 faireenlangage nat urel,lÕexistencedÕunlang agealgorithmiquesÕim pose. ÐEtape4:TraductiondelÕalgorithmedan sunlan gagedeprogrammation Lestap es1,2et3sefonts ansler ecou rs lam achine. Sionveutren drelÕalgo- rithmeconcretouprati que,ilfaudrait letra duiredansunlangagedepro gramma tion. Nousdironsal orsquÕunprogramme estunalgorithmeex primdansunlan gagede programmation.

ÐEtape5:Miseaupoin tdu programme

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

delapr ogrammation.

2.Lamac hinetraduitlesensexprim parleprogramme.

Silesrs ultats obtenussontceuxattendus,lam iseaupointduprogr ammesetermine. Sinou snÕobtenonspa sdersultats,ondiraquÕilyaex istencedeser reursde logique. Leprog rammesoitnedonneaucunrsulta t,soitdesrsul tatsi nattendussoitdes rsultatspartiels.Danscecas ,ilfautrevoirenprioritsi lÕalgorithme at bien traduit,ouencoreest-cequÕil yaeuune bonneanalys e.

1.2Notion dÕalgorithme

1.2.1DÞn ition

Onpeutd Þnirunalg orithmecommesu it:

Ouencor e:

Unes quencedepasdecalculqui prendun ensembledevaleurscommeentr eainputg et produitunensembledevaleurscomme sortieaoutputg.

1.2.2Proprits

Onpeutn oncerlescinqp ropritssuiv antesqu edoitsati sfaireunalgorithme:

ventualitsdÕuntraitement.

2.Finitude:Unalgorithmedo its Õarrter auboutdÕuntempsÞni.

3.DÞnitude:touteslesopration sd Õunalgorithmedo iventtr edÞniessansambigut

4.Rptitivit:gnralement,unalgorithm econ tientplusieursitrations,cÕest dire

5.Eocacit:Idalement ,u nalgorithmedoittreconude telleso rtequÕilsedroule

enun tempsmi nimaletquÕil consommeunminimumderes so urces.

1.2.3Ex emples

ÐPGCDaPlu sGrandCommunDivis eurgdedeuxnom bresuetv. ÐAlgorithmenaf:ontestesuccessivemen tsichaquenom bre entieres tdiviseur commun.

ÐDcompositionennombrespremiers.

ÐAlgorithmesdetri

ÐAlgorithmesderecherche

texteg.

ÐRecherchedansundictionna ire.

Ð...etc.

1.2.4Rema rque

lisable.Onutilisedans cecasdes algorithmesheuristiquesq uifournissent dess olutio ns approches.

1.3Langag ealgorithmiqueutilis

Durantcecours,onvau til iserunlangageal gorith miquep ourladescriptiondesdi B gnraledÕunalgorit hmeetlaplupa rtdesdclarationsetinstructionsut ili ses. 5

AlgorithmePremierExemple;

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

ConstPi=3.14 ;

ProcdureDoubleax:reelg;

Dbut

xBxo2; Fin;

FonctionInverseax:reelg:reel;

Dbut

InverseB1/x;

Fin;

Vari,j, k:entier;

T:TTab;

S:chaine;

R:reel;

Dbut

EcrireaÕBonjour,d onnerun nombreentiern10:Õg;

Lireaig ;

Siai>10gAlors

EcrireaÕErreur:id oittren10Õg

Sinon

Pourjde1ifaire

LireaRg;

DoubleaRg;

T[j]BR;

FinPour ;

kB1;

Tantqueaknigfaire

EcrireaT[k]oInverseaPigg;

kBk+1;

FinTQ;

SBÕProgrammeterminÕ;

EcrireaSg;

FinSi;

Fin.

Algorithme1:Algorithmet ype

Chapitre2

Complexitdesalgorithmes

2.1Introduc tion

Letemps dÕexcutiondÕun algorithmedpenddesfacteurssu ivants:

ÐLesdonn esutilisesparlep rogramme,

ÐLaqua litducompilateuralanga geuti lisg, ÐLamach ineutiliseavitesse,mmo ire,...g, ÐLacom plexitdelÕalgorithmelui-mm e, Oncherc hemesurerlacomplexi td Õunalgorithmein dpenda mmentdelamachineet dulang ageutiliss,c--duniqu ementenfonctiondelatailledesd onnesnquelÕalgori thme doittraiter. Parexemple,danslecasdetr idÕuntabl eau,nestlen ombred Õlmentsdu tableau,etdanslecasdecal cul dÕuntermedÕu nesuit enestlÕin diceduterme,...etc.

2.2O-notat ion

Soitlafonction Tangquireprsent elÕvolutiondutempsdÕex cutiondÕunprogramme

Penfo nctiondunombrededonnes n.

Parexemple:

Tang=cn

2 Ocestune constanten onspciÞequireprsentelavit essedelama chine,lesper- formancesdulangage,... etc.Ond itdanslÕexempleprcdentqu elacomplexitdePest Oan 2 g.Cel aveutdireq uÕilexist euneconstante cpositivetelquepournsuosamment grandona :

Tangncn

2 7 Cettenotati ondonneunemajorationduno mbredÕoprations excutesatemp sdÕex- cutiongparleprogram meP.Un progra mmedontlacomplexitestOafanggestunpr o- grammequia fangcommefonctiond ecroissancedutempsdÕex cution .

2.3.1L acomplexitdÕu neinstructionlmentaire

Uneoprat ionlmentaireestuneopratio ndontletempsdÕexcutionestin dpendan t dela taillendesdonn estelquelÕaBectation,lalecture,lÕcritu re,lacom paraison...etc. Lacompl exitdÕuneinstructionlment aireestOa1g

2.3.2La multiplicati onparuneconstante

Oacofangg= Oafangg

Exemple:

Oa n 3 4 g=Oan 3 g

2.3.3La complexitdÕun esquencededeuxmo dules

Lacompl exitdÕunesquencededeuxmodu lesM 1 decompl exitOafanggetM 2 decompl exitOaganggestgale laplusgrand ed escomplex itdesdeuxmodu les:

Oamaxafang,ganggg.

Oafangg+Oagangg= Oamaxafang,agangg

2.3.4La complexitdÕu neconditionnelle

Lacomp lexitdÕuneconditionnelle

SiaCondgAlors

M 1 Sinon M 2

FinSi;

8 estlema xentrel escomplexits delÕvaluati onde,M 1 etM 2

Sia[Oahangg]gAlors

M 1 [Oafangg] Sinon M 2 [Oagangg]

FinSi;

Lacomp lexitdelaconditionnelleest:Max{Oahangg,Oafangg,Oagangg}

2.3.5La complexitdÕun eboucle

Lacompl exitdÕuneboucleestgalel asommesurtoutesl esitrationsdela com- plexitducorpsdelabo ucle.

Tantquea[Oahangg]gfaire

[mfois ]

P;[Oafangg]

FinTQ;

Lacompl exitdelaboucleest:

B m Maxahang,fanggomest len ombred Õitrat ions excutesparlabou cle. 9

Exemple1:

AlgorithmeRecherche;

VarT:tableau[1..n]deen tier;

x,i:entier; trouv:booleen;

Dbut

Pouride1nfaire

LireaT [i]g;Oa1gOa

B n 1

1g=Oang

FinPou r;

Lireaxg;Oa1g

TrouvBfaux;Oa1gOa1g

iB1;Oa1gOang

Tantqueatrouv=fauxeti<=n[Oa1g]gfaire

SiaT[i]=x[Oa1g]gAlors

TrouvBvrai;[Oa1g]Oa1gOang

FinSi;

iBi+1;[Oa1g]

FinTQ;

Siatrouv=vrai[Oa1g]gAlors

Ecrireax,ÕexisteÕ g[Oa1g]Oa1g

Sinon

Ecrireax,ÕnÓexist epasÕg[Oa1g]

FinSi;

Fin. Lacomp lexitdelÕalgorithmeestdeOang+Oa1g+Oang+Oa1g=Oang. 10

Exemple2:Soitlemo dulesuivan t:

Pouride1nfaire

[nfoisOa B n i=1 n igg]

Pourjdei+1nfaire

[n ifoisOa B nBi 1

1g=Oan ig]

SiaT[i]>T[j][Oa1g]gAlors

tmpBT[i];[Oa1g]

T[i]BT[j];[Oa1g]Oa1g

T[j]Btmp;[Oa1g]

FinSi;

FinPour ;

Lacomp lexit=Oa

B n an ig=Oaan 1g+a n 2g...+1g =Oa nanB1g 2 g=Oa n 2 2 n 2 g=Oan 2 g 11

Exemple3:Reche rchedi chot omique

AlgorithmeRechercheDecho;

VarT:tableau[1..n]deen tier;

x,sup,inf,m:entier; trouv:booleen;

Dbut

Lireaxg;[Oa1g]

TrouvBfaux;[Oa1g]

infB1;[Oa1gOa1g] supBn;[Oa1g]

Tantqueatrouv=fauxetinf [log 2 angfois] mBainf+Supg div 2;[Oa1g]
SiaT[m]=x[Oa1g]gAlors

TrouvBvrai[Oa1g]
Sinon
SiaT[m] infBm+1;[Oa1gOa1gOalog 2 angg] Sinon
SupBm-1;[Oa1g]

FinSi;

FinSi;

FinTQ;

Siatrouv=vrai[Oa1g]gAlors

Ecrireax,ÕexisteÕ g;[Oa1g]Oa1g
Sinon
Ecrireax,ÕnÕexist epasÕg;[Oa1g]

FinSi;
Fin.
Lacomp lexitdelÕalgorithmeestde:
12
Oa1g+Oalog
2 angg+Oa1g=Oalog 2 angg=Oalogangg.
2.4Complex itdesalgorithmesrcursifs
Lacomp lexitdÕunalgorithmercurs ifsefaitparla rsolutiondÕunequationder- currenceenliminantl arcu rrenceparsubstitutiondepr ocheen proche.
Exemple

Soitlafonction rcursiv esuivante:

FonctionFactan:entierg:entier;

Dbut

Sian<=1 [Oa1g]gAlors

FactB1[Oa1g]
Sinon
FactBneF acta n-1g[Oa1g]

FinSi;
Fin; PosonsTangletemps dÕexcutionncess airepourunappelFactang,Tangest le maximumentre:
Ðlacompl exitdutestnn1quiestenOa1g,

Ðlacompl exitde:FactB1qu iestaussien Oa1g,
Ðlacompl exitde:FactBneFactan-1gdontletempsd Õex cutiond penddeTan 1g apourlecalculdeFa ctan-1g g
Onpeutd onccrirequ e:
Tang= o n asin<=1 b+Tan 1gsinonasin>1g ÐLaconstan teaenglobeletempsdutest an<=1getle tempsde lÕaBectation aFactB1g
ÐLaconstan tebenglobe:
eletemps dutestan<=1g, eletemp sdelÕopratio neentre netle rsulta tdeFactan 1g, 13 eetl etempsd elÕaBectationÞnaleaFactB...g Tan 1galetempsnces sairepourleca lculdeFactan 1gseracalcula rcursivementg aveclammed composi tion.Pou rcalculerlasolutiongnraledecettequation, onpeut procderparsubstitut ion:
Tang=b+Tan 1g
=b+[b+Tan 2g] =2b+Tan 2g =2b+[b+Tan 3g] =ib+Tan ig =ib+[b+Tan i+1g] =an 1gb+Tan n+1g= nb b+Ta1g=nb b+a
Tang=nb b+a

DoncFactestenOangcarbest une constan tepositiv e.

2.5Typesdec omplexitalgo rit hmique

1.Tang=Oa1g,tem psconstant:t empsdÕexcutionindpenda ntd elatailledesdonn es

tr aiter.

2.Tang=Oalogangg,tem pslogarithm ique:onrencontregnralementunetellecom-

3.Tang=Oang,tem pslinaire:cet tecomplexitestgnralemen tob tenuelorsq uÕun
travailentempsconstantest e B ectusurcha quedonne enentre.
5.Tang=Oan
2 g,t empsquadratiq ue:appara"tnotammentlorsquelÕalgo rit hmeenvi- sagetouteslesp airesdedonnespar milesnen tresaex.deuxboucles imbriq uesg
Remarque:Oan
3 gtempscubique
6.Tang=Oa2
n g,t empsexponentiel :souventlersultatderechercheb rut aledÕune solution. 14
2.6Exercic es

1.Calculerlacomplexit delÕal gorithmesuivant:

Pouride2nfaire
kBi-1; xBT[i];
TantqueaT[k]>xetk >0 gfaire

T[k+1]BT[k];
kBk-1;
FinTQ;

T[k+1]Bx;

FinPour ;

2.Calculerlacomplexit delÕa lgorithmesuivant:
iBn; SB0;
Tantqueai>0gfaire
jB2ei;
Tantqueaj>1gfaire

SBS+aj-igeaS+1g;
jBj-1;
FinTQ;
iBidiv2;
FinTQ;
15
3.Calculerlacomplexit delÕal gorithmesuivant:
iB1; jB0;
Pourkde1nfaire
jBi+j; iBj-i;
FinPour ;
Quefaitcetal gorithmes ach antquelersultatestdansj?
4.Calculerlacomplexit delafon ctionrcursivesuivante:

FonctionFiban:entierg:entier;

Dbut

Sian<2gAlors

FibB1;
Sinon
FibBFiban-1g+Fiban- 2g;

FinSi;
Fin; 16
5.Calculerlacomplexit delÕal gorithmesuivant:
PB1;
PourIde1nfaire
JB1; KB1;
TantqueaKnngfaire

PBPeaK+Jg;

KBK+1;

SiaK>ngAlors

JBJ+1;

SiaJ>ngAlors
KB1
FinSi;

FinSi;

FinTQ;

FinPour ;

6.Calculerlacomplexit delÕa lgorithmesuivant:
iB1;
Tantqueai jB1;
Tantqueaj<2engfaire
jBje2;
FinTQ;
iBi+1;
FinTQ;
17
7.Trouverlacomplexitde lafonct ionsuivante:
quotesdbs_dbs45.pdfusesText_45

[PDF] algorithme de dijkstra exercice corrigé PDF Cours,Exercices ,Examens

[PDF] algorithme de ford plus long chemin PDF Cours,Exercices ,Examens

[PDF] Algorithme de héron Terminale Mathématiques

[PDF] Algorithme de mathématiques 2nde Mathématiques

[PDF] Algorithme de maths 1ère Mathématiques

[PDF] Algorithme de maths 2nde Mathématiques

[PDF] Algorithme de mesure d'angle 1ère Mathématiques

[PDF] Algorithme de niveau Seconde 2nde Mathématiques

[PDF] algorithme de parcours en largeur PDF Cours,Exercices ,Examens

[PDF] algorithme de parcours en profondeur en c PDF Cours,Exercices ,Examens

[PDF] ALGORITHME DE PILE OU FACE svp essayer de me faire comprendre cette algorithme 2nde Mathématiques

[PDF] Algorithme de Pythagore 2nde Mathématiques

[PDF] ALGORITHME DE PYTHAGORE ( TI-84 plus ) 2nde Mathématiques

[PDF] algorithme de recherche dextremum 2nde Mathématiques

[PDF] algorithme de recherche dans un tableau PDF Cours,Exercices ,Examens

[PDF] Cours dAlgorithmique et structures de données 1

UniversitMohamedKhider-Bisk ra

DpartementdÕInformatique

CoursdÕAlgorith miqueetstructures

Chargducours:Dr. Abdelh amidDJEFFAL

AnneUnivers itaire2012/2013

Sommaire

1Introduction3

1.2Notiond Õalgorithme...............................4

1.3Langageal gorithmiqueutilis ..........................5

2Com plexitdesalgorithmes7

2.1Introd uction....................................7

2.2O-notation .....................................7

2.4Complexi tdesalgorithmesrcursifs......................13

2.5Typesd ecomplexitalg orithm ique.......................14

2.6Exercices .....................................15

3Structuressquentielles20

3.1Leslist eslinai rescha"nesaLLCg........................20

3.2Lespiles astack sg.................................26

3.3LesFil esdÕatt enteaQueuesg...........................34

4StructuresHirarchiques45

4.1Lesarb res.....................................45

4.2Lesarbr esbinai resderecherche.........................56

4.3Lestas aHeapsg ..................................63

5StructuresenTables69

5.1Introd uction....................................69

5.3Tablet rie.....................................70

5.4Hachag eaHashCodingg..............................70

6Lesgraphes75

6.1Introd uction....................................75

6.2DÞnit ions.....................................75

6.3Reprsent ationdesgraphes...........................78

6.4Parcou rsdegraphes...............................80

6.5Plusco urtcheminaalg orithmedeDi jkstrag..................83

7PreuvedÕalgorithmes86

7.1Introd uction....................................86

7.2Mthod edepreuvedÕalgorit hme........................86

7.3Outil sdepreuvedÕalgorith meaLo giquedeHoareg...............88

7.4Exemple ......................................91

7.5Conclusi on.....................................92

8SujetsdÕexamens93

Rfrences137

Chapitre1

Introduction

ÐEtape5:Miseaupoin tdu programme

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

2.Lamac hinetraduitlesensexprim parleprogramme.

1.2Notion dÕalgorithme

1.2.1DÞn ition

Onpeutd Þnirunalg orithmecommesu it:

Ouencor e:

1.2.2Proprits

ventualitsdÕuntraitement.

2.Finitude:Unalgorithmedo its Õarrter auboutdÕuntempsÞni.

3.DÞnitude:touteslesopration sd Õunalgorithmedo iventtr edÞniessansambigut

4.Rptitivit:gnralement,unalgorithm econ tientplusieursitrations,cÕest dire

5.Eocacit:Idalement ,u nalgorithmedoittreconude telleso rtequÕilsedroule

1.2.3Ex emples

ÐDcompositionennombrespremiers.

ÐAlgorithmesdetri

ÐAlgorithmesderecherche

ÐRecherchedansundictionna ire.

Ð...etc.

1.2.4Rema rque

1.3Langag ealgorithmiqueutilis

AlgorithmePremierExemple;

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

ConstPi=3.14 ;

ProcdureDoubleax:reelg;

Dbut

FonctionInverseax:reelg:reel;

Dbut

InverseB1/x;

Vari,j, k:entier;

T:TTab;

S:chaine;

R:reel;

Dbut

Lireaig ;

Siai>10gAlors

UniversitMohamedKhider-Bisk ra

DpartementdÕInformatique

Chargducours:Dr. Abdelh amidDJEFFAL

AnneUnivers itaire2012/2013

1.3Langageal gorithmiqueutilis ..........................5

2Com plexitdesalgorithmes7

2.4Complexi tdesalgorithmesrcursifs......................13

2.5Typesd ecomplexitalg orithm ique.......................14

3Structuressquentielles20

3.1Leslist eslinai rescha"nesaLLCg........................20

4StructuresHirarchiques45

5.3Tablet rie.....................................70

6.2DÞnit ions.....................................75

6.3Reprsent ationdesgraphes...........................78

7.2Mthod edepreuvedÕalgorit hme........................86

Rfrences137

2.Lamac hinetraduitlesensexprim parleprogramme.

1.2.1DÞn ition

Onpeutd Þnirunalg orithmecommesu it:

1.2.2Proprits

ventualitsdÕuntraitement.

2.Finitude:Unalgorithmedo its Õarrter auboutdÕuntempsÞni.

3.DÞnitude:touteslesopration sd Õunalgorithmedo iventtr edÞniessansambigut

4.Rptitivit:gnralement,unalgorithm econ tientplusieursitrations,cÕest dire

5.Eocacit:Idalement ,u nalgorithmedoittreconude telleso rtequÕilsedroule

ÐDcompositionennombrespremiers.

1.3Langag ealgorithmiqueutilis

ProcdureDoubleax:reelg;

Dbut

Dbut

Dbut

EcrireaÕErreur:id oittren10Õg

Pourjde1ifaire

SBÕProgrammeterminÕ;

Complexitdesalgorithmes

ÐLesdonn esutilisesparlep rogramme,

Penfo nctiondunombrededonnes n.

2.3.1L acomplexitdÕu neinstructionlmentaire

2.3.3La complexitdÕun esquencededeuxmo dules

2.3.4La complexitdÕu neconditionnelle

Lacomp lexitdÕuneconditionnelle

2.3.5La complexitdÕun eboucle

Lacompl exitdelaboucleest:

Dbut

Pouride1nfaire