Optimizing the deployment of IoT networks under connectivity constraints is critical for the effective implementation of dynamic digital twin systems. This work addresses the challenge of designing IoT networks that ensure seamless data acquisition and transmission while maintaining robust connectivity in dynamic and evolving environments. By leveraging advanced optimization techniques, the study proposes strategies to enhance network efficiency, scalability, and resilience. The resulting framework supports real-time synchronization and interaction between physical systems and their digital counterparts, enabling improved monitoring, predictive analysis, and decision-making in diverse applications.
Tag : Français
La génération de configurations optimisées pour les réseaux distribués dans le domaine de l’avionique est une tâche cruciale pour améliorer la performance et la fiabilité des systèmes embarqués. Ce travail explore les méthodes de conception et d’optimisation des réseaux avioniques, intégrant des algorithmes avancés pour la distribution des données et la gestion des ressources. En adoptant une approche systématique, l’auteur met en avant des solutions capables de répondre aux exigences strictes de sécurité et d’efficacité énergétique, tout en assurant une architecture modulaire et évolutive pour les systèmes avioniques modernes.
This talk will provide an introduction to real-time systems, focusing on fundamental scheduling problems and the classical models employed in the field. We will then delve into the concept of the feasibility interval and its associated schedulability tests. Building on this foundation, we will present original research conducted in collaboration with Damien Masson. Specifically, we will introduce a model that explicitly incorporates system preemption costs and propose an exact and robust schedulability test. Notably, the proposed test is immune to scheduling anomalies, ensuring its reliability in real-world applications.
In this talk, we explore the relative complexity of different numerical bases, such as d-ary expansions and continued fractions, focusing on cases with zero entropy ( « predictable » expansions). For two expansions S1 and S2 with positive entropies h(S1) and h(S2), Dajani and Fieldsteel (2001) showed each symbol of S2 costs, on average, h(S1)/h(S2) symbols from S1.
We extend this result to sources with zero entropy by introducing a renormalized entropy function. When such a function exists (write f1 for S1 and f2 for S2), we show that the symbol generation rate satisfies lim f2(m)/f1(n)=1. For positive entropy, f is linear, but for the zero-entropy case, it is sub-linear. We give natural examples of this function, in particular from discrete codings of lines (Sturmian words).
Based on joint work with Valérie Berthé, Eda Cesaratto and Martín D. Safe.
Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n to 2^n. In this talk, we investigate this classical result in a probabilistic setting where we take a random deterministic automaton with n state and add just one random transition.
Given a conjunctive query Q and a database 𝐃, a direct access to the answers of Q over 𝐃 is the operation of returning, given an index j, the j-th answer for some order on its answers. While this problem is #P-hard in general with respect to combined complexity, many conjunctive queries have an underlying structure that allows for a direct access to their answers for some lexicographical ordering that takes polylogarithmic time in the size of the database after a polynomial time precomputation. Previous work has precisely characterised the tractable classes and given fine-grained lower bounds on the precomputation time needed depending on the structure of the query. In our work, we generalise these tractability results to the case of signed conjunctive queries, that is, conjunctive queries that may contain negative atoms. Our technique is based on a class of circuits that can represent relational data. We first show that this class supports tractable direct access after a polynomial time preprocessing. We then give bounds on the size of the circuit needed to represent the answer set of signed conjunctive queries depending on their structure. Both results combined together allow us to prove the tractability of direct access for a large class of conjunctive queries. On the one hand, we recover the known tractable classes from the literature in the case of positive conjunctive queries. On the other hand, we generalise and unify known tractability results about negative conjunctive queries – that is, queries having only negated atoms. In particular, we show that the class of β-acyclic negative conjunctive queries and the class of bounded nest set width negative conjunctive queries admit tractable direct access.
Joint work with Florent Capelli (CRIL)
We investigate two-player win/lose games over finite graphs. In all generality, these games are concurrent, i.e. at each state of the graph, there is a concurrent interaction between the two players to determine the next state visited. In the special case where, at every state of the graph, there are no real concurrent interaction, i.e. only one player is truly playing, the game is turn-based. Various desirable properties hold on turn-based games, but do not on arbitrary concurrent games; e.g. there exist subgame optimal strategies in all prefix-independent turn-based games, while there do not in very simple prefix-independent concurrent games. A possible way to circumvent this issue is to define a subclass of concurrent games, that is a proper superclass of turn-based games, while enjoying several of their nice properties. The goal of this talk is to introduce such a subclass of concurrent games, namely finitely maximizable games, and to show step by step how we came up with this definition. The novel way that we use to define such a subclass of well-behaving concurrent games constitutes a promising approach for investigating more general concurrent games, such as non-antagonistic two-player games, or even multi-player games.
Training neural networks with backpropagation from scratch requires considerable human effort in data annotation and network adaptation, leaving several questions unanswered: What is the simplest model for a given problem? How can it be trained with minimum human effort? Can experts control the training process? This lecture presents ongoing research towards creating convolutional neural networks (CNNs) for object detection, segmentation, and identification using very few representative images. Its results benefit diagnostic medicine, in which data annotation is costly and sometimes impractical, and the diagnosis of gastrointestinal parasites is taken as an example. Feature extraction is a crucial stage performed by the CNN’s encoder. One can append a decoder for object detection, a classifier for object identification, or a decoder followed by a delineator for object segmentation. The talk shows how experts can control feature extraction, such that the encoder’s parameters are estimated from a few markers (weak supervision) placed on discriminative image regions. The talk then introduces an adaptive decoder followed by a delineator for object segmentation, demonstrating how to create CNNs with minimum human effort and no need for backpropagation. The current results for the segmentation and identification of gastrointestinal parasites are presented. Finally, the concluding remarks provide directions for other applications, representative image selection, and classifier training with reduced human effort in data annotation.
Bio: Alexandre Xavier Falcão is a Professor in Computer Science at the Institute of Computing, State University of Campinas (UNICAMP). He holds a PhD from UNICAMP (1997), focusing on medical image analysis at the University of Pennsylvania from 1994-1996. He has been in the image analysis field for over 31 years, with projects in video quality assessment (Globo TV, 1997), plant phenotyping (Cornell University, 2011-2012), and several other image analysis applications developed at UNICAMP since 1998. He has authored over 360 papers and licensed over ten technologies, with five currently in the market. His research interests cover image analysis, data visualization, and human-machine interaction by combining humans’ superior cognitive abilities with machines’ higher data processing capacity.
Balanced binary search trees are a common data structure for implementing ordered sets, with three kinds of queries: checking whether a given value belongs to the set, inserting a value, and
deleting a value; the two latter queries require updating the data structure. Some implementations, like red-black trees or weak AVL trees, allow efficient update procedures, which run in a top-down way and require an amortised constant number of write operations per update query; by contrast, AVL trees still require bottom-up updating procedures, which may require a logarithmic number of write operations per query.
In this presentation, we will present new algorithms for updating AVL trees that bridge this gap: they run in a top-down way and/or require only an amortised constant number of few write operations per update query.
Network design is a class of problems with wide applicability, including well-known problems such as Steiner tree and the travelling salesperson problem. In general, these problems concern the task of finding subgraphs establishing connections between nodes with some desired property, such as fault tolerance or structural constraints.
One technique that has found success in this area is the use of tree embeddings, which transform the input graph into a tree, where the problem is usually easier to solve.
However, these techniques cannot perfectly embed the graph, and thus incur a loss in the approximation factor of O(log n), even for simple input graphs such as grids, expanders, and bounded-treewidth graphs.
In this talk, we will look at a classic problem in the area of network design, the group Steiner tree problem, as well as the approximation techniques used to solve it.
We will then introduce the setting of bounded treewidth, and see how we can use this additional structure to design a lossless reduction-to-tree technique for network design problems.
Finally, we will see how this technique can be applied to group Steiner tree to break the O(log n) tree embedding barrier and obtain an optimal approximation factor (matching trees), with the running time increasing as a function of the treewidth.
This talk is based on joint work with Parinya Chalermsook, Syamantak Das, Guy Even and Bundit Laekhanukit.