(résultat légérement meilleur que pour un vecteur non-ordonné) Opérations sur tableaux ordonnés : – recherche sequentielle O(N) – suppression, insertion : O( N)
13 sept 2000 · LANGAGE C - EXEMPLES DE PROGRAMMES Programm int main() e de recherche dichotomique d'un élément dans une liste d'entiers */
Recherche dans un tableau, dichotomie 7 de 47 Recherche dichotomique itérative Remarque : La recherche dichotomique est récursive terminale Algorithme
Peut-on éviter de parcourir tout le tableau pour rechercher le maximum d'un tableau d'entiers non trié ? Exercice 2 Recherche séquentielle dans un annuaire On
12 mar 2013 · 3 RECHERCHE DICHOTOMIQUE Algorithme recherche_dichotomique { Recherche le premier indice où se trouve la valeur val en utilisant la
Soit une structure tabulaire A[1 n] triée en ordre croissant On effectue une recherche dichotomique d'une valeur x comme suit Soient : • g l'indice de gauche
(résultat légérement meilleur que pour un vecteur non-ordonné) Opérations sur tableaux ordonnés : – recherche sequentielle O(N) – suppression, insertion : O( N)
23 déc 2019 · Consolider et étendre vos connaissances d'un langage de programmation (le Recherche dichotomique : 256000 vérifications par seconde
28 avr 2013 · Recherche dichotomique d'un élément dans un tableau 3 Dénombrement Dénombrement Recherche itérative : langage algorithmique
factorielle, Fibonaci, exponenÄaÄon rapide, recherche dichotomique, tri fusion gérée par le langage de programmaÄon : une pile LIFO de taille préfixée
[PDF] recherche dichotomique recursive langage c
[PDF] exemple de manuel de procedure informatique
[PDF] organisation d une dsi type
[PDF] manuel de procédures informatiques
[PDF] cyberlux 8
[PDF] organisation d'un service informatique dans une entreprise
[PDF] cyberlux 8 crack
[PDF] exemple dossier exploitation informatique
[PDF] cyberlux 8 full
[PDF] bibliographie de max weber
[PDF] max weber pdf
[PDF] max weber économie et société tome 2 pdf
[PDF] max weber le savant et le politique pdf
[PDF] max weber économie et société fiche de lecture
[PDF] max weber économie et société tome 1 résumé
Methodesdeprogrammation Algorithmesderecherche, trietselection
MihaelaMATHIEU-JUGANARU mathieu@emse.fr
2007-2008 Selection.Recherche.Tri Hypothesesdetravail EnsembleniE.Esous-ensembled'unensemble debaseX(EX).
EnsembleXmunid'unerelationd'ordretotale kEk=N.
E=fx1;x2;:::xNg Problemes Recherche "Verierl'existenced'unelementdonne"
Six2X,trouversix2E.(trouveritelque x=xi)
Selection Trouverx=min(E)et/ouy=max(E) c
M.MathieuGeneralites Tri "Ordonnerenordrecroissant(oudecroissant) leselementsd'unensemble"
Trouverunepermutationdel'ensemble f1;2;:::;Ng telleque8i
AcherleselementsdeEdansl'ordreinduit par: x (1)x(2):::x(N) c M.MathieuGeneralites Schemad'etude: {Complexitetheorique {Solutions {(Nouvelles)Structuresdedonneesetleurs solutions {(Solutionspourcasparticuliers) {Complexitepourchaquesolution c M.MathieuGeneralites Structuresdedonnees: Structuresdedonnesconnues:Vecteuret listecha^nee(ordonnesoupas) Co^utdemiseenplaceetdemiseajour: {insertion {suppression {(recherche) Nouvellesstructures:tas,arbres... c M.MathieuGeneralites Recherche 1.Problematiqueetcomplexitetheorique non-ordonnes/ordonnes 3.Recherchedichotomique Rechercheparinterpollation 4.Arbresbinairesderecherche 5.Arbresequilibres 6.Tablesdehachage c M.MathieuRecherche Probleme:SoientEXuneensembledecles, munid'unordretotaletx2X,veriersi x2E. Veriersiunelementsetrouvedansunen- nonindiquerundiagnosticd'erreuret/ouin- diquerlepluspetitelementquiledepasseou autresinformations... Clemultiple:unevaleurquisetrouveplus d'unefoisdansl'ensembleE.SiEadmetdecles multiples,encasderecherchesurunetellecle trouverlapremiere/derniere/unequelconque apparitiondecettecle. D'apresKnuth[4]larechercheprendlaplu- partdutempsdelaplupartdesprogrammes c M.MathieuRecherche Structuresdedonnees Dictionnaire :structurededonneesquiper- met: {insertion {supression {recherche Exemples:listechainee,vecteurnon-ordonne /ordonne,arbrederecherche,arbrerougeet noir,AVL,B-arbre,tabledehachage. c M.MathieuRecherche Complexite Hypothese: Onnefaitquedescomparaisons entrexetxi2E.Leresultatd'unecomparai- sonest:=,ou. Exemple:L'arbredescomparaisonspourl'en- semblefx1;x2g. x1 : x OUIx2 : x OUIOUINONNONNONNON x2 : x c M.MathieuRecherche Remarque1:Sivnudinterieurd'unarbre decomparaisons,alorsdegre(v)=4ou3pour laracine;sinon,degre(v)=1.Chaquenud interieuracommedescendantauplus2autres nudsinterieurs. Remarque2: SiAarbredecomparaisons,alors AaaumoinsNnudsinterieurs. Theoreme: Larecherched'unelementdans unensembledetailleN,eneectuantquedes comparaisons,sefaitenexecutantaumoins dlogNecomparaisons. Preuve: SiAestl'arbredecomparaisonsd'une tellerecherche,lenombredecomparaisonsest donneeparlahauteurdel'arbre. Comptetenuderemarquesfaites,soitklahau- teurminimaled'unarbredecomparisonayant aumoinsNnudsinterieurs.Alors: 1+2+:::+2k1 2 k1Donck=dlogNe. c M.MathieuRecherche Recherchesequentielle Principe: Parcourirleselementsdel'ensemble El'unapresl'autreenveriantl'egalite. Pourtoutide1aNcomparerxetxi ComplexiteenO(N) Nombredecomparaisons:minimum1etmaxi- mumN,six2E.Six=2E,entre1ouN+1 comparaisons. c M.MathieuRecherche intr_seq_vect_non_ord(intv[],intN,intx) inti; for(i=0;iNombremoyendecomparaisons: M=p1+2p2+:::+NpN+(N+1)q,ou p i=probabilitex=xi,i=1;N q=probabilitex=2E. NX i=1p i+q=1 Remarque:Lamethodederechercheestplus ecace,sileselementslesplusfrequentssont placesversledebutdelastructure. Sip1=p2=:::=pN,alors M=p1N(N+1) 2+q(N+1) c M.MathieuRecherche siq=0,M=N+12 siq=1 2,alorsM=3(N+1)4 Operationsavecuntableaunon-ordonne: {insertion:O(1) {suppression:O(1)apresunerecherche intinsert_vect_non_ord( intv[],int*taille,intvaleur) v[*taille]=valeur; ++*taille; return; intsupp_vect_non_ord( intv[],int*taille,intposition) v[position]=v[*taille-1]; --*taille; return; c M.MathieuRecherche listerecherche_seq_liste_non_ord( listetete,intvaleur) listeaux; aux=tete; while((aux!=NULL)&&(aux->cle!=valeur)) aux=aux->next; returnaux; Operationsavecunelistenon-ordonnee: {recherche:O(N) {insertion:O(1) {suppression:O(N),i.e.O(1)apresunere- cherche. c M.MathieuRecherche intinsert_liste_non_ord( liste*tete,intvaleur) listeaux; aux->cle=valeur; aux->next=*tete; *tete=aux; intsupp_elt_liste_non_ord( liste*tete,intvaleur) listeaux,avant; if(*tete==NULL) returnFALSE; if((*tete)->cle==valeur) *tete=(*tete)->next; returnTRUE; else avant=*tete; aux=(*tete)->next; while((aux!=NULL) &&(aux->cle!=valeur)) avant=aux; aux=aux->next; if(aux==NULL) returnFALSE; else avant->next=aux->next; c M.MathieuRecherche intrecherche_seq_vecteur_ord( intv[],intN,intvaleur) inti; for(i=0;(iComplexitemoyenne: M=NX i=1ip i+NX i=0(i+1)qiou: p i=probabilitex=xi,i=1;N q 0=probabilitex q N=probabilitex>xN q i=probabilitexiM.MathieuRecherche Sousl'hypothese: p 1=p2=:::=pNetq0=q1=:::=qN lenombremoyendecomparaisonsest: M=p1N(N+1) 2+q0(N+1)(N+2)2 SiP(x2E)=1,alorsM=N+1 2. SiP(x2E)=1 2,alorsM=2N+34(resultat Operationssurtableauxordonnes: {recherchesequentielleO(N) {suppression,insertion:O(N) Remarque: leminimumetlemaximumsetrouvent sitiondutableau. c M.MathieuRecherche listerecherche_seq_liste_ord( listetete,intvaleur) listeaux; aux=tete; while((aux!=NULL)&&(aux->clenext; if((aux!=NULL)&&(aux->cle==valeur)) returnaux; else returnNULL; Recherche,insertion,suppressionentemps lineaire(O(N)). c M.MathieuRecherche intsupp_elt_liste_ord( liste*tete,intvaleur) listeaux,avant; if(*tete==NULL) returnFALSE; if((*tete)->cle==valeur) *tete=(*tete)->next; returnTRUE; else avant=*tete; aux=(*tete)->next; while((aux!=NULL)&&(aux->clenext; if((aux==NULL)||(aux->cle>valeur)) returnFALSE; else avant->next=aux->next; c M.MathieuRecherche intinsert_liste_ord( liste*tete,intvaleur) listeaux; listetemp,prev; aux->cle=valeur; if(valeur<=(*tete)->cle) aux->next=*tete; *tete=aux; return; else prev=*tete; temp=(*tete)->next; while((temp!=NULL)&&(valeur>temp->cle)) prev=temp; temp=temp->next; prev->next=aux; aux->next=temp; return; c M.MathieuRecherche Recherchedichotomique Applicableadesvecteursordonnes. Remarquepreliminaire: SoientTunvecteuror- donneetxunelementquisetrouveentrele positiongetdduvecteur(gSix>T[j],alorsxsetrouvententrej+1etd. Sixquotesdbs_dbs31.pdfusesText_37
×
if you Get
No preview available Click on (Next PDF)
Next PDF
[PDF] Recherche dichotomique dans un tableau dentiers - LAMSADE![[PDF] Méthodes de programmation Algorithmes de recherche, tri et sélection](https://pdfprof.com/Listes/18/2504-18mislides.pdf.pdf.jpg "[PDF] Méthodes de programmation Algorithmes de recherche, tri et sélection")