|
|
Posters et exposés jeunes chercheursLundi : 16:15 - Florian Faissole
Paul-Elliot Anglès d’Auriac Titre : Définissabilité et Calculabilité. Résumé : En théorie des ensembles, de nombreux efforts sont fait pour formaliser la notion de définissabilité, puis étudier les ensembles définissables et non définissables. Cette notion a des liens fort avec la calculabilité, en particulier avec des modèles de calcul plus fort que les machines de Turing. Après avoir discuté des constructibles de Godel et des machines de Turing à temps ordinal, j'exposerai le lien qui existe entre les deux. Élise Vandomme Titre : Arbres pleinement feuillus Abstract : Dans les 30 dernières années, les polyominos ont été l'objet de nombreuses investigations. Un problème central, qui est pourtant toujours ouvert, est de déterminer le nombre de polyominos à n cellules carrées. Une approche possible de ce problème est d'utiliser une description combinatoire. Derrière chaque polyomino se cache un graphe dont les sommets correspondent aux cellules, tel que deux sommets sont adjacents si les cellules ont un côté en commun. Dans ce contexte, on peut étudier les polyominos dont le graphe est acyclique, appelés polyominos-arbres. En 2016, Blondin-Massé et al. ont déterminé le nombre maximal de feuilles que peut posséder un polyomino-arbre à n cellules. Dans cet exposé, nous généralisons ce problème aux graphes en général et nous montrons que le problème est NP-complet. Cependant, le problème devient polynomial lorsqu'on se restreint aux arbres et aux graphes de largeur arborescente constante.
Louis-Marie Dando Titre : Expressions de Hadamard et automates circulaires Résumé : On se place dans le cadre de l'étude des séries formelles sur un alphabet fini. Une série associe à un mot donné un poids dans un semi-anneau. On se restreint à l'étude des séries de Hadamard, c'est à dire la clôture des séries rationnelles par les opérations de Hadamard. Ces séries peuvent être représentées par au moins deux objets : les automates circulaires et les expressions de Hadamard (de la même façon que les langages rationnels peuvent être représentés par les automates finis et les expressions rationnelles). Je présenterais ces deux objets et une façon de passer d'une représentation à une autre.
José Luis Vilchis Medina Titre : Autonomous Aerial Vehicle: Based on Non-Monotonic Logic. Résumé : The glider is one of the most relevant aircraft in terms of the ratio of the distance traveled and the loss of altitude. Making it one of the most efficient aircraft to fly. This is possible thanks to its long and thin wings, and its aerodynamic fuselage. Offering minimal opposition to air resistance. The challenge of a glider is to remain in flight as long as possible. But external perturbations tend to disturb it. Causing it to deviate from its intended flight path. The task of the pilot is to apply control commands to fly in the desired direction. Decision-making plays an important role under circumstances where the pilot has incomplete and contradictory information about the situation of flight. I present a formulation of a model from the point of view of logical theory, using non-monotonic logic, more specifically default logic, to tackle these problems. Also, results from a simulation for further application in a reduced glider model which will use solar cells for power management in embedded system.
Manon Stipulanti Titre : Des triangles de Pascal généralisés aux coefficients binomiaux de mots Résumé : Il existe un lien bien connu entre le triangle de Pascal et le triangle de Sierpinski. Il est possible de généraliser la construction du triangle de Pascal en utilisant les coefficients binomiaux de mots finis. Ces coefficients binomiaux de mots sont des généralisations classiques des coefficients binomiaux d'entiers. On a démontré qu'un objet limite, semblable au triangle de Sierpinski, existe également dans le cas où l'on généralise le triangle de Pascal aux représentations binaires des entiers.
Hamza Ben Ammar Titre : Optimization of network resources for efficient distribution of media content in content-centric networks Résumé : The last few years witnessed a rise in the popularity of content-oriented services, which are expected to increase even more with the growth of data-intensive applications. In fact, applications such as Peer-to-Peer file sharing, Video on Demand and video/audio streaming are, nowadays, massively driving content retrieval and data dissemination in the Internet. In such a context, many research initiatives proposed the Content-Centric Networking paradigm (CCN), which is emerging as one of the most interesting alternatives to the existing network architecture. The CCN paradigm consists in redesigning the future Internet architecture by focusing on named data instead of the end-to-end principle and the host-centric approach. One major feature considered in CCN to achieve service scalability and performance, is the in- network caching. Thus, each node equipped with a content store module has the ability to cache the content that pass by it. Therefore, the end-users’ requests, that are routed toward the Content Providers’ servers, can be satisfied by the cached data at the intermediate nodes. The caching and request routing protocols on which the CCN networks are currently based are lacking efficiency and there is not yet a consensus on the strategies to be used. It is in this context that the present thesis is situated. The major aim of this thesis is to study and analyze the state of the art in order to propose new efficient techniques of in-network caching and request routing and thus optimizing the network resources in Content-Centric Networks.
Florian Bridoux Titre : On the cost of simulating a parallel boolean automata network by a block-sequential one. Résumé : In this presentation, we study Boolean automata networks (BANs). A given BAN can be associated with several dynamics, depending on the schedule (i.e. the order) we choose to update its automata. In this presentation, we consider all block-sequential update schedules: we group automata into blocks, and we update all automata of a block at once, and iterate the blocks sequentially. For the last 15 years, people have studied the influence of the update schedules on the dynamics of a BAN. Here, we do the opposite. We want to determine the minimum number κ of additional automata that a BAN associated with a given block-sequential update schedule needs to simulate a given BAN with a parallel update schedule. To solve this problem, we introduce a graph that we call confusion graph built from the BAN and the update schedule. We show the relation between κ and the chromatic number of the confusion graph. Thanks to this confusion graph, we bound κ in the worst case between n/2 and 2n/3 + 2 (n being the size of the BAN simulated) and we conjecture that this number equals n/2. We support this conjecture with two results: the clique number of a confusion graph is always less than or equal to n/2 and, for the subclass of bijective BANs, κ is always less than or equal to n/2. Tatiana Rocher Titre : Indexation de séquences annotées, Indexing labeled sequences Résumé : Labelling sequences is a way to add information on sequences or parts of sequences. Labels can be used in many fields, as in bioinformatics to add functional annotations on genes or on regulation sites. For example, we can have a DNA sequence ACGTAA...GTTAT of length 50 with the label L1 from the letters 12 to 31. In such situtations, one would like to index both the text and the labels and to make some queries such as : Which are the sequences that have the label L1 ? Which ones have the pattern AAA and the label L2 ? We introduce here a new index structure which stores labeled sequences and which efficiently answers to sequence-label association queries. Our structure share some ideads with the RL-FMI [3]. It uses a Burrows-Wheeler Transform [1] (BWT) which stores the sequences, a Wavelet Tree [2] which indexes the labels and a bit vector which binds them. This structure, storing a text T of length n, can be made in a O(nHk(T) + nH0(B) + mH0(M)) + o(n) complexity, where B is the bit vector, M is a compacted list of labels generated in the BWT order, and m its length. The proposed structure was implemented and tested to index 100MB random files with random or fixed labels, and real data. Indexing completely random files does not give any compression. On the contrary, random files with fixed labels a compression of 0% to 90% in 10s to 2000s. Experimental results on 233MB of real data coming from immune DNA recombined sequences labeled with V/D/J gene segments show a compression of 60% in 143s. Laurent Feuilloley Titre : Hierarchy of Local Decision Résumé : An analogue of the theory of complexity has recently been developed for distributed computing on networks. This work describes the analogue of the polynomial hierarchy. In the talk, I will define all these terms, and try to give intuitions on these classes and the computational problems inside.
Florian Faissole Titre : Une preuve formelle du théorème de Lax-Milgram.
Adeline Massuir Titre : Extension d’un théorème de Cobham pour l’anneau des polynômes à coefficients dans un champ fini Résumé : Dans cet exposé, nous présenterons notre projet de recherche. En 1969, Alan Cobham démontra le théorème suivant : Théorème 1. Soient p et q deux entiers naturels multiplicativement indépendants et stricte- ment supérieurs à 1. Si N est une partie p-reconnaissable et q-reconnaissable de N, alors N est une union finie de progressions arithmétiques. Notre présentation consistera dans un premier temps en des explications de ce théorème via des définitions et des exemples. Dans la poursuite de la thèse de L. Waxweiler, nous souhaitons démontrer un théorème similaire à celui de Cobham dans le cadre des polynômes à coefficients dans un champ fini. C’est pourquoi nous expliquerons ensuite comment transférer les concepts utilisés pour les naturels vers les polynômes. Enfin, nous présenterons les pistes envisageables pour démontrer un tel théorème, avant de nous focaliser sur l’approche logique, méthode que nous avons choisi d’aborder en premier lieu.
Félix Baschenis Titre : Transducteurs bidirectionnels Résumé : Certains théorèmes classiques de la théorie des automates ne sont pas valables pour les transducteurs, l'ajout d'un output sur la fonction de transition apportant une problématique d'ordre dans les étapes du calcul. L'année dernière, nous avons présenté ici-même un résultat de calculabilité sur les transducteurs "sweeping". Nous présentons ici le modèle plus général des transducteurs bidirectionnels, et nous balaierons des questions classiques de déterminisation, de transformation en transducteurs unidirectionnels, et d'équivalence avec d'autres modèles de calcul des transductions.
Thibault Godin Titre : Machines de Mealy et groupes d'automate Résumé : Dans cet exposé, je voudrais présenter les machines de Mealy, un genre particulier d'automates, et expliquer comment elles peuvent être utilisées pour engendrer des groupes. Je donnerai ensuite des exemples de problèmes où ces groupes engendrés par des automates de Mealy ont été utiles, ainsi que des problèmes auxquels je m’intéresse dans le cadre de ma thèse et du projet Mealy. Florian Lietard Titre : Evitabilité des k-puissances additives en combinatoire des mots Résumé : L'étude de la possibilité d'éviter ou non certaines structures de mots s'est essentiellement développée après le travail de Thue en 1912. Il a montré, entre autres choses, qu'il était possible de construire un mot infiniment long, sur un alphabet ternaire (composé de trois lettres), qui évite les carrés (les mots du type ww où w est un mot). Il travaillait essentiellement avec des morphismes de mots et leurs points fixes. Après un rappel rapide de ces notions, l'exposé s'orientera vers les puissances additives et notamment sur les perspectives offertes par les travaux de J. Cassaigne, J.D. Currie, L. Schaeffer et J. Shallit dans ce domaine.
Marion Hallet Titre : Dynamiques sur le jeux sois formé extensive Résumé : Les jeux sous forme extensive, joués sur des arbres, sont des jeux où les joueurs jouent à tour de rôle. Nous nous intéresserons uniquement aux jeux finis à information parfaite. Différents concepts d'équilibres sont étudiés dans ces jeux, principalement les équilibres de Nash et les équilibres parfaits en sous jeu. Notre but est d'étudier différentes dynamiques d'amélioration des joueurs qui, à partir d'un profil de stratégie arbitraire, conduit vers un équilibre.
Posters
Lucas Morlet Intégration des surfaces de subdivision dans la CAO Félix Baschenis Expressivité et minimisation des transducteurs bidirectionnels Yoann Dufresne Algorithmique pour les peptides non ribosomiques
Laurent Feuilloley A Hierarchy of Local Decision
Agnieszka Słowik Random projections in Extreme Learning Machines |
| Personnes connectées : 1 |
|
