Normal view MARC view ISBD view

Méthodes d'analyse pour les constructions combinatoires et les algorithmes / Michèle Soria-Cousineau ; sous la direction de Philippe Flajolet

Auteur principal : Soria, Michèle, AuteurAuteur secondaire : Flajolet, Philippe, 1948-2011, Directeur de thèseAuteur secondaire collectivité : Université Paris-Sud, Etablissement de soutenanceType de document : ThèseLangue : français.Pays : France.Éditeur : [S.l.] : [s.n.], 1990Description : 1 vol. (179 p.) ; 30 cmISBN : 2726106420.Bibliographie : Bibliogr. p. 175-179.Sujet MSC : 68Q25, Computer science -- Theory of computing, Analysis of algorithms and problem complexity
68R05, Computer science -- Discrete mathematics in relation to computer science, Combinatorics
68Wxx, Computer science, Algorithms
65Y04, Numerical analysis -- Computer aspects of numerical algorithms, Algorithms for computer arithmetic, etc.
97A70, Mathematics education - General, mathematics and education, Theses and postdoctoral theses
Note de thèse: Thèse de doctorat, informatique, 1990, université Paris Sud
Tags from this library: No tags from this library for this title. Log in to add tags.
Current location Call number Status Date due Barcode
CMI
Salle S
Thèses SOR (Browse shelf) Available 10474-01

Bibliogr. p. 175-179

Thèse de doctorat informatique 1990 université Paris Sud

L'objet de cette these est l'etude des proprietes statistiques de structures combinatoires, et la motivation premiere est l'analyse d'algorithmes. Analyser la complexite d'un algorithme revient souvent a etudier une classe particuliere d'objets combinatoires. Nous presentons ici l'analyse de la complexite moyenne des systemes de recriture reguliers, qui repose sur l'etude des familles simples d'arbres. Plus generalement nous etudions les relations existant entre la description structurelle des objets combinatoires et leurs proprietes statistiques. Nous montrons l'apparition de distributions probabilistes communes dans des schemas combinatoires tres generaux et nous classifions les constructions les constructions combinatoires vis-a-vis de leurs proprietes statistiques. Les proprietes statistiques des schemas combinatoires resultent des proprietes analytiques des series generatrices associees. Une partie essentielle de notre etude est donc consacree a la recherche de conditions analytiques entrainant l'apparition de lois limites donnees dans certains types de schemas fonctionnels. Ce travail repose sur deux principes generaux: d'une part la traduction des constructions combinatoires en operateurs sur les series generatrices, et d'autre part l'utilisation de methodes asymptotiques d'analyse complexe et de theoremes limites de probabilites. En application de nos resultats analytiques generaux nous derivons bon nombre de resultats originaux sur une grande variete de structures combinatoires et informatiques: nombres entiers, polynomes sur un corps fini, mots sur un alphabet fini, permutations avec differents types de contraintes, diverses familles d'arbres etiquetes et non etiquetes, graphes 2-reguliers, classes de graphes fonctionnels de divers types, etc.

There are no comments for this item.

Log in to your account to post a comment.