From: couchot Date: Tue, 18 Aug 2015 06:05:39 +0000 (+0200) Subject: ajout d'unesynthèse X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/54b170f26af2fb6bf6150f003918ac5992314293?ds=inline ajout d'unesynthèse --- diff --git a/14Secrypt.tex b/14Secrypt.tex index e160bc3..a60e4ff 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -13,13 +13,13 @@ graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graph arête sortante et une arête entrante. -This aim of this section is to show -that finding DSSC matrices from a hypercube -is a typical finite domain satisfaction -problem, classically denoted as -Constraint Logic Programming on Finite Domains (CLPFD). -This part is addressed in the first section. Next, we analyse the first -results to provide a generation of DSSC matrices with small mixing times. +% This aim of this section is to show +% that finding DSSC matrices from a hypercube +% is a typical finite domain satisfaction +% problem, classically denoted as +% Constraint Logic Programming on Finite Domains (CLPFD). +% This part is addressed in the first section. Next, we analyse the first +% results to provide a generation of DSSC matrices with small mixing times. \section{Programmation logique par contraintes sur des domaines finis} Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. diff --git a/demandeInscription/fiche-navette-autorisation-inscription-hdr.doc b/demandeInscription/fiche-navette-autorisation-inscription-hdr.doc index 8f6cac9..16da0fb 100644 Binary files a/demandeInscription/fiche-navette-autorisation-inscription-hdr.doc and b/demandeInscription/fiche-navette-autorisation-inscription-hdr.doc differ diff --git a/demandeInscription/synthese.tex b/demandeInscription/synthese.tex index a2761f2..0d467aa 100755 --- a/demandeInscription/synthese.tex +++ b/demandeInscription/synthese.tex @@ -208,7 +208,7 @@ de 5000 lignes de Code C annoté fourni par Dassault aviation. -\subsection*{Publication issues de ces recherches} +\subsection*{Publications issues de ces recherches} \begin{enumerate} @@ -300,10 +300,175 @@ Analyse d'atteignabilit\'e d\'eductive. \newpage \section{Exposé des recherches réalisées au cours de la période postdoctorale (5 pages maximum)} +\JFC{chapeau à refaire} + + +\subsection{Convergence de systèmes dynamiques discrets} + +Un système dynamique discret (SDD) est une fonction $f$ +du $n$-cube ($\{0,1\}^n$) dans lui même et un mode opératoire +(parallèle, unaire, généralisé) qui peut être itéré +en synchrone ou en asynchrone. +Ils ont été étudiés à de maintes reprises~\cite{Rob95,Bah00,bcv02}. +Pour chacun de ces modes, il existe des critères (suffisants) de convergence +globale ou locale, souvent basés sur le fait que $f$ est +est un opérateur contractant ans un espace. + +Les modes asynchrones ont une dynamique avec plus de liberté +puisqu'ils autorisent chaque élément à modifier sa valeur avant +de connaître les valeurs des autres éléments dont il dépend. +Cependant, lorsque les calculs à effectuer sur certains n{\oe}uds +sont coûteux en temps et/ou que les temps de communication sont élevés, +ces modes peuvent présenter une convergence plus rapide que le cas synchrone. + +Dans~\cite{BCVC10:ir}, j'ai formalisé le mode des +\emph{itérations mixes} (introduit dans~\cite{abcvs05}) +qui combine synchronisme et asynchronisme. +Intuitivement, les n{\oe}uds qui pourraient engendrer des cycles dans +les itérations asynchrones sont regroupés dans une même classe. +Les noeuds à l'intérieur celle-ci groupe seront itérés de manière +synchrone et les itérations asynchrones sont conservées entre les groupes. +Pour gommer les différences entre les n{\oe}uds d'une même classe +lorsqu'ils sont vus depuis des n{\oe}uds extérieurs, j'ai défini le +mode des \emph{itérations mixes avec delais uniformes}. + + +Grâce à cette formalisation, j'ai pu énoncer puis démontrer un théorème +établissant que pour des conditions classiques de convergence des itérations +synchrones d'une fonction $f$, les itérations mixes à délai uniforme +convergent aussi vers le même point fixe. + + +L'étude de convergence de SDD est simple à vérifier +pratiquement pour le mode synchrone. Lorsqu'on introduit des stratégies +pseudo périodiques pour les modes unaires et généralisées, le problème +se complexifie. C'est pire encore lorsqu'on traite des itérations asynchrones +et mixes prenant de plus en compte les délais. +Des méthodes de simulation basées sur des stratégies et des délais générés aléatoirement ont déjà été présentées~\cite{BM99,bcv02}. +Cependant, comme ces implantations ne sont pas exhaustives, elles ne sont intéressantes que lorsqu'elles fournissent un contre-exemple. +Lorsqu'elles exhibent une convergence, +cela ne permet que donner une intuition de convergence, pas une preuve. +Autant que je sache, aucune démarche de preuve formelle automatique +de convergence n'avait jamais été établie. + + +J'ai montré dans~\cite{Cou10:ir} comment simuler +des SDDs selon tous les modes pour établir +formellement leur convergence (ou pas). +Cette simulation est basée sur l'outil SPIN de \emph{Model-Checking} +qui est une classe d'outils adressant le problème de vérifier automatiquement +qu'un modèle vérifie une propriété donnée. Pour traiter le problème d'explosion +combinatoire, les outils de cette classe +appliquent des méthodes d'ordre partiel, d'abstraction, +de quotientage selon une relation d'équivalence. + +Pour cela, j'ai présenté pour cela une démarche de traduction d'un SDD +dans PROMELA qui est le langage de SPIN. +J'ai énoncé puis prouvé ensuite la correction et la complétude de la démarche +Des données pratiques comme la complexité et des synthèses d'expérimentation +ont aussi été fournies. + + + +\subsection{Construction de fonctions chaotiques} +Pr. Christophe Guyeux de l'équipe AND a proposé dans sa thèse~\cite{guyeuxphd} +une caractérisation des fonctions $f$ de $\{0,1\}^n$ dans lui même +dont les itérations sont chaotiques selon Devanney dans certains mode: +il est nécessaire et suffisant que son graphe des itérations soit +fortement connexe. +J'ai proposé plusieurs méthodes de construction de +fonctions ayant de tels graphes d'itérations~\cite{bcgr11:ip,chgw+14:oip}. + +Dans la première~\cite{bcgr11:ip}, +l'algorithme enlève des arcs et vérifie ensuite que +la forte connexité est maintenue. +Même si cet algorithme retourne toujours des fonctions dont le graphe +des itérations est fortement connexe, il n'en est pas pour autant efficace +car il nécessite une vérification à postériori de la +forte connexité sur le graphe entier composé de $2^n$ sommets. +La seconde méthode propose une solution à ce problème en présentant +des conditions suffisantes sur un graphe à $n$ sommets +qui permettent d'obtenir des graphes d'itérations fortement connexes. +Ce théorème a aussi été prouvé dans~\cite{bcgr11:ip} +et des instanciations effectives +ont été produites. +Une troisième méthode~\cite{chgw+14:oip} s'appuie sur les codes +de Gray, ou de manière équivalente sur les cycles hamiltoniens du graphe des +itérations: un cycle qui visite chaque n{\oe}ud exactement une fois est un +\emph{cycle hamiltonien}. +La démarche consiste à enlever du graphe un de ses cycles hamiltoniens dont +la démarche de génération est un problème connu. + +Ces méthodes ont permis d'étendre à l'infini la classe des fonctions +dont les itérations sont chaotiques. + + +\subsection{Apprentissage par réseaux neuronaux} +Nous disposons grâce aux travaux présentés à la section précédente d'un grand +nombre de fonctions dont les itérations sont chaotiques. +Nous avons entrepris d'étudier ces itérations et plus particulièrement leur +apprentissage par un réseau de neurones. +J'ai notamment pu contribuer à montrer pratiquement qu'il +est très difficile (voir impossible) de les prédire +à l'aide de tels outils d'intelligence artificielle~\cite{bcgs12:ij}. + + +Nous nous sommes attaqués à un problème physique d'optimisation de +l'écoulement d'un flux d'air le long d'un véhicule. +Ce flux peut être modifié si l'on active des injecteurs d'air placés +par exemple sur le becquet du véhicule. +Le flux d'air peut être modélisé à l'aide d'équations de Navier-Stokes +dont on ne connaît pas de méthode analytique de résolution. +De plus, le nombre de Reynolds calculé dans cette situation fait apparaître +que le régime est extrêment turbulent, donc difficile à prévoir. +Nous avons souhaité +continuer nos expériences d'apprentissage à l'aide +de réseau de neurones dans ce contexte~\cite{cds12:ip,cds13:ij}. + +Il est apparu comme judicieux de mémoriser les configurations +représentant l'état des actionneurs à l'aide de nombres binaires. +De plus les codes de Gray, dont deux mots adjacents ne diffèrent que d'un +bit se sont présentés comme une des manière de mémoriser les sorties du +réseau de neuronnes comme un seul nombre binaire. +Quand on sait que trouver un chemin hamiltonien (comme étudié dans la partie précédente) dans un +$n$-cube revient à trouver un code +de Gray dans un mot de $n$-bits. Les compétences acquises lors du travail +sur les chemins hamiltoniens ont ainsi pu être réutilisées et approfondies. +Les résultats pratiques quant à l'utilisation de ces codes ce sont cependant +révélés comme moins pertinents que l'utilisation de $n$ sorties. + +\subsection{Génération de nombres pseudo-aléatoires} + +Plein de fonctions chaotiques : cependant chaos n'est pas aléatoire et pseudo +aléatoire. + +Condition nécessaire et suffisante : matrice de Markov doublement sotchastique + +méthode 1 : génération de fonction chaotiques par théorème FCT puis +filtrage de celles qui sont doublement stochastiques + +méthode 2 : directe par suppression de cycles hamiltonien + +Evaluation statistique + +Mesure de la qualité (stoping time) + + +\subsection{Masquage d'information} + +Formalisation de la méthode + + + + +\subsection{Application à la génomique} + +Core génome + + + +\subsection*{Publications issues de ces recherches} -(ou post-DEA pour les candidats autorisés à présenter leur demande sans -thèse), en identifiant les grandes thématiques de recherche, la démarche suivie et les -retombées en terme de publications et/ou de brevets ; \newpage \section{Perspectives de recherche (1 à 2 pages maximum)} @@ -341,8 +506,8 @@ Internationaux ; Nationaux ; Communications diverses. \section{Avis du directeur de l'Equipe}\label{sec:avis:directeur} \bibliographystyle{alpha} -\bibliography{biblio} -\include{Bibliographie} +\bibliography{abbrev,biblioand} + \end{document}