• Langue : Français
• Discipline : Informatique
• Identifiant : Thèse : 2000LIL10079
• Type de thèse : Doctorat
• Date de soutenance : 01/01/2000

Résumé en langue originale

Tout d'abord par une etude theorique du phenomene de seuil dans 3sat, une categorie du probleme de satisfaction de contraintes booleennes, sous forme normale conjonctive (cnf), avec exactement 3 variables par clauses. soit g le rapport entre le nombre de clauses et le nombre de variables, experimentallement on a decouvert un seuil brutal pour g appele g 0 (= 4.25), tel que, quand le nombre de variables tend vers l'infini, la proportion des expressions satisfiables s'effondre de 1 a 0 quand g passe d'inferieur a superieur a g 0. peu de proprietes relatives au seuil sont prouvees. son existence meme reste a etablir. de plus 3sat semble np dur en moyenne seulement au seuil, l'analyse de l'algorithme de davis-puttnam montrant que le probleme est polynomial en moyenne. apres avoir ameliore (de 4.60 a 4.58) la valeur du plus petit majorant existant pour g 0, nous montrons que les techniques utilisees ne permettraient plus d'ameliorations significatives. ensuite, chez detexis service contre-mesures, par l'etude d'un probleme de resolution de contraintes booleennes : l'identification de menaces en territoire inconnu, un probleme d'optimisation multifactorielle, np-complet pour plusieurs parametres. il illustre les difficultes de l'informatique, a exprimer un probleme, a le modeliser convenablement puis a le resoudre en un temps raisonnable. description du probleme : il s'agit, a partir de donnees electromagnetiques recues et d'une base de donnees des signatures electromagnetiques des appareils connus, de reconstituer l'environnement et d'anticiper les actions des appareils reconnus. ici la pratique est souvent pragmatique (utilisation de coefficients de confiance). nous y avons esquisse une approche probabiliste. en particulier, dans un cas simple, nous montrons comment cette approche permet de substituer a des calculs exhaustifs durs un calcul des solutions les plus dangereuses base sur des methodes formelles.