[PDF] Cours de structures de données licence 2 - Université CLERMONT 2

View - Download Cours de structures de données licence 2 - Université CLERMONT 2

Previous PDF

Next PDF

COURSDESTRU CTURESDE DONNÉES

LICENCE2-UNIVERSITÉC LER MON T2

MAMADOUMOUSTAPHA KANTÉ

Tabledesmatières

1.Niv eaudeDescription2

1.1.S tructureGénéraled'unOrdinateur 2

1.2.MémoireCe ntrale3

1.3.Langages 3

2.Algorithmes, Valeurs,Typ esetÉlémentsduLangage 4

2.1.Don nées5

2.2.Tab leauxstatiques5

2.3.LaS yntaxed uLangage6

3.Typ esdeDonnéesAbstraits 7

3.1.TDA7

3.2.TDADicti onnair e8

3.3.TDAEnsem bleDyn amique8

3.4.TDAPile9

3.5.TDAFile10

3.6.TDAListe1 1

4.Élém entsdeComplexité14

4.1.Critères d'Évalutation14

4.2.Év aluationduTempsd'Exécution 14

4.3.Notations O,!et"15

4.4.Règlesd eCalcu l16

4.5.Pvs NP17

5.Type sInductifs19

5.1.Arborescen ces20

5.2.Tas 21

5.3.Arbres deRecherc he23

5.4.App lications26

6.Tab lesdeHashage27

6.1.Résolution descollisionsp archaînage28

6.2.Fon ctionsdeHashage29

6.3.Ad ressageOuvert30

Références30

L'algorithmiqueremonteàl' antiquité.Onpeu tcite rlecalculdesimpôtsàBa- byloneoulecalcul dessur faces cultivablesaprèsle scruesdu Nildansl'Egypte Ancienne,lecribled'Erathostènequip ermet detrouvertous lesnombrespremiers inférieursàuncertainentier, etc. Denosjours ,avecl'avèneme ntdesordinateurs

Date:31 mars201 4.

1

2MAMADOUMOUSTAPHAKANTÉ

l'algorithmiquefaitp artieintégrantedenotreviede touslesjou rs.Onpeutci- ter:achem in ement(poste,GPS,téléphone,Internet), ordonnancement(usine s), multimédia(compression),flot s(emploidutemps,embarquement),etc. Danscecou rsonvaétu diercertainesmé tho despour manipulerlesdonnées desalgori thmes.Cecoursestbasésurleslivre[1]et [4 ]etlecoursdeJ.G .Penaud auquelj'aiassistéquand j'étaisétudiant àl'Univ ersitéBordeaux1[5].Desid éessont empruntéesaupolycopiéducour sdisp enséparO.Raynaudlesannéesprécédentes [6].Jeremerc ieégal ementWikipedia.LesChapit res3,5et6ontchacununesecti on dédiéeàuneou plusieur sappl ications.

1.NiveaudeDescription

Unepartiede cechap itreestbas ésurlelivre [7].

1.1.StructureGénéraled'unOrdina teur.Lemod èledenosordinateurse st

celuideVon Neumann( communémentappelé machinesàregistres).Ilsso ntéqu iva- lentsauxmachinesdeTuringetaulambda-calculdeCh urch,etsontprincipalement composésde: (1)d'unemémoireadressableenlect ureetécriture, (2)d'uneunitéarithmético-l ogique(communémentappeléprocesseur)quis 'oc- cupedescal culs, (3)d'uncompteurd'instruction spourexécut erlesinstructionsuneàun e. EnF ig.??vousavezune versionsim plifiéede l'ordinateur.Onpeu ttrouver: (1)unbus dedonnées oùci rculentles valeursr eprésentantlesdonnées, (2)unbusd' adresses oùcirculentlesval eursreprésen tantlesvaleurs, (3)danslapar tie1, ona: (a)unemicr o-mémoire:stockagedesinstructions del 'ordinateur, (b)unmicr o-pc:compteurpourlesinstr uctio nsdelamicro-mémo ire, (c)undécodeur d'instructi ons:lesinstructionsenmémoiresonttra duite s parcedernier endes instructionsdel amicr o-mémoi re, (4)danslapar tie2,o nal'unitéarithmético -logique avecdeuxreg istr esR0et R1quiserv entcommesupportdestockagee tquicons tituel'unitédecalcul dela machine 1 (5)danslapar tie3,o nalecompteurordinalqui sertàincrémen terlesinst ruc- tionsdansla mémoire(lesprogrammes sont séquen tiels), (6)danslapar tie4,o na: (a)unemémoi recentralepourl estockagedesprogrammesenex écutionet lesdonn éesdecesderniers, (b)unreg istred'adresses:certainesdonnéesen mémoirereprésententdes adressesetilfau tpou voirles communiqueraubu sd'adressespourlire/écrire dessus. ckage,etc.Ilfautre marquerquec esd i

érentespartiespeuven tcommuniquerentre

ellesàtraversd' aut rescircuits.Chaquepar tied'unordinateurestréa liséeàpartir decir cuitsdontlesentréesetles sortiesont deuxétatsp ossibles:unétatposi tif (interprétécomme1)etunétatnégatif(interprétécomme0).U nétatest appelé bit.

1.Unreg istreest uncircuitséquenti elserva ntàstoc keruneséquencedebi ts.Ildisposed'une

entréespécialequ icommandelechargement desdonnée s.

STRUCTURESDEDONNÉES3

Pourqueles construct eurspuis sentmodifierleursordinateurs(avecdenouve lles instructions,améliorationdesperformances,. ..)san spourautantoblige ràréécrire lesprogrammes, seulesquelquesp artiessontvisiblesauxprogrammeurs .Enpar- ticulier,nousn'avon saccèsenpartic ulierqu'àlamémoirecentrale,le compteur ordinaletquelquesregistresd ontR0etR1.

1.2.MémoireCentrale.Lamémoire centralees tdiviséeenblocs (appelésmots)

demêmet ai lle.Latailledesmotsrepr ésentelat ailledesbusetdoncdesadresseset permetdecalculer ainsil ataillemaximaled'unemém oiredansunordi nateur .Un motsemesur eenbits (ex:32bits,64bits,etc.). Silataille d'unmotmémoir ec'est n,alorslenombredemotspossiblesc'est2 n etceci estla tail lemaximale d'une tellemémoire 2 desmémoi resavecmoinsde4Go. Chaquemotdelamé moirecont ientso itune donnéeouuneinstructi onouune adresse.Ilpeutarriverqu' unm otcontienne uneinstructionetlesa rgumentsde cettedernière.

1.3.Langages.Lelangagemachine c'estl'ensembl edesinstructionssupportées

parunemachi ne.L esinstructionsd'unemachine sontcodéesen binaireetmalheu- reusementnousnesommespasfaitspou rréfléchire nbinaire(d'aille urscelafait despr ogrammespresqueillisiblespour lecommundesmor tels,mêmesiaudébut del 'informatiquec'étaitlamanièrequel'onavai tdeprogrammeravecles cartes perforées).Pourremédieràceprob lème,oncréed eslangagesdeprogrammationqui sontunensemble demotsclés(chacunavecunsens )etderèglesdec onstructions pourécrirede sprogrammes.Cespro grammesso ntensuitetraduitsenlangage machineàl'aidedetraducteurs. Assembleur.Lapre mièretentativeaétéd'u tiliserdesinstructions enb ase16 (hexa-décimal)etlelangageobtenuestappeléassembleur.Cha queinstructiond e lamach ineestcodéeen hexa-décimale tcommeondisposedeplusd emotsd'une mêmetaille,on peut égalementco derdescombinaisonsd'instructions dulangage machineenun eseuleinst ructionhexa-déci male.Lorsquel'onconnaîtlescorres- pondancesentreinstruction smachinesetcod eshexa-décimauxonpeuttraduire(à lamain) sonprogrammeassembleurenlangagemachine. Exemple1.Danslesmachi nesx86,1011000001100001quisignifie" écrire97 danslere gistre al"se traduite nassembleurparmovb0x61,%al Mêmesi l'assembleurestmoins verbeuxque lelangagemachine,ilresteun peutro pcomplexeàma nipuleretesttrèsdépenda ntd elamachine.Néanmoinsil restelemeilleur moy enraisonnablepourécrired escodesoptimisésetre steencore utilisédansbeaucoupdeprog rammes(comme lessystèmesd'exploit ati onoules pilotesdepériphériques). Leslang agesdehautniveau.Onutilis elesmécanism esdeslan gageshumainsen utilisantlestravauxdéjàe ectuésdessusparles linguistestelsque Chomskyet al. Cependant,leslangageshumain ssonttrop complexesetnousnepourro nsjamais avoirunpro gramme quipuissentlestraduireenla ngagesmach ines.Néanmoinson peuts'eni nspireretpro duiredesmodèlesmathémat iquesq uiconviennentànos besoins.Leslangagesdeh autnivea usontconstitués:

2.Ilfa utserapp elerqu'unemé mo irecentraleestuncircuitet doncchaqueentréeav aleursoit

0soit1.

4MAMADOUMOUSTAPHAKANTÉ

(1)d'uncerta innombred'expressions(cha cunayantunsens)etunensem blede règlessophistiqué esquipermetd'écriredesprogrammescom préhens iblespar leshumains entraînés(ceuxqui prennentletempsdel'app rendre), (2)d'unensembled' outilspourt raduirelesprogrammesenlang agesmachines. L'avantagedecetteappro che:un seulprogrammepou rdestypesdemachines di

érents,ilsu

tjuste dedisposer d'unt raducteurpourchaque type. Ondis tingue2grandesclassesd elangage sdehautniveau. (1)leslangagesc ompilés:onécritu ncodesourcepu isonle compile .Ala compilationunfichierenlangageassembleurestcr ééquiestencoretraduit enlangagemachineparunaut reo util(lemêmeoutilp eutfairelesdeux étapes).Ensuite,onappell eunéditeurdeliens pour"r elier"lesdi

érents

boutscompilé sséparément.Desexemples delangagescompiléssontleC,

Ocaml,Lisp,...

(2)leslangagesin terprétés:unou tillitlecodesourceet"simu le"l'e xécution. Iltr aduitchaqueinstructi ondulangageetl'exé cute.Desexemplessontles langagesdescript (Javascript,HTML,...),Java,Lisp,Ocaml,... Onpe utégalementlesclas sifiersuivanttroisprincipaux paradigmes. (1)paradigmeimpératif:onadese !etsdebor dsurl esobjetsmanipulés(o nles manipuleàtr av ersleursadressesenmémoire).Unprogrammeeststr ucturé eninst ructionsdonnéesàexécuterparlamachine.On peutci terl eC,C++,

Pascal,...

(2)paradigmeobjet:lesvaleursma nipuléessontr egro upéesenensembleset chaqueensembleac cepteuncertainnombred' opérations.Onpeutcit erle

C++,Java,Scala,...

(3)paradigmefonctionnel:lesfonct ionssontlesobjetsdeba sedul angage(tout e valeurestvuecomm eunefonc tion).Onp eutciterLisp,Ocaml,Scala,

Haskell,...

Unlangage peutcom binerlesdi

érentsparadigmesetles concepteurspeu vent

proposerdesoutilspourl 'in terpréteret/oulecompil er.Onpeutmesurerl aqualité d'unlanga gesuivantplusieurscritères: (1)lav erbosité,i.e.lacap acitédefairedesgrosp rogrammesavec peudelign es decode, (2)lesméthod esproposéespourstructure runprogramme, (3)lacomp létudedulangage,i.e.,est-cequel'onpeutprogrammertoutceque peutpermett releslangagemachine . (4)...

2.Algorithmes,Valeurs,TypesetÉlém entsduLangage

Lemotalgorithmevientd'unmathé maticienarabedu9èmesiècl e(AlKhou- warizmi).Unalgorithmec'estunesérie d'opér ationsàe!ectuerdanslebut de résoudreunproblème.Ilpre ndenen tréedesdonnéesetfournitler és ultat.Lamise enoeuv redel'algorithme( appelée aussiimplémentation),i.e.,écrituredesdi!é- rentesopérationsdansu nlangagedeprogrammationdo nneunprogrammedans lelan gagechoisi.Avan td'écriredesalgorithmes, ilfautd'abordserap pelerde

TuringetChurchindép endam ment.

Theorem1(Indécidabilité).Onnep eutpas résoudretousles problèmesav ec desalgori thmes.Leproblèmedel'arrêtetlavé rificati ondeprogrammessontdes exemples.

STRUCTURESDEDONNÉES5

Theorem2(ThèsedeChurch-Tu ring) .Lesproblèm esayantunesolutionalgo- rithmiquesontexactementceu xquel'onp eutrésoudreparunemachinedeTuring (théoriedelacalculabili té ).

2.1.Données.Unidentifiantc'estunesuit edecar actèresalphanumériq ues(on

commencetoujour sparuncaractèrealphabét ique) . Untypec'estunensemble deval eursmunid'unensembl ed' opérationssurles valeursetuncertainn ombre d'axio mes/propriétésvérifié esparlesopérations .Un typeestrep résenté/ identifiéparunidentifiant. Exemple2.Sionpren dle typeintenC:le svaleursson tlesentiers.Lesopér ations sontl'additi on(+),lamultiplication (*),lasoustrac tion(-) ,ladivision(/)etle modulo(%).Ladivis ionpar0estinter dite. Uneconstantec'estuneval eurd'un certaintype.P arexemple10estuneconst ante (c'estunevaleur dutypeintenC).Un edonnéec'estsoituneconst ante,soitune entitéquiauntype,unev aleuretuniden tifian t. Unevariablec'estunident ifiant quidésigneunespacedestockageenmémoire etqui auntype T,i.e.,quedanscetespaceonnepeutstockerquedesvaleursde T.Unea!ectationd'unevaleur vàunevariablexconsisteàstocker vdansl'espace desto ckagedésignéparx.Avanttouteutilisationunevariabledoitêtreinitialisée (ilf autya ecterunevaleur).Ap rèsinitialisation,un evariablepeutêtreman ipulée commen'importe quellevaleurdesontype.Ilfau tfaireladi

érenceentreune

variableetlecontenuqu iyaits tocké .

Ondis tinguedeuxsortesdetype s.

fourniespardéfaut.Dans laplupart deslangagesl estypesprimit ifssont lesentiers,lesréels,lescaractères.Cer tainsproposentenplusl eschaînesde caractèresetles booléens. (2)Lestypescomposés.Ils sontco nstruitsàpa rtird'autrestypes.Danslaplu- partdeslanga gesde programmationonfournitpar défautl etypecomposé mêmetyp eaveclapropriétéque l'onpuisseaccéderàchaquecasemémoir e nombred'éléments).Sui vantleslangagesdeprogra mmationvoicilesdi rentestechniquesp ourconstruired'autrestypescomposé s. produit:SiT 1 ,...,T n sontdesty pes, onpeutconstruireletype T 1 T n composédesval eurs{(x 1 ,...,x n )|x i #T i somme:SiT 1 ,...,T n sontdestyp es,onp eutconstruireletyp eT 1 $...$T n dontl'ensembledes valeursc'estl'uniondesv al eursdesT i enregistrement:C'estuntypeco mposéd eplusieurse ntitésappeléchamps, chacunayantuniden tifiantetuntype. C'estu ntypeproduitmaisoùil n'yapasd' ord reentrel eschamps.Commepourlest ableaux,chaque champestunesp acedestock ageen mémoire.

2.2.Tableauxstatiques.Laprop riétéfondamentaledestableauxstatiquesc'est

quel'onpu isse accéderàchaqueélémen tenspécifiantseulement sonin diceet letemp sd'yaccéde rdoitê treproportionnelàlatailledel'élément. Lemoyen leplu ssimplederepré senteruntable auenmémoire estdestockerseséléments consécutivement(etc'estcequiestfai tleplussouv ent).Ai nsisitabestun tableau etchaq ueélémentdutableaunécessi tecmotspour sonstockage,alor slejéme

élémenteststocké àl' adressetab

0 +cjoùtab 0 estl 'adressedupremierélément.A vec cettereprésentati on,onn'abesoindeconnaîtrequel'adressedupr emierél ément

6MAMADOUMOUSTAPHAKANTÉ

fautconnaî treàl'avancelenombred'él éments dutableau.Enplusilfautfaire attentioncarsiletab leaucontien tnéléments,demanderàaccéderau(n+i)ème élémentpeutproduir euncomport ementbizarre(onaccèdeàunezonemémoire danslaq uelleonn'apeut-êtrepasaccèsou lavaleur luen'estpa scohérente),ce genredecomporteme ntpeutp roduiredeserreursditesoverflow. Onpe utétendrecettere présentationdestableauxs tatiquesàunedim ension auxtableauxstatiqu esàdeux,trois,qu atre,...dimen sionsd etellesortequepour accéderàunélémen t,ond onnejuste sescoordonnées. Ilf autnoterqued ansnotrereprés entationd estableaux, iln'yaaucunmoye n deconna îtrelatailled'untablea u.Ainsi, ilfaudratoujours,lorsquel'o ndonneun tableauenparamètreà unefon ction,spécifie rdan slalistedesparamè treslataille dut ableausionenabesoindans lafo nction. Onve rraplustardcomme ntfairedestableauxdynamiques(pasbes oindeconnaître

àl'avancelataille).

2.3.LaSynt axeduLangage.Onva utiliserun esyntaxeprochedec elleduC.

Chaqueinstructi onsetermineparunpoint-virgule.On vautil iserlamêmesyntaxe queleCpourlesst ructuresc onditionnellesetitérative(voi rn'importequellivre surle C,parexemple[3]).UnevariabledetypeTestdéclar éeàl'aidedel' instr uc- Typesprimiti fs.Nousallonsdis poserde int,float,bool,char,stringsreprésentant respectivementlesentiers,lesréels,lesbooléens ,lescarac tèresetleschaînesde caractères.Poura cherunevaleur oule contenud'unevar iable d'untyp eprimitif, vaut iliserlessymboles=,>,<,%,&,'=aveclas ignific ationstandard.Pourconca- ténerdeuxchaîne sdecaractèresonva utiliserlecaractère^.Pouridentifierles caractèresdeschi resetdeschaî nesdecar actères composéesd'unseulcaractèr e, onécrit lescaractèresen treapostrop heset leschaînesd ecaractèresentreguille- mets.Par exemplelesvaleurs'0',0e t"0" sontrespect ivementdetypechar,intet string. Typescomposés. Pourdéclar eruntableaudenélémentsdetypeTonécritT auièmeélém entd'untableautabonécrittab[i].Com mechaquecase d'untableau représenteunespacedestockage ,alorstab[i]peut-êtreutiliséecommen' importe quellevariable.

Pourdécla reruntableauàkdimensionsavecn

1 "..."n k

élémentsdetype

TonécritTid_tab[n

1 ][n 2 ]...[n k ]etpour accéderàlav aleurst ock éeàlacase (i 1 ,...,i k ),onécritid_tab[i 1 ][i 2 ]...[i k ].Ce qui estvalabl epourlest ableauxàune dimensionresteaussiv alable. Pourcréerd estypescomposé s,onvauti liserleconstruc teurdetypestructqui construitdestypesenregist rement .Sionveutcréeruntyp eid_typeonécrit struct id_typelistedeschamp s;oùch aquechampestdonnésous laformetypeid_champ;. Aprèsunedé clarationdutypeid_type,onpeutlesutiliserpourdéclarerdesva- riablescommep ourn'importequelautret ype.Lorsquevarestune vari abledetype id_type,pouraccéderàunchampid_champs,onécritvar.id_champs.Com me chaquechampestun espacedestoc kage,onpe utlem anipulercommeuneva riabl e.quotesdbs_dbs13.pdfusesText_19

[PDF] arbre binaire de recherche algorithme

[PDF] arbre binaire de recherche algorithme suppression

[PDF] parcours en profondeur arbre

[PDF] arbre binaire complet

[PDF] dénombrement cours

[PDF] arbre de probabilité pile ou face

[PDF] arbre de probabilité seconde

[PDF] arbre probabilité conditionnelle

[PDF] arbre de décision exercices corrigés

[PDF] arbre de décision data mining

[PDF] cours arbre de décision

[PDF] classification par arbre de décision

[PDF] arbre de décision exemple

[PDF] arbre de décision cart

[PDF] construire un arbre de décision