Job objectives
From LRDE
This is a property of type Text.
J
The minimization of an automaton consists of its "optimization": it means building the smallest equivalent automaton. There are many algorithms for the minimization of automata, whose fields of application and performance vary. The task of the intern will be to implement some of these algorithms in Vaucanson 2, to optimize them, and to conduct a comparative study of their performance. These results will provide an adaptive approach that selects the algorithm to be applied depending on the profile of the automaton / transducer. +
La minimisation d’un automate consiste à l’«optimiser» : construire le plus petit des automates équivalents. Il existe de nombreux algorithmes de minimisation d’automates, dont les domaines d’application et les performances varient.
Il s’agira d’implémenter dans Vaucanson 2 certains de ces algorithmes, de les optimiser, et de mener une étude comparative de leurs performances. Ces résultats permettront de proposer une approche adaptative, qui choisisse l’algorithme à appliquer en fonction du profil de l’automate/transducteur. +
The objective of this internship is to exploit the existing features of Vcsn to apply them to 𝔽₂ in a first step, and then, in a second step, to use Vcsn as a tool to explore novel results. +
The objective of this internship is to develop support for syntactic monoids in Vcsn, and to implement recent research results in Automata Theory that use the syntactic monoid. +
The objective of this internship is to develop a complete Computational Linguistics toolchain on top of Vcsn, for instance the "SMS to French" project from François Yvon (sms.limsi.fr). To this end, Vcsn will have to be completed with the needed data structures and algorithms, and possibly the existing implementation will have to be overhauled to cope with the extremely demanding size of these real-life automata. +
The goal of this internship is to survey, implement,
and extend existing algorithms that simplify omega-automata (with
different acceptance conditions), and convert between various
acceptance conditions. +
DSL design and implementation is booming. There are many approaches to this problem, one is about using the extensibility capabilities of a general-purpose programming language in order to meet specific requirements. Many multi-paradigm approaches (eg functional languages / compile-time meta-programming) also offer benefits. Lisp is a language that is particularly well suited for this type of problem, but it is almost totally absent from the literature on DSLs. Indeed, most researchers are not (or not anymore) familiar with this language. They prefer a language based on a static approach, or have simply forgotten everything Lisp is capable of.
The purpose of this internship is to (begin to) fill the gap by adding Lisp to the comparative literature. The work will consist in the study of literature demonstrating some useful approaches for the design of DSLs, further it should propose an alternative approach with Lisp and then compare the results. The steps of this training will include: (i ) Familiarization with Common Lisp and in particular its extensibility capabilities. (ii) Getting acquainted with the literature on the design and implementation of DSLs in other languages. (iii ) Choice of an application-centric approach or a comparative approach based on this literature and implementation of a Lispish equivalent. (iv) Finally, analysis of the results following the aspects such as: ease of implementation, expressiveness, performance etc. . +
La conception et l'implémentation des DSLs est un domaine en plein essor. Il existe de nombreuses approches à ce problème, dont l'une consiste à utiliser les capacités d'extensibilité d'un langage de programmation généraliste, pour l'adapter à des besoins spécifiques. De nombreuses approches multi-paradigmes (par ex. langages fonctionnels / méta-programmation à la compilation) offrent également des avantages. Lisp est un langage particulièrement bien adapté à ce type de problématique, mais il est presque totalement absent de la littérature sur les DSLs. En effet, la plupart des chercheurs du domaine ne sont pas (ou plus) familiers avec ce langage, préfèrent une approche basée sur un langage statique, ou encore ont simplement oublié tout ce dont Lisp est capable. Le but de ce stage est de (commencer à) restaurer l'équilibre, en rajoutant Lisp à la littérature comparative. Le travail consistera en l'étude de la bibliographie démontrant certaines approches utiles à la conception de DSLs, de proposer une approche alternative avec Lisp, puis de comparer les résultats obtenus. Les étapes de ce stages seront les suivantes: (i) Familiarisation avec le langage Common Lisp et en particulier avec ses capacités d'extensibilité ; (ii) Prise de contact avec la littérature sur la conception et l'implémentation de DSLs dans d'autres langages ; (iii) Choix d'une approche applicative ou d'un comparatif basé sur cette bibliographie et implémentation d'un équivalent Lispien ; (iv) Finalement, analyse des résultats selon des axes tels que: facilité d'implémentation, expressivité, performances etc. +
R is a programming language for statistics. Because of its historical development, it has many similarities with Scheme (a language from the Lisp family), but also many problems: in particular, it is a language which is not compiled. The biggest complaint of its users is therefore its lack of performance. For this (bad) reason a number of totally esoteric features have been added to it.
The goal of this internship is to study how to port a particular application of R to an equivalent one in Common Lisp. The first objective (which is certain) is to achieve a much higher level of performance than that of the original application. The long term goal is to consider a new implementation of R (or of a subset of R) over Common Lisp, with the intuition that it will result in a much simpler and better system, which is in addition much more efficient. +
R est un langage de programmation orienté vers les statistiques. De par son développement historique, il possède de nombreuses similitudes avec Scheme (un langage de la famille des Lisps) et aussi de nombreux problèmes: en particulier, c'est un langage qui n'est pas compilé. Le plus gros reproche que ses utilisateurs lui font est par conséquent son manque de performance. C'est d'ailleurs pour cette (mauvaise) raison qu'un certain nombre de fonctionnalités totalement ésotériques lui ont été rajoutées. Le but de ce stage est d'étudier le portage d'une application particulière de R vers un équivalent Common Lisp. Le premier objectif, qui est certain, est d'atteindre un niveau de performance bien supérieur à celui de l'application d'origine. Le but à plus long terme est d'envisager une nouvelle implémentation de R (ou d'un sous-ensemble de celui-ci) au dessus de Common Lisp, avec l'intuition d'aboutir à un système beaucoup plus simple, de bien meilleure qualité et de surcroît beaucoup plus performant. +
The context is the analysis of video sequences containing text elements. Once localized, it may be necessary to remove the text following the desired application. The goal of this internship is to remove text in video sequences, especially subtitles. The video images without the text will then be reconstructed thanks to the technique of video inpainting. +
Le contexte est l’analyse de séquences d’images vidéos contenant des éléments de texte. Une fois le texte localisé, il peut être nécessaire de le faire disparaître en fonction de l’application désirée. Le sujet proposé a pour objet l’effacement de texte dans des séquences d’images, et en particulier la suppression de sous-titres. La reconstruction des images dont le texte a été supprimé s’appuiera sur des techniques d’inpainting vidéo. +
Some working aspects include the following ideas:
* The design and the addition of data structures for large volumes of data.
* The use of vectorization instructions (SIMD) to speed up computations.
* The use of parallel programming (multicore) to distribute computations.
* The implementation of algorithms (or algorithms families) using a declarative strategy to uncouple their definition and implementation in low-level hardware in a given context.
* The use of generic programming (e.g., canvas of algorithms) and / or generative programming (generation and assembly of code based on templates).
* the introduction of Profile-Guided Optimizations taking advantage of real data to improve the generated code via “machine learning” techniques introduced in the compilation.
In any case, the research work should be conducted with a reusability / genericity goal (even a partial one) of the proposed solutions in mind, for example based on an incremental refinement (“lifting”) of a first implementation. Ultimately, the goal is to actually set the first elements of a more formal set of properties and data types, in order to generalize the performance improvements mentioned above. +
Les pistes de travail proposées incluent notamment les idées suivantes :
* la conception et l'ajout de structures de données destinées à de gros volumes de données ;
* l'utilisation d'instructions de vectorisation (SIMD) pour accélérer les calculs ;
* l'utilisation de programmation parallèle (multicœur) pour répartir les calculs.
* la réalisation d'algorithmes (ou de familles d'algorithmes) en utilisant une approche déclarative, permettant de découpler leur définition et leur implémentation bas-niveau dans un contexte matériel donné ;
* l'utilisation de la programmation générique (par exemple, des canevas d'algorithmes) et/ou la programmation générative (génération et assemblage de code basés sur des modèles) ;
* l'introduction d'optimisations dirigées par les profils (Profile-Guided Optimizations), tirant parti de données réelles pour améliorer un code via des technique d'apprentissage introduites dans la compilation.
Dans tous les cas, les travaux de recherche devront être menés en gardant à l'esprit une intention de réutilisabilité / généricité (même partielle) des solutions proposées, en s'appuyant par exemple sur un raffinement (''lifting'') incrémental d'une première proposition. À terme, l'objectif est en effet de poser les premières briques d'une formalisation d'un ensemble de propriétés et de types de données permettant de généraliser les améliorations de performance mentionnées ci-avant. +
<div>
* theory: 10%
* bibliography: 20%
* exploration: 40%
* implementation and tests: 30%
</div> +
* theory: 10%
* bibliography: 20%
* exploration: 40%
* implementation and tests: 30%
+
<div>
* theory: 20%
* bibliography: 10%
* exploration: 30%
* proof design: 30%
* implementation and tests: 10%
</div> +
<div>
* theory: 20%
* bibliography: 10%
* exploration: 30%
* proof design: 30%
* implementation and tests: 10%
</div> +
<div>
* theory: 10%
* bibliography: 10%
* exploration: 30%
* algorithm design: 30%
* implementation and tests: 20%
</div> +
<div>
* theory: 10%
* bibliography: 10%
* exploration: 30%
* algorithm design: 30%
* implementation and tests: 20%
</div> +