[PDF] les structures de l'entreprise pdf
[PDF] les structures de l'entreprise résumé
[PDF] les structures organisationnelles de l'entreprise
[PDF] Les subordonnées : Alors que et tandis que, ils expriment l'opposition, le temps ou les deux
[PDF] les subordonnées conditionnelles
[PDF] LES SUBORDONNES SVP !!
[PDF] Les substitus et leurs référents!Urgent besoin d'aide!!!
[PDF] les substituts exercices
[PDF] les substituts grammaticaux 1am
[PDF] les substituts grammaticaux exercices 3am
[PDF] les substituts grammaticaux pdf
[PDF] les substituts lexicaux et grammaticaux 3am
[PDF] les substituts lexicaux et grammaticaux exercices corrigés pdf
[PDF] Les succès de L'Union Européenne
[PDF] Les Sud : Croissance Démographique et Richesses
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:SiTquotesdbs_dbs46.pdfusesText_46
COURS DE STRUCTURES DE DONNÉES LICENCE 2 - UNIVERSITÉ CLERMONT 2