Theses Year : 1998

Recherche combinatoire : problèmes de pesage, reconstruction de graphes et applications

Abstract

Not available
La recherche combinatoire est une branche de l'algorithmique combinatoire qui est étroitement liée avec d'autres domaines des mathématiques et de l'informatique, tels que l'étude de la complexité d'algorithmes, la théorie des graphes, la théorie des nombres, la théorie des ensembles extrémaux. En termes très généraux, la recherche combinatoire étudié les problèmes d'identification d'un objet inconnu dans un ensemble d'objets à l'aide de questions indirectes sur cet objet. Les méthodes de la recherche combinatoire trouvent de nombreuses applications pratiques dans les domaines de la biologie, la médecine, la conception de réseaux, et d'autres. Le thème central de la thèse est le modèle additif en recherche combinatoire. Nous étudions la puissance de ce modèle en l'appliquant à quelques problèmes classiques de recherche combinatoire. Trois familles de problèmes sont considérées : les problèmes de pesage de monnaies, le problème de reconstruction de graphes d'une classe donnée et le problème de reconstruction de partitions. Pour les problèmes de reconstruction de graphes et de pesage, nous examinons les résultats connus et démontrons de nouveaux résultats plus généraux. Un des résultats les plus importants est l'obtention d'une borne supérieure pour le problème de reconstruction de vecteurs à poids borné. Nous introduisons également le problème de reconstruction de partitions, pour lequel nous développons des algorithmes efficaces dont nous analysons la complexité
No file

Dates and versions

tel-01754255 , version 1 (30-03-2018)

Identifiers

  • HAL Id : tel-01754255 , version 1

Intranet access

Cite

Vladimir Grebinski. Recherche combinatoire : problèmes de pesage, reconstruction de graphes et applications. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 1998. Français. ⟨NNT : 1998NAN10248⟩. ⟨tel-01754255⟩
93 View
0 Download

Share

More