Université Lille1 - Sciences et Technologies Contribution à l'ananlyse de la complexité de problèmes de résolution de contraintes 004.015 1 Probabilités Recherche opérationnelle Complexité de calcul (informatique) Optimisation combinatoire Intelligence artificielle Applications militaires Contre-mesures électroniques Text Electronic Thesis or Dissertation fr 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. application/pdf 1 : 1 Mo https://pepite-depot.univ-lille.fr/RESTREINT/Th_Num/2000/50376-2000-210.pdf Dandrieux Jean-Pierre 1900-01-01 060900121 Thèse : 2000LIL10079 2000-01-01 Informatique Université Lille1 - Sciences et Technologies 026404184 Doctorat non oui Dauchet Max 110327969 ddc:004 ASCII PDF 9999 restriction 2012-01-01 9999-01-01 restriction 2012-01-01 9999-01-01