Recherche combinatoire : problèmes de pesage, reconstruction de graphes et applications - Université de Lorraine Accéder directement au contenu
Thèse Année : 1998

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

Résumé

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é
Fichier non déposé

Dates et versions

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

Identifiants

  • HAL Id : tel-01754255 , version 1

Accès intranet

Citer

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⟩
77 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More