Exercices avec Solutions
Les Structures de Contrôle (Conditionnelles – Itératives). Exercices Corrigés d'Algorithmique – 1ére Année MI 5. EXERCICE 1. Ecrire un algorithme qui
Langage C : énoncé et corrigé des exercices IUP GéniE
Les exercices 1 à 1 6 20 à 2 5
Cours SGBD 1 Concepts et langages des Bases de Données
IUT de Nice - Cours SGBD1. 2. Plan. Chapitre 1. Introduction générale. Chapitre 2. Le modèle relationnel ensemble structuré de données apparentées qui.
Cours dAlgorithmique et structures de données 1
29 Jan 2012 2.6 Exercices . ... 8 Sujets d'examens. 93. Références. 137. 2 ... Durant ce cours on va utiliser un langage algorithmique pour la ...
cours-python.pdf
22 Mar 2018 Le cours est disponible en version HTML 2 et PDF 3. ... Une liste est une structure de données qui contient une série de valeurs.
DII - Plan du cours INF4063 - UQO
13 Sept 2021 2. Objectifs spécifiques du cours : • Introduire l'étudiant(e) à ... structures de données en fonction de l'efficacité d'algorithme.
INF3105 - Structures de données et algorithmes
3 Sept 2020 Collections et les structures de données nécessaires à leurs ... Ce cours comporte une séance obligatoire de laboratoire (2 heures).
Algorithmes et structures de données génériques
ALGORITHMES. ET STRUCTURES DE. DONNÉES GÉNÉRIQUES. Cours et exercices corrigés en langage C. Michel Divay. Professeur à l'université Rennes 1. 2e édition.
SECTION DE MATHÉMATIQUES
Ce cours a pour but d'introduire les techniques importantes du calcul scientifique et d'en analyser les algorithmes. Contenu. 1. Intégration numérique. 2.
SUJET + CORRIGE
17 Dec 2010 UE : Algorithmes et structures de données. Épreuve : Examen ... Définition 2 Un arbre binaire A de hauteur h est presque parfait lorsque :.
UniversitMohamedKhider-Bisk ra
FacultdesSciencesExact esetdesSc iencesdelaNatureetdel aVieDpartementdÕInformatique
2 `eme anneLMDCoursdÕAlgorith miqueetstructures
dedonne s1Chargducours: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
15.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
2Chapitre1
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 nscasonpeu 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
44.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. 5AlgorithmePremierExemple;
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
SinonPourjde1ifaire
LireaRg;
DoubleaRg;
T[j]BR;
FinPour ;
kB1;Tantqueaknigfaire
EcrireaT[k]oInverseaPigg;
kBk+1;FinTQ;
SBÕProgrammeterminÕ;
EcrireaSg;
FinSi;
Fin.Algorithme1:Algorithmet ype
6Chapitre2
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ÕunprogrammePenfo 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 aireestOa1g2.3.2La multiplicati onparuneconstante
Oacofangg= Oafangg
Exemple:
Oa n 3 4 g=Oan 3 g2.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 2FinSi;
8 estlema xentrel escomplexits delÕvaluati ondeSia[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. 9Exemple1:
AlgorithmeRecherche;
VarT:tableau[1..n]deen tier;
x,i:entier; trouv:booleen;Dbut
Pouride1nfaire
LireaT [i]g;Oa1gOa
B n 11g=Oang
FinPou r;
Lireaxg;Oa1g
TrouvBfaux;Oa1gOa1g
iB1;Oa1gOangTantqueatrouv=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
SinonEcrireax,ÕnÓexist epasÕg[Oa1g]
FinSi;
Fin. Lacomp lexitdelÕalgorithmeestdeOang+Oa1g+Oang+Oa1g=Oang. 10Exemple2:Soitlemo dulesuivan t:
Pouride1nfaire
[nfoisOa B n i=1 n igg]Pourjdei+1nfaire
[n ifoisOa B nBi 11g=Oan ig]
SiaT[i]>T[j][Oa1g]gAlors
tmpBT[i];[Oa1g]T[i]BT[j];[Oa1g]Oa1g
T[j]Btmp;[Oa1g]
FinSi;
FinPour ;
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 11Exemple3: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 ;
quotesdbs_dbs45.pdfusesText_45
SiaT[m]=x[Oa1g]gAlors
TrouvBvrai[Oa1g]
SinonSiaT[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 ;
quotesdbs_dbs45.pdfusesText_45
SupBm-1;[Oa1g]
FinSi;
FinSi;
FinTQ;
Siatrouv=vrai[Oa1g]gAlors
Ecrireax,ÕexisteÕ g;[Oa1g]Oa1g
SinonEcrireax,ÕnÕexist epasÕg;[Oa1g]
FinSi;
Fin.Lacomp lexitdelÕalgorithmeestde:
12Oa1g+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]
SinonFactBneF 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 gOnpeutd 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+aTang=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 uesgRemarque:Oan
3 gtempscubique6.Tang=Oa2
n g,t empsexponentiel :souventlersultatderechercheb rut aledÕune solution. 142.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;
153.Calculerlacomplexit delÕal gorithmesuivant:
iB1; jB0;Pourkde1nfaire
jBi+j; iBj-i;FinPour ;
quotesdbs_dbs45.pdfusesText_45[PDF] algorithme et structure de données pdf PDF Cours,Exercices ,Examens
[PDF] algorithme et suite à faire mais difficile pour moi à comprendre merci de votre Terminale Mathématiques
[PDF] algorithme et suite math 1ère Mathématiques
[PDF] Algorithme et valeur de x 2nde Mathématiques
[PDF] Algorithme et vecteurs 2nde Mathématiques
[PDF] algorithme euclide 3eme 3ème Mathématiques
[PDF] Algorithme euclidien : le PGCD 3ème Mathématiques
[PDF] algorithme exemple PDF Cours,Exercices ,Examens
[PDF] algorithme exercice DM 2nde Mathématiques
[PDF] algorithme exercice et solution PDF Cours,Exercices ,Examens
[PDF] ALgorithme exercice long 2nde Mathématiques
[PDF] Algorithme exercice seconde 2nde Mathématiques
[PDF] algorithme exercices corrigés pdf PDF Cours,Exercices ,Examens
[PDF] algorithme exo long 2nde Mathématiques