skip to main content

ANALYSE EN MOYENNE D'ALGORITHMES, TRI RAPIDE ET ARBRES DE RECHERCHE

HENNEQUIN, PASCAL ; Steyaert, Jean-Marc

S.l. : s.n., 1991

Voir les exemplaires

  • Titre:
    ANALYSE EN MOYENNE D'ALGORITHMES, TRI RAPIDE ET ARBRES DE RECHERCHE
  • Auteur: HENNEQUIN, PASCAL
  • Autre(s) auteur(s): Steyaert, Jean-Marc
  • Sujets: ALGORITHME DE TRI;
    THEORIE DE LA COMPLEXITE;
    H-INF.TH.
  • Description: Thèse Doctorat
    CETTE THESE EST CONSACREE A L'ANALYSE DES COMPORTEMENTS EN MOYENNE ET DES DISTRIBUTIONS DE PROBABILITE DE DIFFERENTES STRUCTURES D'ARBRES DE RECHERCHE ET DE L'ALGORITHME DE TRI RAPIDE QUICKSORT AVEC SES PRINCIPALES VARIANTES: MEDIANE DE K, MULTIPARTITIONNEMENT, TRI PARTIEL. L'OBJECTIF EST DE MONTRER, DANS LE CAS DE STRUCTURES ALGORITHMIQUES CLASSIQUES DE L'INFORMATIQUE, L'EFFICACITE DE CERTAINES METHODES D'ANALYSE COMBINATOIRE ET D'ANALYSE ASYMPTOTIQUE ARTICULEES AUTOUR DE L'UTILISATION DE SERIES GENERATRICES DE DENOMBREMENT. ON MONTRE COMMENT DANS LE CADRE D'UNE METHODOLOGIE PLUS LARGE, ON PEUT PASSER DIRECTEMENT D'UNE DESCRIPTION DE LA STRUCTURE COMBINATOIRE ET RECURRENTE DU PROBLEME A UN ENSEMBLE D'EQUATIONS ANALYTIQUES SUR DES SERIES GENERATRICES CARACTERISTIQUES DES COUTS D'EXECUTION DE L'ALGORITHME. POUR L'ALGORITHME ASSEZ GENERAL CONSIDERE, ON MET EN PLACE UN SCHEMA DE RESOLUTION QUI PERMET D'OBTENIR LES VALEURS MOYENNES EXACTES POUR DIFFERENTES FONCTIONS DE COUT POSSIBLES. ON INTEGRE DE PLUS DANS CETTE RESOLUTION DES METHODES ASYMPTOTIQUES ISSUES DE L'ANALYSE DE SINGULARITE. POUR LES DISTRIBUTIONS DES COUTS LIEES A LA RECHERCHE DANS LES ARBRES, ON PROUVE AINSI LA CONVERGENCE VERS UNE LOI LIMITE GAUSSIENNE. POUR LE TRI QUICKSORT, ON MONTRE L'EXISTENCE D'UNE LOI LIMITE POUR LA DISTRIBUTION DU NOMBRE DE COMPARAISONS. LA DERNIERE PARTIE DE CE TRAVAIL REPREND L'ANALYSE EN MOYENNE DU TRI DANS LE CAS DU MODELE AVEC CLES REPETEES
  • Éditeur: S.l. : s.n.
  • Date de publication: 1991
  • Langue: Français
  • Source: Mines ParisTech (catalogue)

Recherche dans les bases de données distantes en cours. Merci de patienter.

  • Recherche
  • dansscope:(33PSL-CNSAD),scope:(33PSL-EHESS),scope:(33PSL-PSL_OMEKA),scope:(33PSL-MINES),scope:(33PSL-EFEO),scope:(33PSL-CNSMDP),scope:(33PSL-CHIMIE),scope:(33PSL),scope:("DAU"),scope:(33PSL-CDF),scope:(33PSL-ENS),scope:("33PSL-OBSERV"),scope:("33PSL-ESPCI"),scope:(33PSL-CURIE),scope:(33PSL-ENSBA),scope:("33PSL-ENC"),scope:(33PSL-PSL_STAR),scope:(33PSL-PSL_SFX),scope:("33PSL-EPHE"),scope:(33PSL-ENSAD),primo_central_multiple_fe
  • Afficher ce qui a déjà été récupéré